September  2011, 6(3): 443-464. doi: 10.3934/nhm.2011.6.443

Evacuation dynamics influenced by spreading hazardous material

1. 

Department of Mathematics, University of Mannheim, D-68131 Mannheim, Germany

2. 

Department of Mathematics, TU Kaiserslautern, D-67663 Kaiserslautern, Germany, Germany, Germany, Germany

Received  December 2010 Revised  July 2011 Published  August 2011

In this article, an evacuation model describing the egress in case of danger is considered. The underlying evacuation model is based on continuous network flows, while the spread of some gaseous hazardous material relies on an advection-diffusion equation. The contribution of this work is twofold. First, we introduce a continuous model coupled to the propagation of hazardous material where special cost functions allow for incorporating the predicted spread into an optimal planning of the egress. Optimality can thereby be understood with respect to two different measures: fastest egress and safest evacuation. Since this modeling approach leads to a pde/ode-restricted optimization problem, the continuous model is transferred into a discrete network flow model under some linearity assumptions. Second, it is demonstrated that this reformulation results in an efficient algorithm always leading to the global optimum. A computational case study shows benefits and drawbacks of the models for different evacuation scenarios.
Citation: Simone Göttlich, Sebastian Kühn, Jan Peter Ohst, Stefan Ruzika, Markus Thiemann. Evacuation dynamics influenced by spreading hazardous material. Networks & Heterogeneous Media, 2011, 6 (3) : 443-464. doi: 10.3934/nhm.2011.6.443
References:
[1]

R. K. Ahuja, T. L. Mananti and J. B. Orlin, "Network Flows: Theory, Algorithms, and Applications,", Prentice Hall, (1993). Google Scholar

[2]

D. Armbruster, P. Degond and C. Ringhofer, A model for the dynamics of large queuing networks and supply chains,, SIAM J. on Applied Mathematics, 66 (2006), 896. doi: 10.1137/040604625. Google Scholar

[3]

R. E. Burkard, K. Dlaska and B. Klinz, The quickest flow problem,, Z. Oper. Research, 37 (1993), 31. Google Scholar

[4]

L. G. Chalmet, R. L. Francis and P. B. Saunders, Network models for building evacuation,, Fire Technology, 18 (1982), 90. doi: 10.1007/BF02993491. Google Scholar

[5]

W. Choi, H. W. Hamacher and S. Tufekci, Modeling of building evacuation problems by network flows with side constraints,, European Journal of Operational Research, 35 (1988), 98. doi: 10.1016/0377-2217(88)90382-7. Google Scholar

[6]

G. M. Coclite, M. Garavello and B. Piccoli, Traffic flow on a road network,, SIAM Journal on Mathematical Analysis, 36 (2005), 1862. doi: 10.1137/S0036141004402683. Google Scholar

[7]

C. D'Apice, S. Göttlich, M. Herty and B. Piccoli, "Modeling, Simulation and Optimization of Supply Chains: A Continuous Approach,", SIAM, (2010). Google Scholar

[8]

L. Fleischer and É. Tardos, Efficient continuous-time dynamic network flow algorithms,, Operations Research Letters, 23 (1998), 71. doi: 10.1016/S0167-6377(98)00037-6. Google Scholar

[9]

L. R. Ford and D. R. Fulkerson, Constructing maximal dynamic flows from static flows,, Operations Research, 6 (1958), 419. doi: 10.1287/opre.6.3.419. Google Scholar

[10]

A. Fügenschuh, S. Göttlich, M. Herty, A. Klar and A. Martin, A discrete optimization approach to large scale supply networks based on partial differential equations,, SIAM Journal on Scientific Computing, 30 (2008), 1490. Google Scholar

[11]

A. Fügenschuh, M. Herty, A. Klar and A. Martin, Combinatorial and continuous models for the optimization of traffic flows on networks,, SIAM Journal on Optimization, 16 (2006), 1155. doi: 10.1137/040605503. Google Scholar

