Lifted and Local Reachability Cuts for the Vehicle Routing Problem with Time Windows

Computational experiments show that the new cutting plane families can substantially improve the lower bounds returned by Lysgaard's Reachability Cuts. The Branch-and-Cut algorithm could also provide the optimal solution of three previously unsolved instances - C222, C225 and C226 - with large capacities and wide time windows and therefore difficult for exact algorithms.