Most reliable path-finding algorithm for maximizing on-time arrival probability

Abstract

Finding the most reliable path that maximizes the probability of on-time arrival is commonly encountered by travelers facing travel time uncertainties. However, few exact solution algorithms have been proposed in the literature to efficiently determine the most reliable path in large-scale road networks. In this study, a two-stage solution algorithm is proposed to exactly solve the most reliable path problem. In the first stage, the upper and lower bounds of on-time arrival probability are estimated. Dominance conditions and the monotonic property of the most reliable path problem are then established. In the second stage, the multi-criteria label-setting approach is utilized to efficiently determine the most reliable path. To illustrate the applicability of the proposed solution algorithm, a comprehensive case study is carried out using a real road network with stochastic travel times. The results of case study show that the proposed solution algorithm has a remarkable computational advantage over the existing multi-criteria label-correcting algorithm.