Bidirectional Labeling in Column-Generation Algorithms for Pickup-and-Delivery Problems

Timo Gschwind (), Stefan Irnich (), Ann-Kathrin Rothenbächer () and Christian Tilk ()
Additional contact information
Timo Gschwind: Johannes Gutenberg-University Mainz, Germany
Stefan Irnich: Johannes Gutenberg-University Mainz, Germany
Ann-Kathrin Rothenbächer: Johannes Gutenberg-University Mainz, Germany
Christian Tilk: Johannes Gutenberg-University Mainz, Germany

No 1710, Working Papers from Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz

Abstract: For the exact solution of many types of vehicle-routing problems, column-generation based algorithms have become predominant. The column-generation subproblems are then variants of the shortest-path problem with resource constraints which can be solved well with dynamic-programming labeling algorithms. For vehicle-routing problems with a pickup-and-delivery structure, the strongest known dominance between two labels requires the delivery triangle inequality (DTI) for reduced costs to hold. When the direction of labeling is altered from forward labeling to backward labeling, the DTI requirement becomes the pickup triangle inequality (PTI). DTI and PTI cannot be guaranteed at the same time. The consequence seemed to be that bidirectional labeling, one of the most successful acceleration techniques developed over the last years, is not applicable with a strong dominance in both directions for problems with a pickup-and-delivery structure. Surely, relying on a weak dominance in one direction is feasible but makes the bidirectional approach less powerful. In this paper, we show that bidirectional labeling with the strongest dominance rules in forward as well as backward direction is possible and computationally bene?cial. A full-?edged branch-cut-and-price algorithm is tested on the pickup-and-delivery problem with time windows (PDPTW).

Keywords: vehicle routing; pickup-and-delivery; shortest-path problem with resource constraints; bidirectional labeling; column generation (search for similar items in EconPapers)
Pages: 14 pages
Date: 2017-05-24
New Economics Papers: this item is included in nep-cmp
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://download.uni-mainz.de/RePEc/pdf/Discussion_Paper_1710.pdf First version, 2017 (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:jgu:wpaper:1710

Access Statistics for this paper

More papers in Working Papers from Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz Contact information at EDIRC.
Bibliographic data for series maintained by Research Unit IPP ().