Bidirectional labeling in column-generation algorithms for pickup-and-delivery problems

Timo Gschwind, Stefan Irnich, Ann-Kathrin Rothenbächer and Christian Tilk

European Journal of Operational Research, 2018, vol. 266, issue 2, 521-530

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 the strong dominance on both directions for problems with a pickup-and-delivery structure. In this paper, we show that bidirectional labeling with the strong dominance rules in forward as well as backward direction is possible by using different cost matrices in the two directions. We adopt the both-sided strong bidirectional labeling approach to integrate the standard robust and non-robust cuts. Moreover, a recent acceleration technique that dynamically adjusts the bidirectional half-way point is implemented. Full-fledged branch-cut-and-price algorithms are tested on the pickup-and-delivery problem with time windows (PDPTW). In particular, an in-depth analysis of different mono- and bidirectional labeling algorithms is presented. Overall, compared to the standard pure forward labeling-based algorithm, we obtain average reductions in computation time of more than 40 percent when solving PDPTW instances exactly.

Keywords: Routing; Pickup-and-delivery; Shortest-path problem with resource constraints; Bidirectional labeling; Column generation (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (12)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221717308780
Full text for ScienceDirect subscribers only

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:eee:ejores:v:266:y:2018:i:2:p:521-530

DOI: 10.1016/j.ejor.2017.09.035

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().