Finding Reliable Shortest Path in Stochastic Time-dependent Network

AbstractThis paper addresses the problem of finding reliable a priori shortest path to maximize the probability of arriving on time in a stochastic and time-dependent network. Optimal solutions to the problem can be obtained from finding non-dominated paths, which are defined based on first-order stochastic dominance. We formulate the problem of finding non-dominated paths as a general dynamic programming problem because Bellman's principle of optimality can be applied to construct non-dominated paths. A label-correcting algorithm is designed to find optimal paths based on the new proporty for which Bellman's Principle holds. Numerical results are provided using a small network