Application of Lagrangian relaxation approach to alpha-reliable path finding in stochastic networks with correlated link travel times

作者：Zeng Weiliang^*; Miwa Tomio; Wakita Yukiko; Morikawa Takayuki

来源：Transportation Research Part C: Emerging Technologies , 2015, 56: 309-334.

DOI：10.1016/j.trc.2015.04.018

• Reliable path
• Lagrangian relaxation
• Cholesky decomposition
• Stochastic network
• Correlated link travel time
• Navigation system

This study investigates the important problem of determining a reliable path in a stochastic network with correlated link travel times. First, the distribution of path travel time is quantified by using trip records from GPS probe vehicles. Second, the spatial correlation of link travel time is explicitly considered by using a correlation coefficient matrix, which is incorporated into the alpha-reliable path problem by Cholesky decomposition. Third, the Lagrangian relaxation based framework is used to handle the alpha-reliable path problem, by which the intractable problem with a non-linear and non-additive structure can be decomposed into several easy-to-solve problems. Finally, the path-finding performance of this approach is tested on a real-world network. The results show that 15 iterations of calculation can yield a small relative gap between upper and lower bounds of the optimal solution and the average running time is about 5 s for most OD settings. The applicability of alpha-reliable path finding is validated by a case study.

• 出版日期2015-7