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). We solve the VRPTWS exactly by a branch-and-cut-and-price algorithm. The master problem is a set partitioning with an additional constraint for every shift. Each constraint requires the total quantity loaded in a shift to be less than its loading capacity. For every shift, a pricing problem 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 master variables. Numerical results show that cover inequalities defined directly on the master variables have a significant impact on the size of the obtained lower bounds.

• Registration to Remy Spliet, spliet@ese.eur.nl is required for availability of lunch.

This event is organised by the Econometric Institute.
Twitter: @MetricsSeminars