American Journal of Applied Mathematics

| Peer-Reviewed |

Minimum Clearance Time on the Prioritized Integrated Evacuation Network

Received: 08 April 2020    Accepted: 20 July 2020    Published: 28 July 2020
Views:       Downloads:

Share This Article

Abstract

The evacuation planning problem can be viewed as different variants of dynamic flow maximization and time minimization problems. An optimal solution to the latter problem sends a given amount of flow from disaster zones to safe zones in minimum time. We solve this problem on an embedded integrated network of a prioritized primary and a bus-routed secondary sub-networks. For a lexicographically maximum (lex-max) dynamic flow problem, we are given a time horizon and a prioritized network, where we need a feasible dynamic flow that lexicographically maximizes the flow amount leaving each terminal respecting the priority. Here, we use the quickest transshipment partial arc reversal strategy to collect the evacuees in minimum time from the disaster zones to the pickup locations of the primary sub-network. By treating such pickup locations as sources, the available set of transit-buses is assigned in the secondary sub-network to shift the evacuees finally to the sinks on the first-come-first-serve basis. This novel approach proposed here is better suited for the simultaneous flow of evacuees with minimum waiting delay at such pickup locations in the integrated evacuation network topology. The lane reversal strategy significantly reduces the evacuation time, whereas reversing them only partially has an additional benefit that the unused road capacities can be used for supplying emergency logistics and allocating facilities as well.

DOI 10.11648/j.ajam.20200804.15
Published in American Journal of Applied Mathematics (Volume 8, Issue 4, August 2020)
Page(s) 207-215
Creative Commons

This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited.

Copyright

Copyright © The Author(s), 2024. Published by Science Publishing Group

Keywords

Evacuation Planning, Integrated Network, Minimum Clearance Time, Lexicographic Flow, Partial Arc Reversal

References
[1] Ford, L. R. and Fulkerson, D. R. (1958). Constructing maximal dynamic flows from static flows. Operations Research, 6: 419-433.
[2] Ford, L. R. and Fulkerson, D. R. Flows in Networks. Princeton University Press, Princeton, NJ, 1962.
[3] Adhikari, I. M., Pyakurel U., and Dhamala, T. N. (2020). An integrated solution approach for the time minimization evacuation planning problem. International Journal of Operation Research, 17 (1): 27-39.
[4] Dhamala, T. N. and Adhikari, I. M. (2018). On evacuation planning optimization problems from transit-based perspective. International Journal of Operation Research, 15 (1): 29-47.
[5] Dhamala, T. N., Adhikari, I. M., Nath, H. N., and Pyakurel, U. (2018). Meaningfulness of OR models and solution strategies for emergency planning. In: Living Under the Threat of Earthquakes, Edited by Kruhl, J. H., Adhikari, R. and Dorka, U. E., Springer Natural Hazards, 175-194.
[6] Dhamala, T. N., Pyakurel, U., and Dempe, S. (2018). A critical survey on the network optimization algorithms for evacuation planning problems. International Journal of Operation Research, 15 (3): 101-133.
[7] Bish, D. R. (2011). Planning for a bus-based evacuation. OR Spectrum, 33: 629-654.
[8] Goerigk, M., Grün B., and Heᵦler, P. (2013). Branch and bound algorithms for the bus evacuation problem. Computers and Operations Research, 40: 3010-3020.
[9] Pyakurel, U., Goerigk, M., Dhamala, T. N., and Hamacher, H. W. (2015). Transit dependent evacuation planning for Kathmandu valley: a case study. International Journal of Operations Research Nepal, 5: 49-73.
[10] Megiddo, N. (1974). Optimal flows in networks with multiple sources and sinks. Mathematical Programming, 7: 97-107.
[11] Megiddo, N. (1977). A good algorithm for lexicographically optimal flows in multi-terminal networks. Bulletin of the American Mathematical Society, 83: 407-409.
[12] Minieka, E. Maximal. (1973). Lexicographic, and dynamic network flows. Operation Research, 21: 517-527.
[13] Wilkinson, W. L. (1971). An algorithm for universal maximal dynamic flows in a network. Operations Research, 19 (7): 1602-1612.
[14] Kamiyama, N. (2019). Lexicographically optimal earliest arrival flows. Networks, 1-16.
[15] Pyakurel, U. and Dhamala, T. N. (2015). Models and algorithms on contraflow evacuation planning network problems. International Journal of Operations Research, 12 (2): 36-46.
[16] Pyakurel, U., Nath, H. N., and Dhamala, T. N. (2019). Partial contraflow with path reversals for evacuation planning. Annals of Operation Research, 283, 591-612.
[17] Pyakurel, U., Nath, H. N., Dempe, S., and Dhamala, T. N. (2019). Efficient dynamic flow algorithms for evacuation planning problems with partial lane reversal. Mathematics, 7 (10), 993.
[18] Hoppe B. and Tardos E. (2000). The quickest transshipment problem. Mathematics of Operation Research, 25 (1): 36-62.
[19] Fleischer L. K. (2001). Faster algorithms for the quickest transshipment problem. SIAM Journal on Optimization, 12 (1): 18-35.
[20] Orlin, J. B. (1988). Faster strongly polynomial cost flow algorithm. Proceeding of the 20th annual symposium of theory of computing, 377-387.
[21] Schloter, M., and Skutella, M. (2017). Fast and Memory-Efficient Algorithms for Evacuation Problems. Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 821-840.
[22] Goerigk, M. and Grün B. (2014) A robust bus evacuation model with delayed scenario information. OR Spectrum, 36: 923-948.
Author Information
  • Prithvi Narayan Campus, Tribhuvan University, Pokhara, Nepal

  • Central Department of Mathematics, Tribhuvan University, Kathmandu, Nepal

