Volume 8, Issue 4, August 2020, Page: 207-215
Minimum Clearance Time on the Prioritized Integrated Evacuation Network
Iswar Mani Adhikari, Prithvi Narayan Campus, Tribhuvan University, Pokhara, Nepal
Tanka Nath Dhamala, Central Department of Mathematics, Tribhuvan University, Kathmandu, Nepal
Received: Apr. 8, 2020;       Accepted: Jul. 20, 2020;       Published: Jul. 28, 2020
DOI: 10.11648/j.ajam.20200804.15      View  22      Downloads  38
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.
Evacuation Planning, Integrated Network, Minimum Clearance Time, Lexicographic Flow, Partial Arc Reversal
To cite this article
Iswar Mani Adhikari, Tanka Nath Dhamala, Minimum Clearance Time on the Prioritized Integrated Evacuation Network, American Journal of Applied Mathematics. Vol. 8, No. 4, 2020, pp. 207-215. doi: 10.11648/j.ajam.20200804.15
Copyright © 2020 Authors retain the copyright of this article.
This article is an open access article distributed under the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0/) which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Ford, L. R. and Fulkerson, D. R. (1958). Constructing maximal dynamic flows from static flows. Operations Research, 6: 419-433.
Ford, L. R. and Fulkerson, D. R. Flows in Networks. Princeton University Press, Princeton, NJ, 1962.
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.
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.
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.
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.
Bish, D. R. (2011). Planning for a bus-based evacuation. OR Spectrum, 33: 629-654.
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.
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.
Megiddo, N. (1974). Optimal flows in networks with multiple sources and sinks. Mathematical Programming, 7: 97-107.
Megiddo, N. (1977). A good algorithm for lexicographically optimal flows in multi-terminal networks. Bulletin of the American Mathematical Society, 83: 407-409.
Minieka, E. Maximal. (1973). Lexicographic, and dynamic network flows. Operation Research, 21: 517-527.
Wilkinson, W. L. (1971). An algorithm for universal maximal dynamic flows in a network. Operations Research, 19 (7): 1602-1612.
Kamiyama, N. (2019). Lexicographically optimal earliest arrival flows. Networks, 1-16.
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.
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.
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.
Hoppe B. and Tardos E. (2000). The quickest transshipment problem. Mathematics of Operation Research, 25 (1): 36-62.
Fleischer L. K. (2001). Faster algorithms for the quickest transshipment problem. SIAM Journal on Optimization, 12 (1): 18-35.
Orlin, J. B. (1988). Faster strongly polynomial cost flow algorithm. Proceeding of the 20th annual symposium of theory of computing, 377-387.
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.
Goerigk, M. and Grün B. (2014) A robust bus evacuation model with delayed scenario information. OR Spectrum, 36: 923-948.
Browse journals by subject