Minimum Clearance Time on the Prioritized Integrated Evacuation Network

Iswar Mani Adhikari; Tanka Nath Dhamala

doi:doi:10.11648/j.ajam.20200804.15

| Peer-Reviewed

Minimum Clearance Time on the Prioritized Integrated Evacuation Network

Iswar Mani Adhikari, Tanka Nath Dhamala

Published in American Journal of Applied Mathematics (Volume 8, Issue 4)

Received: 8 April 2020 Accepted: 20 July 2020 Published: 28 July 2020

Views: Downloads:

Download PDF

Share This Article

Twitter
Linked In
Facebook

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.

Published in	American Journal of Applied Mathematics (Volume 8, Issue 4)
DOI	10.11648/j.ajam.20200804.15
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), 2020. 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.

Cite This Article

Plain Text BibTeX RIS

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://article.sciencepublishinggroup.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

Author Information

Iswar Mani Adhikari

Prithvi Narayan Campus, Tribhuvan University, Pokhara, Nepal
Tanka Nath Dhamala

Central Department of Mathematics, Tribhuvan University, Kathmandu, Nepal

Download PDF

Sections

Plain Text BibTeX RIS

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://article.sciencepublishinggroup.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