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

• Published in: Operations research 2021-05, Vol.69 (3), p.709-726
• Main Authors: Ruß, Matthias, Gust, Gunther, Neumann, Dirk
• Format: Article
• Language: English
• Subjects: Analysis; Constraints; Dependent variables; Exact solutions; multiobjective A search; Networks; networks/graphs: stochastic; programming: multiple criteria; Operations research; Problem solving; Public transportation; Random variables; reliable route planning; resource constraints; Stochastic models; Studies; technology; Time dependence; Traffic congestion; Transportation; transportation: travel: mode/route choice; Travel time
• ISSN: 0030-364X; 1526-5463
• DOI: 10.1287/opre.2020.2089

Finding Shortest Paths That Are Reliable and Satisfy Constraints on Time-Dependent Weights Shortest path problems are used to model and solve a variety of real-world problems. In “The Constrained Reliable Shortest Path Problem in Stochastic Time-Dependent Networks,” Ruß, Gust, and Neumann generalize multiple versions of the well-studied shortest path problem: first, the reliable shortest path problem in which travel time is minimized while guaranteeing a certain on-time arrival probability; second, the time-dependent shortest path problem in which edge weights depend on the time at which an edge is used; and third, the constrained shortest path problem in which constraints on additional edge weights need to be satisfied. This generalized problem naturally appears in transportation networks, in which travel times are notoriously uncertain and costs become more and more time dependent. Examples of such time-dependent costs include peak and off-peak fares in public transport, time-dependent congestion charges, and dynamic pricing for shared vehicles. 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 perf