Maximum Flow Evacuation Planning Problem  with Non-Conservation Flow Constraint

Phanindra Prasad Bhandari; Shree Ram Khadka

doi:10.21467/ias.10.1.25-32

Authors

Phanindra Prasad Bhandari Department of Science and Humanities, Khwopa Engineering College, Bhaktapur, Nepal https://orcid.org/0000-0001-6496-6873
Shree Ram Khadka Central Department of Mathematics, Tribhuvan University, Kathmandu, Nepal https://orcid.org/0000-0001-8581-8634

DOI:

https://doi.org/10.21467/ias.10.1.25-32

Abstract

The optimization model of the maximum flow evacuation planning problem efficiently sends a maximum number of evacuees along with the routes of their transshipment from the disastrous zone, the source, to the safe zone, the sink, over a given time horizon. The limitation of the problem with the flow conservation constraint at the intermediate nodes is that even one more evacuee cannot be sent out from the source, if the evacuee cannot reach the sink. However, evacuators must attempt to send out as many evacuees as possible to safer places despite the sink. There may be relatively safe places in between the source and the sink. The limitation is due to the flow conservation constraint. In this paper, we remodel the problem with non-conservation flow constraint and propose an efficient algorithm. With this approach one can send as many evacuees as in the flow conservation case from the source to the sink. Moreover, a maximum number of evacuees can also be sent to the relatively safe places in between the source and the sink. The routes of their transshipment can also be identified.

Keywords:

Evacuation Planning Problem, Pre-flow-push Algorithm, Network Flow, Disaster Management

Downloads

Download data is not yet available.

References

A. Kimms and K. C. Maassen, “Optimization and simulation of traffic flows in the case of evacuating urban areas”, OR Spectrum, vol. 33, pp. 571-593, 2011.

L. R. Ford and D. R. Fulkerson, “Maximal flow through a network”, Can. J. Math., 8, pp. 399-404, 1956.

L. R. Ford and D. R. Fulkerson, “Constructing maximal dynamic flows from static flows’, Operations Research, vol. 6, pp. 419-433, 1958.

L. R. Ford and D. R. Fulkerson, “Flows in Networks”, Princeton University Press, 1962.

J. Edmonds and R. M. Karp, “Theoretical improvements in algorithmic efficiency for network flow problems”, Journal of the Association for Computing Machinery, vol. 19, pp. 248-264, 1972.

E. A. Dinic, “Algorithm for solution of a problem of maximum flow in a network with power estimation”, Soviet Math. Dokl, vol. 11, pp. 1277-1280, 1970.

A. V. Goldberg and R. E. Tarjan, “A new approach to the maximum-flow problem”, Journal of the Association for Computing Machinery, vol. 35, pp. 921-940, 1988.

J. B. Orlin, "Max flows in O (nm) time, or better", In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pp. 765-774, 2013.

P. Kovacs, "Eﬃcient Algorithms for Graph Optimization Problems", PhD thesis, Eotvos Lorand University, Hungary, 2019.

H. W. Hamacher, S. Heller, W. Klein, G. Köster, and S. Ruzika, "A sandwich approach for evacuation time bounds", In Pedestrian and Evacuation Dynamics, pp. 503-513. Springer, Boston, MA, 2011.

A. Borrmann, A. Kneidl, G. Köster, S. Ruzika, and M. Thiemann, "Bidirectional coupling of macroscopic and microscopic pedestrian evacuation models", Safety science, vol. 50, pp. 1695-1703, 2012.

G. Borradaile, P. N. Klein, S. Mozes, Y. Nussbaum and C. Wulff-Nilsen, "Multiple-source multiple-sink maximum flow in directed planar graphs in near-linear time", SIAM Journal on Computing, vol. 46, pp. 1280-1303, 2017.

R. Burkard, K. Dlaska and B. Klinz, “The quickest flow problem”, ZOR-Methods and Models of Operations Research, vol. 37, pp. 31-58, 1993.

B. Hoppe, “Efficient Dynamic Network Flow Algorithms”, PhD Thesis, Cornell University, 1995.

D. Gale, “Transient flows in networks”, The Michigan Mathematical Journal, vol. 6, pp. 59-63, 1959.

E. Minieka, “Maximal, lexicographic, and dynamic network flows”, Operations Research, vol. 21, pp. 517-527, 1973.

