A factoring approach for the stochastic shortest path problem

A factoring approach for the stochastic shortest path problem

0.00 Avg rating0 Votes
Article ID: iaor1992664
Country: Netherlands
Volume: 10
Issue: 6
Start Page Number: 329
End Page Number: 334
Publication Date: Aug 1991
Journal: Operations Research Letters
Authors: ,
Abstract:

This paper studies the problem of determining the exact distribution of shortest path length in directed stochastic networks. The present approach is based on the concept of structural factoring, in which a stochastic network is decomposed into an equivalent set of smaller, generally less complex subnetworks. Several network constructs are identified and exploited to reduce significantly the computational effort required to solve a problem relative to complete enumeration. This algorithm can be applied to two important classes of stochastic network problems: determining the critical path length distribution for acyclic networks and the two-terminal reliability for probabilistic networks. Computational experience with the algorithm has been encouraging and has allowed the exact solution of networks analyzed only by approximation techniques.

Reviews

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