Using stochastic-dominance relationships for bounding travel times in stochastic networks

We consider stochastic networks in which link travel times are dependent, discrete random variables. We present methods for computing bounds on path travel times using stochastic dominance relationships among link travel times, and discuss techniques for controlling tightness of the bounds. We apply these methods to shortest-path problems, show that the proposed algorithm can provide bounds on the recommended path, and elaborate on extensions of the algorithm for demonstrating the anytime property