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

Publication: Research - peer-reviewJournal article – Annual report year: 2009

Documents

DOI

View graph of relations

In the pickup and delivery problem with time windows (PDPTW), vehicle routes must be designed to satisfy a set of transportation requests, each involving a pickup and a 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 a non-elementary shortest path problem. Valid inequalities are added dynamically to strengthen the relaxations. Some of the previously proposed inequalities for the PDPTW 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.
Original languageEnglish
JournalTransportation Science
Publication date2009
Volume43
Issue3
Pages267-286
ISSN0041-1655
DOIs
StatePublished
CitationsWeb of Science® Times Cited: 28

Keywords

  • pickup and delivery, column generation, branch-and-cut, branch-and-price, valid inequalities
Download as:
Download as PDF
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
PDF
Download as HTML
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
HTML
Download as Word
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
Word

Download statistics

No data available

ID: 4128530