Path finding under uncertainty: Considering both reliability and unreliability of travel time distributions

• Develop a mean-excess shortest path model that considers both reliability and unreliability. • Model both on-time arrival and excess delay of late trips. • Develop an efficient Benders decomposition method scalable to large-scale networks. • Demonstrate the features of mean-excess shortest path model. In transportation networks, travel times are stochastic and often exhibit a skewed distribution with a long right tail, which can lead to significant delays. In this paper, we present an α -reliable mean-excess shortest path model, where mean-excess travel time is interpreted as the conditional value-at-risk (CVaR) of the travel time distribution, for identifying optimal paths in stochastic networks. This model addresses both the reliability aspect–minimizing the travel time budget that ensures a certain level of on-time arrival–and the unreliability aspect–managing potential worst-case travel times beyond that budget. Formulated as a mixed-integer nonlinear programming (MINLP) problem with complex coupling of random link travel time distributions, the model is reformulated into a mixed-integer linear programming (MILP) problem based on link travel time samples for tractability. We develop a tailored Benders Decomposition (BD) method, which selectively uses worst-case samples to generate optimality cuts, reducing the computational burden caused by large sample sizes. An accelerated variant, BD with multiple cuts, further improves convergence. Numerical experiments on small, medium, and large-scale networks demonstrate the path-finding model’s effectiveness, the solution procedure’s efficiency, and its scalability for real-world applications like in-vehicle route guidance systems.