An Exact Solution Method for Truck-Assisted Drone Routing Problem

Drone-truck combined delivery has huge potential for becoming an innovative last-mile solution for logistics. This paper presents a variation of drone-truck operation with the goal to minimize the completion time, where the truck provides a mobile recharging station for drones and drones serve all the customers. This problem can be decomposed into two elementary phases: (1) truck with a drone arriving at rendezvous nodes and (2) drone flying to the customer points. Our exact method is based on branch-and-bound, in which a tree node represents a customer subsequence and the lower bound is the objective value with optimal launch and retrieve locations for the fixed customer sequence. The best departing and collection sites for each tree node are obtained through custom cuts, which consider a customer-based pruning strategy and the interaction-based pruning between customers. Our experimental results show that the novel exact algorithm outperforms CPLEX in terms of computational time, while obtaining results on par regarding quality.