The Stochastic Shortest Route Problem

C. Elliott Sigal, A. Alan B. Pritsker and James J. Solberg
Additional contact information
C. Elliott Sigal: Purdue University, West Lafayette, Indiana
A. Alan B. Pritsker: Purdue University, West Lafayette, Indiana
James J. Solberg: Purdue University, West Lafayette, Indiana

Operations Research, 1980, vol. 28, issue 5, 1122-1129

Abstract: The problem addressed in this paper is the selection of the shortest path through a directed, acyclic network where the arc lengths are independent random variables. This problem has received little attention although the deterministic version of the problem has been studied extensively. The concept of a path optimality index is introduced as a performance measure for selecting a path of a stochastic network. A path optimality index is defined as the probability a given path is shorter than all other network paths. This paper presents an analytic derivation of path optimality indices for directed, acyclic networks. A new network concept, Uniformly Directed Cutsets (UDCs), is introduced. UDCs are shown to be important to the efficient implementation of the prescribed analytic procedure. There are strong indications that stochastic shortest route analysis has numerous applications in operations research and management science. Potential application areas include, equipment replacement analysis, reliability modeling, maximal flow problems, stochastic dynamic programming problems, and PERT-type network analysis.

Date: 1980
References: Add references at CitEc
Citations: View citations in EconPapers (12)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.28.5.1122 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:28:y:1980:i:5:p:1122-1129

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().