基于三阶段优化的大无人机辅助小无人机物流配送方法

Three Stage Optimization Method for Mother UAV Assist Small UAV Parcels Delivery

中文关键词  异构无人机  物流配送  路径规划  分而治之  

英文关键词  heterogeneous multi-UAV  logistics delivery  routing  divide and conquer  

中文摘要

      无人机包裹配送是近年来获得广泛关注的新配送方式, 相比于基于地面车辆的配送方式, 多无人机配送具 有高效率、强时效性和灵活机动等优势. 因此, 本文提出了一种全新的异构多无人机物流配送模式, 即单架大无人 机辅助多架小无人机进行的包裹配送. 该配送模式的新特点是: 大无人机携带多架小无人机到配送区域放飞, 多架 小无人机分别配送所指派区域的包裹, 每架无人机在一次航行中可配送多个包裹, 多架小无人机同时进行配送. 为 了高效的求解这个新配送问题, 文章设计了一种基于分而治之三阶段的迭代优化算法, 第1阶段采用聚类方法对客 户点聚类并生成初始解; 第2阶段提出一种改进的变邻域搜索算法优化大无人机路径; 第3阶段使用动态规划方法 优化小无人机路径. 这3个阶段不断迭代优化直至满足停止准则. 为了验证所提出算法的有效性, 在大量算例上进 行了实验测试, 实验结果展示了所提出算法的求解效率和目标函数值显著优于其他对比算法. 文章所提出的新的 异构多无人机配送模式及其求解方法, 为解决现代物流配送的痛点问题提供了一种全新方式与决策依据.

英文摘要

      The unmanned aerial vehicle (UAV) parcel delivery is a new delivery mode that has received widely attention in recent years. Compared with the distribution mode based on ground vehicles, multi-UAV delivery has the significant advantages of high efficiency, strong timeliness and flexibility. Thus, this paper proposed a new delivery modea using heterogeneous multi-UAV, where a large UAV assists multiple small UAVs in parcel delivery. The large drone carries multiple small drones to the distribution sub-regions and launches them in sequence, and each UAV can deliver multiple parcels in a flight. To solve this new problem efficiency, we design a three-stage iterative optimization method. The first stage generates the initializing routes by a clustering method. The second stage optimizes the large UAV route by the proposed improved variable neighborhood search algorithm, and the third stage optimizes the small UAV routes by the dynamic programming algorithm. Extensive experiments are conducted and the results show that both the distance cost and runtime of the proposed algorithm are significantly superior to that of other comparison algorithms, which provide a new way and decision basis to solve the pain point of modern logistics delivery problems.