An iterative two-phase optimization method for heterogeneous multi-drone routing problem considering differentiated demands

Abstract Owing to low cost, high flexibility and delivery efficiency, effectively addressing the challenges of “last-mile” delivery. While collaborative truck-drone delivery systems have been proposed to overcome limitations such as limited battery life and payload capacity, they are not well-suited for large and heavy parcel delivery. To solve the issue, a pioneering heterogeneous multi-drone delivery system. In this system, the mother drone handles the delivery of large and heavy parcels, releasing small drones to manage the delivery of smaller and lighter parcels. To address the complexities of this multi-drone delivery system, we introduce a divide-and-conquer framework consisting of two integral phases. The first phase, the task allocation phase, generates multiple task allocation schemes, while the second phase, the single-drone route planning phase, produces high-quality routes for each individual drone. Two phases are performed in an iterative manner until the predefined stopping criteria are satisfied. In the task allocation phase, we propose a simulated annealing algorithm (SA) to facilitate task allocation among multiple drones, utilizing transfer and recombination operators to generate high-quality solutions. After obtaining the task allocation scheme, a satisfactory route of a mother drone is generated by a variable neighborhood descent algorithm (VND). A desirable route for each single small drone is produced by dynamic programming (DP).Extensive experiments are conducted, demonstrating the outstanding optimization and time efficiency of the proposed two-phase optimization method by the fact that it obtains within a 4.89% gap from the optimal solution generated by CPLEX in 15.48 s for instance up to 125 nodes.