This Article Full Text (PDF) e-companion References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Desaulniers, G. Search for Related Content

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

Ecole Polytechnique de Montréal and GERAD, Succursale Centre-Ville, Montréal, Quebec H3C 3A7, Canada
guy.desaulniers{at}gerad.ca

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.

Subject classifications: transportation; vehicle routing; integer programming; branch-and-price-and-cut algorithm.
History: Received April 2008; revision received November 2008; accepted February 2009.