Optimal reliability path problem on networks with random and correlated link travel times bilevel formulation and solution procedure

This study addressed the most reliable path problem on stochastic networks with correlated link travel times from general multivariate distributions. Both evaluation and optimization of this problem are difficult because of the absence of closed-form distribution at the path level. For tractability in reliability evaluation, the path reliability objective function was substituted by the standard-score objective with the same mean and variance as the given distribution. However, this simplified proxy objective was difficult to optimize because it was nonlinear in path mean and variance. These difficulties were circumvented by reformulating the problem as a bilevel minimization model, in which the master problem corresponded to the proxy reliability objective, and the subproblem corresponded to the solution of a related minimum robust-cost path problem. The subproblem was easier to solve because it minimized a linear combination of path travel time mean and standard deviation. An efficient algorithm was proposed to solve this bilevel model, whose exact and monotonic convergence was established for the proxy objective function. Computational experiments on various test networks demonstrated the robustness of the algorithm under various travel time distributions. The algorithm identified the optimal path in 96% to 99% of the cases with a maximum error of less than 0.5%. The algorithm was also applied with real-world data from an intelligent transportation systems test bed in Chennai, India. The results showed that the most reliable paths varied within the day and from day to day; this result showed potential applications of the algorithm with advanced traveler information systems.