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. Bayram, Vedat & Yaman, Hande, 2024. "A joint demand and supply management approach to large scale urban evacuation planning: Evacuate or shelter-in-place, staging and dynamic resource allocation," European Journal of Operational Research, Elsevier, vol. 313(1), pages 171-191.
    5. 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.
    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. 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.
    8. 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.
    9. 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.
    10. 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.
    11. 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.
    12. Mehdi Ghiyasvand, 2019. "An $$O(n(m+n\log n)\log n)$$O(n(m+nlogn)logn) time algorithm to solve the minimum cost tension problem," Journal of Combinatorial Optimization, Springer, vol. 37(3), pages 957-969, April.
    13. Al-Takrouri, Saleh & Savkin, Andrey V., 2013. "A decentralized flow redistribution algorithm for avoiding cascaded failures in complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 392(23), pages 6135-6145.
    14. Bretschneider, S. & Kimms, A., 2012. "Pattern-based evacuation planning for urban areas," European Journal of Operational Research, Elsevier, vol. 216(1), pages 57-69.
    15. Urmila Pyakurel & Hari Nandan Nath & Stephan Dempe & Tanka Nath Dhamala, 2019. "Efficient Dynamic Flow Algorithms for Evacuation Planning Problems with Partial Lane Reversal," Mathematics, MDPI, vol. 7(10), pages 1-29, October.
    16. Weiqi Hong & Zishu Yang & Xu Sun & Jianyu Wang & Pengpeng Jiao, 2022. "Temporary Reversible Lane Design Based on Bi-Level Programming Model during the Winter Olympic Games," Sustainability, MDPI, vol. 14(8), pages 1-17, April.
    17. Chi Sun & Weiqi Hong & Hao Li & Chenjing Zhou, 2022. "Lane Optimization of Highway Reconstruction and Expansion Work Zone Considering Carbon Dioxide Emission Factors," Sustainability, MDPI, vol. 14(19), pages 1-17, September.
    18. Huan Cao & Tian Li & Shuxia Li & Tijun Fan, 2017. "An integrated emergency response model for toxic gas release accidents based on cellular automata," Annals of Operations Research, Springer, vol. 255(1), pages 617-638, August.
    19. Antonio Frangioni & Antonio Manca, 2006. "A Computational Study of Cost Reoptimization for Min-Cost Flow Problems," INFORMS Journal on Computing, INFORMS, vol. 18(1), pages 61-70, February.
    20. Jin, Jian Gang & Shen, Yifan & Hu, Hao & Fan, Yiqun & Yu, Mingjian, 2021. "Optimizing underground shelter location and mass pedestrian evacuation in urban community areas: A case study of Shanghai," Transportation Research Part A: Policy and Practice, Elsevier, vol. 149(C), pages 124-138.

    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.