A Branch-and-Price Algorithm for the Vehicle Routing Problem with Drones

This paper considers a new variant of the vehicle routing problem with drones (VRPD), where multiple vehicles and drones work collaboratively to serve customers. Several practical constraints such as customers' delivery deadlines and drones' energy capacity are considered. Different from existing studies, we treat the number of drones taken by each vehicle as a decision variable instead of a given parameter, which provides more flexibility for planning vehicle and drone routes. We also allow a drone to perform multiple back-and-forth trips when its paired vehicle stops at a customer node. We first formulate this problem as a mixed-integer linear programming model, which is solvable by off-the-shelf commercial solvers. To tackle VRPD instances more efficiently, we next develop a set-partitioning model. To solve it, a branch-and-price algorithm is proposed, where a bidirectional labeling algorithm is used to solve the pricing problem. To speed up the algorithm, the cheapest insertion heuristic is developed for initial column generation, and a tabu search algorithm is first applied before the exact labeling algorithm for finding desired columns in each iteration of the column generation process. Extensive numerical tests show that our algorithm can solve most instances within 25 customers to optimality in a short time frame and some instances of 35 customers to optimality within a three-hour time limit. Results also demonstrate that the allocation decisions of drones can help save the duration of all routes by 3.45\% on average for 25-customer instances, compared to the case of fixing the number of paired drones on each vehicle. In addition, sensitivity analyses show that multiple strategies, e.g., adopting batteries of a higher energy density and developing faster drones, can be applied to further improve the delivery efficiency of a truck-drone system.

Article

Download

View A Branch-and-Price Algorithm for the Vehicle Routing Problem with Drones