W. L. Wilkinson, “An algorithm for universal maximal dynamic flows in a network”, Operations Research, vol. 19, pp. 1602-1612, 1971.

B. Hoppe and E. Tardos, “Polynomial time algorithms for some evacuation problems”, In Proccedings of 5th Ann. ACM-SIAM Symp. on Discrete Algorithms, pp. 433-441, 1994.

N. Baumann, “Evacuation by Earliest Arrival Flows”, PhD Thesis, University of Dortmund, Germany, 2007.

N. Baumann and M. Skutella, “Solving evacuation problems efficiently: earliest arrival flows with multiple sources”, In 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), pp. 399-410, 2006. IEEE.

N. Baumann and M. Skutella, “Earliest arrival flows with multiple sources”, Mathematics of Operations Research, vol. 34, pp. 499-512, 2009.

M. Steiner, “A Survey on Earliest Arrival Flows and a Study of the Series-parallel Case”, Diploma Thesis, University of Kaiserslautern, Germany, 2009.

S, Ruzika, H. Sperber and M. Steiner, “Earliest arrival flows on series-parallel graphs”, Networks, vol. 57, pp. 169-173, 2011.

S. A. Tjandra, “Dynamic Network Optimization with Application to the Evacuation Problem”, PhD Thesis, University of Kaiserslautern, Germany, 2003.

S. Rebennack, A. Arulselvan, L. Elefteriadou and P. M. Pardalos, “Complexity analysis of maximum flow problem with arc reversal”, Journal of Combinatorial Optimization, vol. 19, pp. 200-216, 2010.

T. N. Dhamala and U. Pyakurel, “Earliest arrival contraflow problem on series-parallel graphs”, International Journal of Operations Research, vol. 10, pp. 1-13, 2013.

U. Pyakurel, H. W. Hamacher and T. N. Dhamala, “Generalized maximum dynamic contraflow on lossy network”, International Journal of Operations Research Nepal, vol. 3, pp. 27-44, 2014.

U. Pyakurel and T. N. Dhamala, “Models and algorithms on contraflow evacuation planning network problems”, International Journal of Operations Research, vol. 12, pp. 36-46, 2015.

A. B. Philpott, “Algorithms for Continuous Network Flow Problems”, PhD Thesis, University of Cambridge, UK, 1982.

E. J. Anderson, P. Nash and A. B. Philpott, “A Class of Continuous Network Flow Problems”, Mathematics of Operations Research, vol. 7, pp. 501-514, 1982.

A. B. Philpott, “Continuous-time flows in networks”, Mathematics of Operations Research, vol. 15, pp. 640-661, 1990.

R. Koch, E. Nasrabadi and M. Skutella, “Continuous and discrete flows over time: a general model based on measure theory”, Mathematical Methods of Operations Research, vol. 73, pp. 301-337, 2011.

S. M. Hashemi and E. Nasrabadi, “On solving continuous-time dynamic network flows”, Journal of Global Optimization, vol. 53, pp. 497-524, 2012.

L. Fleischer and E. Tardos, “Efficient continuous-time dynamic network flow algorithms”, Operations Research Letters, vol. 23, pp. 71-80, 1998.

S. R. Khadka and P. P. Bhandari, “Dynamic network contraflow evacuation planning problem with continuous time approach”, International Journal of Operations Research, vol. 14, pp. 27-34, 2017.

U. Pyakurel and T. N. Dhamala, “Continuous dynamic contraflow approach for evacuation planning”, Annals of Operations Research, vol. 253, pp. 573-598, 2017.

M. Skutella, “An introduction to network flows over time”, In: Research trends in combinatorial optimization, pp. 451-482. Springer, Heidelberg 2009.

T. N. Dhamala, “A survey on models and algorithms for discrete evacuation planning network problems”, Journal of Industrial and Management Optimization, vol. 11, pp. 265-289, 2015.

S. R. Khadka and P. P. Bhandari, "Model and solution for non-conservation flow evacuation planning problem", The Nepali Mathematical Sciences Report, vol. 36, pp. 11-16, 2019.

D. D. Sleator and R. E. Tarjan, “A data structure for dynamic trees”, Journal of Computer and System Sciences, vol. 26, pp. 362-391, 1983.

R. K. Ahujia, T. L. Magnanti and J. B. Orlin, "Network Flows: Theory, Algorithms and Applications", New Jersey: Rentice-Hall, 1993.