The Constrained Reliable Shortest Path Problem in Stochastic Time-Dependent Networks

Matthias Ruß (), Gunther Gust () and Dirk Neumann ()
Additional contact information
Matthias Ruß: Chair for Information Systems Research, University of Freiburg, 79098 Freiburg im Breisgau, Germany
Gunther Gust: Chair for Information Systems Research, University of Freiburg, 79098 Freiburg im Breisgau, Germany
Dirk Neumann: Chair for Information Systems Research, University of Freiburg, 79098 Freiburg im Breisgau, Germany

Operations Research, 2021, vol. 69, issue 3, 709-726

Abstract: The constrained reliable shortest path problem in stochastic time-dependent networks (CRSP-STD) extends the reliable, the time-dependent, and the constrained shortest path problem. In the CRSP-STD, shortest paths need to ensure on-time arrival with a given probability and additionally satisfy constraints on time-dependent weights. Examples of such time-dependent weights in transport networks include time-varying congestion charges or dynamic fees for shared vehicles. If weights decrease over time, waiting at nodes can be beneficial and is, therefore, allowed in our problem formulation. Travel times are modeled as time-dependent random variables and assumed to satisfy stochastic first in, first out (FIFO). We introduce a weak form of this condition to extend applicability to networks with scheduled connections, for example, public transport. To solve the CRSP-STD, we define essential paths, a subset of optimal paths. Essential paths have two main properties: first, they cover all nondominated combinations of worst-case weights that occur in the set of optimal paths, and second, their subpaths are nondominated, which can be used for pruning. Multiple properties of essential paths are exploited in our exact solution method, which extends multiobjective A* search. Runtime complexity is analyzed in theory and in numerical experiments, which show that key elements of our solution method effectively improve runtime performance.

Keywords: networks/graphs: stochastic; programming: multiple criteria, technology, transportation: travel: mode/route choice, Transportation, reliable route planning, resource constraints, multiobjective A* search (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2020.2089 (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:oropre:v:69:y:2021:i:3:p:709-726

Access Statistics for this article

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