• Previous Article
    Optimal consumption with reference-dependent preferences in on-the-job search and savings
  • JIMO Home
  • This Issue
  • Next Article
    Solution continuity of parametric generalized vector equilibrium problems with strictly pseudomonotone mappings
January  2017, 13(1): 489-503. doi: 10.3934/jimo.2016028

Evacuation planning by earliest arrival contraflow

Central Departments of Mathematics IOST Tribhuvan University, Kathmandu, Nepal

Received  June 2015 Published  March 2016

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

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.

Citation: Urmila Pyakurel, Tanka Nath Dhamala. Evacuation planning by earliest arrival contraflow. Journal of Industrial & Management Optimization, 2017, 13 (1) : 489-503. doi: 10.3934/jimo.2016028
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.  Google Scholar

[2]

A. Arulselvan, Network model for disaster management, PhD Thesis, University of Florida, USA, 2009. Google Scholar

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

[4]

R. E. BurkardK. Dlaska and B. Klinz, The quickest flow problem, ZOR-Methods and Models of Operations Research, 37 (1993), 31-58.  doi: 10.1007/BF01415527.  Google Scholar

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

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

[7]

T. N. Dhamala and U. Pyakurel, Earliest arrival contraflow problem on series-parallel graphs, International Journal of Operations Research, 10 (2013), 1-13.   Google Scholar

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

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

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

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

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

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

[14]

J. -P. W. Kappmeier, Generalizations of Flows Over Time with Application in Evacuation Optimization, PhD Thesis, Technical University, Berlin, Germany, 2015. Google Scholar

[15]

S. KimS. Shekhar and M. Min, Contraflow transportation network reconfiguration for evacuation route planning, IEEE Transactions on Knowledge and Data Engineering, 20 (2008), 1-15.   Google Scholar

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

[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).  Google Scholar

[18]

E. Minieka, Maximal, lexicographic, and dynamic network flows, Operations Research, 21 (1973), 517-527.  doi: 10.1287/opre.21.2.517.  Google Scholar

[19]

U. PyakurelH. W. Hamacher and T. N. Dhamala, Generalized maximum dynamic contraflow on lossy network, International Journal of Operations Research Nepal, 3 (2014), 27-44.   Google Scholar

[20]

U. Pyakurel and T. N. Dhamala, Earliest arrival contraflow model for evacuation planning, Neural, Parallel, and Scientific Computations, 22 (2014), 287-294.   Google Scholar

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

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

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

[24]

S. RebennackA. ArulselvanL. 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.  Google Scholar

[25]

S. RuzikaH. Sperber and M. Steiner, Earliest arrival flows on series-parallel graphs, Networks, 10 (2011), 169-173.  doi: 10.1002/net.20398.  Google Scholar

[26]

M. Schmidt and M. Skutella, Earliest arrival flows in networks with multiple sinks, Electronics Notes in Discrete Mathematics, 36 (2010), 607-614.   Google Scholar

[27]

H. Tuydes and A. Ziliaskopoulos, Network re-design to optimize evacuation contraflow, in Proceedings 83rd Ann. Meeting of the Transportation Research Board, 2004. Google Scholar

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

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

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

show all references

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.  Google Scholar

[2]

A. Arulselvan, Network model for disaster management, PhD Thesis, University of Florida, USA, 2009. Google Scholar

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

[4]

R. E. BurkardK. Dlaska and B. Klinz, The quickest flow problem, ZOR-Methods and Models of Operations Research, 37 (1993), 31-58.  doi: 10.1007/BF01415527.  Google Scholar

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

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

[7]

T. N. Dhamala and U. Pyakurel, Earliest arrival contraflow problem on series-parallel graphs, International Journal of Operations Research, 10 (2013), 1-13.   Google Scholar

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

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

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

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

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

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

[14]

J. -P. W. Kappmeier, Generalizations of Flows Over Time with Application in Evacuation Optimization, PhD Thesis, Technical University, Berlin, Germany, 2015. Google Scholar

[15]

S. KimS. Shekhar and M. Min, Contraflow transportation network reconfiguration for evacuation route planning, IEEE Transactions on Knowledge and Data Engineering, 20 (2008), 1-15.   Google Scholar

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

[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).  Google Scholar

[18]

E. Minieka, Maximal, lexicographic, and dynamic network flows, Operations Research, 21 (1973), 517-527.  doi: 10.1287/opre.21.2.517.  Google Scholar

[19]

