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

• 成果类型: Article
• 署名作者: Russ, Matthias; Gust, Gunther; Neumann, Dirk
• 署名单位: University of Freiburg
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2020.2089
• 发表日期: 2021
• 页码: 709-726
• 关键词: reliable route planning; resource constraints; multiobjective A* search

摘要

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.