Evacuation planning by earliest arrival contraflow

Urmila Pyakurel; Tanka Nath Dhamala

doi:10.3934/jimo.2016028

Article Contents

2017, Volume 13, Issue 1: 489-503. Doi: 10.3934/jimo.2016028

This issue Previous Article Solution continuity of parametric generalized vector equilibrium problems with strictly pseudomonotone mappings Next Article Optimal consumption with reference-dependent preferences in on-the-job search and savings

Evacuation planning by earliest arrival contraflow

Urmila Pyakurel and
Tanka Nath Dhamala

Central Departments of Mathematics IOST Tribhuvan University, Kathmandu, Nepal

Received: June 2015

Published: August 2017

The second would like to thank Alexander von Humboldt Foundation for the research support on evacuation planning.

Abstract / Introduction Full Text(HTML) Figure(4) Related Papers Cited by

Abstract

The very challenging emergency issues because of large scale natural or man-created disasters promote the research on evacuation planning. The earliest arrival contraflow is an important model for evacuation planning that rescue as many evacuees as possible at any point in time by reversing the direction of arcs towards the safe destinations with increased outbound arc capacity. We present efficient algorithms to solve the earliest arrival contraflow problem on multiple sources and on multiple sinks networks separately. We also introduce an approximate-earliest arrival contraflow solution on multi-terminal networks.

Keywords:

Mathematics Subject Classification: Primary: 90B10, 90C27, 68Q25; Secondary: 90B06, 90B20.

Citation:

Full Text(HTML)

Figure 1. Two sources and single sink small MDCF scenario and its solution

Download: Full-size image PowerPoint slide

Figure 2. Non-existence of earliest arrival contraflow on multiple sinks

Download: Full-size image PowerPoint slide

Figure 3. EACF solution does not always exist on multiple terminal networks

Download: Full-size image PowerPoint slide

Figure 4. Existence of earliest arrival contraflow on multiple sinks

Download: Full-size image PowerPoint slide

Related Papers

Cited by

References

