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

Guy Desaulniers ()
Additional contact information
Guy Desaulniers: Ecole Polytechnique de Montréal and GERAD, Succursale Centre-Ville, Montréal, Quebec H3C 3A7, Canada

Operations Research, 2010, vol. 58, issue 1, 179-192

Abstract: 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.

Keywords: transportation; vehicle routing; integer programming; branch-and-price-and-cut algorithm (search for similar items in EconPapers)
Date: 2010
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (83)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1090.0713 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:58:y:2010:i:1:p:179-192

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().