IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v7y2019i10p993-d278317.html
   My bibliography  Save this article

Efficient Dynamic Flow Algorithms for Evacuation Planning Problems with Partial Lane Reversal

Author

Listed:
  • Urmila Pyakurel

    (Central Department of Mathematics, Tribhuvan University, P.O. Box: 13143, Kathmandu, Nepal
    Current address: TU Bergakademie, Fakultät für Mathematik und Informatik, 09596 Freiberg, Germany.)

  • Hari Nandan Nath

    (Central Department of Mathematics, Tribhuvan University, P.O. Box: 13143, Kathmandu, Nepal)

  • Stephan Dempe

    (TU Bergakademie, Fakultät für Mathematik und Informatik, 09596 Freiberg, Germany)

  • Tanka Nath Dhamala

    (Central Department of Mathematics, Tribhuvan University, P.O. Box: 13143, Kathmandu, Nepal)

Abstract

Contraflow technique has gained a considerable focus in evacuation planning research over the past several years. In this work, we design efficient algorithms to solve the maximum, lex-maximum, earliest arrival, and quickest dynamic flow problems having constant attributes and their generalizations with partial contraflow reconfiguration in the context of evacuation planning. The partial static contraflow problems, that are foundations to the dynamic flows, are also studied. Moreover, the contraflow model with inflow-dependent transit time on arcs is introduced. A strongly polynomial time algorithm to compute approximate solution of the quickest partial contraflow problem on two terminal networks is presented, which is substantiated by numerical computations considering Kathmandu road network as an evacuation network. Our results show that the quickest time to evacuate a flow of value 100,000 units is reduced by more than 42% using the partial contraflow technique, and the difference is more with the increase in the flow value. Moreover, the technique keeps the record of the portions of the road network not used by the evacuees.

