IDEAS home Printed from https://ideas.repec.org/a/spr/snopef/v3y2022i4d10.1007_s43069-022-00168-2.html
   My bibliography  Save this article

Efficient Algorithms for Abstract Flow with Partial Switching

Author

Listed:
  • Durga Prasad Khanal

    (Tribhuvan University)

  • Urmila Pyakurel

    (Tribhuvan University)

  • Tanka Nath Dhamala

    (Tribhuvan University)

  • Stephan Dempe

    (TU Bergakademie Freiberg)

Abstract

The tragic circumstances caused by natural or human-made (unexpected human or technological errors) hazard such as earthquakes, floods, glaciers, fires or industrial explosions causing significant physical damages, loss of lives or destruction of environment as well as economic and social life of people are known as disasters. Planned evacuation is essential to save the maximum number of evacuees in minimum time, which also helps in minimize losses. Due to mass dispatch (movement) of people aftermath of disaster, traffic scenario at the intersection of roads may create the disappointing situation if the vehicles have to wait for hours to cross the intersection. The main reason behind this is the lack of crossing elimination. In this paper, we discuss the partial switching property on an abstract network, in which crossing effect of roads is eliminated to transship optimal flow of evacuees. Due to the switching property, crossing of the flows at the intersections is diverted to non-crossing sides which can be a milestone to smooth the flows during evacuation. We present polynomial time solution procedures to solve abstract maximum static and dynamic flow problems with partial switching of paths. We also introduce the abstract quickest flow and quickest contraflow problems with partial switching and present polynomial time algorithms to solve the problems. For disaster management, maximum, quickest and contraflow problems on partially switched paths play an important role as the flow on a path system without crossing effect is very essential during evacuation process.

