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).

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

[3]

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

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

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

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

[7]

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

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

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

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

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

[12]

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

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

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

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

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

[17]

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

[18]

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

[19]

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

[20]

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

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

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

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

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

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

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

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

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

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

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

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

[32]

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

[33]

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

[34]

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

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

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

[37]

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

[38]

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

[39]

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

show all references

References:
[1]

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

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

[3]

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

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

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

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

[7]

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

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

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

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

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

[12]

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

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

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

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

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

[17]

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

[18]

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

[19]

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

[20]

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

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

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

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

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

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

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

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

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

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

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

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

[32]

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

[33]

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

[34]

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

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

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

[37]

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

[38]

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

[39]

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

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

2017 Impact Factor: 1.187

Metrics

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

[Back to Top]