[1]	R. K. Ahuja, T. L. Magnati and J. B. Orlin, Network flows: Theory, algorithms and applications, Prentice Hall, Englewood Cliffs, New Jersey, 1993.
[2]	A. Arulselvan, Network model for disaster management, PhD Thesis, University of Florida, USA, 2009.
[3]	N. Baumann and M. Skutella, Earliest arrival flows with multiple sources, Mathematics of Operations Research, 34 (2009), 499-512. doi: 10.1287/moor.1090.0382.
[4]	R. E. Burkard, K. Dlaska and B. Klinz, The quickest flow problem, ZOR-Methods and Models of Operations Research, 37 (1993), 31-58. doi: 10.1007/BF01415527.
[5]	J. Cheriyan and S. N. Maheshwari, Analysis of preflow push algorithm for maximum network flow, SIAM J. Comput., 18 (1989), 1057-1086. doi: 10.1137/0218072.
[6]	T. N. Dhamala, A survey on models and algorithms for discrete evacuation planning network problems, Journal of Industrial and Management Optimization, 11 (2015), 265-289. doi: 10.3934/jimo.2015.11.265.
[7]	T. N. Dhamala and U. Pyakurel, Earliest arrival contraflow problem on series-parallel graphs, International Journal of Operations Research, 10 (2013), 1-13.
[8]	L. K. Fleischer and E. Tardos, Efficient continuous-time dynamic network flow algorithms, Operations Research Letters, 23 (1998), 71-80. doi: 10.1016/S0167-6377(98)00037-6.
[9]	F. R. Ford and D. R. Fulkerson, Constructing maximal dynamic flows from static flows, Operations Research, 6 (1958), 419-433. doi: 10.1287/opre.6.3.419.
[10]	A. V. Goldberg and R. E. Tarjan, Finding minimum-cost circulations by cancelling negative cycles, J. ACM, 36 (1989), 873-886. doi: 10.1145/76359.76368.
[11]	M. Gross, J. -P. W. Kappmeier, D. R. Schmidt and M. Schmidt, Approximating earliest arrival flows in arbitrary networks, in Algorithms-ESA 2012 (eds. L. Epstein and P. Ferragina), Lecture Notes in Comput. Sci., 7501, Springer, Heidelberg, 2012, 551-562. doi: 10.1007/978-3-642-33090-2_48.
[12]	G. Hamza-Lup, K. A. Hua, M. Le and R. Peng, Enhancing intelligent transportation systems to improve and support homeland security, in Proceedings of the Seventh IEEE International Conference, Intelligent Transportation Systems (ITSC), 2004, 250-255. doi: 10.1109/ITSC.2004.1398906.
[13]	B. Hoppe and E. Tardos, The quickest transshipment problem, Mathematics of Operations Research, 25 (2000), 36-62. doi: 10.1287/moor.25.1.36.15211.
[14]	J. -P. W. Kappmeier, Generalizations of Flows Over Time with Application in Evacuation Optimization, PhD Thesis, Technical University, Berlin, Germany, 2015.
[15]	S. Kim, S. Shekhar and M. Min, Contraflow transportation network reconfiguration for evacuation route planning, IEEE Transactions on Knowledge and Data Engineering, 20 (2008), 1-15.
[16]	S. Kim and S. Shekhar, Contraflow network reconfiguration for evacuation planning: A summary of results, in Proceedings of 13th ACM Symposium on Advances in Geographic Information Systems (GIS 05), 2005, 250-259. doi: 10.1145/1097064.1097099.
[17]	T. Litman, Lessons from Katrina and Rita: what major disasters can teach transportation planners, Journal of Transportation Engineering, 132 (2006), 11-18. doi: 10.1061/(ASCE)0733-947X(2006)132:1(11).
[18]	E. Minieka, Maximal, lexicographic, and dynamic network flows, Operations Research, 21 (1973), 517-527. doi: 10.1287/opre.21.2.517.
[19]	U. Pyakurel, H. W. Hamacher and T. N. Dhamala, Generalized maximum dynamic contraflow on lossy network, International Journal of Operations Research Nepal, 3 (2014), 27-44.
[20]	U. Pyakurel and T. N. Dhamala, Earliest arrival contraflow model for evacuation planning, Neural, Parallel, and Scientific Computations, 22 (2014), 287-294.
[21]	U. Pyakurel and T. N. Dhamala, Lexicographically contraflow problem for evacuation planning, in Proceedings of the Second International Conference, Operations Research Society Nepal, 2014, 287-294.
[22]	U. Pyakurel and T. N. Dhamala, Models and algorithms on contraflow evacuation planning network problems, International Journal of Operations Research, 12 (2015), 36-46.
[23]	U. Pyakurel, M. Goerigk, T. N. Dhamala and H. W. Hamacher, Transit dependent evacuation planning for Kathmandu valley: A case study, International Journal of Operations Research Nepal, (accepted), 2015.
[24]	S. Rebennack, A. Arulselvan, L. Elefteriadou and P. M. Pardalos, Complexity analysis for maximum flow problems with arc reversals, Journal of Combinatorial Optimization, 19 (2010), 200-216. doi: 10.1007/s10878-008-9175-8.
[25]	S. Ruzika, H. Sperber and M. Steiner, Earliest arrival flows on series-parallel graphs, Networks, 10 (2011), 169-173. doi: 10.1002/net.20398.
[26]	M. Schmidt and M. Skutella, Earliest arrival flows in networks with multiple sinks, Electronics Notes in Discrete Mathematics, 36 (2010), 607-614.
[27]	H. Tuydes and A. Ziliaskopoulos, Network re-design to optimize evacuation contraflow, in Proceedings 83rd Ann. Meeting of the Transportation Research Board, 2004.
[28]	H. Tuydes and A. Ziliaskopoulos, Tabu-based heuristic for optimization of network evacuation contraflow in Proceedings, 85th Annual Meeting of the Transportation Research Board, 2006. doi: 10.3141/1964-17.
[29]	W. L. Wilkinson, An algorithm for universal maximal dynamic flows in a network, Operations Research, 19 (1971), 1602-1612. doi: 10.1287/opre.19.7.1602.
[30]	B. Wolshon, E. Urbina and M. Levitan, National Review of Hurricane Evacuation Plans and Policies, Technical Report, Hurricane Center, Louisiana State University, Baton Rouge, Louisiana, 2002.