Evacuation Contraflow Problems with Not Necessarily Equal Transit Time on Anti-parallel Arcs

Phanindra Prasad Bhandari; Shree Ram Khadka

doi:doi:10.11648/j.ajam.20200804.18

| Peer-Reviewed

Evacuation Contraflow Problems with Not Necessarily Equal Transit Time on Anti-parallel Arcs

Phanindra Prasad Bhandari, Shree Ram Khadka

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

Received: 27 July 2020 Accepted: 10 August 2020 Published: 17 August 2020

Views: Downloads:

Download PDF

Share This Article

Twitter
Linked In
Facebook

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.

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

Network Flow, Contraflow, TTSP Network, Evacuation Planning Problem, Disaster Management

References

[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.

Cite This Article

Plain Text BibTeX RIS

APA Style

Phanindra Prasad Bhandari, Shree Ram Khadka. (2020). Evacuation Contraflow Problems with Not Necessarily Equal Transit Time on Anti-parallel Arcs. American Journal of Applied Mathematics, 8(4), 230-235. https://doi.org/10.11648/j.ajam.20200804.18

Copy | Download

ACS Style

Phanindra Prasad Bhandari; Shree Ram Khadka. Evacuation Contraflow Problems with Not Necessarily Equal Transit Time on Anti-parallel Arcs. Am. J. Appl. Math. 2020, 8(4), 230-235. doi: 10.11648/j.ajam.20200804.18

Copy | Download

AMA Style

Phanindra Prasad Bhandari, Shree Ram Khadka. Evacuation Contraflow Problems with Not Necessarily Equal Transit Time on Anti-parallel Arcs. Am J Appl Math. 2020;8(4):230-235. doi: 10.11648/j.ajam.20200804.18

Copy | Download

@article{10.11648/j.ajam.20200804.18,
  author = {Phanindra Prasad Bhandari and Shree Ram Khadka},
  title = {Evacuation Contraflow Problems with Not Necessarily Equal Transit Time on Anti-parallel Arcs},
  journal = {American Journal of Applied Mathematics},
  volume = {8},
  number = {4},
  pages = {230-235},
  doi = {10.11648/j.ajam.20200804.18},
  url = {https://doi.org/10.11648/j.ajam.20200804.18},
  eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.ajam.20200804.18},
  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.},
 year = {2020}
}

Copy | Download

TY  - JOUR
T1  - Evacuation Contraflow Problems with Not Necessarily Equal Transit Time on Anti-parallel Arcs
AU  - Phanindra Prasad Bhandari
AU  - Shree Ram Khadka
Y1  - 2020/08/17
PY  - 2020
N1  - https://doi.org/10.11648/j.ajam.20200804.18
DO  - 10.11648/j.ajam.20200804.18
T2  - American Journal of Applied Mathematics
JF  - American Journal of Applied Mathematics
JO  - American Journal of Applied Mathematics
SP  - 230
EP  - 235
PB  - Science Publishing Group
SN  - 2330-006X
UR  - https://doi.org/10.11648/j.ajam.20200804.18
AB  - 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.
VL  - 8
IS  - 4
ER  -

Copy | Download

Author Information

Phanindra Prasad Bhandari

Central Department of Mathematics, Tribhuvan University, Kirtipur, Kathmandu, Nepal
Shree Ram Khadka

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

Download PDF

Sections

Plain Text BibTeX RIS

APA Style

Phanindra Prasad Bhandari, Shree Ram Khadka. (2020). Evacuation Contraflow Problems with Not Necessarily Equal Transit Time on Anti-parallel Arcs. American Journal of Applied Mathematics, 8(4), 230-235. https://doi.org/10.11648/j.ajam.20200804.18

Copy | Download

ACS Style

Phanindra Prasad Bhandari; Shree Ram Khadka. Evacuation Contraflow Problems with Not Necessarily Equal Transit Time on Anti-parallel Arcs. Am. J. Appl. Math. 2020, 8(4), 230-235. doi: 10.11648/j.ajam.20200804.18

Copy | Download

AMA Style

Phanindra Prasad Bhandari, Shree Ram Khadka. Evacuation Contraflow Problems with Not Necessarily Equal Transit Time on Anti-parallel Arcs. Am J Appl Math. 2020;8(4):230-235. doi: 10.11648/j.ajam.20200804.18

Copy | Download

@article{10.11648/j.ajam.20200804.18,
  author = {Phanindra Prasad Bhandari and Shree Ram Khadka},
  title = {Evacuation Contraflow Problems with Not Necessarily Equal Transit Time on Anti-parallel Arcs},
  journal = {American Journal of Applied Mathematics},
  volume = {8},
  number = {4},
  pages = {230-235},
  doi = {10.11648/j.ajam.20200804.18},
  url = {https://doi.org/10.11648/j.ajam.20200804.18},
  eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.ajam.20200804.18},
  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.},
 year = {2020}
}

Copy | Download

TY  - JOUR
T1  - Evacuation Contraflow Problems with Not Necessarily Equal Transit Time on Anti-parallel Arcs
AU  - Phanindra Prasad Bhandari
AU  - Shree Ram Khadka
Y1  - 2020/08/17
PY  - 2020
N1  - https://doi.org/10.11648/j.ajam.20200804.18
DO  - 10.11648/j.ajam.20200804.18
T2  - American Journal of Applied Mathematics
JF  - American Journal of Applied Mathematics
JO  - American Journal of Applied Mathematics
SP  - 230
EP  - 235
PB  - Science Publishing Group
SN  - 2330-006X
UR  - https://doi.org/10.11648/j.ajam.20200804.18
AB  - 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.
VL  - 8
IS  - 4
ER  -

Copy | Download