IDEAS home Printed from https://ideas.repec.org/a/spr/eurjtl/v6y2017i2d10.1007_s13676-015-0092-6.html
   My bibliography  Save this article

Shortest path problem with arc failure scenarios

Author

Listed:
  • Preethi Issac

    (The University of Iowa)

  • Ann Melissa Campbell

    (The University of Iowa)

Abstract

We consider a shortest path problem from source to destination over a set of arc failure scenarios, considering the probability of different scenarios. A primary path is chosen, which is the first path a driver will take, along with a set of alternative paths to use when an impassible road is encountered. These paths should minimize the expected cost to reach the destination and be useful in natural disaster applications. Our paper includes a formal problem description and integer programming model for this new problem. We also provide an exact algorithm based on the modified label-correcting algorithm but with extended labels that preserve information about the scenarios. We describe dominance rules and how to use a version of the A-star algorithm to generate an initial bound. We conduct computational experiments with real road data sets with varying number of scenarios and disaster intensities. These experiments show the value of the dominance rules and initial bounds, as well as the structure of the chosen paths.

Suggested Citation

  • Preethi Issac & Ann Melissa Campbell, 2017. "Shortest path problem with arc failure scenarios," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 6(2), pages 139-163, June.
    • Handle: RePEc:spr:eurjtl:v:6:y:2017:i:2:d:10.1007_s13676-015-0092-6
    DOI: 10.1007/s13676-015-0092-6
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s13676-015-0092-6
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s13676-015-0092-6?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. F. Benjamin Zhan & Charles E. Noon, 1998. "Shortest Path Algorithms: An Evaluation Using Real Road Networks," Transportation Science, INFORMS, vol. 32(1), pages 65-73, February.
    2. Lodree, Emmett J. & Ballard, Kandace N. & Song, Chang H., 2012. "Pre-positioning hurricane supplies in a commercial supply chain," Socio-Economic Planning Sciences, Elsevier, vol. 46(4), pages 291-305.
    3. Campbell, Ann Melissa & Jones, Philip C., 2011. "Prepositioning supplies in preparation for disasters," European Journal of Operational Research, Elsevier, vol. 209(2), pages 156-165, March.
    4. H. Frank, 1969. "Shortest Paths in Probabilistic Graphs," Operations Research, INFORMS, vol. 17(4), pages 583-599, August.
    5. Akgun, Vedat & Erkut, Erhan & Batta, Rajan, 2000. "On finding dissimilar paths," European Journal of Operational Research, Elsevier, vol. 121(2), pages 232-246, March.
    6. Jotshi, Arun & Gong, Qiang & Batta, Rajan, 2009. "Dispatching and routing of emergency vehicles in disaster mitigation using data fusion," Socio-Economic Planning Sciences, Elsevier, vol. 43(1), pages 1-24, March.
    7. Serhan Duran & Marco A. Gutierrez & Pinar Keskinocak, 2011. "Pre-Positioning of Emergency Items for CARE International," Interfaces, INFORMS, vol. 41(3), pages 223-237, June.
    8. April K. Andreas & J. Cole Smith, 2008. "Mathematical Programming Algorithms for Two-Path Routing Problems with Reliability Considerations," INFORMS Journal on Computing, INFORMS, vol. 20(4), pages 553-564, November.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. A. Anaya-Arenas & J. Renaud & A. Ruiz, 2014. "Relief distribution networks: a systematic review," Annals of Operations Research, Springer, vol. 223(1), pages 53-79, December.
    2. Jingxian Chen & Liang Liang & Dong-Qing Yao, 2017. "Pre-positioning of relief inventories for non-profit organizations: a newsvendor approach," Annals of Operations Research, Springer, vol. 259(1), pages 35-63, December.
    3. Kılcı, Fırat & Kara, Bahar Yetiş & Bozkaya, Burçin, 2015. "Locating temporary shelter areas after an earthquake: A case for Turkey," European Journal of Operational Research, Elsevier, vol. 243(1), pages 323-332.
    4. Alem, Douglas & Clark, Alistair & Moreno, Alfredo, 2016. "Stochastic network models for logistics planning in disaster relief," European Journal of Operational Research, Elsevier, vol. 255(1), pages 187-206.
    5. Aurelie Charles & Matthieu Lauras & Luk N. van Wassenhove & Lionel Dupont, 2016. "Designing an efficient humanitarian supply network," Post-Print hal-01532132, HAL.
    6. Paul, Jomon A. & Zhang, Minjiao, 2019. "Supply location and transportation planning for hurricanes: A two-stage stochastic programming framework," European Journal of Operational Research, Elsevier, vol. 274(1), pages 108-125.
    7. Jean-Claude Baraka Munyaka & Venkata Seshachala Sarma Yadavalli, 2021. "Using transportation problem in humanitarian supply chain to prepositioned facility locations: a case study in the Democratic Republic of the Congo," International Journal of System Assurance Engineering and Management, Springer;The Society for Reliability, Engineering Quality and Operations Management (SREQOM),India, and Division of Operation and Maintenance, Lulea University of Technology, Sweden, vol. 12(1), pages 199-216, February.
    8. Sabbaghtorkan, Monir & Batta, Rajan & He, Qing, 2020. "Prepositioning of assets and supplies in disaster operations management: Review and research gap identification," European Journal of Operational Research, Elsevier, vol. 284(1), pages 1-19.
    9. Akgün, İbrahim & Gümüşbuğa, Ferhat & Tansel, Barbaros, 2015. "Risk based facility location by using fault tree analysis in disaster management," Omega, Elsevier, vol. 52(C), pages 168-179.
    10. Meng, Qingchun & Kao, Zhiping & Guo, Ying & Bao, Chunbing, 2023. "An emergency supplies procurement strategy based on a bidirectional option contract," Socio-Economic Planning Sciences, Elsevier, vol. 87(PA).
    11. Dönmez, Zehranaz & Kara, Bahar Y. & Karsu, Özlem & Saldanha-da-Gama, Francisco, 2021. "Humanitarian facility location under uncertainty: Critical review and future prospects," Omega, Elsevier, vol. 102(C).
    12. Mohsen Alawi & Dongzhu Chu & Seba Hammad, 2023. "Resilience of Public Open Spaces to Earthquakes: A Case Study of Chongqing, China," Sustainability, MDPI, vol. 15(2), pages 1-20, January.
    13. Abazari, Seyed Reza & Aghsami, Amir & Rabbani, Masoud, 2021. "Prepositioning and distributing relief items in humanitarian logistics with uncertain parameters," Socio-Economic Planning Sciences, Elsevier, vol. 74(C).
    14. Renata Turkeš & Kenneth Sörensen & Daniel Palhazi Cuervo, 2021. "A matheuristic for the stochastic facility location problem," Journal of Heuristics, Springer, vol. 27(4), pages 649-694, August.
    15. Patra, T. Devi Prasad & Jha, J.K., 2021. "A two-period newsvendor model for prepositioning with a post-disaster replenishment using Bayesian demand update," Socio-Economic Planning Sciences, Elsevier, vol. 78(C).
    16. Acar, Müge & Kaya, Onur, 2023. "Dynamic inventory decisions for humanitarian aid materials considering budget limitations," Socio-Economic Planning Sciences, Elsevier, vol. 86(C).
    17. Wang, Weiqiao & Yang, Kai & Yang, Lixing & Gao, Ziyou, 2021. "Two-stage distributionally robust programming based on worst-case mean-CVaR criterion and application to disaster relief management," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 149(C).
    18. Özdamar, Linet & Ertem, Mustafa Alp, 2015. "Models, solutions and enabling technologies in humanitarian logistics," European Journal of Operational Research, Elsevier, vol. 244(1), pages 55-65.
    19. TURKEŠ, Renata & SÖRENSEN, Kenneth, 2018. "Case studies and random instances for the problem of pre-positioning emergency supplies," Working Papers 2018004, University of Antwerp, Faculty of Business and Economics.
    20. Hasani, Aliakbar & Mokhtari, Hadi, 2018. "Redesign strategies of a comprehensive robust relief network for disaster management," Socio-Economic Planning Sciences, Elsevier, vol. 64(C), pages 92-102.

    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:spr:eurjtl:v:6:y:2017:i:2:d:10.1007_s13676-015-0092-6. 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.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.