A Column Generation-and-Enumeration Algorithm for the Vehicle Routing Problem with Time Windows and Route Duration Minimization

This work presents an exact algorithmic framework for the Vehicle Routing Problem with Time Windows and Route Duration Minimization (VRPTWDM). We develop a column-generation-and-enumeration approach built on new dominance relations for the pricing subproblem. The central methodological contribution is a cost-timing trade-off condition that preserves reduced-cost ordering under extension while enabling substantially stronger label pruning. Computational experiments on Solomon benchmark instances show marked gains in efficiency and robustness, including significantly shorter runtimes and a higher number of solved cases than prior branch-and-price variants.