Suggested Citation

  • 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.
    • Handle: RePEc:gam:jmathe:v:7:y:2019:i:10:p:993-:d:278317
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/7/10/993/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/7/10/993/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Edward Minieka, 1973. "Maximal, Lexicographic, and Dynamic Network Flows," Operations Research, INFORMS, vol. 21(2), pages 517-527, April.
    2. Steffen Rebennack & Ashwin Arulselvan & Lily Elefteriadou & Panos M. Pardalos, 2010. "Complexity analysis for maximum flow problems with arc reversals," Journal of Combinatorial Optimization, Springer, vol. 19(2), pages 200-216, February.
    3. Bruce Hoppe & Éva Tardos, 2000. "The Quickest Transshipment Problem," Mathematics of Operations Research, INFORMS, vol. 25(1), pages 36-62, February.
    4. Marta Pascoal & M. Captivo & João Clímaco, 2006. "A comprehensive survey on the quickest path problem," Annals of Operations Research, Springer, vol. 147(1), pages 5-21, October.
    5. 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.
    6. Lichun Chen & Elise Miller‐Hooks, 2008. "The building evacuation problem with shared information," Naval Research Logistics (NRL), John Wiley & Sons, vol. 55(4), pages 363-376, June.
    7. Urmila Pyakurel & Tanka Nath Dhamala, 2017. "Continuous Dynamic Contraflow Approach for Evacuation Planning," Annals of Operations Research, Springer, vol. 253(1), pages 573-598, June.
    8. Nimrod Megiddo, 1979. "Combinatorial Optimization with Rational Objective Functions," Mathematics of Operations Research, INFORMS, vol. 4(4), pages 414-424, November.
    9. Altay, Nezih & Green III, Walter G., 2006. "OR/MS research in disaster operations management," European Journal of Operational Research, Elsevier, vol. 175(1), pages 475-493, November.
    10. MacGregor Smith, J. & Cruz, F.R.B., 2014. "M/G/c/c state dependent travel time models and properties," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 395(C), pages 560-579.
    11. Cova, Thomas J. & Johnson, Justin P., 2003. "A network flow model for lane-based evacuation routing," Transportation Research Part A: Policy and Practice, Elsevier, vol. 37(7), pages 579-604, August.
    12. W. L. Wilkinson, 1971. "An Algorithm for Universal Maximal Dynamic Flows in a Network," Operations Research, INFORMS, vol. 19(7), pages 1602-1612, December.
    13. Urmila Pyakurel & Tanka Nath Dhamala, 2016. "Continuous Time Dynamic Contraflow Models and Algorithms," Advances in Operations Research, Hindawi, vol. 2016, pages 1-7, March.
    14. Nadine Baumann & Martin Skutella, 2009. "Earliest Arrival Flows with Multiple Sources," Mathematics of Operations Research, INFORMS, vol. 34(2), pages 499-512, May.
    Full references (including those not matched with items on IDEAS)

    Citations

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


    Cited by:

    1. 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.
    2. 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.
    3. 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.

    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. Urmila Pyakurel & Tanka Nath Dhamala, 2017. "Continuous Dynamic Contraflow Approach for Evacuation Planning," Annals of Operations Research, Springer, vol. 253(1), pages 573-598, June.
    2. 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.
    3. 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.
    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. Hong Zheng & Yi-Chang Chiu & Pitu B. Mirchandani, 2015. "On the System Optimum Dynamic Traffic Assignment and Earliest Arrival Flow Problems," Transportation Science, INFORMS, vol. 49(1), pages 13-27, February.
    6. Tanka Nath Dhamala & Urmila Pyakurel & Ram Chandra Dhungana, 2018. "Abstract Contraflow Models and Solution Procedures for Evacuation Planning," Journal of Mathematics Research, Canadian Center of Science and Education, vol. 10(4), pages 89-100, August.
    7. Nadine Baumann & Martin Skutella, 2009. "Earliest Arrival Flows with Multiple Sources," Mathematics of Operations Research, INFORMS, vol. 34(2), pages 499-512, May.
    8. 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.
    9. Jianghua Zhang & Yang Liu & Yingxue Zhao & Tianhu Deng, 2020. "Emergency evacuation problem for a multi-source and multi-destination transportation network: mathematical model and case study," Annals of Operations Research, Springer, vol. 291(1), pages 1153-1181, August.
    10. 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.
    11. Melchiori, Anna & Sgalambro, Antonino, 2020. "A branch and price algorithm to solve the Quickest Multicommodity k-splittable Flow Problem," European Journal of Operational Research, Elsevier, vol. 282(3), pages 846-857.
    12. Pursals, Salvador Casadesús & Garzón, Federico Garriga, 2009. "Optimal building evacuation time considering evacuation routes," European Journal of Operational Research, Elsevier, vol. 192(2), pages 692-699, January.
    13. Esposito Amideo, A. & Scaparra, M.P. & Kotiadis, K., 2019. "Optimising shelter location and evacuation routing operations: The critical issues," European Journal of Operational Research, Elsevier, vol. 279(2), pages 279-295.
    14. Goerigk, Marc & Deghdak, Kaouthar & Heßler, Philipp, 2014. "A comprehensive evacuation planning model and genetic solution algorithm," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 71(C), pages 82-97.
    15. Shahriar Akter & Samuel Fosso Wamba, 2019. "Big data and disaster management: a systematic review and agenda for future research," Annals of Operations Research, Springer, vol. 283(1), pages 939-959, December.
    16. Yosuke Hanawa & Yuya Higashikawa & Naoyuki Kamiyama & Naoki Katoh & Atsushi Takizawa, 2018. "The mixed evacuation problem," Journal of Combinatorial Optimization, Springer, vol. 36(4), pages 1299-1314, November.
    17. Deepa Mishra & Sameer Kumar & Elkafi Hassini, 2019. "Current trends in disaster management simulation modelling research," Annals of Operations Research, Springer, vol. 283(1), pages 1387-1411, December.
    18. Li Liu & Huan Jin & Yangguang Liu & Xiaomin Zhang, 2022. "Intelligent Evacuation Route Planning Algorithm Based on Maximum Flow," IJERPH, MDPI, vol. 19(13), pages 1-14, June.
    19. Ismaila Abderhamane Ndiaye & Emmanuel Neron & Antoine Jouglet, 2017. "Macroscopic evacuation plans for natural disasters," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 39(1), pages 231-272, January.
    20. 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.

    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:gam:jmathe:v:7:y:2019:i:10:p:993-:d:278317. 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: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.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.