An Exact Method for Reliable Shortest Path Problems With Correlation

Abstract

ABSTRACT Shortest path problems often arise in contexts where travel times are uncertain. In these settings, reliable paths are often valued more than paths with lower expected travel times. This has led to several variants of reliable shortest path problems (RSPP) that handle travel time reliability differently. We propose an algorithmic framework for solving RSPPs with non‐negatively correlated travel times and resource constraints. By building upon the flexibility of the pulse algorithm, our unified and exact algorithmic framework solves multiple variants of the RSPP: the ‐reliable shortest path (‐RSP), the maximum probability of on‐time arrival (MPOAP) problem, and the shortest ‐reliable path (S‐). We derive a bound on the reliability of path travel times and incorporate three pruning strategies: bounds, infeasibility, and dominance, leveraging properties of the normal distribution and non‐negative correlation structures. Computational experiments on large‐scale transportation networks (with up to 33 113 nodes and 75 379 arcs) demonstrate that the framework achieves a ten‐fold speed improvement over state‐of‐the‐art methods, highlighting its potential real‐world applications and extensions to related problems.