Branch and Cut and Price for the Pickup and Delivery Problem with Time Windows

Stefan Ropke () and Jean-François Cordeau ()
Additional contact information
Stefan Ropke: Department of Transport, Technical University of Denmark, 2800 Kgs. Lyngby, Denmark
Jean-François Cordeau: HEC Montréal, 3000, chemin de la Côte-Sainte-Catherine, Montréal H3T 2A7, Canada

Transportation Science, 2009, vol. 43, issue 3, 267-286

Abstract: In the pickup and delivery problem with time windows vehicle routes must be designed to satisfy a set of transportation requests, each involving a pickup and delivery location, under capacity, time window, and precedence constraints. This paper introduces a new branch-and-cut-and-price algorithm in which lower bounds are computed by solving through column generation the linear programming relaxation of a set partitioning formulation. Two pricing subproblems are considered in the column generation algorithm: an elementary and nonelementary shortest path problem. Valid inequalities are added dynamically to strengthen the relaxations. Some of the previously proposed inequalities for the pickup and delivery problem with time windows are also shown to be implied by the set partitioning formulation. Computational experiments indicate that the proposed algorithm outperforms a recent branch-and-cut algorithm.

Keywords: pickup and delivery; column generation; branch and price; branch and cut; valid inequalities (search for similar items in EconPapers)
Date: 2009
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (123)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.1090.0272 (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:43:y:2009:i:3:p:267-286

Access Statistics for this article

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