Sample-Based Algorithm to Determine Minimum Robust Cost Path with Correlated Link Travel Times

Travel time reliability is an important and desirable property in route and departure time choice, especially for a risk-averse traveler. Thus, optimizing for reliability has seen growing interest in the recent past in transportation and also in the fields of computer science, stochastic optimization, and so forth. The present study addressed reliability optimization under uncertainty, in which travel time distributions were represented with a sample. The weighted mean–standard deviation measure (robust cost) was adopted as a metric of reliability. The minimum robust cost path problem with link travel times following a general correlation structure was addressed. A sampling-based approach, which had been relatively unused, was adopted from the literature to capture and represent spatial correlations. A novel network transformation and pruning procedure was proposed to determine an exact solution to the problem while circumventing the high dimensionality of the formulations in the literature. Computation experiments demonstrated the efficacy of the algorithm on real-world networks. The impact of the sample approximation on finding the true optimal solution of the population was quantified and found to be acceptable.