Cite This Article
  • APA Style

    Iswar Mani Adhikari, Tanka Nath Dhamala. (2020). Minimum Clearance Time on the Prioritized Integrated Evacuation Network. American Journal of Applied Mathematics, 8(4), 207-215. https://doi.org/10.11648/j.ajam.20200804.15

    Copy | Download

    ACS Style

    Iswar Mani Adhikari; Tanka Nath Dhamala. Minimum Clearance Time on the Prioritized Integrated Evacuation Network. Am. J. Appl. Math. 2020, 8(4), 207-215. doi: 10.11648/j.ajam.20200804.15

    Copy | Download

    AMA Style

    Iswar Mani Adhikari, Tanka Nath Dhamala. Minimum Clearance Time on the Prioritized Integrated Evacuation Network. Am J Appl Math. 2020;8(4):207-215. doi: 10.11648/j.ajam.20200804.15

    Copy | Download

  • @article{10.11648/j.ajam.20200804.15,
      author = {Iswar Mani Adhikari and Tanka Nath Dhamala},
      title = {Minimum Clearance Time on the Prioritized Integrated Evacuation Network},
      journal = {American Journal of Applied Mathematics},
      volume = {8},
      number = {4},
      pages = {207-215},
      doi = {10.11648/j.ajam.20200804.15},
      url = {https://doi.org/10.11648/j.ajam.20200804.15},
      eprint = {https://download.sciencepg.com/pdf/10.11648.j.ajam.20200804.15},
      abstract = {The evacuation planning problem can be viewed as different variants of dynamic flow maximization and time minimization problems. An optimal solution to the latter problem sends a given amount of flow from disaster zones to safe zones in minimum time. We solve this problem on an embedded integrated network of a prioritized primary and a bus-routed secondary sub-networks. For a lexicographically maximum (lex-max) dynamic flow problem, we are given a time horizon and a prioritized network, where we need a feasible dynamic flow that lexicographically maximizes the flow amount leaving each terminal respecting the priority. Here, we use the quickest transshipment partial arc reversal strategy to collect the evacuees in minimum time from the disaster zones to the pickup locations of the primary sub-network. By treating such pickup locations as sources, the available set of transit-buses is assigned in the secondary sub-network to shift the evacuees finally to the sinks on the first-come-first-serve basis. This novel approach proposed here is better suited for the simultaneous flow of evacuees with minimum waiting delay at such pickup locations in the integrated evacuation network topology. The lane reversal strategy significantly reduces the evacuation time, whereas reversing them only partially has an additional benefit that the unused road capacities can be used for supplying emergency logistics and allocating facilities as well.},
     year = {2020}
    }
    

    Copy | Download

  • TY  - JOUR
    T1  - Minimum Clearance Time on the Prioritized Integrated Evacuation Network
    AU  - Iswar Mani Adhikari
    AU  - Tanka Nath Dhamala
    Y1  - 2020/07/28
    PY  - 2020
    N1  - https://doi.org/10.11648/j.ajam.20200804.15
    DO  - 10.11648/j.ajam.20200804.15
    T2  - American Journal of Applied Mathematics
    JF  - American Journal of Applied Mathematics
    JO  - American Journal of Applied Mathematics
    SP  - 207
    EP  - 215
    PB  - Science Publishing Group
    SN  - 2330-006X
    UR  - https://doi.org/10.11648/j.ajam.20200804.15
    AB  - The evacuation planning problem can be viewed as different variants of dynamic flow maximization and time minimization problems. An optimal solution to the latter problem sends a given amount of flow from disaster zones to safe zones in minimum time. We solve this problem on an embedded integrated network of a prioritized primary and a bus-routed secondary sub-networks. For a lexicographically maximum (lex-max) dynamic flow problem, we are given a time horizon and a prioritized network, where we need a feasible dynamic flow that lexicographically maximizes the flow amount leaving each terminal respecting the priority. Here, we use the quickest transshipment partial arc reversal strategy to collect the evacuees in minimum time from the disaster zones to the pickup locations of the primary sub-network. By treating such pickup locations as sources, the available set of transit-buses is assigned in the secondary sub-network to shift the evacuees finally to the sinks on the first-come-first-serve basis. This novel approach proposed here is better suited for the simultaneous flow of evacuees with minimum waiting delay at such pickup locations in the integrated evacuation network topology. The lane reversal strategy significantly reduces the evacuation time, whereas reversing them only partially has an additional benefit that the unused road capacities can be used for supplying emergency logistics and allocating facilities as well.
    VL  - 8
    IS  - 4
    ER  - 

    Copy | Download

  • Sections