Pruning Algorithms to Determine Reliable Paths on Networks with Random and Correlated Link Travel Times

Abstract

This study addresses various formulations of the optimal reliability path problem on stochastic networks. Robust-Cost is adopted as the measure of reliability, which is defined as a weighted combination of the mean and standard deviation of travel time. The principal problem solved is the Minimum Robust-Cost Path (MRCP) problem in the presence of Correlated link travel times. It is shown that the subpath optimality and subpath non-dominance principles, which are conventionally adopted in the literature, cannot be used to solve this problem. In this light, this study proposes an algorithm based on the subpath pruning approach, which eliminates nonoptimal subpaths by using a pruning criterion. We construct the novel pruning criterion, which depends on only two independent objectives, by transforming the network and using efficient shortest path algorithms. The correctness of the algorithm is established, and its good practical performance is demonstrated on real-world networks. Furthermore, the pruning procedure is generalized with suitable modifications to solve three related problems: (i) the MRCP problem with independent link travel times, (ii) the K-best Robust-Cost Paths problem, and (iii) the MRCP problem with stochastic nondominance constraints. These extensions demonstrate the potential wider applications of the proposed solution approach.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 18 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.