[12]

S. Göttlich, M. Herty and A. Klar, Network models for supply chains,, Communications in Mathematical Sciences, 3 (2005), 545. Google Scholar

[13]

E. Graat, C. Midden and P. Bockholts, Complex evacuation; effects of motivation level and slope of stairs on emergency egress time in a sports stadium,, Safety Science, 31 (1999), 127. doi: 10.1016/S0925-7535(98)00061-7. Google Scholar

[14]

S. Gwynne, E. R. Galea, M. Owen, P. J. Lawrence and L. Filippidis, A review of the methodologies used in evacuation modelling,, Fire and Materials, 23 (1999), 383. doi: 10.1002/(SICI)1099-1018(199911/12)23:6<383::AID-FAM715>3.0.CO;2-2. Google Scholar

[15]

H. W. Hamacher, S. Heller, G. Köster and W. Klein, A Sandwich Approach for Evacuation Time Bounds,, in, (2011), 503. doi: 10.1007/978-1-4419-9725-8_45. Google Scholar

[16]

H. W. Hamacher, K. Leiner and S. Ruzika, Quickest Cluster Flow Problems,, in, (2011), 327. doi: 10.1007/978-1-4419-9725-8_30. Google Scholar

[17]

H. W. Hamacher and S. A. Tjandra, Eariest arrival flows with time dependent capacity for solving evacuation problems,, in, (2002), 267. Google Scholar

[18]

H. W. Hamacher and S. A. Tjandra, Mathematical modelling of evacuation problems-a state of the art,, in, (2002), 227. Google Scholar

[19]

D. Helbing, A mathematical model for the behavior of pedestrians,, Behavioral Science, 36 (1991), 298. doi: 10.1002/bs.3830360405. Google Scholar

[20]

M. Herty and A. Klar, Modeling, simulation, and optimization of traffic flow networks,, SIAM Journal on Scientific Computing, 25 (2003), 1066. Google Scholar

[21]

H. Holden and N. H. Risebro, A mathematical model of traffic flow on a network of unidirectional roads,, SIAM Journal on Mathematical Analysis, 26 (1995), 999. doi: 10.1137/S0036141093243289. Google Scholar

[22]

S. P. Hoogendoorn and P. H. L. Bovy, Gas-kinetic modeling and simulaton of pedestrian flows,, Transportation Research Record, (2000), 28. doi: 10.3141/1710-04. Google Scholar

[23]

R. Hughes, A continuum theory for the flow of pedestrians,, Transportation Research Part B, 36 (2002), 507. doi: 10.1016/S0191-2615(01)00015-7. Google Scholar

[24]

C. Kirchner, M. Herty, S. Göttlich and A. Klar, Optimal control for continuous supply network models,, Networks Heterogenous Media, 1 (2006), 675. doi: 10.3934/nhm.2006.1.675. Google Scholar

[25]

H. Klüpfel, M. Schreckenberg and T. Meyer-König, "Models for Crowd Movement and Egress Simulation,", Traffic and Granular Flow '03, (2005), 357. Google Scholar

[26]

A. Kneidl, M. Thiemann, A. Borrmann, S. Ruzika, H. W. Hamacher, G. Köster and E. Rank, Bidirectional Coupling of Macroscopic and Microscopic Approaches for Pedestrian Behavior Prediction,, in, (2011), 459. doi: 10.1007/978-1-4419-9725-8_41. Google Scholar

[27]

E. Köhler, K. Langkau and M. Skutella, "Time-Expanded Graphs for Flow-Dependent Transit Times,", Lecture Notes in Computer Science, 2461 (2002), 599. Google Scholar

[28]

E. Köhler and M. Skutella, Flows over time with load-dependent transit times,, SIAM Journal on Optimization, 15 (2005), 1185. doi: 10.1137/S1052623403432645. Google Scholar

