EconPapers    
Economics at your fingertips  
 

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 ().

 
Page updated 2025-03-19
Handle: RePEc:inm:ortrsc:v:45:y:2011:i:3:p:285-298