Premium
State space partitioning methods for stochastic shortest path problems
Author(s) -
Alexopoulos Christos
Publication year - 1997
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/(sici)1097-0037(199708)30:1<9::aid-net2>3.0.co;2-h
Subject(s) - shortest path problem , computer science , partition (number theory) , mathematical optimization , state space , monte carlo method , path (computing) , constrained shortest path first , k shortest path routing , measure (data warehouse) , algorithm , mathematics , theoretical computer science , graph , data mining , combinatorics , statistics , programming language
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. © 1997 John Wiley & Sons, Inc. Networks 30:9–21, 1997