IDEAS home Printed from https://ideas.repec.org/a/inm/ortrsc/v30y1996i3p220-236.html
   My bibliography  Save this article

A Relaxation-Based Pruning Technique for a Class of Stochastic Shortest Path Problems

Author

Listed:
  • Ishwar Murthy

    (Department of Information Systems and Decision Sciences, Louisiana State University, Baton Rouge, Louisiana 70803)

  • Sumit Sarkar

    (Department of Information Systems and Decision Sciences, Louisiana State University, Baton Rouge, Louisiana 70803)

Abstract

In this paper a form of the stochastic shortest path problem is considered where the optimal path is one that maximizes the expected utility which is concave and quadratic. The principal contribution of this paper is the development of a relaxation based pruning technique which is incorporated into a label setting procedure. The basic label setting procedure solves the problem by generating all Pareto-optimal paths. However, the number of such paths can grow exponentially with the size of the problem. The relaxation based pruning technique developed here is able to recognize and discard most of the Pareto-optimal paths that do not contribute to the optimal path. Our computational results show that the label setting procedure that incorporates the pruning technique consistently outperforms the basic label setting procedure, and is able to solve large problems very quickly.

Suggested Citation

  • Ishwar Murthy & Sumit Sarkar, 1996. "A Relaxation-Based Pruning Technique for a Class of Stochastic Shortest Path Problems," Transportation Science, INFORMS, vol. 30(3), pages 220-236, August.
    • Handle: RePEc:inm:ortrsc:v:30:y:1996:i:3:p:220-236
    DOI: 10.1287/trsc.30.3.220
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/trsc.30.3.220
    Download Restriction: no
    File URL: https://libkey.io/10.1287/trsc.30.3.220?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. Fu, Liping, 2001. "An adaptive routing algorithm for in-vehicle route guidance systems with real-time information," Transportation Research Part B: Methodological, Elsevier, vol. 35(8), pages 749-765, September.
    2. Leilei Zhang & Tito Homem-de-Mello, 2017. "An Optimal Path Model for the Risk-Averse Traveler," Transportation Science, INFORMS, vol. 51(2), pages 518-535, May.
    3. Ishwar Murthy & Sumit Sarkar, 1998. "Stochastic Shortest Path Problems with Piecewise-Linear Concave Utility Functions," Management Science, INFORMS, vol. 44(11-Part-2), pages 125-136, November.
    4. 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.
    5. 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.
    6. Huang, He & Gao, Song, 2012. "Optimal paths in dynamic networks with dependent random link travel times," Transportation Research Part B: Methodological, Elsevier, vol. 46(5), pages 579-598.
    7. Fu, Liping & Rilett, L. R., 1998. "Expected shortest paths in dynamic and stochastic traffic networks," Transportation Research Part B: Methodological, Elsevier, vol. 32(7), pages 499-516, September.
    8. Yu Nie & Xing Wu & Tito Homem-de-Mello, 2012. "Optimal Path Problems with Second-Order Stochastic Dominance Constraints," Networks and Spatial Economics, Springer, vol. 12(4), pages 561-587, December.
    9. Shahabi, Mehrdad & Unnikrishnan, Avinash & Boyles, Stephen D., 2013. "An outer approximation algorithm for the robust shortest path problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 58(C), pages 52-66.
    10. Yang, Lixing & Zhang, Yan & Li, Shukai & Gao, Yuan, 2016. "A two-stage stochastic optimization model for the transfer activity choice in metro networks," Transportation Research Part B: Methodological, Elsevier, vol. 83(C), pages 271-297.
    11. Zhang, Yuli & Shen, Zuo-Jun Max & Song, Shiji, 2016. "Parametric search for the bi-attribute concave shortest path problem," Transportation Research Part B: Methodological, Elsevier, vol. 94(C), pages 150-168.
    12. Levering, Nikki & Boon, Marko & Mandjes, Michel & Núñez-Queija, Rudesindo, 2022. "A framework for efficient dynamic routing under stochastically varying conditions," Transportation Research Part B: Methodological, Elsevier, vol. 160(C), pages 97-124.
    13. Nie, Yu (Marco) & Wu, Xing & Dillenburg, John F. & Nelson, Peter C., 2012. "Reliable route guidance: A case study from Chicago," Transportation Research Part A: Policy and Practice, Elsevier, vol. 46(2), pages 403-419.
    14. Murthy, Ishwar & Sarkar, Sumit, 1997. "Exact algorithms for the stochastic shortest path problem with a decreasing deadline utility function," European Journal of Operational Research, Elsevier, vol. 103(1), pages 209-229, November.
    15. Axel Parmentier, 2019. "Algorithms for non-linear and stochastic resource constrained shortest path," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 89(2), pages 281-317, April.

    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:ortrsc:v:30:y:1996:i:3:p:220-236. 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.