基于聚类和二分图匹配的物流派件调度方法  

Logistics delivery scheduling method based on clustering algorithm and bipartite graph matching

作　　者：应毅[1] 唐立 刘定一[1] 刘亚军[3] YING Yi;TANG Li;LIU Dingyi;LIU Yajun(College of Computer Science and Technology, Sanjiang University, Nanjing, Jiangsu 210012, China;Graduate School of Computer Science and Engineering, University of Aizu, Aizu-Wakamatsu 965-8580, Japan;School of Computer Science and Engineering, Southeast University, Nanjing, Jiangsu 210096, China)

机构地区：[1]三江学院计算机科学与工程学院,江苏南京210012 [2]会津大学计算机科学与工程研究生院,日本会津若松965-8580 [3]东南大学计算机科学与工程学院,江苏南京210096

出　　处：《江苏大学学报（自然科学版）》2020年第3期274-280,共7页Journal of Jiangsu University：Natural Science Edition

基　　金：国家自然科学基金青年科学基金资助项目(61502206);江苏省高等学校自然科学研究面上项目(17KJB520033);江苏高校“青蓝工程”项目(苏教师[2018]12号)。

摘　　要：针对物流末端配送服务中派件调度时区域划分不合理、工作分配差异大的问题,提出“先分区,后排班”2阶段派件调度算法.首先利用GIS技术、Web技术和移动开发技术,构建了针对“最后1 km”配送的智能物流信息系统;在此系统内,基于k-medoids聚类算法,引入工作量均衡指标,依据实际路径距离,实现了“点面聚合,区域聚类”配送区域划分方法;应用二分图最大权匹配KM算法,实现了派件调度分配算法.在顺丰速运某网点的配送活动中进行试验,结果表明:2阶段派件调度算法的区域划分更加聚集,快递人员间的工作分配更加均衡,有效地提升物流网点的服务效率.To solve the problems of unreasonable area partitioning and unbalanced work assignment in delivery scheduling of logistics terminal distribution service,a two-stage dispatch scheduling algorithm of area partitioning before scheduling was proposed.Based on GIS technology,Web technology and mobile development technology,an intelligent logistics information system with considering the last 1 km delivery was constructed.Introducing workload balance index with considering actual path distance,the distribution area partitioning method of point-to-surface aggregation with regional clustering was realized based on the k-medoids clustering algorithm.Based on the maximum weight,the bipartite graph matching KM algorithm was proposed to implement delivery scheduling algorithm.The two-stage dispatch scheduling algorithm was applied in the distribution activities of SF EXPRESS.The results show that the proposed method can realize more clustered area partitioning performance and more balanced work distribution among express delivery personnels,which effectively improves the service efficiency of logistics network.

关 键 词：派件调度 智能物流信息系统 聚类算法 二分图匹配 工作量均衡 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]