An Exact Algorithm for the Vehicle Routing Problem with Time Windows and Shifts

This paper introduces the Vehicle Routing Problem with Time Windows and Shifts (VRPTWS). At the depot, several shifts with non-overlapping operating periods are available to load the planned trucks (e.g., the day shift, the evening shift and the night shift). Each of these shifts has a limited loading capacity. We solve the VRPTWS exactly by means of a branch-and-cut-and-price algorithm. The standard Dantzig-Wolfe decomposition of the arc flow formulation leads to a set partitioning problem, with an additional capacity constraint for every shift, as the master problem.  Moreover, for every shift, a pricing sub problem, which is an elementary shortest path problem with constrained resources, is solved by a label setting algorithm. Shift capacity constraints define knapsack structures, hence we use valid inequalities for the knapsack problem to strengthen the LP-relaxation of the master problem when solved by column generation. In particular, we use a family of tailored cover inequalities defined both on the flow variables and directly on the path variables. Numerical results show that cover inequalities defined directly on the path variables have a significant impact on the obtained lower bounds.