2-path cuts for the vehicle routing problem with time windows

This paper introduces a strong valid inequality, the 2-path cut, to produce better lower bounds for the vehicle routing problem with time windows. It also develops an effective separation algorithm to find such inequalities. We next incorporate them as needed in, the master problem of a Dantzig-Wolf e decomposition approach. In this enhanced optimization, algorithm, the cou pling constraints require that each customer be serviced. The subproblem is a shortest path problem with time window and capacity constraints. We appl y branch and bound to obtain integer solutions. We first branch on the numb er of vehicles if this is fractional, and then on the flow variables. The a lgorithm has been implemented and tested on, problems of up to 100 customer s from the Solomon. datasets. It has succeeded in solving to optimality sev eral previously unsolved problems and a new 150-customer problem. In additi on, the algorithm proved faster than algorithms previously considered in th e literature. These computational results indicate the effectiveness of the valid inequalities we have developed.