基于改进 DBSCAN 省级电力物资仓库聚类的配送车辆路径优化研究论文

　　【关键词】库容均衡,改进DBSCAN聚类算法,C-W法,路径优化
 

　　Research on Optimization of Vehicle Routing Problem Based on Improved DBSCAN Clustering Algorithm of Power Material Warehouses
 

　　JIANG Zheng-hua1,GAO Zhan2,WANG Liu-j un3,ZHU Ming-da4,CHEN Da-qiang5
 

　　(1.Department of Supply,Wenzhou Power Supply Company of State Grid Zhejiang Electric Power Co.,Ltd.,Wenzhou 325028;2.Department of Supply,State Grid Zhejiang Electric Power Co.,Ltd.,Hangzhou 310063;3.Department of Supply,Jiaxin Power Supply Company of State Grid Zhejiang Electric Power Co.,Ltd.,Jiaxin 314033;4.Information and Communication Branch of State Grid Zhejiang Electric Power Co.,Ltd.,Hangzhou 310016;5.School of Management and E-business,Zhejiang Gongshang University,Hangzhou 310018,China)
 

　　【Abstract】Given the complexity of the vehicle routing problem with multiple origin depots and dispersed warehouses of power materials warehouses,a two-stage method was proposed based on improved DBSCAN clustering algorithm,in which the clustering algorithm was used to simplify the problem of multiple storage warehouses of power materials.Firstly,the storage warehouses were classified by using the improved DBSCAN clustering algorithm,and a certain number of warehouse clusters were obtained.Thus,the vehicle routing problem was transformed into a single origin depot vehicle routing for each warehouse clusters.Secondly,the improved C-W method is used to solve the vehicle routing problem for each warehouse cluster.Finally,with the case study of the power material warehouse in Zhejiang Province,the applicability and feasibility of the proposed two-stage method and algorithm were verified.

       【Ｋｅｙｗｏｒｄｓ】ｓｔｏｒａｇｅｃａｐａｃｉｔｙｂａｌａｎｃｅ；ｉｍｐｒｏｖｅｄＤＢＳＣＡＮｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍ；Ｃ－Ｗｍｅｔｈｏｄ；ｒｏｕｔｉｎｇｏｐｔｉｍｉｚａｔｉｏｎ

       １引言
 

　　电力物资仓库是电力物资集中存储的重要场所，也是企业顺利生产、检修的重要基础，随着电力技术的不断发展和物力集约化进程的不断推进，国网公司对电力物资管理的要求逐步提高，针对普遍存在的仓库库存积压、管理精益度不足、物资供给配送成本高等问题，要求在中心库集中配送模式下，兼顾效率与效益。因此，如何通过电力物资存储与配送的联动提升物资需求的高效响应，对实现电力物资整体的资源优化配置以及仓储网络的库容均衡具有重要的研究意义。
 

　　当前提升电力物资存储与配送供应的效率与效益的相关研究主要集中在以下几个方面：一是基于提升电力物资需求预测精度视角，为提升物资供给水平并消除物资预测与实际分配比例严重失衡问题，陈珏伊［１］提出了基于大数据技术开展物资需求预测的方法；王竹君等［２］为准确预测变电站及配网工程的物资需求，提出了基于矩阵分解的预测方法；陶加贵等［３］为有效保障智慧仓储系统的物资供应能力，提出了一种结合蒙特卡洛模拟和改进长短期记忆网络的电力物资需求预测方法。二是基于电力物资仓储网络规划与优化角度，针对物资供应在仓储网络面临的挑战，赵深等［４］讨论了以中心库为生态核心的省级电力物资仓储生态系统构建；魏雅楠，赵刚［５］以保障供应和降低成本为目标，提出了基于免疫算法的电网物资仓库布点优化；王贞民［６］以低成本高效率配送为原则，运用ＡＨＰ进行了省域范围内电力物资仓储网络布局规划优化。三是基于电力物资配送路径优化层面，如张云翔［７］针对深圳供电局的实证数据，提出了基于引入道路交通运行指数的节约法的电力物资配送路径寻优模型；汤雪松等［８］考虑电力物资配送多目标路径优化方案；徐郁等［９］考虑了电力物资配送区域的加油站分布情况、物资运输车辆的油耗等约束，提出了一种基于深度强化学习（ＤｅｅｐＲｅｉｎｆｏｒｃｅｍｅｎｔＬｅａｒｎｉｎｇ，ＤＲＬ）的电力物资配送多目标路径优化模型和求解算法。总体上看，为提升电力物资供应水平，行业进行了大量的研究，但类似非电力行业多级配送网络运作优化的选址－路径问题（ Ｌｏｃａｔｉｏｎ Ｒｏｕｔｉｎｇ Ｐｒｏｂｌｅｍ，ＬＲＰ）的仓储节点选址与配送路径 优化相结合的研究还有待深入。
 

