Archive
Special Issues

Volume 8, Issue 4, August 2020, Page: 230-235
Evacuation Contraflow Problems with Not Necessarily Equal Transit Time on Anti-parallel Arcs
Phanindra Prasad Bhandari, Central Department of Mathematics, Tribhuvan University, Kirtipur, Kathmandu, Nepal
Shree Ram Khadka, Central Department of Mathematics, Tribhuvan University, Kirtipur, Kathmandu, Nepal
Received: Jul. 27, 2020;       Accepted: Aug. 10, 2020;       Published: Aug. 17, 2020
Abstract
An evacuation planning problem provides a plan for existing road topology that sends maximum number of evacuees from risk zone to the safe destination in minimum time period during disasters. The problems with different road network attributes have been studied, and solutions have been proposed in literature. Evacuation planning problems with network contraflow approach, reversing the direction of traffic flow on lanes, with the same transit time on anti-parallel arcs have also been extensively studied. The approach, due to its lane-direction reversal property, can be taken as a potential remedy to mitigate congestion and reduce casualties during emergencies. In this paper, we propose a mathematical optimization contraflow model for the evacuation problem with the case where there may exist different transit time on anti-parallel arcs. We also propose analytical solutions to a few variants of problems, such as maximum dynamic contraflow problem and earliest arrival contraflow problem in which arc reversal capability is allowed only once at time zero. We extend the solution to solve the problems with continuous time settings by applying the natural relation between discrete time flows and continuous time flows. The solution procedures are based on application of temporally repeated flows (TRFs) on modified network, and they solve the problems optimally in strongly polynomial time.
Keywords
Network Flow, Contraflow, TTSP Network, Evacuation Planning Problem, Disaster Management
Phanindra Prasad Bhandari, Shree Ram Khadka, Evacuation Contraflow Problems with Not Necessarily Equal Transit Time on Anti-parallel Arcs, American Journal of Applied Mathematics. Vol. 8, No. 4, 2020, pp. 230-235. doi: 10.11648/j.ajam.20200804.18
Reference
[1]
Wei, Leyu, Jinliang Xu, Tian Lei, Menghui Li, Xingliang Liu, and Haoru Li. "Simulation and experimental analyses of microscopic traffic characteristics under a contraflow strategy." Applied Sciences. Vol. 9, No. 13, 2019, pp. 2651.
[2]
Urbina, Elba, and Brian Wolshon. "National review of hurricane evacuation plans and policies: a comparison and contrast of state practices." Transportation research part A: policy and practice. Vol. 37, No. 3, 2003, pp. 257-275.
[3]
Kim, Sangho, Shashi Shekhar, and Manki Min. "Contraflow transportation network reconfiguration for evacuation route planning." IEEE Transactions on Knowledge and Data Engineering. Vol. 20, No. 8, 2008, pp. 1115-1129.
[4]
Ford Jr, Lester R., and Delbert Ray Fulkerson. "Constructing maximal dynamic flows from static flows." Operations research. Vol. 6, No. 3, 1958, pp. 419-433.
[5]
Borradaile, Glencora, Philip N. Klein, Shay Mozes, Yahav Nussbaum, and Christian Wulff-Nilsen. “Multiple-source multiple-sink maximum flow in directed planar graphs in near-linear time.” SIAM Journal on Computing. Vol. 46, No. 4, 2017, pp. 1280–1303.
[6]
Borrmann, André, Angelika Kneidl, Gerta Köster, Stefan Ruzika, and Markus Thiemann. "Bidirectional coupling of macroscopic and microscopic pedestrian evacuation models." Safety Science. Vol. 50, No. 8, 2012, pp. 1695-1703.
[7]
Göttlich, Simone, Sebastian Kühn, Jan Peter Ohst, Stefan Ruzika, and Markus Thiemann. "Evacuation dynamics influenced by spreading hazardous material." Networks & Heterogeneous Media. Vol. 6, No. 3, 2011, pp. 443-464.
[8]
Khadka, Shree Ram and Phanindra Prasad Bhandari. “Model and solution for non-conservation flow evacuation planning problem.” The Nepali Mathematical Sciences Report. Vol. 36, No. 1-2, 2019, pp. 11-16.
[9]
Bhandari, Phanindra Prasad and Shree Ram Khadka. “Evacuation planning problems with intermediate storage.” In Proceedings of International Conference on Applied Mathematics and Computational Sciences (17-19 October, 2019), Dehradun, India. (To appear online).
[10]
Bhandari, Phanindra Prasad, Shree Ram Khadka, Stefan Ruzika and Luca E Schäfer. “Lexicographically maximum dynamic flow with vertex capacities.” Journal of Mathematics and Statistics. Vol. 16, No. 1, 2020, pp. 142–147.
[11]
Rebennack, Steffen, Ashwin Arulselvan, Lily Elefteriadou, and Panos M. Pardalos. "Complexity analysis for maximum flow problems with arc reversals." Journal of Combinatorial Optimization. Vol. 19, No. 2, 2010, pp. 200-216.
[12]
Anderson, Edward J., P. Nash, and Andrew B. Philpott. "A class of continuous network flow problems." Mathematics of Operations Research. Vol. 7, No. 4, 1982, pp. 501-514.
[13]
Philpott, Andrew B. "Continuous-time flows in networks." Mathematics of Operations Research. Vol. 15, No. 4, 1990, pp. 640-661.
[14]
Anderson, Edward J., and Andrew B. Philpott. “Optimisation of flows in networks over time.” Probability, Statistics and Optimisation, F. P. Kelly, ed., Wiley, New York, ch. 27, 1994, pp. 369-382.
[15]
Fleischer, Lisa, and Éva Tardos. "Efficient continuous-time dynamic network flow algorithms." Operations Research Letters. Vol. 23, No. 3-5, 1998, pp. 71-80.
[16]
Koch, Ronald, Ebrahim Nasrabadi, and Martin Skutella. "Continuous and discrete flows over time." Mathematical Methods of Operations Research. Vol. 73, No. 3, 2011, pp. 301.
[17]
Hashemi, S. Mehdi, and Ebrahim Nasrabadi. "On solving continuous-time dynamic network flows." Journal of Global Optimization. Vol. 53, No. 3, 2012, pp. 497-524.
[18]
Khadka, Shree Ram, and Phanindra Prasad Bhandari. "Dynamic network contraflow evacuation planning problem with continuous time approach." International Journal of Operations Research. Vol. 14, No. 1, 2017, pp. 27-34.
[19]
Pyakurel, Urmila, and Tanka Nath Dhamala. "Continuous dynamic contraflow approach for evacuation planning." Annals of Operations Research. Vol. 253, No. 1, 2017, pp. 573-598.
[20]
Gale, David. "Transient flows in networks." The Michigan Mathematical Journal. Vol. 6, No. 1, 1959, pp. 59-63.
[21]
Minieka, Edward. "Maximal, lexicographic, and dynamic network flows." Operations Research. Vol. 21, No. 2, 1973, pp. 517-527.
[22]
Wilkinson, William L. "An algorithm for universal maximal dynamic flows in a network." Operations Research. Vol. 19, No. 7, 1971, pp. 1602-1612.
[23]
Hoppe, Bruce. “Efficient dynamic network flow algorithms.” PhD diss., Cornell University, 1995.
[24]
Hoppe, Bruce, and Éva Tardos. "Polynomial time algorithms for some evacuation problems." In SODA. Vol. 94, 1994, pp. 433-441.
[25]
Baumann, Nadine. "Evacuation by earliest arrival flows." PhD diss., University of Dortmund, Germany, 2007.
[26]
Ruzika, Stefan, Heike Sperber, and Mechthild Steiner. "Earliest arrival flows on series-parallel graphs." Networks. Vol. 57, No. 2, 2011, pp. 169-173.
[27]
Dhamala, Tanka Nath, and Urmila Pyakurel. "Earliest arrival contraflow problem on series-parallel graphs." International Journal of Operations Research. Vol. 10, No. 1, 2013, pp. 1-13.
[28]
Dhungana, Ram Chandra and Tanka Nath Dhamala. “Maximum FlowLoc problems with network reconfiguration, International Journal of Operations Research. Vol. 16, No. 1, 2019, pp. 13–26.
[29]
Dhungana, Ram Chandra, Urmila Pyakurel and Tanka Nath Dhamala. “Abstract contraflow models and solution procedures for evacuation planning.” Journal of Mathematics Research. Vol. 10, No. 4, 2018, pp. 89–100.
[30]
Pyakurel, Urmila, Hari Nandan Nath and Tanka Nath Dhamala. “Partial contraflow with path reversals for evacuation planning.” Annals of Operations Research. Vol. 283, No. 1-2, 2019, pp. 591–612.