State space partitioning methods for stochastic shortest path problems

This paper describes methods for computing measures related to shortest paths in networks with discrete random arc lengths. These measures include the probability that there exists a path with length not exceeding a specified value and the probability that a given path is shortest. The proposed methods are based on an iterative partition of the network state space and provide bounds that improve after each iteration and eventually become equal to the respective measure. These bounds can also be used for constructing simple variance reducing Monte Carlo sampling plans, making the proposed algorithms useful for large problems where exact evaluations are virtually impossible. The algorithms can be easily modified to compute performance characteristics in stochastic activity networks. Computational experience has been encouraging as we have been able to solve networks that have presented difficulties to existing methods.