　　综上，考虑前人对电力物资配送车辆路径优化研究很少涉及仓库的选择，以及运算过程大多直接采用单起点配送路径优化的局限性，尤其难以解决区域电力物资库配送现状，本文考虑电力物资多个仓库协同配送的特点，拟通过对电力物资仓库（物资需求方）合理分类，根据配送中心（物资供应方）数量划分为若干个仓库簇，将多起点路径优化问题转化为单起点路径优化问题，以此形成一种不同于传统ＬＲＰ的两阶段仓储节点选址与配送路径优化方案。
 

　　２基于省级仓库簇划分的配送路径优化
 

　　２．１基于改进ＤＢＳＣＡＮ聚类的省级仓库簇划分
 

　　第一阶段，基于改进ＤＢＳＣＡＮ聚类的省级仓库簇划分。ＤＢＳＣＡＮ聚类算法由Ｅｓｔｅｒ等［１０］在１９９６年提出，是一种基于密度空间的聚类算法，它一般认为同一类别的样本在其周围不远处一定存在同样类别的样本，并将这些同类样本划分为同一聚类，通过将所有样本划分为不同的类别，得到最终的聚类结果。ＤＢＳＣＡＮ聚类算法将数据点分为三类：一是核心点，若样本Ｘｉ的ε邻域内至少包含了ＭｉｎＰｔｓ个样本，则称Ｘｉ为核心点；二是边界点，若样本Ｘｉ的ε邻域内少于ＭｉｎＰｔｓ个样本，则称Ｘｉ为边界点；三是噪音点，除以上两种之外即为噪音点。
 

　　传统的ＤＢＳＣＡＮ聚类算法一般用于对客户的聚类，且未考虑到不同客户之间的需求差异。本文结合电力物资仓库的特点，即其配送中心既承担为其他仓库配送物资的任务，同时也直接为需求点配送需求物资，在聚类分析过程中将其作为样本分析，并根据其库存容量划分聚类点。通过多次聚类实现配送中心与仓库的配对，以此形成多个包含单一配送中心及其配对仓库的仓库簇。由此，改进ＤＢＳＣＡＮ聚类算法具体流程如下：
 

　　第一步：初始化核心聚类簇数ｋ＝０，初始化核心对象集合Ω＝Φ，初始化未访问样本集合Γ＝Ｄ，初始化划分后的簇Ｃ＝Φ。
 

　　第二步：设定邻域ε和样本数ＭｉｎＰｔｓ，对所有样本点按以下步骤进行聚类：
 

　　①随机选取样本点Ｘｉ，若Ｘｉ的ε邻域内至少包含了ＭｉｎＰｔｓ个样本点，则为核心点，且和邻域内所有点组成一个初始的ｃｌｕｓｔｅｒ。
 

　　②遍历ｃｌｕｓｔｅｒ里所有的其他点，如果遍历的点刚好是核心点则把核心点及其邻域内所有点归为ｃｌｕｓｔｅｒ，如果有噪音点，则剔除。
 

　　③重复步骤②，直到没有更多的点加入ｃｌｕｓｔｅｒ，得到ｃｌｕｓｔｅｒ１。
 

　　④重复以上步骤，直到所有样本点被遍历，算法结束。由此，可得ｃｌｕｓｔｅｒ１，ｃｌｕｓｔｅｒ２，…，ｃｌｕｓｔｅｒ。
 

　　第三步：按照就近原则，将噪音点划分到就近的聚类簇。
 

　　第四步：根据配送中心及各仓库的需求量，重新设定邻域ε和样本数ＭｉｎＰｔｓ，按照以上步骤对ｃｌｕｓｔｅｒ１中所有样本点重新进行聚类。
 

　　第五步，重复第四步，直到所有样本点有相应的聚类簇。
 

