Research on Optimization Algorithm Based on Drone-Delivery Vehicle Joint Delivery

doi:10.3778/j.issn.1002-8331.2011-0114

Abstract

Abstract:

Aiming at a new delivery method in the field of logistics distribution—drone combined with delivery vehicle to coordinate parcel delivery, and to study the joint path of drone and delivery vehicle to minimize delivery time, this paper proposes a new optimization iterative algorithm. The algorithm divides the problem into two steps： firstly, determine the delivery vehicle route and customer node allocation, then fix the delivery vehicle route and the drone node, and determine the two merging nodes to generate the drone delivery route. At the end of the algorithm, the drone route and the corresponding delivery vehicle route that meet the constraints are retained to obtain the total time for joint delivery. In this way, starting from the least delivery vehicle node, iteratively obtain the optimal solution by updating the global upper bound. The verification of examples on nodes 10 and 11 shows that the algorithm can effectively narrow the search range, improve operating efficiency, and solve small and medium-sized examples in a reasonable time.

Key words: route optimization, new optimization iterative algorithm, unmanned aerial vehicle, delivery vehicle, joint delivery

摘要：

针对物流配送领域的一种新型交付方式——无人机联合配送车协同配送包裹，研究无人机与配送车联合路径以最小化交付时间的问题，提出了一种新型优化迭代算法。该算法将问题分为两步，首先确定配送车路线及客户节点分配，然后固定配送车路线及无人机节点，确定二者汇合节点生成无人机配送路线。算法最后保留满足约束条件的无人机路线及对应配送车路线，得到联合配送总耗时。以此方式从最少的配送车节点开始迭代，通过更新全局上界得到最优解。通过对10、11节点的示例验证，表明该算法能够有效缩小搜索范围，提高运行效率，在合理时间内求解中小规模示例。

关键词: 路径优化, 新型优化迭代算法, 无人机, 配送车, 联合配送

XIONG Xinglong, LIU Jia, LI Meng, MA Yuzhao. Research on Optimization Algorithm Based on Drone-Delivery Vehicle Joint Delivery[J]. Computer Engineering and Applications, 2021, 57(19): 259-266.

熊兴隆，刘佳，李猛，马愈昭. 基于无人机-配送车联合配送的优化算法研究[J]. 计算机工程与应用, 2021, 57(19): 259-266.

References

[1] SCHERMER D，MOEINI M，WENDT O.Algorithms for solving the vehicle routing problem with drones[C]//Asian Conference on Vietnam：Intelligent Information and Database Systems，2018.
[2] SCHERMER D，MOEINI M，WENDT O.A branch-and-cut approach and alternative formulations for the traveling salesman problem with drone[J].Networks，2020，76：164-186.
[3] HA Q M，DEVILLE Y，PHAM Q D，et al.Heuristic methods for the traveling salesman problem with drone[J].arXiv：1509.08764，2015.
[4] MARIO M，LEONARDO C，MICHELE O，et al.En route truck-drone parcel delivery for optimal vehicle routing strategies[J].IET Intelligent Transport Systems，2017，12（4）：253-261.
[5] 邓永蕤，徐菱，吴茂婷，等.基于无人机与卡车联合运输下的冷链物流网络优化[J].江苏农业科学，2019，47（13）：268-272.
DENG Y R，XU L，WU M T，et al.Optimization of cold chain logistics network based on combined transportation of UAV and truck[J].Jiangsu Agricultural Sciences，2019，47（13）：268-272.
[6] MURRAY C C，CHU A G.The flying sidekick traveling salesman problem：Optimization of drone-assisted parcel delivery[J].Transportation Research Part C Emerging Technologies，2015，54（5）：86-109.
[7] AGATZ N，BOUMAN P，SCHMIDT M.Optimization approaches for the traveling salesman problem with drone[J].Transportation Science，2018，52（4）：965-981.
[8] BOUMAN P，AGATZ N，SCHMIDT M.Dynamic programming approaches for the traveling salesman problem with drone[J].Networks，2018，72：528-542.
[9] SACRAMENTO D，PISINGER D，ROPKE S.An adaptive large neighborhood search metaheuristic for the vehicle routing problem with drones[J].Transportation Research，2019，102（5）：289-315.
[10] YUREK E E，OZMUTLU H C.A decomposition-based iterative optimization algorithm for traveling salesman problem with drone[J].Transportation Research，2018，91（6）：249-262.
[11] HA Q M，DEVILLE Y，PHAM Q D，et al.On the min-cost traveling salesman problem with Drone[J].Transportation Research，2018，86（1）：597-621.
[12] SCHERMER D，MOEINI M，WENDT O.A hybrid VNS/Tabu search algorithm for solving the vehicle routing problem with drones and en route operations[J].Computers & Operations Research，2019，109（9）：134-158.
[13] MAITY S，ROY A，MAITI M.A rough multi-objective genetic algorithm for uncertain constrained multi-objective solid travelling salesman problem[J].Granular Computing，2019，4（1）：125-142.
[14] DELL’AMICO M，MONTEMANNI R，NOVELLANI S.Matheuristic algorithms for the parallel drone scheduling traveling salesman problem[J].arXiv：1906.02962，2019.
[15] CLIMACO G，SIMONETTI L，ROSSETI I.A branch-and-cut and MIP-based heuristics for the prize-collecting travelling salesman problem[J].RAIRO-Operations Research，2021，55：5719-5726.