You are here: Home News Publication in "Operations …

Publication in "Operations Research"

27 August 2020

Our study "The Constrained Reliable Shortest Path Problem in Stochastic Time-Dependent Networks" has been accepted for publication in the journal "Operations Research" (VHB-JOURQUAL: A+) .

Authors: Matthias Ruß, Gunther Gust, Dirk Neumann

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 timedependent 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 FIFO. We introduce a weak form of this condition to extend applicability to networks with scheduled connections, e. g., public transport. To solve the CRSP-STD, we define essential paths, a subset of optimal paths. Essential paths have two main properties: firstly, they cover all non-dominated combinations of worst-case weights that occur in the set of optimal paths, secondly, their subpaths are non-dominated, which can be used for pruning. Multiple properties of essential paths are exploited in our exact solution method, which extends multi-objective 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.