[29]

C. D. Laird, L. T. Biegler and B. G. van Bloemen Waanders, Real-time, large-scale optimization of water network systems using a subdomain approach,, in, (2007), 289. doi: 10.1137/1.9780898718935.ch15. Google Scholar

[30]

C. D. Laird, L. T. Biegler, B. G. van Bloemen Waanders and R. A. Bartlett, Contaminant source determination for water networks,, Journal of Water Resources Planning and Management, 131 (2005), 125. doi: 10.1061/(ASCE)0733-9496(2005)131:2(125). Google Scholar

[31]

O. Østerby, Five ways of reducing the Crank-Nicolson oscillations,, BIT Numerical Mathematics, 43 (2003), 811. doi: 10.1023/B:BITN.0000009942.00540.94. Google Scholar

[32]

C. E. Pearson, Impulsive end condition for diffusion equation,, Mathematics of Computation, 19 (1965), 570. doi: 10.1090/S0025-5718-1965-0193765-5. Google Scholar

[33]

B. Rajewsky, "Strahlendosis und Strahlenwirkung,", Thieme, (1954). Google Scholar

[34]

G. Santos and B. Aguirre, "A Critical Review of Emergency Evacuation Simulation,", Proceedings of Building Occupant Movement during Fire Emergencies, (2004), 10. Google Scholar

[35]

A. Schadschneider, W. Klingsch, H. Klüpfel, T. Kretz, C. Rogsch and A. Seyfried, Evacuation dynamics: Empirical results, modeling and applications,, in, (2009), 3142. Google Scholar

[36]

J. G. Siek, L.-Q. Lee and A. Lumsdaine, "The Boost Graph Library: User Guide and Reference Manual (C++ In-Depth Series),", Addison-Wesley, (2001). Google Scholar

[37]

M. Skutella, "An Introduction to Network Flows Over Time,", Research Trends in Combinatorial Optimization, (2009), 451. Google Scholar

[38]

F. Southworth, "Regional Evacuation Modeling: A State-of-the-Art Review,", ORNL/TAM-11740, (1991). doi: 10.2172/814579. Google Scholar

[39]

, IBM ILOG CPLEX Optimization Studio,, Cplex version 12, (2010). Google Scholar

show all references

References:
[1]

R. K. Ahuja, T. L. Mananti and J. B. Orlin, "Network Flows: Theory, Algorithms, and Applications,", Prentice Hall, (1993). Google Scholar

[2]

D. Armbruster, P. Degond and C. Ringhofer, A model for the dynamics of large queuing networks and supply chains,, SIAM J. on Applied Mathematics, 66 (2006), 896. doi: 10.1137/040604625. Google Scholar

[3]

R. E. Burkard, K. Dlaska and B. Klinz, The quickest flow problem,, Z. Oper. Research, 37 (1993), 31. Google Scholar

[4]

L. G. Chalmet, R. L. Francis and P. B. Saunders, Network models for building evacuation,, Fire Technology, 18 (1982), 90. doi: 10.1007/BF02993491. Google Scholar

[5]

W. Choi, H. W. Hamacher and S. Tufekci, Modeling of building evacuation problems by network flows with side constraints,, European Journal of Operational Research, 35 (1988), 98. doi: 10.1016/0377-2217(88)90382-7. Google Scholar

[6]

G. M. Coclite, M. Garavello and B. Piccoli, Traffic flow on a road network,, SIAM Journal on Mathematical Analysis, 36 (2005), 1862. doi: 10.1137/S0036141004402683. Google Scholar

[7]

C. D'Apice, S. Göttlich, M. Herty and B. Piccoli, "Modeling, Simulation and Optimization of Supply Chains: A Continuous Approach,", SIAM, (2010). Google Scholar

[8]

L. Fleischer and É. Tardos, Efficient continuous-time dynamic network flow algorithms,, Operations Research Letters, 23 (1998), 71. doi: 10.1016/S0167-6377(98)00037-6. Google Scholar

