Branch-and-Price-and-Cut for the Split-Delivery Vehicle Routing Problem with Time Windows

This paper addresses the split-delivery vehicle routing problem with time windows (SDVRPTW) that consists of determining least-cost vehicle routes to service a set of customer demands while respecting vehicle capacity and customer time windows. The demand of each customer can be fulfilled by several vehicles. For solving this problem, we propose a new exact branch-and-price-and-cut method, where the column generation subproblem is a resource-constrained elementary shortest-path problem combined with the linear relaxation of a bounded knapsack problem. Each generated column is associated with a feasible route and a compatible delivery pattern. As opposed to existing branch-and-price methods for the SDVRPTW or its variant without time windows, integrality requirements in the integer master problem are not imposed on the variables generated dynamically, but rather on additional variables. An ad hoc label-setting algorithm is developed for solving the subproblem. Computational results show the effectiveness of the proposed method.