Asymmetry Helps: Dynamic Half-Way Points for Solving Shortest Path Problems with Resource Constraints Faster

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

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

Abstract: With their paper “Symmetry helps: Bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints” [Discrete Optimization 3, 2006, pp. 255–273] Righini and Salani introduced bounded bidirectional dynamic programming (DP) as an acceleration technique for solving variants of the shortest path problem with resource constraints (SPPRC). SPPRCs must be solved iteratively when vehicle routing and scheduling problems are tackled via Lagrangian relaxation or column-generation techniques. Righini and Salani and several subsequent works have shown that bounded bidirectional DP algorithms are often superior to their monodirectional counterparts, since the former can mitigate the effect that the number of labels increases strongly with the path length. Bidirectional DP has become a quasi-standard for solving SPPRCs. In computational experiments, however, one can still observe that the number of forward and backward label extensions is very unbalanced despite a symmetric bounding of a critical resource in the middle of its feasible domain. We exploit this asymmetry in forward and backward label extensions and introduce a so-called dynamic half-way point, which is a dynamic bounding criterion based on the current state of the simultaneously solved forward and backward DPs. Experiments with the standard and the electric vehicle routing problem with time windows as well as the vehicle routing and truck driver scheduling problem con?rm that dynamic half-way points better balance forward and backward workload.

Keywords: Shortest path problem with resource constraints (SPPRC); bidirectional labeling algorithms (search for similar items in EconPapers)
New Economics Papers: this item is included in nep-cmp
Date: 2016-08-04
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1) Track citations by RSS feed

Downloads: (external link)
https://download.uni-mainz.de/RePEc/pdf/Discussion_Paper_1615.pdf First version, 2016 (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:1615

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