KMG:考虑逆向物流的无人机路径规划策略研究  

KMG:Study on UAV path planning strategy by considering reverse logistics

作　　者：裴颂文 沈天马[2] 宁钟 谢雨鸣[1] PEI Songwen;SHEN Tianma;NING Zhong;XIE Yuming(School of Management,Fudan University,Shanghai 200433,China;School of Optical-Electrical and Computer Engineering,University of Shanghai for Science and Technology,Shanghai 200093,China)

机构地区：[1]复旦大学管理学院,上海200433 [2]上海理工大学光电信息与计算机工程学院,上海200093

出　　处：《系统工程理论与实践》2019年第12期3111-3119,共9页Systems Engineering-Theory & Practice

基　　金：上海市浦江人才(16PJ1407600);中国博士后科学基金(2017M610230);国家自然科学基金重点项目(61332009);国家自然科学基金面上项目(61775139);上海市自然科学基金(15ZR1428600)~~

摘　　要：物流领域无人机派送正成为一种快捷高效的派件方式和应用热点.针对于正向、逆向的物流数据,无人机派送是国内外大型物流企业实施高效物流派送的重要手段.本文提出了一种融合拓展性K-Means++算法和遗传算法的路径动态规划模型(KMG),实现包含逆向物流的无人机调度策略.KMG模型将逆向物流路径融入正向物流路径之中,采用加权聚类算法确定不同属性包裹所需派送无人机的最小数量.在每一簇坐标数据的连通图中,采用遗传算法求解TSP问题,并对可行解进行编码,最终求解出最小欧拉回路.在仿真实验中,KMG模型比独立逆向物流派送的成本减少20.08%,使用拓展性K-Means++聚类计算的时间比传统K-Means算法缩短了298.85%.Delivery by UAV in the logistics field is becoming a fast and efficient dispatch method and application hotspot.For forward and reverse logistics data,drone dispatch is an important means for large-scale logistics enterprises at home and abroad to implement efficient logistics delivery.A path dynamic programming model(KMG)that integrates the scalable K-Means++algorithm and genetic algorithm to implement a UAV scheduling strategy including reverse logistics.The KMG model integrates the reverse logistics path into the forward logistics path,using weighted clustering.The algorithm determines the minimum number of dispatched drones required for different attribute packages.For each connected graph of coordinate data,the genetic algorithm is used to solve the TSP problem and the feasible solution is coded,and finally the minimum Euler loop is solved.The simulation results show that the cost of the KMG model is 20.08%lower than that of the independent reverse logistics.The time of using the scalable K-Means++clustering calculation is 298.85%shorter than the traditional K-Means algorithm.

关 键 词：无人机 逆向物流 拓展性K-Means++ 遗传算法 路径规划 

分 类 号：O221.3[理学—运筹学与控制论]