基于改进麻雀搜索算法的配送中心选址研究.pdf

摘要院 针对物流配送中心选址不合理导致配送效率低下的问题，采用萤火虫扰动策略改进麻雀搜索算法，构建二级物流配送中心网络结构，解决配送中心选址问题。采用手肘法确定最优二级配送中心数量，将运输成本、运输时间和配送时间三项成本之和最小值作为目标函数，增加运送车辆限制等约束条件，获得合理的配送中心地址和最佳成本。以吉林省某区县小区实际情况为例，将改进后的麻雀搜索算法与常规的麻雀搜索算法进行对比，结果表明：改进后的麻雀搜索算法可将总成本降低16.67%，配送中心选址更加合理有效。关键词院 配送中心选址曰麻雀搜索算法曰萤火虫扰动策略曰手肘法曰成本中图分类号院 TP18曰F252文献标识码院 A文章编号院 2095 原 0926（圆园23）02 原 园园14 原 园6Study on distribution center location based on improved sparrow search algorithmCHEN Qingbin1袁YANG Genghuang1袁2袁GENG Liqing1袁2袁SHI Xun1袁ZHENG Huhu1渊 1.School of Automation and Electrical Engineering袁 Tianjin University of Technology and Education袁 Tianjin 300222袁China曰 2.Tianjin Key Laboratory of Information Sensing and Intelligent Control袁 Tianjin University of Technology andEducation袁Tianjin 30022袁 China冤Abstract院Aiming at the problem of low distribution efficiency caused by unreasonable location of logistics distributioncenter袁 the firefly disturbance strategy is used to improve the sparrow search algorithm袁 and the network structure ofsecondary logistics distribution center is built to solve the location problem of distribution center.The elbow method isused to determine the optimal number of secondary distribution centers.The minimum sum of the three costs in trans鄄portation cost袁 transportation time and distribution time is taken as the objective function袁 and the constraints such astransportation vehicle restrictions are increased to obtain a reasonable distribution center address and optimal cost.Tak鄄ing the actual situation of some district and county in Jilin Province as an example袁 the improved sparrow search algo鄄rithm is compared with the conventional one.The results show that the improved sparrow search algorithm can reducethe total cost by 16.67%袁 and the location of the distribution center is more reasonable and effective.Key words院 distribution center location曰 sparrow search algorithm曰 firefly disturbance strategy曰 elbow method曰 cost基于改进麻雀搜索算法的配送中心选址研究陈庆斌1，杨耿煌1，2，耿丽清1，2，石迅1，郑虎虎1（1.天津职业技术师范大学自动化与电气工程学院，天津300222；2.天津职业技术师范大学天津市信息传感与智能控制重点实验室，天津300222）收稿日期院 2023-03-27基金项目院 天津市高等学校科技发展基金计划项目（2022ZD037）.作者简介院陈庆斌（2000），男，硕士研究生，研究方向为智能信息处理.通信作者院杨耿煌（1978），男，教授，博士，硕士生导师，研究方向为信息处理与智能控制系统，.物流行业商品运输过程中，配送中心作为连接商家和用户的重要中间环节，其选址至关重要。合适的配送中心地址选择对物流的运输距离和运输模式至关重要，它将直接影响到物流系统的整体效率。因此，对于配送中心选址研究具有重要的现实价值1-3。近几年来，学者就配送中心选址规划问题进行了深入研究，配送中心的选址问题主要集中在重心法4、边界法5以及层次分析法6等方法，这些方法存在着约束条件多、优化困难以及算法复杂度高的缺点。因此，利用群智能优化算法对该问题进行研究，如差分进化第 33 卷第 2 期圆园23 年 6 月天 津 职 业 技 术 师范 大 学 学 报允韵哉砸晕粤蕴 韵云 栽陨粤晕允陨晕 UNIVERSITY OF TECHNOLOGY AND EDUCATIONVol.33No.2Jun.2023DOI：10.19573/j.issn2095-0926.202302003第 2 期算法7、粒子群算法8、猴群算法9等，这些算法虽然具有操作简单、算法复杂度低的优点，但是普遍存在陷入局部最优解，求解精度不高等缺点。其中，Xue 等10于2020 年提出的麻雀搜索算法是一种新型群体智能优化算法，该算法相较于其他群智能优化算法具有搜索精度高、收敛速度快、鲁棒性强等特点。但是，当其搜索接近全局最优时，依旧会出现种群多样性减少，易陷入局部最优解等问题。鉴于此，本文采用萤火虫扰动策略对麻雀搜索算法进行优化，并建立从一级配送中心到二级配送中心的分销配送、从二级配送中心到小区的末端配送的模型，解决配送中心选址问题。1麻雀搜索算法麻雀搜索算法（sparrow search algorithm，SSA）11是一种模拟麻雀觅食行为的自然启发式算法，它的基本思想是通过模拟麻雀觅食的行为来搜索最优解。根据麻雀种群的生存机制，将麻雀个体分为发现者、跟随者和警戒者。其中，警戒者所占种群比例 10%20%，发现者和跟随者是动态变化的。按照分工划分，发现者主要为整个种群提供觅食方向和区域，跟随者则是跟随发现者进行觅食，警戒者负责对于觅食区域的监视。在觅食过程中，通过不断更新三者位置，完成资源的获取。发现者位置的更新公式为12-14xt+1i，j=xti，je-1琢maxR2 STxti，j+QLR2逸ST扇墒设设设设设缮设设设设设（1）式中：xti，j为第 t 代第 i 只麻雀在第 j 维的位置；琢 为属于（0，1）的随机数；琢max为最大迭代次数；R2为报警值；ST 为安全值；Q 为服从正态分布的随机数，L 为1 伊 n 的全 1 矩阵。跟随者的位置更新公式为xt+1i，j=Qextworst-xti，ji2i n2xt+1p+xt+1i，j-xt+1pA+Li逸n2扇墒设设设设设设设缮设设设设设设设（2）式中：xtworst为第 t 代适应度最差的个体位置；xt+1p为第 t+1 代中适应度最佳的个体位置；A 为 1 伊 dim 的矩阵，其中每个元素的值随机为-1 或 1，A+=AT（AAT）-1。警戒者的位置更新公式为xt+1i，j=xtbest+茁 xti，j-xtbestfi屹 fgxtbest+kxti，j-xtbestfi-fw+着蓸蔀fi=fg扇墒设设设设设设缮设设设设设设（3）式中：xtbest为第 t 代全局最优的位置；茁 为控制步长，是一个服从标准正态分布的随机数；k沂-1，1；着 为常数，用以避免分母为 0；fi为当前个体的适应度值；fg为目前全局最优个体的适应度值；fw为目前全局最差个体的适应度值。2改进的麻雀搜索算法2.1萤火虫扰动策略萤火虫算法（firefly algorithm，FA）15-17模拟了萤火虫的自然现象，通过无智能群体的各种交互，表现出智能的行为。在萤火虫算法中，萤火虫发出光亮的主要目的是吸引其他的萤火虫，有下述设定：萤火虫只到比它更亮的萤火虫那；萤火虫的亮度和吸引力呈正比，与距离呈反比。在萤火虫算法中，萤火虫的相对荧光亮度为I=I0e-酌ri，j（4）式中：I0为萤火虫的最大萤光亮度；酌 为光强吸收系数；ri，j为萤火虫 i 与 j 之间的空间距离。萤火虫的吸引度为茁=茁0e-酌r2i，j（5）式中：茁0为萤火虫的最大吸引度。萤火虫 i 被吸引向萤火虫 j 移动的运动方程为xit+1=xit+茁（xjt-xit）+琢 rand-12蓸蔀（6）式中：xit为第 t 代萤火虫 i 所处的空间位置；琢 为步长因子，属于0，1的随机数；rand 为0，1上均匀分布的随机数。2.2改进的麻雀搜索算法流程由于麻雀搜索算法缺乏全局搜索能力，可能会陷入局部最优解18-19，因此在麻雀搜索基础上，利用萤火虫扰动策略对麻雀搜索算法进行改进，所有麻雀通过萤火虫扰动的方式进行位置更新，以提高其搜索性，两类麻雀进行对比，如果更优则更新麻雀位置。具体算法如图 1 所示。陈庆斌袁等院 基于改进麻雀搜索算法的配送中心选址研究15天 津 职 业 技 术 师范 大 学 学 报第 33 卷3模型建立及求解3.1模型假设根据物流实际情况，为便于选址模型的建立分析，给定以下假设：（1）各小区之间的人口不会大规模流动。（2）每次运输会携带该小区的全部待配送物品。（3）配送人员在每栋楼、每层楼的配送效率是相同的。（4）在配送过程中，运输车辆的速度是保持不变的。（5）每个人的待配送物品数量是相同的。3.2目标函数本研究目标旨在通过优化配送中心选址，提高配送效率，减少时间和资源的浪费。基于此，考虑运输车辆的运输成本损耗、运输过程中的时间成本和配送人员在小区内配送的时间成本，上述成本分别用 F1、F2、F3表示，建立目标函数为Fitness=F1+F2+F3（7）运输车辆的运输成本损耗主要与各小区到该配送中心的欧式距离和该小区的常住人口有关20-21。因此，F1可表示为F1=wj=1移zi=1移ai（xi-xj）2+（yi-yj）2姨（8）式中：w 为二级配送中心的个数；z 为该二级配送中心辐射的小区数；（xi，yi）为第 i 个小区的横纵坐标；ai为第 i 个小区的人口数量；（xj，yj）为第 j 个二级配送中心的横纵坐标。运输过程中的时间成本 F2主要与各小区到该配送中心的欧式距离和车辆的行进速度有关，而车辆携带的待配送物品越多，车辆的行进速度越慢，呈反比例关系。因此，F2可表示为F2=wj=1移zi=1移（xi-xj）2+（yi-yj）2姨vi（9）式中：vi为运输车辆向第 i 个小区的行进速度。配送人员在小区内配送的时间成本 F3主要与各小区内包含的栋数和每一栋的层数有关。因此，F3可表示为F3=wj=1移Lik=1移Qkp=1移t1（10）式中：Li为第 i 个小区的总栋数；Qk为第 k 栋楼的总层数；p 为当前层数；t1为配送人员在每层配送的时间。约束条件如下zi=1移si=1（11）zi=1移si-zj=1移sj=1（12）式中：s 为运输车辆，式（11）表示第 i 小区仅有一辆运输车辆配送；式（12）表示车辆离开配送中心 i 向 j 小区进行配送并在配送结束后返回配送中心。本文使用萤火虫扰动策略改进的麻雀搜索算法，在约束条件下，求解三项成本目标函数最小值。3.3求解流程在采用的算法中，针对物流配送中心选址问题所提出的数学模型，建立虚拟麻雀来寻找食物，所有麻雀的位置 X 可表示为X=（X1XW）T（13）式中：Xj=（xj，yj）（j=1，w）即待定的最优物流配送中心的第 j 个可行解。所有麻雀的适应度值 Fitness 可以表示为Fitness=（F1（X1）FW（XW）T（14）式中：每只麻雀的适应度值记为 Fi（Xi）=F1+F2+F3。（1）初始化参数。设置种群规模、迭代次数和维度，初始化捕食者和加入者比例。由于最佳二级配送中心个数为 w 个，每个配送中心均有横、纵 2 个坐标，共计 2w 个优化变量。因此，种群规模设置为 w，维度设置为 2w。开始参数初始化初始化麻雀种群，并计算适应度值得到全局最优、全局最差个体更新发现者、跟随者、侦察者位置计算各个麻雀的适应度值并更新麻雀位置采用萤火虫扰动策略更新麻雀的位置采用扰动后的麻雀位置采用原麻雀位置结束扰动后的麻雀位置是否比原麻雀位置更优？是否满足停止条件？是否是否图 1改进的麻雀搜索算法流程16第 2 期图 3二级物流配送中心网络结构图物资需求点物资需求点物资需求点物资需求点一级配送中心二级配送中心二级配送中心一级配送中心辐射范围二级配送中心辐射范围（2）计算适应度值，并排序。（3）假设 10%到 20%的麻雀会意识到危险，收到危险信号的麻雀根据式（3）更新它的位置。（4）麻雀更新警戒者位置。考虑实际情况，配送中心位置应位于所有小区范围内，因此最初警戒者为小区的整体边界。（5）计算适应度值并更新麻雀位置。（6）利用萤火虫扰动更新麻雀位置。此时麻雀种群位置等同于萤火虫位置，即优物流配送中心的可行解，根据式（4）、式（5）计算出萤火虫群体的相对亮度 I和 茁 吸引度，确定萤火虫的移动方向。（7）根据式（6）更新萤火虫的位置，并对处于最优位置的萤火虫进行随机扰动，判断是否满足停止条件，若满足则退出，并输出结果；否则，从第 2 步开始重复执行。4算例分析4.1二级配送中心个数的选取本文在 Window 10 系统下，使用 Python 3.7 语言进行编程仿真，以第十九届中国研究生数学建模竞赛中吉林省某区县的配送中心选址问题为例进行实证分析。该区县共有 84 个小区，每个小区的常住人口并不相同，根据每个小区的坐标和人口数量，可绘制出各小区的位置分布图，点的大小表示小区的人口数量，人口数量越多的小区在图中的点越大，小区位置分布如图 2 所示。考虑到每个小区的人口数量和地理位置差异，本文选择二级物流配送中心网络结构22，这是因为二级配送中心具有更多的配送点，配送针对性更强，更适用于物品的配送需求，整体结构如图 3 所示。二级配送中心的特性可有效降低配送时间和配送距离，提升配送效率，但过多的二级配送中心会导致资源的浪费和成本的增加。因此，本文采用手肘法23对二级配送中心的个数进行选取，其基本思想是随着聚类数量增加，簇内平均畸变程度（sum of squarederrors，SSE）会逐渐减小，但是当聚类数量增加到一定程度时，簇内平均畸变程度的下降速度会急剧减缓，因此本文将拐点处的聚类数量作为最佳聚类数量。对于一个簇 Ci，它的 SSE 计算公式为SSE（Ci）=xj沂Ci移（xj-滋i）2（15）式中：xj表示簇 Ci中的第 j 个点；滋i表示簇 Ci的质心；SSE（Ci）表示簇 Ci内所有样本点到质心的距离平方和。所有簇的 SSE 是将每一个簇依次累加，得到 SSE随簇个数增加的变化趋势，如图 4 所示。由图 4 可知，在 5 个簇之后，曲线整体趋于平缓，可得最佳的二级配送中心个数为 5。3025201510530.047.532.540.0维度坐标37.535.045.042.5图 2小区位置分布图765432102108簇的个数64图 4簇内平均畸变程度变化图陈庆斌袁等院 基于改进麻雀搜索算法的配送中心选址研究17天 津 职 业 技 术 师范 大 学 学 报第 33 卷4.2对比实验采用麻雀搜索算法，得到其适应度值随迭代次数增加的变化如图 5 所示，二级配送中心具体信息如表1 所示。从图 5 可以发现，麻雀搜索算法在迭代 300 多次后最佳成本趋于平缓，说明已陷入局部最优解。同时，出现一个二级配送中心的辐射人数为 0，这不利于提高配送效率，容易造成时间和资源的浪费。在此进行对比实验，采用萤火虫扰动策略改进后的麻雀搜索算法，得到其适应度值随迭代次数增加的变化如图 6 所示，二级配送中心具体信息如表 2 所示。通过图 6 可以发现，改进后的麻雀搜索算法迭代1 000 多次后趋于平缓，避免了陷入局部最优解，同时，5 个二级配送中心位置选取合理，能较好地提高配送效率，避免时间和资源的浪费。由表 1 和表 2 可知，改进后的麻雀搜索算法可以更合理地对二级配送中心的地址进行选取，总成本降低 12.54%，二级配送中心的选取实现了改善。二级配送中心货物通常来源一级配送中心，二级配送中心辐射的人数不同，待配送的物品数也不同，辐射人数多的二级配送中心需要容纳更多的物品。因此，一个位置恰当的一级配送中心，会极大地避免时间和资源的浪费。因此，根据二级配送中心的横、纵坐标，再次采用对比实验，对一级配送中心地址进行选取，进一步验证改进后麻雀搜索算法的优势。通过计算，得到麻雀搜索算法的一级配送中心坐标为36.94，20.40，成本为 2 688 478.8，一级配送中心的选址结果如图 7 所示。采用改进后的麻雀搜索算法，到一级配送中心的坐标为36.74，17.13，成本为 2 304 315.15，一级配送中心的选址结果如图 8 所示。迭代次数图 5SSA 二级配送中心成本收敛曲线横坐标纵坐标辐射人数138.5844.75000 000.0229.4820.35029 288.0339.6109.53081 389.0438.3624.76146 017.0531.6611.33069 474.0成本1 174 945.35二级配送中心麻雀搜索算法表 1SSA 二级配送中心具体信息1.8迭代次数图 6FASSA 二级配送中心成本收敛曲线纬度坐标353025201510530.047.533.544.040.537.0二级配送中心 1二级配送中心 2二级配送中心 3二级配送中心 4二级配送中心 5图 7SSA 一级配送中心分布图纬度坐标3025201510530.047.533.544.040.537.0二级配送中心 1二级配送中心 2二级配送中心 3二级配送中心 4二级配送中心 5图 8FASSA 一级配送中心分布图表 2FASSA 二级配送中心具体信息横坐标纵坐标辐射人数144.7427.4240 815.0236.8125.3373 334.0339.0909.1291 211.0432.0914.5082 005.0539.8219.6638 803.0成本1 044 007.64二级配送中心改进的麻雀搜索算法1.61.41.21.01.21.41.61.818第 2 期综上分析，改进后的麻雀搜索算法相较于麻雀搜索算法，在二级配送中心的选取上总成本降低12.54%，整个二级物流配送中心网络结构总成本降低16.67%。5结语本文针对配送中心选址不合理的问题，建立了二级物流配送中心网络结构，提出影响配送中心选址的三项成本因素，以三项成本之和最小值作为优化目标建立模型，使用改进后的麻雀搜索算法对模型进行求解。以吉林省某区县实际小区分布情况为例，通过手肘法确定二级配送中心的个数。本文采用萤火虫扰动策略对麻雀搜索算法进行改进，降低麻雀搜索算法可能会陷入局部最优解的几率，在三类麻雀位置更新的过程中，加入萤火虫扰动，重新进行适应度的计算和麻雀位置更新。通过考虑配送中心与各小区距离和人口数量的关系，避免出现因小区密集但人口稀少而造成的配送中心选址不恰当问题。根据模型对比实验的求解结果可知，改进后的麻雀搜索算法大幅降低了总成本，虽在一定程度上提高了物流效率，但约束条件较少，后续研究将进一步添加约束条件，修改目标函数，以便适用于各种复杂情景。参考文献：1 何黎明.二二三年我国现代物流发展趋势与重点工作：在二二二年中国物流学术年会跨年会暨二二三年第十五届 物流领域产学研结合工作会上的讲话 N.现代物流报，2023-03-01（1）.2 张懿.科技创新引领，推动产业结构优化升级：新的一年，上海要加快建设现代化产业体系，推进高水平科技自立自强 N.文汇报，2023-03-06（9）.3 何彤，熊瑞琦.计算机信息技术在智能交通系统中的应用 J.石河子科技，2023（01）：42-43.5 高迪，张博，何富康.乌鲁木齐市京东家电配送中心选址分析 J.中国储运，2023（2）：134.6 王文忠.可可盖煤矿工业场地选址分析 J.内蒙古煤炭经济，2022（15）：175-177.7 傅新平，邹珺.层次分析法在物流中心选址中的应用 J.世界海运，2002，25（4）：23-24，28.8 耿焕同，周利发，丁洋洋，等.一种基于新型差分进化模型的 MOEA/D 改进算法 J.计算机工程与应用，2019，55（8）：138-146，263.9 YU H B.Surrogate-assisted hierarchical particle swarm opti原mization J.Information Sciences，2018，454/455：59-72.10陈信，周永权.基于猴群算法和单纯法的混合优化算法 J.计算机科学，2013，40（11）：248-254.11 XUE J K，SHEN B.A novel swarm intelligence optimizationapproach：sparrow search algorithm J.Systems Science&Control Engineering，2020，8（1）：22-34.12吕鑫，慕晓冬，张钧，等.混沌麻雀搜索优化算法 J.北京航空航天大学学报，2021，47（8）：1712-1720.13唐宇，代琪，杨梦园，等.改进麻雀搜索算法优化 SVM 的异常点检测 J.计算机工程与科学，2023，45（2）：346-354.14杨超，王宗山，聂仁灿，等.车联网中基于麻雀搜索算法的计算卸载策略 J.计算机工程与设计，2023，44（1）：1-7.15张文帅，王占刚.基于改进麻雀算法优化深度极限学习机的缺失数据预测 J.电子测量技术，2022，45（15）：63-67.16 DINESH KUMAR P，VALARMATHI K.Fuzzy based hybridBAT and firefly algorithm for optimal path selection and secu原rity in wireless sensor network J.Automatika，2023，64（2）：199-210.17仲臣，余学祥，邰晓曼，等.萤火虫算法优化支持向量机室内定位研究 J.计算机工程与科学，2022，44（11）：1969-1975.18MOHAMMADI B.Modeling various drought time scales via amerged artificial neural network with a firefly algorithm J.Hydrology，2023，10（3）：58.19唐宇，代琪，杨梦园，等.改进麻雀搜索算法优化 SVM 的异常点检测 J.计算机工程与科学，2023，45（2）：346-354.20李茹，范冰冰.基于混合策略改进的鲸鱼优化算法 J.计算机与现代化，2022（6）：13-20.21张楠.低碳约束下冷链物流配送共享仓选址多目标优化方法 J.自动化与仪器仪表，2023（1）：57-63.22冉昊杰，王宏智.基于改进模拟退火算法的生鲜农产品配送中心选址 J.计算机与现代化，2022（10）：36-40.23陈聿，田博今，彭云竹，等.联合手肘法和期望最大化的高斯混合聚类电力系统客户分群算法 J.计算机应用，2020，40（11）：3217-3223.本文引文格式：陈庆斌，杨耿煌，耿丽清，等.基于改进麻雀搜索算法的配送中心选址研究 J.天津职业技术师范大学学报，2023，33（2）：14-19.CHEN Q B，YANG G H，GENG L Q，et al.Study on distribu原tion center location based on improved sparrow search algo原rithm J.Journal of Tianjin University of Technology andEducation，2023，33（2）：14-19.陈庆斌袁等院 基于改进麻雀搜索算法的配送中心选址研究19