基于粒子群优化K-means聚类算法的快递网点选址方法研究.pdf
《基于粒子群优化K-means聚类算法的快递网点选址方法研究.pdf》由会员分享,可在线阅读,更多相关《基于粒子群优化K-means聚类算法的快递网点选址方法研究.pdf(7页珍藏版)》请在咨信网上搜索。
1、第 22 卷 第 2 期2023 年 6 月宁 夏 工 程 技 术Vol.22 No.2Ningxia Engineering TechnologyJun.2023基于粒子群优化 K-means 聚类算法的快递网点选址方法研究倪萌萌,李春树*,刘银(宁夏大学 电子与电气工程学院,宁夏 银川750021)摘 要:对于大规模客户群体,如何高效合理地规划出网点位置,在节省物流企业配送成本的前提下提高货物的周转率和及时送达率,目前已成为快递物流系统网络优化的难点。为解决此类问题,针对某地区物流公司的客户信息,采用粒子群优化的 K-means 聚类算法进行快递网点选址。具体过程:首先采用手肘法评估研究区
2、域需设立的最佳快递网点数;为改善 K-means 初始簇中心带来的易陷入局部最优解问题,利用粒子群优化算法对数据集进行迭代寻优,重新确定初始簇中心;最后通过 K-means 聚类算法在全局最优解附近空间完成聚类任务,最终得到的聚类结果代表配送区域的划分方案,聚类的簇中心即为快递网点位置。此外,利用 3 个评价指标对粒子群优化 K-means 聚类算法和传统 K-means 聚类算法进行对比分析。结果表明,结合粒子群优化算法后的聚类结果其类内数据相似度更高,类间数据的差异与距离更大,取得的聚类效果更合理。关键词:粒子群优化;K-means聚类;快递网点;簇中心中图分类号:TP301 文献标志码:
3、A近年来,信息技术的快速发展为电子商务的崛起奠定了坚实的基础,也推动了快递企业的暴发式增长。快递末端网点是快递企业的关键节点,在物流网络中发挥着枢纽作用。规划合理的快递站点可以降低交通运输成本,减少配送过程中带来的污染,为客户提供高效的物流收发服务,获取更高的经济效益。国内学者们进行了许多相关研究。毛海军等1构建了配送中心的综合评价指标体系,并结合模糊聚类算法,解决了多配送中心的选址问题。段冠华等2运用模糊聚类方法解决了最佳物流中心的选址问题。王勇等3利用改进的 K-means 聚类算法对备选物流分拨中心进行聚类,确定了配送中心的位置。徐小平等4利用 Laplace 分布对蜘蛛猴群进行初始化,
4、并结合非线性递减的步长,对物流中心的选址问题进行了求解。刘善球等5考虑运输成本等因素,建立了基于遗传算法的快递站点选址模型。梁玥等6提出了一种 FA-kmeans 算法,解决了区域内城乡物流配送中心的选址问题。王小雨等7利用AHP 法对选址区域进行划分,通过 Dijkstra 算法在ArcGIS 上实现了对传统重心法的改进,并对最优快递站点的位置进行了求解。郑乔芳等8在构建物流配送中心选址模型时,引入了交通拥堵参数。影响快递网点选址的因素非常多,如果统筹考虑各种因素,就需要采集大量数据,这样会使计算过程变得非常复杂,而单一的传统算法在面对庞大的数据集时,又无法求解到精确的选址中心。目前,K-m
5、eans 作为成熟的聚类算法,在选址问题上得到了广泛的应用。K-means 是一种迭代计算的动态聚类算法,通过设定某个中止条件(迭代次数、最小平方误差、簇中心点变化率等),反复修改、优化聚类结果,最终获得较满意的聚类效果,使得网点的分布更加科学有效。本文采取 K-means 聚类算法对某地区进行快递网点地址规划,并通过手肘法确定聚类个数;同时,为了降低 K-means 聚类算法对簇中心的敏感度,本文利用粒子群算法进行全局寻优以确定聚类的初始簇中心,使快递网点与就近客户点之间的距离之和尽可能小,从而降低物流配送成本,方便客户寄取物品,提升快递服务效率和质量。文章编号:1671-7244(2023
6、)02-0181-06收稿日期:2022-06-01基金项目:宁夏自然科学基金项目(2020AAC3033);宁夏大学研究生创新项目(GIP2020074)作者简介:倪萌萌(1998),女,硕士研究生,主要从事模式识别与图像处理研究()。*通信作者:李春树(1974),男,教授,博士,主要从事无线通信、信道编码及图像处理等研究()。宁 夏 工 程 技 术第 22 卷1快递网点选址分析快递网点的选址问题可以视为数据聚类问题,即根据数据集中的相似性,把数据分成不同的簇,每个簇内数据的相似性要尽可能大,而簇与簇之间的相似性要尽可能小。对于选址而言,这种“相似性”以距离作为标准,并依据数据集的经纬度特
7、点,在迭代过程中将客户点不断划分到更合理的簇中。每个簇代表不同的快递配送区域,要使簇内各个客户点到簇中心的距离之和最小,这样以簇中心作为快递网点选址依据时,配送货物所需的路径最小、时间最短,才能够满足快递配送的需求。在数据集维度有限的情况下,K-means 聚类算法的低复杂度能在短时间内快速获得较为准确的选址结果。此外,快递客户的信息数量庞大,K-means 聚类算法对于大规模数据集合具有良好的聚类效果及高效性,因此通过该算法能够确定合理的快递网点位置,从而达到优化快递配送网络的目的。2K-means聚类算法聚类是一种根据某种特定指标,将数据集分类再组织的无监督学习算法。K-means 聚类算
8、法自1967 年由 J.Macqueen 提出后,经过近 60 年的研究与发展,目前仍是应用最为广泛的聚类算法之一9。2.1K-means聚类算法的流程K-means 算法的聚类过程可以视为反复迭代的过程。针对 n 个数据点集合S=S1,S2,Sn,假设聚类的迭代次数为 t,K-means 算法的步骤如下10。(1)在数据集中随机选定 k 个数据作为初始簇中心,记为 X=x1(t),x2(t),xk(t)。(2)使用最近邻原则,求解每个数据至初始簇中心的欧氏距离,并依据欧氏距离的最小值,将所有数据分配至就近簇中心所在的簇中。(3)计算 k 个簇内所有数据的均值,更新簇中心。(4)根据最近邻原则
9、,将所有数据重新分配到k 个簇中。(5)如果迭代过程中簇中心 xi(t+1)xi(t),说明尚未得到最佳聚类结果,于是返回至第(3)步,继续进行迭代计算;如果 xi(t+1)=xi(t),即簇中心与上次迭代的结果一致或已达到设定的聚类最大迭代次数,便可以输出聚类结果。2.2k值的选取在 K-means 聚类算法中,聚类个数 k 对最终聚类结果发挥着重要作用,而该值需要在聚类前确定11。对于数据量较大的实际问题,如果 k 值选取过小,类内的数据差异会很大;反之,若 k 值选取过大,类间的差异会很小。确定 k 值的主流方法有手肘法和轮廓系数法,其中手肘法实现简单,结果显而易见,处理大批量数据时其效
10、率较高,因此本文采用手肘法对 k 值进行选取。手肘法利用 k 值与误差平方和(sum of squared errors,SSE)的关系变化来确定k 值12。SSE 的计算公式为ESSE=i=1ks Cis-xi22,(1)式中:ESSE为误差平方和;k 为簇数;Ci为第 i 个簇,s为 Ci中的样本点;xi为 Ci的簇中心。式(1)对所有簇内每个数据点到簇中心的欧氏距离平方和进行求和,求解结果是评判聚类后各个簇中数据点密集程度的依据,ESSE的值越小,各个簇中的数据点越紧密。在 k 值的迭代过程中,可以计算出每一代的ESSE值。当 k 值增大时,数据点被聚至更多的簇中,类间距离紧密。同时,E
11、SSE的值随着 k 值的增大而减小,直到 k 值等于数据点的个数时,计算终止。此外,ESSE值并不是越小越好,当 k 值小于数据集应当合理聚类的真实聚类数时,ESSE值会随着 k 值的增大而大幅下降。当 ESSE值的变化趋于平缓时,此时对应的 k 值即为最佳值,通过 ESSE-k 仿真曲线可以确定 k 的值。2.3K-means聚类算法的优缺点K-means 聚类算法主要有以下几个特点。(1)数据密集且聚类之间的差异明显时,聚类效果较好。(2)数据集较大时,该算法执行效率高,表现出较好的伸缩性。(3)k 值的选取不好把握,其过大或过小都会对聚类效果产生影响。(4)该算法对初始簇中心比较敏感,容
12、易陷入局部最优解。(5)数据集较小时,数据中数值差异大的离群值或异常点对该算法聚类效果的影响比较大。针对 K-means 聚类算法的缺点,本文采用手肘法解决 k 值的选取问题,并通过粒子群优化算法初步搜索数据集的全局最优解,最后通过 K-means 聚类算法在全局最优解附近的空间对数据集重新进行聚类划分,以得到更合理的聚类结果。182第 2 期倪萌萌等:基于粒子群优化K-means聚类算法的快递网点选址方法研究3粒子群优化算法粒子群优化算法(particle swarm optimization,PSO)13是一种模拟鸟群觅食的全局优化算法,其主要通过粒子群中个体间的相互合作与信息共享对最优解
13、进行搜索,该算法主要适用于对含有大量非线性数据、多峰值的复杂问题进行优化14。在粒子群优化算法中,所有粒子都可视为问题潜在的解,这些粒子在目标空间中不断迭代更新以寻找最优解。假设存在 1 个 n 维目标空间,在第 t 次迭代过程中,某粒子 i 不但需要记忆和更新自身的个体极值 Pi(t)=(pi1,pi2,pin),还要通过信息共享更新所有粒子检索到的全局极值 G,以此调整粒子i 的速度 Vi(t)=(vi1,vi2,vin)与位置 Xi(t)=(Zi1,Zi2,Zin),以便在下次迭代过程中更准确地向个体极值与全局极值飞行。粒子的速度和位置更新方程分别为Vi(t+1)=Vi(t)+c1r1(
14、Pi(t)-Xi(t)+c2r2(G-Xi(t),(2)Xi(t+1)=Xi(t)+Vi(t+1),(3)式中:为与上一次迭代过程中的速度有关的惯性权重;c1,c2为调整粒子向全局极值和个体极值方向飞行的步长加速系数,合适的 c1,c2能够加快粒子群收敛且避免陷入局部最优解,一般令 c1=c2=215;r1,r2为 0 与 1 之间的随机数。4粒子群优化的K-means聚类算法针对 K-means 聚类算法容易受初始簇中心影响的缺点,本文采用基于粒子群优化的 K-means 聚类算法(以下简称 PSO-K-means)来改善聚类效果。PSO-K-means 流程图如图 1 所示。假设 d 维数
15、据集 S=S1,S2,Sn 中存在 n 个数据点,聚类个数为 k,粒子个数为 m,粒子群寻优的迭代次数为 t,PSO-K-means 的聚类步骤如下。(1)初始化粒子参数,c1,c2;根据数据差值,初始化粒子速度的上限 Vmax与下限 Vmin;根据数据最大值及最小值,初始化粒子位置的上限 Xmax与下限 Xmin。(2)将数据集 S 中的 n 个数据随机划分到 k 个簇中,并计算 k 个簇的均值,由此形成 1 个粒子。这个过程循环 m 次,初始化 m 个粒子,每个粒子都由k 个簇中心构成,记为 X1(0),X2(0),Xm(0),第 i个 粒 子 可 以 表 示 为 Xi(0)=(Xi1(0
16、),Xi2(0),Xik(0)。(3)粒子的适应度值体现的是簇内相似度16,适应度值越小,说明该粒子的聚类效果越好。初始适应度所对应的粒子位置为粒子的初始个体极值 Pi=(pi1,pi2,pik),i=1,2,m。全局极值 G 为 m个适应度中的最小值所对应的个体极值。适应度值J(Xi)的计算公式为J(Xi)=j=1ks Cijdist(s,Xij),(4)式中:Cij为第 i 个粒子中的第 j 个簇。(4)根据式(2)更新下一代粒子的速度 Vi(t+1),并将其限制在 Vmin,Vmax 中;根据式(3)更新下一代粒子的位置 Xi(t+1),并将其限制在 Xmin,Xmax 中。(5)根据最
17、近邻原则,将数据重新归类到 Xi(t+1)就近的簇中,并计算新簇的均值以更新粒子。(6)同第(3)步,利用式(4)重新计算第 i 个粒子的适应度值,并根据迭代过程中粒子 i 适应度值的最小值来更新 Pi(t+1)与 G。开始初始化k个簇中心及粒子群参数数据随机分配,初始化粒子计算个体极值、全局极值产生下一代粒子群数据再聚类,重新计算粒子位置计算个体极值、全局极值全局极值不再变化数据聚类到粒子群全局极值最近的簇重新计算簇中心簇中心不再变化结束NYYN图1PSO-K-means流程图183宁 夏 工 程 技 术第 22 卷(7)重复第(4)(6)步,直至达到粒子群最大迭代次数或全局极值不再发生变化
18、,退出迭代循环。(8)将粒子群优化算法迭代结束时所得到的 G=(g1,g2,gk)作为 K-means 聚类算法的初始簇中心,并根据最近邻原则,将数据划分到就近的 k 个簇中。(9)计算每个簇的均值,将其作为新的簇中心;根据最近邻原则,再次对数据划分聚类。(10)当簇中心不再改变或达到聚类的最大迭代次数时,输出最终的聚类结果。5实验仿真结果及分析5.1数据分析本文对快递企业客户点的分布情况进行了初步分析,主要包括:客户原始数据为 57 584 个点,经预处理过滤重复数据后,得到可用数据 10 544 个点;采用统计方式对该数据集构建客户密度直方散点图(图 2),散点颜色越明亮,表示该地区快递客
19、户的密度越大,并且通过坐标边界的直方图标记,可直观地看出客户在经纬度上分布的密集程度;结合客户密度分布热力图(图 3),初步推测图中明亮处为簇中心密集处(105.17E105.27E,37.37N37.45N),即快递网点覆盖最多的区域。5.2k值的确定本次实验设定 K-means 聚类算法的迭代次数为 500 次,每个 k 值运行 40 次并获得对应的 ESSE值,然后对 40 个 ESSE值求均值,即为最终 ESSE值。通过 Matlab 软件的仿真,可以得到 ESSE-k 关系图(图 4),表 1 为对应的 ESSE-k 值表。由图 4 可知,曲线的后半部分比较平缓,由此推断 k 值在此
20、附近。结合表 1,可知当 k16 时,ESSE-k 的斜率较小,说明k 值已达到“肘部”值,从而导致减小 k 值后所带来的“收益”大幅减少,因此最合理的 k 值为 16,即针对该地区的数据集,应选取 16 个快递网点。5.3实验结果根据本文提出的基于粒子群优化的 K-means聚类算法,项目组在 Matlab 2016 a 仿真平台上对某地区快递客户数据完成聚类任务。本次实验将粒子群优化算法的最大迭代次数设置为 1 000 次,通常粒子群数量为 4060 时,可以得到较好的寻优效果,但仿真中数据集较大,所以粒子数取为 100。K-means 聚类算法的最大迭代次数为 8 000 次,文中采用
21、7 种颜色标记不同的簇类,以区分每个快递网点覆盖的客户点,簇中心即为快递网点的位置(用“”标记)。最终得到的快递网点规划方案如表 2 所示,对应的快递网点分布图如图 5 所示。5.4实验对比分析为评估粒子群算法对数据集聚类的优化效果,本文采取 3 种聚类评价指标对 K-means 及 PSO-K-图2客户密度直方散点图图3客户密度分布热力图表1ESSE-k值表k12345678910ESSE2 131.525 759114.319 85291.166 43560.876 52758.714 46549.060 86039.084 61437.580 14533.441 15830.527 37
22、5k11121314151617181920ESSE29.552 07428.474 39629.280 19323.088 70425.153 31819.525 65718.718 92419.935 17919.314 12916.809 793184第 2 期倪萌萌等:基于粒子群优化K-means聚类算法的快递网点选址方法研究means 算法的聚类效果进行对比分析,具体如下。(1)轮廓系数(silhouette coefficient,SC)。SC 结合了类内紧密度和类间分离度17。对于数据点 i,SC的计算公式为YSC(i)=b(i)-a(i)max a(i),b(i),(5)式中:
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 粒子 优化 means 算法 快递 网点 选址 方法 研究
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。