　　传统的邻域半径未考虑各仓库的需求量，本文根据有利形成单起点配送仓库点簇的原则，综合考虑各仓库的需求量，设置邻域半径影响参数β，即可适当调整邻域半径与具备供给能力的配送中心进行适配，形成方法改进。
 

　　２．２基于改进Ｃ－Ｗ算法的仓库簇路径优化
 

　　第二阶段，仓库簇路径优化。本文根据电力物资仓库实际情况，针对每一个仓库簇分别进行配送路径优化，在此，应用Ｃ－Ｗ算法进行求解。Ｃ－Ｗ算法由Ｃｌａｒｋｅ，Ｗｒｉｇｈｔ［１１］在１９６４年提出，是为了解决旅行商问题，但它解决问题时忽略了各种限制条件。本文在其基础上，考虑配送车辆载重约束对其进行改进。算法步骤如下：

　　第一步：对所有点进行排序，并构建距离表。
 

　　第二步：根据距离表计算节约里程表，根据公式ｓｉｊ＝ｄｏｉ＋ｄｏｊ－ｄｉｊ（ｉ，ｊ＝１，２，…，ｎ）依次计算任意仓库ｉ和ｊ相连后的节约值，若有ｎ个仓库，那么节约值的个数是Ｃ，并赋予节约里程集合Ｓ，Ｓ＝｛ｓ（ｉ，ｊ）＞０；ｉ，ｊ＝１，２，３，…，ｎ｝。
 

　　第三步：对节约里程表按节约值进行降序排列。
 

　　第四步：构建配送路线，从节约值最大的点依次向下构建，满足以下条件之一则继续执行第五步，否则舍去。
 

　　①仓库ｉ和仓库ｊ都不在配送路线上；
 

　　②仓库ｉ和仓库ｊ在不同的配送路线上，其中一个是起点，一个是终点；
 

　　③仓库ｉ和仓库ｊ都在同一配送路线上。
 

　　第五步：若满足以上条件则可以计算连接仓库ｉ和ｊ之后线路上的货运量ｑｉｊ，若Ｑ＞ｑｉｊ（Ｑ为额定载重量），转到第六步，否则删除点ｉ和点ｊ之间的连接，转到第四步；
 

　　第六步：仓库ｉ和ｊ可以连成同一路径；
 

　　第七步：直到把Ｃ个节约值ｓ（ｉ，ｊ）检验完，并找到最优路径。
 

　　３算例分析
 

　　３．１算例概况
 

　　本文选取浙江省８３家电力物资仓库（含配送中心）为研究对象，仓库及配送中心分布如图１所示，各仓库经纬度坐标如表１所示，其中编号１１、１３、４５、５４、６３、６８、５９分别为杭州、嘉兴、温州、宁波、丽水、金华和舟山等７家配送中心。在运作中由配送中心向仓库供应配送，拟通过多次ＤＢＳＣＡＮ聚类算法对仓库进行聚类分析，将大规模的多起点路径优化问题转为单起点路径优化问题，然后采用改进Ｃ－Ｗ算法求解计算。

 

　　由图１可知，仓库的分布有一定规律性且比较分散。如果采用多起点路径优化模型可能无法得到最优解，因此采用ＤＢＳＣＡＮ聚类算法进行分类，利用各仓库的位置关系，将仓库分类并对应配送中心，以简化问题求解难度。
 

　　３．２区域仓库簇划分
 

　　基于改进ＤＢＳＣＡＮ聚类进行多次聚类。首次对邻域ε＝０．４、样本数ＭｉｎＰｔｓ＝４进行聚类分析，结果如图２所示，不同的颜色代表不同的聚类簇，其中圆圈所表示的噪声点较多，可将其归入就近的聚类簇。由此，首次聚类将仓库点分为四类，聚类簇成员数量如表２所示。

 

 

　　由于首次聚类结果中聚类簇成员中配送中心分布仍然分散，综合考虑配送中心地理位置、库容量及各仓库点需求量，对各聚类簇继续进行聚类分析。其中聚类簇３的成员数量为１０，相对已较为集中且对应宁波配送中心，故无需再次聚类，即是否需要再次聚类以有利形成单起点配送仓库点簇的原则。由此，聚类簇１、２、４可进行二次聚类，结果如图３所示。以聚类簇１为例，在二次聚类时参数设置根据有利形成单起点配送仓库点簇原则，调整邻域半径影响参数β，使所得各子簇都能匹配到具备供给能力的配送中心，以便优化后续的单起点路径。聚类结果如图所示，其中“×”“＋”为两个聚类簇（⊗⊕表示各子簇仓库点中的配送中心），“○”为噪音点；根据上文所述方法，将噪音点按照就近原则划分到就近的聚类簇，如左上角的四个噪音点归入“＋”聚类簇、左下角的四个噪音点归入“×”聚类簇。

 

