Customer Base Analysis with Social Interaction: A Structural Model

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 obtained lower bounds.