A branch-cut-and-price approach for the two-echelon vehicle routing problem with drones

We present a new set-partitioning model for the two-echelon vehicle routing problem with drones (2E-VRP-D). In this model, partial routes corresponding to drone movements are enumerated by an efficient dynamic program. A state-of-the-art exact branch-cut-and-price algorithm solves the model using a labeling algorithm for the pricing problems. We further propose an adaptation of the well-known rounded capacity cuts, specifically tailored to address this problem, as well as pre-processing methods designed to enhance the algorithm’s efficiency. In addition, we propose an effective heuristic branch-cut-and-price based on the exact algorithm. Computational experiments demonstrate that the exact algorithm solves all instances from the 2E-VRP-D literature and significantly increases the size of optimally solved clustered instances. Finally, a sensitivity analysis is conducted to assess the impact of the proposed enhancements. • The Two-Echelon Vehicle Routing Problem with Drones is considered. • A new set-partitioning formulation is proposed. • A heuristic procedure based on graph shrinking is proposed. • An adaptation of cutting planes for the specific problem is proposed. • The exact algorithm solves all literature instances. • New datasets of larger size instances are presented.