Application of Lagrangian relaxation approach to α-reliable path finding in stochastic networks with correlated link travel times. (July 2015)

• Record Type: Journal Article
• Authors: Zeng, Weiliang; Miwa, Tomio; Wakita, Yukiko; Morikawa, Takayuki
• Is Part Of: Transportation research. Volume 56(2015)
• Page Start: 309
• Page End: 334
• Publication Date: 2015-07
• Subjects: Reliable path -- Lagrangian relaxation -- Cholesky decomposition -- Stochastic network -- Correlated link travel time -- Navigation system; Transportation -- Periodicals; Transportation -- Technological innovations -- Periodicals; 388.011
• DOI: 10.1016/j.trc.2015.04.018
• Languages: English
• ISSNs: 0968-090X

Abstract

Graphical abstract: Highlights: Link and path travel time are respectively fitted by lognormal and normal distribution. Cholesky decomposition is applied to handle the spatial correlation of link travel time. Lagrangian relaxation is used to handle the α -reliable path problem. Applicability of α -reliable path finding is validated by a real-world network. Abstract: 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 α -reliable path problem by Cholesky decomposition. Third, the Lagrangian relaxation based framework is used to handle the α -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 α -reliable path finding is validated by a case study.