Impacts of correlations on reliable shortest path finding

Ali Zockaie*, Yu Nie, Xing Wu, Hani Mahmassani

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

35 Scopus citations


This paper examines how correlations in link travel times affect reliable path finding in a stochastic network. The reliable path is defined as the path that requires the lowest travel time budget to ensure a given probability of on-time arrival. Such a path can be found by solving the shortest path problem considering on-time arrival reliability (SPOTAR). SPOTAR is solved approximately by using an approach based on Monte Carlo simulation. A major advantage of the simulation-based algorithm is its ability to deal with correlated link travel times. Through the use of a real-world network, the simulation-based algorithm is first validated by comparing it with a label-correcting algorithm that can solve the uncorrelated case exactly; the impacts of the correlations on link travel times are then examined. The results of the numerical experiments indicate that correlations affect the optimal SPOTAR solutions significantly. However, larger correlations do not always lead to larger errors in the reliable route choices that ignore them.

Original languageEnglish (US)
Pages (from-to)1-9
Number of pages9
JournalTransportation Research Record
Issue number2334
StatePublished - Dec 1 2013

ASJC Scopus subject areas

  • Civil and Structural Engineering
  • Mechanical Engineering


Dive into the research topics of 'Impacts of correlations on reliable shortest path finding'. Together they form a unique fingerprint.

Cite this