• Previous Article
    Solution continuity of parametric generalized vector equilibrium problems with strictly pseudomonotone mappings
  • JIMO Home
  • This Issue
  • Next Article
    Optimal consumption with reference-dependent preferences in on-the-job search and savings
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.

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

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

[2]

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

[3]

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

[4]

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

[5]

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 & Continuous Dynamical Systems - B, 2012, 17 (6) : 1651-1672. doi: 10.3934/dcdsb.2012.17.1651

[6]

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

[7]

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

[8]

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

[9]

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

[10]

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

[11]

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

[12]

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 & Management Optimization, 2017, 13 (3) : 1189-1211. doi: 10.3934/jimo.2016068

[13]

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

[14]

Tien-Fu Liang, Hung-Wen Cheng. Multi-objective aggregate production planning decisions using two-phase fuzzy goal programming method. Journal of Industrial & Management Optimization, 2011, 7 (2) : 365-383. doi: 10.3934/jimo.2011.7.365

[15]

Kegui Chen, Xinyu Wang, Min Huang, Wai-Ki Ching. Salesforce contract design, joint pricing and production planning with asymmetric overconfidence sales agent. Journal of Industrial & Management Optimization, 2017, 13 (2) : 873-899. doi: 10.3934/jimo.2016051

[16]

Zongmin Li, Jiuping Xu, Wenjing Shen, Benjamin Lev, Xiao Lei. Bilevel multi-objective construction site security planning with twofold random phenomenon. Journal of Industrial & Management Optimization, 2015, 11 (2) : 595-617. doi: 10.3934/jimo.2015.11.595

[17]

Tzu-Li Chen, James T. Lin, Shu-Cherng Fang. A shadow-price based heuristic for capacity planning of TFT-LCD manufacturing. Journal of Industrial & Management Optimization, 2010, 6 (1) : 209-239. doi: 10.3934/jimo.2010.6.209

[18]

Yi Jing, Wenchuan Li. Integrated recycling-integrated production - distribution planning for decentralized closed-loop supply chain. Journal of Industrial & Management Optimization, 2018, 14 (2) : 511-539. doi: 10.3934/jimo.2017058

[19]

Abdelghani Bouras, Ramdane Hedjar, Lotfi Tadj. Production planning in a three-stock reverse-logistics system with deteriorating items under a periodic review policy. Journal of Industrial & Management Optimization, 2016, 12 (3) : 1075-1089. doi: 10.3934/jimo.2016.12.1075

[20]

Abdelghani Bouras, Lotfi Tadj. Production planning in a three-stock reverse-logistics system with deteriorating items under a continuous review policy. Journal of Industrial & Management Optimization, 2015, 11 (4) : 1041-1058. doi: 10.3934/jimo.2015.11.1041

2018 Impact Factor: 1.025

Metrics

  • PDF downloads (25)
  • HTML views (296)
  • Cited by (2)

Other articles
by authors

[Back to Top]