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

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

物流领域无人机派送正成为一种快捷高效的派件方式和应用热点.针对于正向、逆向的物流数据,无人机派送是国内外大型物流企业实施高效物流派送的重要手段.本文提出了一种融合拓展性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.