U. PyakurelH. W. Hamacher and T. N. Dhamala, Generalized maximum dynamic contraflow on lossy network, International Journal of Operations Research Nepal, 3 (2014), 27-44.   Google Scholar

[20]

U. Pyakurel and T. N. Dhamala, Earliest arrival contraflow model for evacuation planning, Neural, Parallel, and Scientific Computations, 22 (2014), 287-294.   Google Scholar

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

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

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

[24]

S. RebennackA. ArulselvanL. 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.  Google Scholar

[25]

S. RuzikaH. Sperber and M. Steiner, Earliest arrival flows on series-parallel graphs, Networks, 10 (2011), 169-173.  doi: 10.1002/net.20398.  Google Scholar

[26]

M. Schmidt and M. Skutella, Earliest arrival flows in networks with multiple sinks, Electronics Notes in Discrete Mathematics, 36 (2010), 607-614.   Google Scholar

[27]

H. Tuydes and A. Ziliaskopoulos, Network re-design to optimize evacuation contraflow, in Proceedings 83rd Ann. Meeting of the Transportation Research Board, 2004. Google Scholar

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

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

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

Figure 1.  Two sources and single sink small MDCF scenario and its solution
Figure 2.  Non-existence of earliest arrival contraflow on multiple sinks
Figure 3.  EACF solution does not always exist on multiple terminal networks
Figure 4.  Existence of earliest arrival contraflow on multiple sinks
[1]

Hanyu Gu, Hue Chi Lam, Yakov Zinder. Planning rolling stock maintenance: Optimization of train arrival dates at a maintenance center. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020177

[2]

Hongguang Ma, Xiang Li. Multi-period hazardous waste collection planning with consideration of risk stability. Journal of Industrial & Management Optimization, 2021, 17 (1) : 393-408. doi: 10.3934/jimo.2019117

[3]

Jie Li, Xiangdong Ye, Tao Yu. Mean equicontinuity, complexity and applications. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 359-393. doi: 10.3934/dcds.2020167

[4]

Zi Xu, Siwen Wang, Jinjin Huang. An efficient low complexity algorithm for box-constrained weighted maximin dispersion problem. Journal of Industrial & Management Optimization, 2021, 17 (2) : 971-979. doi: 10.3934/jimo.2020007

[5]

Shuxing Chen, Jianzhong Min, Yongqian Zhang. Weak shock solution in supersonic flow past a wedge. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 115-132. doi: 10.3934/dcds.2009.23.115

[6]

Caterina Balzotti, Simone Göttlich. A two-dimensional multi-class traffic flow model. Networks & Heterogeneous Media, 2020  doi: 10.3934/nhm.2020034

[7]

Shuang Liu, Yuan Lou. A functional approach towards eigenvalue problems associated with incompressible flow. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3715-3736. doi: 10.3934/dcds.2020028

[8]

Pablo D. Carrasco, Túlio Vales. A symmetric Random Walk defined by the time-one map of a geodesic flow. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020390

[9]

Joan Carles Tatjer, Arturo Vieiro. Dynamics of the QR-flow for upper Hessenberg real matrices. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1359-1403. doi: 10.3934/dcdsb.2020166

[10]

Petr Pauš, Shigetoshi Yazaki. Segmentation of color images using mean curvature flow and parametric curves. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 1123-1132. doi: 10.3934/dcdss.2020389

[11]

Gui-Qiang Chen, Beixiang Fang. Stability of transonic shock-fronts in three-dimensional conical steady potential flow past a perturbed cone. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 85-114. doi: 10.3934/dcds.2009.23.85

[12]

Peter Frolkovič, Viera Kleinová. A new numerical method for level set motion in normal direction used in optical flow estimation. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 851-863. doi: 10.3934/dcdss.2020347

[13]

Kohei Nakamura. An application of interpolation inequalities between the deviation of curvature and the isoperimetric ratio to the length-preserving flow. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 1093-1102. doi: 10.3934/dcdss.2020385

[14]

Tetsuya Ishiwata, Takeshi Ohtsuka. Numerical analysis of an ODE and a level set methods for evolving spirals by crystalline eikonal-curvature flow. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 893-907. doi: 10.3934/dcdss.2020390

[15]

Imam Wijaya, Hirofumi Notsu. Stability estimates and a Lagrange-Galerkin scheme for a Navier-Stokes type model of flow in non-homogeneous porous media. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 1197-1212. doi: 10.3934/dcdss.2020234

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (166)
  • HTML views (476)
  • Cited by (6)

Other articles
by authors

[Back to Top]