[9]

L. R. Ford and D. R. Fulkerson, Constructing maximal dynamic flows from static flows,, Operations Research, 6 (1958), 419. doi: 10.1287/opre.6.3.419. Google Scholar

[10]

A. Fügenschuh, S. Göttlich, M. Herty, A. Klar and A. Martin, A discrete optimization approach to large scale supply networks based on partial differential equations,, SIAM Journal on Scientific Computing, 30 (2008), 1490. Google Scholar

[11]

A. Fügenschuh, M. Herty, A. Klar and A. Martin, Combinatorial and continuous models for the optimization of traffic flows on networks,, SIAM Journal on Optimization, 16 (2006), 1155. doi: 10.1137/040605503. Google Scholar

[12]

S. Göttlich, M. Herty and A. Klar, Network models for supply chains,, Communications in Mathematical Sciences, 3 (2005), 545. Google Scholar

[13]

E. Graat, C. Midden and P. Bockholts, Complex evacuation; effects of motivation level and slope of stairs on emergency egress time in a sports stadium,, Safety Science, 31 (1999), 127. doi: 10.1016/S0925-7535(98)00061-7. Google Scholar

[14]

S. Gwynne, E. R. Galea, M. Owen, P. J. Lawrence and L. Filippidis, A review of the methodologies used in evacuation modelling,, Fire and Materials, 23 (1999), 383. doi: 10.1002/(SICI)1099-1018(199911/12)23:6<383::AID-FAM715>3.0.CO;2-2. Google Scholar

[15]

H. W. Hamacher, S. Heller, G. Köster and W. Klein, A Sandwich Approach for Evacuation Time Bounds,, in, (2011), 503. doi: 10.1007/978-1-4419-9725-8_45. Google Scholar

[16]

H. W. Hamacher, K. Leiner and S. Ruzika, Quickest Cluster Flow Problems,, in, (2011), 327. doi: 10.1007/978-1-4419-9725-8_30. Google Scholar

[17]

H. W. Hamacher and S. A. Tjandra, Eariest arrival flows with time dependent capacity for solving evacuation problems,, in, (2002), 267. Google Scholar

[18]

H. W. Hamacher and S. A. Tjandra, Mathematical modelling of evacuation problems-a state of the art,, in, (2002), 227. Google Scholar

[19]

D. Helbing, A mathematical model for the behavior of pedestrians,, Behavioral Science, 36 (1991), 298. doi: 10.1002/bs.3830360405. Google Scholar

[20]

M. Herty and A. Klar, Modeling, simulation, and optimization of traffic flow networks,, SIAM Journal on Scientific Computing, 25 (2003), 1066. Google Scholar

[21]

H. Holden and N. H. Risebro, A mathematical model of traffic flow on a network of unidirectional roads,, SIAM Journal on Mathematical Analysis, 26 (1995), 999. doi: 10.1137/S0036141093243289. Google Scholar

[22]

S. P. Hoogendoorn and P. H. L. Bovy, Gas-kinetic modeling and simulaton of pedestrian flows,, Transportation Research Record, (2000), 28. doi: 10.3141/1710-04. Google Scholar

[23]

R. Hughes, A continuum theory for the flow of pedestrians,, Transportation Research Part B, 36 (2002), 507. doi: 10.1016/S0191-2615(01)00015-7. Google Scholar

[24]

C. Kirchner, M. Herty, S. Göttlich and A. Klar, Optimal control for continuous supply network models,, Networks Heterogenous Media, 1 (2006), 675. doi: 10.3934/nhm.2006.1.675. Google Scholar

[25]

H. Klüpfel, M. Schreckenberg and T. Meyer-König, "Models for Crowd Movement and Egress Simulation,", Traffic and Granular Flow '03, (2005), 357. Google Scholar

[26]

