Finding most reliable paths on networks with correlated and shifted log-normal travel times

There is a growing interest in modeling travel time uncertainty in transportation networks in addition to optimizing the reliability of travel times at the path and network level. This paper focuses on the analysis and optimization of travel time (including stopped delays) Reliability on the Urban Road Network in Chennai. Specifically, two objectives are investigated. The first objective involves the quantification of travel time reliability at the link and path level. In particular, the distribution of link travel times is quantified for the Chennai Urban road network using empirical data. The results indicate that the shifted log-normal distribution (SLN) reasonably represents link travel time for all facility types and relevant facility wise distribution parameters are estimated. Further, the resulting path travel time distribution is approximated by a SLN distribution, which is computationally less expensive than traditional Monte-Carlo estimation techniques with an acceptable compromise on accuracy. The second objective addresses the optimal reliability path problem on a network with SLN link travel times with general correlation structure. For this problem, it is shown that the sub-path optimality property of shortest path problems does not hold making traditional label-setting/label correcting algorithms inapplicable. Consequently, a sufficient optimality condition based on reliability bounds is established and a new network optimization algorithm is proposed and proof of correctness is presented. The convergence rate of the algorithm was shown to increase at every iteration under some mild conditions. The computational performance of the proposed algorithm is investigated using synthetic and real-world networks and found to be reasonably accurate. © 2013 Elsevier Ltd.