　　重复上述过程，经过多次聚类，最终聚类结果如图４所示，聚类簇成员数量如表３所示。

　


 

　　3.3单一仓库簇路径优化
 

　　以最终聚类结果中的聚类簇1为例，共有13位成员（含1个配送中心，即杭州配送中心），经纬度坐标及需求量如表4所示。

　
 

　　聚类簇1使用多辆运输车辆配送，车辆从杭州配送中心出发，把货物送至各个仓库点后返回配送中心，车辆最大载重量为8吨，平均燃油费为(5+0.18q)元／千米，油费为6元/升，耗油量为15升／百公里，二氧化碳排放系数为2.66公斤/升，单位碳税为20元／公斤。每辆车的固定成本按500元计算，此外，仓库间距离根据经纬度，由百度地图查找所得。
 

　　通过计算，聚类簇1的配送一共使用了4辆配送车辆，共节约里程615.5公里，节约里程占比约47%。配送路线如图5所示，最大节约里程数615.5公里，车辆路线成本及路线如表5所示。

 

　　参照聚类簇1的配送路线优化步骤，可对其他聚类簇进行配送路线优化，进而实现由7家配送中心对83家电力物资仓库进行物资供给的省域配送车辆排程优化。
 

　　4结论
 

　　本文结合改进DBSCAN聚类算法和改进C-W算法进行解决电力物资车辆路径优化问题提供了新的解决方案，丰富了车辆路径优化问题的解决理论。算例结果表明，该方法有效考虑了电力物资需求配送的复杂性，在操作上简便易行，且参照聚类簇1计算结果，节约里程占比约47%,大大降低了企业运输成本。
 

　　此外，本文提出的基于改进DBSCAN省级电力物资仓库聚类的配送车辆路径优化两阶段方法，可针对多层级电力物资储配网络的节点差异性，进一步考虑仓库节点层级差异改进DBSCAN聚类算法，同时，可针对新能源配送车辆应用场景，进一步考虑车辆行驶里程改进C-W算法，具有较好的拓展性，并可为其他场景的车辆路径优化提供借鉴。
 

　　［参考文献］
 

　　[1]陈珏伊．大数据在电力物资需求预测管理中的应用研究[J].电力大数据，2018,21(03):83-87.

       [2]王竹君，朱颖琪，孙界平．基于矩阵分解的电力物资需求预测[J].四川大学学报（自然科学版），2019,56(04):639-644.

       [3]陶加贵，孙毅，赵恒，管士宁．电力物资小样本集的改进长短期需求预测模型[J].电气自动化，2023,45(01):50-53.

       [4]赵深，高瞻，陈达强，琚泽民．以中心库为生态核心的省级电力物资仓储生态系统构建与实践[J].物流技术，2018,37(10):1-7.

       [5]魏雅楠，赵刚．基于免疫算法的电网物资仓库布点优化研究[J].云南电力技术，2016,44(6):1-5.

       [6]王贞民．电力行业物资仓储网络布局的规划研究[J].物流技术与应用，2015,20(9):134-140.

       [7]张云翔．引入交通指数的节约法对电力物资配送寻优研究[J].物流技术，2016,35(8):111-115.

       [8]汤雪松，邓勇，刘鑫，龚仁兰，廖勇．基于RW-GA的电力物资配送多目标路径优化[J].重庆理工大学学报（自然科学），2021,35(07):161-168.

       [9]徐郁，朱韵攸，刘筱，邓雨婷，廖勇．基于深度强化学习的电力物资配送多目标路径优化[J].计算机应用，2022,42(10) :3252 - 3258.
 

　　[10]Ester M,Kriegel H P,Sander J,Xu X.A Density-based Algorithm for Discovering Clusters in Large Spatial Databases with Noise[C].Proceedings of the Second International Conference on Knowledge Discovery and Data Mining,August 1996:226-231.
 

　　[11]Clarke G,Wright J R.Scheduling of vehicle routing problem from a central depot to a number of delivery points[J].Operations Research,1964(12):568-581.