A. Kneidl, M. Thiemann, A. Borrmann, S. Ruzika, H. W. Hamacher, G. Köster and E. Rank, Bidirectional Coupling of Macroscopic and Microscopic Approaches for Pedestrian Behavior Prediction,, in, (2011), 459. doi: 10.1007/978-1-4419-9725-8_41. Google Scholar

[27]

E. Köhler, K. Langkau and M. Skutella, "Time-Expanded Graphs for Flow-Dependent Transit Times,", Lecture Notes in Computer Science, 2461 (2002), 599. Google Scholar

[28]

E. Köhler and M. Skutella, Flows over time with load-dependent transit times,, SIAM Journal on Optimization, 15 (2005), 1185. doi: 10.1137/S1052623403432645. Google Scholar

[29]

C. D. Laird, L. T. Biegler and B. G. van Bloemen Waanders, Real-time, large-scale optimization of water network systems using a subdomain approach,, in, (2007), 289. doi: 10.1137/1.9780898718935.ch15. Google Scholar

[30]

C. D. Laird, L. T. Biegler, B. G. van Bloemen Waanders and R. A. Bartlett, Contaminant source determination for water networks,, Journal of Water Resources Planning and Management, 131 (2005), 125. doi: 10.1061/(ASCE)0733-9496(2005)131:2(125). Google Scholar

[31]

O. Østerby, Five ways of reducing the Crank-Nicolson oscillations,, BIT Numerical Mathematics, 43 (2003), 811. doi: 10.1023/B:BITN.0000009942.00540.94. Google Scholar

[32]

C. E. Pearson, Impulsive end condition for diffusion equation,, Mathematics of Computation, 19 (1965), 570. doi: 10.1090/S0025-5718-1965-0193765-5. Google Scholar

[33]

B. Rajewsky, "Strahlendosis und Strahlenwirkung,", Thieme, (1954). Google Scholar

[34]

G. Santos and B. Aguirre, "A Critical Review of Emergency Evacuation Simulation,", Proceedings of Building Occupant Movement during Fire Emergencies, (2004), 10. Google Scholar

[35]

A. Schadschneider, W. Klingsch, H. Klüpfel, T. Kretz, C. Rogsch and A. Seyfried, Evacuation dynamics: Empirical results, modeling and applications,, in, (2009), 3142. Google Scholar

[36]

J. G. Siek, L.-Q. Lee and A. Lumsdaine, "The Boost Graph Library: User Guide and Reference Manual (C++ In-Depth Series),", Addison-Wesley, (2001). Google Scholar

[37]

M. Skutella, "An Introduction to Network Flows Over Time,", Research Trends in Combinatorial Optimization, (2009), 451. Google Scholar

[38]

F. Southworth, "Regional Evacuation Modeling: A State-of-the-Art Review,", ORNL/TAM-11740, (1991). doi: 10.2172/814579. Google Scholar

[39]

, IBM ILOG CPLEX Optimization Studio,, Cplex version 12, (2010). Google Scholar

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

Dirk Helbing, Jan Siegmeier, Stefan Lämmer. Self-organized network flows. Networks & Heterogeneous Media, 2007, 2 (2) : 193-210. doi: 10.3934/nhm.2007.2.193

[3]

King Hann Lim, Hong Hui Tan, Hendra G. Harno. Approximate greatest descent in neural network optimization. Numerical Algebra, Control & Optimization, 2018, 8 (3) : 327-336. doi: 10.3934/naco.2018021

[4]

Haiying Liu, Xinxing Luo, Wenjie Bi, Yueming Man, Kok Lay Teo. Dynamic pricing of network goods in duopoly markets with boundedly rational consumers. Journal of Industrial & Management Optimization, 2017, 13 (1) : 429-447. doi: 10.3934/jimo.2016025

[5]

