A Branch-and-Price Algorithm for Robust Drone-Vehicle Routing Problem with Time Windows.

This article focuses on the robust drone-vehicle routing problem with time windows (RDVRPTW), which models cooperative delivery by trucks equipped with multiple drones under uncertain travel and flight times. The study presents a compact mixed-integer programming formulation solvable by standard solvers and develops a novel branch-and-price algorithm featuring a two-phase column generation approach: first generating robust truck routes via a tailored labeling algorithm with dominance rules based on cost bounds, then determining compatible drone dispatch patterns through dynamic programming. Computational experiments on Solomon’s VRPTW instances and real-life UPS data demonstrate that the proposed algorithm outperforms state-of-the-art MIP solvers in solution quality and computational efficiency. The paper also introduces a column generation-based heuristic for larger instances and discusses the advantages and limitations of the budget of uncertainty approach used to model travel time uncertainties.