A Branch-Cut-and-Price algorithm for the vehicle routing problem with time windows and duration constraint

In this work, we study a variant of the Vehicle Routing Problem with Time Windows (VRPTW), which integrates two operationally relevant features: flexible departure times from the depot and strict limits on route duration. The resulting problem, termed VRPTW with Route Duration Constraint (VRPTWDC), introduces a scheduling dimension that makes the routing computationally challenging and largely unexplored in the literature. We develop an exact branch-cut-and-price algorithm, having as its main feature a bi-bidirectional labeling algorithm for solving the complex pricing subproblem. Indeed, as the only previously proposed efficient labeling algorithm for the VRPTWDC has a mistake, we provide rigorous proofs of its correctness. Computational experiments on benchmark instances demonstrate the effectiveness of the approach.