• 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 and 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.

[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. BurkardK. 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. KimS. 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. PyakurelH. 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. 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.

[25]

S. RuzikaH. 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.

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.

[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. BurkardK. 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. KimS. 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. PyakurelH. 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. 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.

[25]

S. RuzikaH. 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.

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]

Hari Nandan Nath, Urmila Pyakurel, Tanka Nath Dhamala, Stephan Dempe. Dynamic network flow location models and algorithms for quickest evacuation planning. Journal of Industrial and Management Optimization, 2021, 17 (5) : 2943-2970. doi: 10.3934/jimo.2020102

[2]

Tanka Nath Dhamala. A survey on models and algorithms for discrete evacuation planning network problems. Journal of Industrial and Management Optimization, 2015, 11 (1) : 265-289. doi: 10.3934/jimo.2015.11.265

[3]

Hanyu Gu, Hue Chi Lam, Yakov Zinder. Planning rolling stock maintenance: Optimization of train arrival dates at a maintenance center. Journal of Industrial and Management Optimization, 2022, 18 (2) : 747-772. doi: 10.3934/jimo.2020177

[4]

Nicolas Boizot, Jean-Paul Gauthier. On the motion planning of the ball with a trailer. Mathematical Control and Related Fields, 2013, 3 (3) : 269-286. doi: 10.3934/mcrf.2013.3.269

[5]

Matthias Gerdts, René Henrion, Dietmar Hömberg, Chantal Landry. Path planning and collision avoidance for robots. Numerical Algebra, Control and Optimization, 2012, 2 (3) : 437-463. doi: 10.3934/naco.2012.2.437

[6]

Rafael Caballero, Trinidad Gomez, Julian Molina, Osvaldo Fosado, Maria A. Leon, Madelen Garofal, Beatriz Saavedra. Sawing planning using a multicriteria approach. Journal of Industrial and Management Optimization, 2009, 5 (2) : 303-317. doi: 10.3934/jimo.2009.5.303

[7]

Dragos-Patru Covei, Elena Cristina Canepa, Traian A. Pirvu. Stochastic production planning with regime switching. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022013

[8]

Xinwei Wang, Hai Wang, Hongyun Zhang, Min Wang, Lei Wang, Kaikai Cui, Chen Lu, Yu Ding. A mini review on UAV mission planning. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022089

[9]

Juan Carlos López Alfonso, Giuseppe Buttazzo, Bosco García-Archilla, Miguel A. Herrero, Luis Núñez. A class of optimization problems in radiotherapy dosimetry planning. Discrete and Continuous Dynamical Systems - B, 2012, 17 (6) : 1651-1672. doi: 10.3934/dcdsb.2012.17.1651

[10]

G. Idone, A. Maugeri. Variational inequalities and a transport planning for an elastic and continuum model. Journal of Industrial and Management Optimization, 2005, 1 (1) : 81-86. doi: 10.3934/jimo.2005.1.81

[11]

Mehmet Önal, H. Edwin Romeijn. Two-echelon requirements planning with pricing decisions. Journal of Industrial and Management Optimization, 2009, 5 (4) : 767-781. doi: 10.3934/jimo.2009.5.767

[12]

Yi Gao, Rui Li, Yingjing Shi, Li Xiao. Design of path planning and tracking control of quadrotor. Journal of Industrial and Management Optimization, 2022, 18 (3) : 2221-2235. doi: 10.3934/jimo.2021063

[13]

Ta-Wei Hung, Ping-Ting Chen. On the optimal replenishment in a finite planning horizon with learning effect of setup costs. Journal of Industrial and Management Optimization, 2010, 6 (2) : 425-433. doi: 10.3934/jimo.2010.6.425

[14]

Nan Liu, Yong Ye. Humanitarian logistics planning for natural disaster response with Bayesian information updates. Journal of Industrial and Management Optimization, 2014, 10 (3) : 665-689. doi: 10.3934/jimo.2014.10.665

[15]

F. Zeyenp Sargut, H. Edwin Romeijn. Capacitated requirements planning with pricing flexibility and general cost and revenue functions. Journal of Industrial and Management Optimization, 2007, 3 (1) : 87-98. doi: 10.3934/jimo.2007.3.87

[16]

Frédéric Gibou, Doron Levy, Carlos Cárdenas, Pingyu Liu, Arthur Boyer. Partial Differential Equations-Based Segmentation for Radiotherapy Treatment Planning. Mathematical Biosciences & Engineering, 2005, 2 (2) : 209-226. doi: 10.3934/mbe.2005.2.209

[17]

Qiong Liu, Jialiang Liu, Zhaorui Dong, Mengmeng Zhan, Zhen Mei, Baosheng Ying, Xinyu Shao. Integrated optimization of process planning and scheduling for reducing carbon emissions. Journal of Industrial and Management Optimization, 2021, 17 (3) : 1025-1055. doi: 10.3934/jimo.2020010

[18]

Jian Xiong, Zhongbao Zhou, Ke Tian, Tianjun Liao, Jianmai Shi. A multi-objective approach for weapon selection and planning problems in dynamic environments. Journal of Industrial and Management Optimization, 2017, 13 (3) : 1189-1211. doi: 10.3934/jimo.2016068

[19]

Lou Caccetta, Elham Mardaneh. Joint pricing and production planning for fixed priced multiple products with backorders. Journal of Industrial and Management Optimization, 2010, 6 (1) : 123-147. doi: 10.3934/jimo.2010.6.123

[20]

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

2021 Impact Factor: 1.411

Metrics

  • PDF downloads (386)
  • HTML views (482)
  • Cited by (7)

Other articles
by authors

[Back to Top]