IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v28y1980i5p1122-1129.html
   My bibliography  Save this article

The Stochastic Shortest Route Problem

Author

Listed:
  • 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)

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.

Suggested Citation

  • C. Elliott Sigal & A. Alan B. Pritsker & James J. Solberg, 1980. "The Stochastic Shortest Route Problem," Operations Research, INFORMS, vol. 28(5), pages 1122-1129, October.
    • Handle: RePEc:inm:oropre:v:28:y:1980:i:5:p:1122-1129
    DOI: 10.1287/opre.28.5.1122
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.28.5.1122
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.28.5.1122?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Lee, Jisun & Joung, Seulgi & Lee, Kyungsik, 2022. "A fully polynomial time approximation scheme for the probability maximizing shortest path problem," European Journal of Operational Research, Elsevier, vol. 300(1), pages 35-45.
    2. Athanassios N. Avramidis & James R. Wilson, 1998. "Correlation-Induction Techniques for Estimating Quantiles in Simulation Experiments," Operations Research, INFORMS, vol. 46(4), pages 574-591, August.
    3. Elise D. Miller-Hooks & Hani S. Mahmassani, 2000. "Least Expected Time Paths in Stochastic, Time-Varying Transportation Networks," Transportation Science, INFORMS, vol. 34(2), pages 198-215, May.
    4. Marie Schmidt & Leo Kroon & Anita Schöbel & Paul Bouman, 2017. "The Travelers Route Choice Problem Under Uncertainty: Dominance Relations Between Strategies," Operations Research, INFORMS, vol. 65(1), pages 184-199, February.
    5. Daniel Reich & Leo Lopes, 2011. "Preprocessing Stochastic Shortest-Path Problems with Application to PERT Activity Networks," INFORMS Journal on Computing, INFORMS, vol. 23(3), pages 460-469, August.
    6. Yanyan Wang & Vicki M. Bier & Baiqing Sun, 2019. "Measuring and Achieving Equity in Multiperiod Emergency Material Allocation," Risk Analysis, John Wiley & Sons, vol. 39(11), pages 2408-2426, November.
    7. Nie, Yu (Marco) & Wu, Xing, 2009. "Shortest path problem considering on-time arrival probability," Transportation Research Part B: Methodological, Elsevier, vol. 43(6), pages 597-613, July.
    8. Elías Escobar-Gómez & J.L. Camas-Anzueto & Sabino Velázquez-Trujillo & Héctor Hernández-de-León & Rubén Grajales-Coutiño & Eduardo Chandomí-Castellanos & Héctor Guerra-Crespo, 2019. "A Linear Programming Model with Fuzzy Arc for Route Optimization in the Urban Road Network," Sustainability, MDPI, vol. 11(23), pages 1-18, November.
    9. David Corredor-Montenegro & Nicolás Cabrera & Raha Akhavan-Tabatabaei & Andrés L. Medaglia, 2021. "On the shortest $$\alpha$$ α -reliable path problem," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 29(1), pages 287-318, April.
    10. Zhouchun Huang & Qipeng P. Zheng & Eduardo L. Pasiliao & Daniel Simmons, 2017. "Exact algorithms on reliable routing problems under uncertain topology using aggregation techniques for exponentially many scenarios," Annals of Operations Research, Springer, vol. 249(1), pages 141-162, February.
    11. Marie Schmidt & Leo Kroon & Anita Schöbel & Paul Bouman, 2017. "The Travelers Route Choice Problem Under Uncertainty: Dominance Relations Between Strategies," Operations Research, INFORMS, vol. 65(1), pages 184-199, February.
    12. Jian Li & Amol Deshpande, 2019. "Maximizing Expected Utility for Stochastic Combinatorial Optimization Problems," Mathematics of Operations Research, INFORMS, vol. 44(1), pages 354-375, February.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:oropre:v:28:y:1980:i:5:p:1122-1129. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.