TY - JOUR
T1 - Collaborative Truck-Drone Routing with Pickup and Delivery Networks
T2 - a Memetic Optimization Approach
AU - Zhai, Ruonan
AU - Chen, Zihong
AU - Hu, Zhaokun
AU - Cui, Yuanhao
AU - Mei, Yi
AU - Du, Wenbo
AU - Guo, Tong
AU - Li, Yumeng
N1 - Publisher Copyright:
© 2002-2012 IEEE.
PY - 2026
Y1 - 2026
N2 - Recent advancements in low-altitude network technology have significantly enhanced the applications of drones across various domains. This study emphasizes the innovative application of drones in collaborative delivery systems. We introduce the Flying Sidekick Traveling Salesman Problem with Pickup and Delivery (FSTSP-PD) to model real world online order and delivery networks. Firstly, the paper provides a new mixed-integer linear programming model aimed at optimal routing and scheduling of drones and trucks in this new paradigm of collaborative delivery networks. To solve this NP-hard problem, a memetic algorithm with tailored solution representation and a variable neighborhood search approach with search operators is proposed in this study. Moreover, a novel PD constraint-handling method is developed to efficiently handle the coupling and tight constraints by repairing the infeasible solutions. Comprehensive experimental results show that the proposed algorithm significantly outperforms the existing state-of-the-art algorithms on most benchmark instances. Further investigations underscore the effectiveness of the integrated truck-drone system in addressing pickup and delivery problems.
AB - Recent advancements in low-altitude network technology have significantly enhanced the applications of drones across various domains. This study emphasizes the innovative application of drones in collaborative delivery systems. We introduce the Flying Sidekick Traveling Salesman Problem with Pickup and Delivery (FSTSP-PD) to model real world online order and delivery networks. Firstly, the paper provides a new mixed-integer linear programming model aimed at optimal routing and scheduling of drones and trucks in this new paradigm of collaborative delivery networks. To solve this NP-hard problem, a memetic algorithm with tailored solution representation and a variable neighborhood search approach with search operators is proposed in this study. Moreover, a novel PD constraint-handling method is developed to efficiently handle the coupling and tight constraints by repairing the infeasible solutions. Comprehensive experimental results show that the proposed algorithm significantly outperforms the existing state-of-the-art algorithms on most benchmark instances. Further investigations underscore the effectiveness of the integrated truck-drone system in addressing pickup and delivery problems.
KW - Combinatorial Optimization
KW - Delivery Networks
KW - Memetic Algorithm
KW - Traveling Salesman Problem
KW - Unmanned Aerial Vehicles (UAVs)
KW - Variable Neighborhood Search
UR - https://www.scopus.com/pages/publications/105036409256
U2 - 10.1109/TMC.2026.3684905
DO - 10.1109/TMC.2026.3684905
M3 - 文章
AN - SCOPUS:105036409256
SN - 1536-1233
JO - IEEE Transactions on Mobile Computing
JF - IEEE Transactions on Mobile Computing
ER -