Hostname: page-component-78c5997874-4rdpn Total loading time: 0 Render date: 2024-11-18T02:22:44.975Z Has data issue: false hasContentIssue false
  • English
  • Français

Approximating the Stochastic Network by its M Shortest Paths

Published online by Cambridge University Press:  27 July 2009

Bajis Dodin
Bajis Dodin
Affiliation:
Graduate School of ManagementUniversity of California Riverside, California 92521
Get access Rights & Permissions [Opens in a new window]

Abstract

Given a stochastic activity network in which the length of some or all of the arcs are random variables with known probability distributions. This paper concentrates on identifying the shortest path and the M shortest paths in the network and on using the M paths to identify surrogate stochastic networks which are amenable for deriving analytical solutions. First, it identifies the M shortest paths using a certain form of stochastic dominance. Second, it identifies the M shortest paths by applying the deterministic methods to the network resulting from replacing the random length of every arc by its mean value. The two sets of the M paths are compared with those obtained by Monte Carlo sampling. Finally, the paper investigates how the distributional properties of the shortest path in the surrogate network compare with those of the shortest path in the original stochastic network.

Type
Articles
Information
Probability in the Engineering and Informational Sciences , Volume 3 , Issue 3 , July 1989 , pp. 435 - 451
Copyright
Copyright © Cambridge University Press 1989

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Deo, N. & Pang, C. (1984). Shortest-path algorithms: taxonomy and annotation. Networks 14: 275–323.CrossRefGoogle Scholar
Dodin, B. (1984). Determining the K most critical paths in PERT networks. Operations Research 32(4): 859–877.CrossRefGoogle Scholar
Eiger, A., Mirchandani, P.B., & Soroush, H. (1985). Path preferences and optimal paths in probabilistic networks. Transportation Science 19(1): 75–84.CrossRefGoogle Scholar
Fishman, G.S. (1985). Estimating critical path and arc probabilities in stochastic activity networks. Naval Research Logistics Quarterly 32: 249–261.CrossRefGoogle Scholar
Frank, H. (1969). Shortest paths in probabilistic graphs. Operations Research 17: 583–599.CrossRefGoogle Scholar
Golden, B.L. & Magnanti, T.L. (1977). Deterministic network optimization: a bibliography. Networks 7: 149–183.CrossRefGoogle Scholar
Kulkarni, V.G. (1986). Shortest paths in networks with exponentially distributed arc lengths. Networks 16: 255–274.CrossRefGoogle Scholar
Lawler, E.L. (1976). Combinatorial optimization: networks and materials. New York: Holt, Rinehart and Winston.Google Scholar
Miller, A.C. & Rice, T.R. (1983). Discrete approximations of probability distributions. Management Science 29 (3): 352–363.CrossRefGoogle Scholar
Mirchandani, P.B. (1976). Shortest distance and reliability of probability networks. Computers and Operations Research 3: 347–355.CrossRefGoogle Scholar
Pierce, A.R. (1975) Bibliography on algorithms for shortest path, shortest spanning tree, and related circuit routing problems (1956–1974). Networks 5: 129–149.CrossRefGoogle Scholar
Sigal, C.E., Pritsker, A.A.B., & Solberg, J.J. (1980). The stochastic shortest-path problem. Operations Research 28: 1122–1129.CrossRefGoogle Scholar
Yen, J.Y. (1971). Finding the K shortest loopless paths in a network. Management Science 17(11): 712–716.CrossRefGoogle Scholar