State space partitioning methods for stochastic shortest path problems

State space partitioning methods for stochastic shortest path problems

0.00 Avg rating0 Votes
Article ID: iaor20021966
Country: United States
Volume: 30
Issue: 1
Start Page Number: 9
End Page Number: 21
Publication Date: Aug 1997
Journal: Networks
Authors:
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.