Enhanced Branch and Price and Cut for Vehicle Routing with Split Deliveries and Time Windows

C. Archetti (), M. Bouchard () and G. Desaulniers ()
Additional contact information
C. Archetti: Department of Quantitative Methods, University of Brescia, 25122 Brescia, Italy
M. Bouchard: Mechanical Engineering Department, Université Laval, Forac Research Consortium, Québec G1V 0A6, Canada
G. Desaulniers: Ecole Polytechnique de Montréal and GERAD, Montréal, Québec H3C 3A7, Canada

Transportation Science, 2011, vol. 45, issue 3, 285-298

Abstract: In this paper, we study the split delivery vehicle routing problem with time windows (SDVRPTW) that is a variant of the well-known vehicle routing problem with time windows (VRPTW), where each customer can be served by more than one vehicle. We propose enhancement procedures for the exact branch-and-price-and-cut algorithm that was recently developed for the SDVRPTW. In particular, we introduce a tabu search algorithm to solve the column-generation subproblem, extensions of several classes of valid inequalities, and a new separation algorithm for the k -path inequalities. Computational results show the effectiveness of the proposed enhancements.

Keywords: vehicle routing; time windows; split deliveries; branch and price; valid inequalities; tabu search column generator (search for similar items in EconPapers)
Date: 2011
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (32)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.1100.0363 (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:ortrsc:v:45:y:2011:i:3:p:285-298

Access Statistics for this article

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