The parallel drone scheduling problem with multiple drones and vehicles

• Published in: European journal of operational research 2022-07, Vol.300 (2), p.571-589
• Main Authors: Mbiadou Saleu, Raïssa G., Deroussi, Laurent, Feillet, Dominique, Grangeon, Nathalie, Quilliot, Alain
• Format: Article
• Language: English
• Subjects: City logistics; Computer Science; Drone delivery; Dynamic programming; ILS; m-TSP; Operations Research; Routing
• ISSN: 0377-2217; 1872-6860
• DOI: 10.1016/j.ejor.2021.08.014

•The generalization of the Parallel Drone Scheduling Problem to multiple trucks.•A giant tour decomposition procedure able to handle multiple vehicles, with innovative label definition, extension rules, lower bounds and upper bounds.•Ad hoc local search moves to complement the decomposition procedure.•An Iterated Local Search framework to improve the exploration of the search space.•A Branch-and-Cut algorithm to solve exactly small instances. Delivery of goods into urban areas constitutes an important issue for logistics service providers. One of the most talked-about developments in recent years has been the potential use of unmanned aerial vehicles, or drones, for transporting packages, food, medicine, and other goods. Delivery by drones offers new possibilities, but also induces new challenging routing problems. In this paper, we address and extend the so-called Parallel Drone Scheduling Traveling Salesman Problem. Basically, in this problem, deliveries are split between a vehicle and one or several drones. The vehicle performs a classical delivery tour from the depot, while the drones are constrained to perform back and forth trips. The objective is to minimize the completion time. We extend the problem by considering several vehicles. We call it Parallel Drone Scheduling Multiple Traveling Salesman Problem. We propose a hybrid metaheuristic for its solution. The procedure starts by building a giant tour visiting all customers. Then, the giant tour is split in order to determine a set of vehicles tours (each vehicle tour following the order defined by the giant tour) and a set of customers assigned to drones. Thirdly, an improvement step move customers between vehicles or between vehicles and drones. We also propose a Mixed Integer Linear Programming formulation and a simple branch-and-cut approach. The proposed approach is validated via an experimental campaign on instances taken from the CVRPLIB11Capacited Vehicle Routing Problem LIBrary library. Computational experiments comparing several variants of the hybrid metaheuristic give some insights on this drone delivery system.