Suggested Citation

  • Durga Prasad Khanal & Urmila Pyakurel & Tanka Nath Dhamala & Stephan Dempe, 2022. "Efficient Algorithms for Abstract Flow with Partial Switching," SN Operations Research Forum, Springer, vol. 3(4), pages 1-17, December.
    • Handle: RePEc:spr:snopef:v:3:y:2022:i:4:d:10.1007_s43069-022-00168-2
    DOI: 10.1007/s43069-022-00168-2
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s43069-022-00168-2
    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/s43069-022-00168-2?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. Urmila Pyakurel & Stephan Dempe, 2021. "Universal Maximum Flow with Intermediate Storage for Evacuation Planning," Springer Optimization and Its Applications, in: Ilias S. Kotsireas & Anna Nagurney & Panos M. Pardalos & Arsenios Tsokas (ed.), Dynamics of Disasters, pages 229-241, Springer.
    2. Bretschneider, S. & Kimms, A., 2011. "A basic mathematical model for evacuation problems in urban areas," Transportation Research Part A: Policy and Practice, Elsevier, vol. 45(6), pages 523-539, July.
    3. Urmila Pyakurel & Tanka Nath Dhamala & Stephan Dempe, 2017. "Efficient continuous contraflow algorithms for evacuation planning problems," Annals of Operations Research, Springer, vol. 254(1), pages 335-364, July.
    4. Urmila Pyakurel & Hari Nandan Nath & Tanka Nath Dhamala, 2019. "Partial contraflow with path reversals for evacuation planning," Annals of Operations Research, Springer, vol. 283(1), pages 591-612, December.
    5. Andrew V. Goldberg & Robert E. Tarjan, 1990. "Finding Minimum-Cost Circulations by Successive Approximation," Mathematics of Operations Research, INFORMS, vol. 15(3), pages 430-466, August.
    6. Omkar Achrekar & Chrysafis Vogiatzis, 2018. "Evacuation Trees with Contraflow and Divergence Considerations," Springer Optimization and Its Applications, in: Ilias S. Kotsireas & Anna Nagurney & Panos M. Pardalos (ed.), Dynamics of Disasters, pages 1-46, Springer.
    7. Urmila Pyakurel & Stephan Dempe, 2020. "Network Flow with Intermediate Storage: Models and Algorithms," SN Operations Research Forum, Springer, vol. 1(4), pages 1-23, December.
    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. Pyakurel, Urmila & Khanal, Durga Prasad & Dhamala, Tanka Nath, 2023. "Abstract network flow with intermediate storage for evacuation planning," European Journal of Operational Research, Elsevier, vol. 305(3), pages 1178-1193.
    2. Urmila Pyakurel & Stephan Dempe, 2020. "Network Flow with Intermediate Storage: Models and Algorithms," SN Operations Research Forum, Springer, vol. 1(4), pages 1-23, December.
    3. Shiva Prakash Gupta & Urmila Pyakurel & Tanka Nath Dhamala, 2023. "Multi-commodity flow problem on lossy network with partial lane reversals," Annals of Operations Research, Springer, vol. 323(1), pages 45-63, April.
    4. Melissa Gama & Bruno Filipe Santos & Maria Paola Scaparra, 2016. "A multi-period shelter location-allocation model with evacuation orders for flood disasters," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 4(3), pages 299-323, September.
    5. Zheng, Hong & Peeta, Srinivas, 2014. "Cost scaling based successive approximation algorithm for the traffic assignment problem," Transportation Research Part B: Methodological, Elsevier, vol. 68(C), pages 17-30.
    6. Zhao Zhang & Zaixin Lu & Xianyue Li & Xiaohui Huang & Ding-Zhu Du, 2019. "Online hole healing for sensor coverage," Journal of Global Optimization, Springer, vol. 75(4), pages 1111-1131, December.
    7. Carlo Mannino & Alessandro Mascis, 2009. "Optimal Real-Time Traffic Control in Metro Stations," Operations Research, INFORMS, vol. 57(4), pages 1026-1039, August.
    8. Abhishek Behl & Pankaj Dutta, 2019. "Humanitarian supply chain management: a thematic literature review and future directions of research," Annals of Operations Research, Springer, vol. 283(1), pages 1001-1044, December.
    9. Soheyl Khalilpourazari & Alireza Arshadi Khamseh, 2019. "Bi-objective emergency blood supply chain network design in earthquake considering earthquake magnitude: a comprehensive study with real world application," Annals of Operations Research, Springer, vol. 283(1), pages 355-393, December.
    10. Marins, Fernando A. S. & Senne, Edson L. F. & Darby-Dowman, Ken & Machado, Arlene F. & Perin, Clovis, 1997. "Algorithms for network piecewise-linear programs: A comparative study," European Journal of Operational Research, Elsevier, vol. 97(1), pages 183-199, February.
    11. Castro, Jordi & Nasini, Stefano, 2021. "A specialized interior-point algorithm for huge minimum convex cost flows in bipartite networks," European Journal of Operational Research, Elsevier, vol. 290(3), pages 857-869.
    12. Wang, Yan & Wang, Junwei, 2019. "Integrated reconfiguration of both supply and demand for evacuation planning," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 130(C), pages 82-94.
    13. Knut Haase & Mathias Kasper & Matthes Koch & Sven Müller, 2019. "A Pilgrim Scheduling Approach to Increase Safety During the Hajj," Operations Research, INFORMS, vol. 67(2), pages 376-406, March.
    14. Urmila Pyakurel & Hari Nandan Nath & Tanka Nath Dhamala, 2019. "Partial contraflow with path reversals for evacuation planning," Annals of Operations Research, Springer, vol. 283(1), pages 591-612, December.
    15. Kimms, A. & Maiwald, M., 2018. "Bi-objective safe and resilient urban evacuation planning," European Journal of Operational Research, Elsevier, vol. 269(3), pages 1122-1136.
    16. Luce Brotcorne & Martine Labbé & Patrice Marcotte & Gilles Savard, 2000. "A Bilevel Model and Solution Algorithm for a Freight Tariff-Setting Problem," Transportation Science, INFORMS, vol. 34(3), pages 289-302, August.
    17. Xinhua Mao & Changwei Yuan & Jiahua Gan & Jibiao Zhou, 2019. "Optimal Evacuation Strategy for Parking Lots Considering the Dynamic Background Traffic Flows," IJERPH, MDPI, vol. 16(12), pages 1-20, June.
    18. Hadas, Yuval & Laor, Amir, 2013. "Network design model with evacuation constraints," Transportation Research Part A: Policy and Practice, Elsevier, vol. 47(C), pages 1-9.
    19. Karine Deschinkel & Sid-Ahmed-Ali Touati & Sébastien Briais, 2011. "SIRALINA: efficient two-steps heuristic for storage optimisation in single period task scheduling," Journal of Combinatorial Optimization, Springer, vol. 22(4), pages 819-844, November.
    20. Denissa Sari Darmawi Purba & Eleftheria Kontou & Chrysafis Vogiatzis, 2021. "Evacuation Route Planning for Alternative Fuel Vehicles," Papers 2109.01578, arXiv.org, revised May 2022.

    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:snopef:v:3:y:2022:i:4:d:10.1007_s43069-022-00168-2. 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.