Shi'an Wang, N. U. Ahmed. Optimum management of the network of city bus routes based on a stochastic dynamic model. Journal of Industrial & Management Optimization, 2019, 15 (2) : 619-631. doi: 10.3934/jimo.2018061

[6]

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

[7]

Yi-Kuei Lin, Cheng-Ta Yeh. Reliability optimization of component assignment problem for a multistate network in terms of minimal cuts. Journal of Industrial & Management Optimization, 2011, 7 (1) : 211-227. doi: 10.3934/jimo.2011.7.211

[8]

Li Gang. An optimization detection algorithm for complex intrusion interference signal in mobile wireless network. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1371-1384. doi: 10.3934/dcdss.2019094

[9]

Bruce D. Craven, Sardar M. N. Islam. Dynamic optimization models in finance: Some extensions to the framework, models, and computation. Journal of Industrial & Management Optimization, 2014, 10 (4) : 1129-1146. doi: 10.3934/jimo.2014.10.1129

[10]

Reetabrata Mookherjee, Benjamin F. Hobbs, Terry L. Friesz, Matthew A. Rigdon. Dynamic oligopolistic competition on an electric power network with ramping costs and joint sales constraints. Journal of Industrial & Management Optimization, 2008, 4 (3) : 425-452. doi: 10.3934/jimo.2008.4.425

[11]

Hongming Yang, C. Y. Chung, Xiaojiao Tong, Pingping Bing. Research on dynamic equilibrium of power market with complex network constraints based on nonlinear complementarity function. Journal of Industrial & Management Optimization, 2008, 4 (3) : 617-630. doi: 10.3934/jimo.2008.4.617

[12]

Fengqiu Liu, Xiaoping Xue. Subgradient-based neural network for nonconvex optimization problems in support vector machines with indefinite kernels. Journal of Industrial & Management Optimization, 2016, 12 (1) : 285-301. doi: 10.3934/jimo.2016.12.285

[13]

Qiong Liu, Ahmad Reza Rezaei, Kuan Yew Wong, Mohammad Mahdi Azami. Integrated modeling and optimization of material flow and financial flow of supply chain network considering financial ratios. Numerical Algebra, Control & Optimization, 2019, 9 (2) : 113-132. doi: 10.3934/naco.2019009

[14]

Yang Chen, Xiaoguang Xu, Yong Wang. Wireless sensor network energy efficient coverage method based on intelligent optimization algorithm. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 887-900. doi: 10.3934/dcdss.2019059

[15]

Jian-Wu Xue, Xiao-Kun Xu, Feng Zhang. Big data dynamic compressive sensing system architecture and optimization algorithm for internet of things. Discrete & Continuous Dynamical Systems - S, 2015, 8 (6) : 1401-1414. doi: 10.3934/dcdss.2015.8.1401

[16]

Jiangtao Mo, Liqun Qi, Zengxin Wei. A network simplex algorithm for simple manufacturing network model. Journal of Industrial & Management Optimization, 2005, 1 (2) : 251-273. doi: 10.3934/jimo.2005.1.251

[17]

Konstantin Avrachenkov, Giovanni Neglia, Vikas Vikram Singh. Network formation games with teams. Journal of Dynamics & Games, 2016, 3 (4) : 303-318. doi: 10.3934/jdg.2016016

[18]

Joanna Tyrcha, John Hertz. Network inference with hidden units. Mathematical Biosciences & Engineering, 2014, 11 (1) : 149-165. doi: 10.3934/mbe.2014.11.149

[19]

T. S. Evans, A. D. K. Plato. Network rewiring models. Networks & Heterogeneous Media, 2008, 3 (2) : 221-238. doi: 10.3934/nhm.2008.3.221

[20]

David J. Aldous. A stochastic complex network model. Electronic Research Announcements, 2003, 9: 152-161.

2018 Impact Factor: 0.871

Metrics

  • PDF downloads (11)
  • HTML views (0)
  • Cited by (7)

[Back to Top]