Collaborative Truck-Drone Routing with Pickup and Delivery Networks: a Memetic Optimization Approach

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.