A Collaborative Truck Multi-Drone Routing Problem with Flexible Launch and Recovery Operations

Authors:

Abstract
The collaborative truck multi-drone routing problem with flexible launch and recovery operations (CTMDRP-FLRO) in last-mile delivery is studied. In contrast to previous methods, CTMDRP-FLRO enables trucks to launch and recover drones at any location on the truck route, in addition to the depot and customer locations. First, the position relationship between nodes on the arc is analyzed, and on this basis, the coordinate calculation approach of the nodes launching and recovering drones on the truck travel routes is presented. Second, a mixed integer programming model of CTMDRP-FLRO is formulated with the objective of minimizing the weighted sum of the total distribution time and delivery completion time. Third, a multistage hybrid heuristic algorithm based on K-means clustering (MHHABKC) is designed to optimize the routes of CTMDRP-FLRO. Lastly, numerical experiments are conducted based on multitype instances. The results show the following: (1) CTMDRP-FLRO expands the flexibility for drone launch and recovery operations. Each drone can launch from the optimal nodes closer to the customer to carry out delivery and can return to the optimal nodes to rendezvous with the truck after completing its task. CTMDRP-FLRO effectively curtails drone flight distance and reduces truck multi-drone collaboration time. (2) The MHHABKC can scientifically allocate the delivery tasks of truck multi-drone tandems, reasonably plan the routes of the CTMDRP-FLRO with very short notice, and effectively improve the distribution efficiency of CTMDRP-FLRO.