IEEE/CAA Journal of Automatica Sinica  2018, Vol. 5 Issue(6): 1104-1112   PDF    
Optimization of Grouping Evacuation Strategy in High-rise Building Fires Based on Graph Theory and Computational Experiments
Yuling Hu1,2, Xiwei Liu3,4     
1. School of Electrical and Information Engineering, Beijing University of Civil Engineering and Architecture, Beijing 100044, China;
2. Beijing Key Laboratory of Intelligent Processing for Building Big Data, Beijing 100044, China;
3. State Key Laboratory for Management and Control for Complex Systems, Institute of Automation, Chinese Academy of Sciences, Beijing 100190, China;
4. Qingdao Academy of Intelligent Industries, Qingdao 266109, China
Abstract: It is difficult to rescue people from outside, and emergency evacuation is still a main measure to decrease casualties in high-rise building fires. To improve evacuation efficiency, a valid and easily manipulated grouping evacuation strategy is proposed. Occupants escape in groups according to the shortest evacuation route is determined by graph theory. In order to evaluate and find the optimal grouping, computational experiments are performed to design and simulate the evacuation processes. A case study shown the application in detail and quantitative research conclusions is obtained. The thoughts and approaches of this study can be used to guide actual high-rise building evacuation processes in future.
Key words: Computational experiments     grouping evacuation     graph theory     high-rise building fire     management strategies    

Building fire is still a serious catastrophe all over the world. On June 14th 2017, the London Grenfell Tower fire burned than 12 hours and resulted in 6 dead 74 person wounded [1]. For the height and complexity of high-rise building and chimney effect of fire, it is very difficult to rescue people from outside. Evacuation is still an important or even most effective way to escape and survive in high-rise building fires.

In order to improve the accuracy of evacuation imitation, representative evacuation models such as social force model [2], [3], cellular automata model [4], [5], agent-based model [6], [7] have been developed. In addition to these popular models, some optimization models including queuing model [8], network model [9], logit model [10], and field model [11], have been proposed in recent years. Along with the improvement of model, some optimization methods [12], [13], such as route planning algorithms [14], [15] have been studied too. However, these studies highlight at escaping of individuals and are deficiency in overall design or planning from the point of management view. And, because of computational complexity, they are mostly impossible to be applied in a real world.

There also have been some management strategy studies in other fields. For example, Tamima and Chouinard gave a framework for evacuation management planning in earthquake emergencies [16]. Epstein et al. provided management strategies for a metro station in China [17]. The idea of combining emergency scenarios to research the escaping strategy in large supermarket was proposed by Nguyen et al. [18]. Gan et al. gave the simulation based stochastic plans separately for traffic evacuation [19]. However, systematic studied of evacuation management strategies in high-rise building fires are still very few and quantitative research results are deficient.

In addition, in recent years some evacuees' behaviors, which have revealed important influence on evacuation processes, have been studies. For instance, Haghani and Sarvi studied the individual decision making by surrounding peers' behaviors and feedback from other individuals' movements and actions [20]. Cuesta et al. analyzed collective behavior among evacuees reflecting the social interaction between evacuees [21]. The extent of these impacts has not been very clear, but it all reflects the psychological tendency of "following the crowd".

In this paper, a grouping evacuation management strategy considered human following or collective behavior is proposed. It can be easily carried out in reality. The group escape route is based on the shortest route determined by graph theory. The optimal computation of this strategy is carried out by computational experiments. The rest of paper is organized as follows. The idea and approach are given in Section Ⅱ. A case is presented to put into effect and verify our method in Section Ⅲ. The conclusion is given in Section Ⅳ.


Due to the human sociality, an occupant usually help others beside him, let alone family member or colleague in emergencies. We want to apply this feature in emergency management. The grouping evacuation is in line with human nature and easy to perform. Then, how many evacuees in one group would be optimal needs to be determined. In this paper, we use graph theory to determine the shortest escape route of groups. And apply computational experiments to design, perform and evaluate the grouping evacuation processes. All evacuation experiments are done in the high-rise building fire environments which are demonstrated in detail.

A. Graph Theory is Used to Determine Evacuation Route

Graph theory is an important branch of Operational Research. It was proposed by mathematician Euler to successfully solve the seven bridges problem of Konigsberg [22]. In recent years, graph theory has been used in road transportation system, route choice, [23], [24] etc..

In graph theory, graph $G$ is represented by ($V, E$) where $V$ is the vertex set and $E$ is the edge set. An edge is called a directed edge is ordered couple ($V_i, V_j$). An edge called hasn't an undirected edge by ordered pair. The graph called a directed graph when all edges are directed, otherwise it is called an undirected graph or a hybrid graph. When an added value $W_{ij}$ is put on edges, the graph is called a weighted graph and $W_{ij}$ is the weight of edge ($V_i, V_j$). The shortest route algorithms based on graph theory are mainly Dijkstra and Floyd algorithms [25], [26]. Dijkstra algorithm is more suitable for solving the shortest route problem of single source vertex, while Floyd algorithm is good at working out the shortest route of multiple source vertexes. And Floyd algorithm is simple at using weighted matrix to get shortest route. Based on above reasons, we use Floyd algorithm to determine the shortest evacuation route in the paper.

Firstly, the weighted matrix of weighted graph is defined as $D=[d_{ij}]{(n\times n)}$. The relationship follows.

$ \begin{eqnarray}\label{2} d_{ij}\mathit{\boldsymbol{=}}\left\{ \begin{array}{cc} w_{ij}&\left(V_i, V_j\right)\mathit{\boldsymbol{\in }}E \\ \mathit{\boldsymbol{\infty }}&{\text{else}} \end{array} \right\}. \end{eqnarray} $ (1)

The Floyd algorithm is follows:

Step 1: Set cycle index $k$ $=$ 0 and weighted matrix $D_0=D$. $D$ follows (1). It can be started from any side and the weight is set as the side distance. If there is no side between two vertexes, the weight is $\infty$.

Step 2: Set $k=k+1$. $D^{\left(k\right)}={\left(d^{\left(k\right)}_{ij}\right)}_{n\times n}, k=1, 2, 3, $ $\ldots, n$. If there is a vertex $V_w$ between $V_i$ and $V_j$ which makes the distance $V_{iw}+V_{wj} <V_{ij}$, then update $d^{(k)}_{ij}={\text{min}}\left\{d^{(k-1)}_{ij}, d^{(k)}_{iw}+d^{(k)}_{wj}\right\}$.

Step 3: If $k=n$ then stop or else come back to Step 2.

For not considering the return phenomenon in evacuation processes, evacuation routes are set as a directed evacuation route graph $G=(V, E)$ and $V=\{S, N, O\}$. $S$ is the vertex set of all room exits. Stair nodes are represented by set $N$. While $O$ is the safety or goal exit set. They constitute vertex set of evacuation graphs. The description follows.

$ \begin{eqnarray*} &&S=\begin{array}{l}(s_{ij}|i \; {\text{is the }} i{\text{th floor number}}, \\j \; {\text{is the }} \;j{\text{th vertex of the }} i{\text{th floor)}}\end{array}\\ &&N=\begin{array}{l}(n_{ik}|i \;{\text{is the floor number }} \\{\text{and}} \; k \; {\text{is the }} k\;{\text{th staircase of the }} i{\text{th floor )}}\end{array}\\ &&O=(o_m|{\text{m is the }} m{\text{th safety exit).}}\end{eqnarray*} $

The weight $w_{ij}$ between two nodes is set by their distance. Then, according to Floyd algorithm of directional weight graph, we can determine the shortest route from $S$ to $O$.

B. Computer Experiment Design

After determining the shortest evacuation routes, the simulation experiments are developed based on computational experiment approach to draw quantitative results and conclusions. Computational experiment [27], [28] is proposed for solving the experiment problems which are difficult to do in reality. It is a valid approach to check the effectiveness of evacuation strategies. Simulation based computational experiment design can provide not only dynamic evolution processes but also quantitative research results.

In this paper, the size of a group is taken as the controllable factor of experiments. According to the way of single factor experiment design, the computational experiment design is described as follows.

Step 1: Determine evaluation index. Because the time required in an escape process is a critical factor to measure or estimate evacuation efficiency, the total evacuation time or the last person' escaping time is set as a crucial quantitative index in the paper, which is called required safety evacuation time written as rset. In addition, the balance of using exits is a potential important factor for improving efficiency. It can be defined as the exit balance situation index ops (optimal performance statistic) which is determined by (2). The value of ops is between 0.0 and 1.0. The smaller the value, the better the exit balance [34].

$ \begin{eqnarray} ops=\frac{\int^n_{i=1}{(rset-{te}_i)}}{n\times rset} \end{eqnarray} $ (2)

where $rset$ is the total evacuation time, and $te_i$ is the $i$th exit evacuation time, and $n$ is the exit number.

In our computational experiments, rset and ops are weighted as the final experiment index $\delta$ in (3) which is provided in case study according to the specific situation.

Step 2: Determine fire scenario and evacuee situation. Occupant density, physical and movement properties of individuals including age, gender and movement velocity all need to be set according to possible actual situations.

Step 3: According to the control factor computational experiments table is designed and computational experiments are performed.

Step 4: Analyze experiment results and draw conclusions.

Ⅲ. APPLICATION CASE A. High-rise Building Construction

A high-rise office building is used as the case. The building has ten floors. Plan area is about 12500 ${\text{m}}^{\text{2}}$. Two stairs and two elevators connect the floors in building. Two outside exits are both 2 meters wide on the first floor. The layout is same from the second to tenth floor. Floor height is all set as 3 meters. Building layout diagram and 3D display are shown in Fig. 1.

Fig. 1 Building layout of the case

Using above graph theory, we can give a hybrid graph for the case in which $n$ represents staircases, $s$ represents room exits, and $o$ represents safety exits. And the actual distances between vertexes are taken as the link weight of the graph. In order to avoid returning behaviors during the evacuation process, the links between staircase and safety exit vertexes are set as a directional connection and obey up to down and inside to outside evacuation rules. For the layout above the second floor is the same, graphs from the third to the eighth floor are omitted. The graph between the first and the second, the ninth and the tenth floor are shown in Fig. 2.

Fig. 2 Hybrid weight graph of the case

Applying the Floyd algorithm, we can determine the shortest evacuation route from the source vertexes to the safety exits. The shortest distances and the shortest routes from the highest floor source vertexes $s_{10-1}\ldots s_{10-19}$ to the safety exits vertexes $o_1$ or $o_2$ are shown in Table Ⅰ. Evacuees at a same source vertex are set as an identical shortest escape route using the "itinerary task list" based on buildingEXODUS platform [29].

Table Ⅰ
B. Fire Scenario

Fire is one regular and sudden disaster in high-rise buildings, which happens much more frequently than earthquake, flooding etc. It produces heat, smoke and toxic or poisonous gases which will influence human behavior in evacuation processes. In order to make our experiments more real and credible, combining with fire scenarios is very important.

The tool to provide fire scenarios is CFAST fire zone model which is developed by NIST (National Institute of Standards and Technology, US). In recent years, it has been widely accepted. CFAST uses the zone idea to divide a room into upper and lower layers. It develops the diffusion of thermal, smoke, poisonous or toxic gases by quality and energy conservation law [30]. Inside the lower or upper layer, thermal, smoke, or toxic gases are considered uniform distribution. The gas diffusion in one room and between two rooms is shown in Fig. 3 [29]. Finally, the influence of fire is reflected on evacuees' motor abilities.

Fig. 3 Description of gas development by CFAST

Representative fire scenarios are set to mimic the building fire emergencies in the case. Ignition position is put on the third floor. The ignition room and its location are shown in Fig. 1 (b). Combustion value of the fire is set as a main fire with 50 000 KJ/kg. Combustion development with time in the ignition room is shown in Fig. 4. Surface radiation value of hot and smoke gas is shown with the red line and the gas radiation value is shown with the blue line. The heat radiation of room both surface and inside all reached high combustion values within 200 seconds. It reflects the uncontrollable characteristic of fire.

Fig. 4 Heat radiation situations in ignition room

In order to more really simulate evacuees' behaviors, the influence of heat and toxicity gas on evacuees' motor ability is considered. The development of fire in the case building is imitated and calculated by CFAST. The development of temperature, height, CO, and CO$_2$ concentration of smoke layer in the ignition room, corridor, and staircase of fire floor are shown in Fig. 5. You can see, Temp, CO and CO$_2$ concentration rise quickly in the ignition room but the influence is not so big in the corridor and staircase. However, the smoke layer in the corridor, staircase and ignition room all drops rapidly. It will take seriously toxic influence on evacuees. It is in agreement with common sense.

Fig. 5 Fire development in the scenario
C. Evacuees

According to human sociality, in fire emergencies, people often take actions following surrounding crowds and familiar evacuees are more likely to choose the same evacuation route, which is known as herd behavior [31]. In fact, reasonable herd behavior can improve evacuation efficiency while non-rational behavior can bring jam phenomena [32]. In this paper, we hope to rationally use the human sociality and herd behavior by grouping evacuees.

Properties of evacuees in the case are set according to our other researches about evacuees [33], [34]. The occupant density of evacuees is set as 11person/100m$^2$ and the gender ratio (male/female) is taken as 3:2. The age composition is supposed twenties, thirties and forties and the ratio is 50: 25: 25 percent. The relationship between physical attributes and movement capabilities obeys Table Ⅱ which is based on the empirical values given by Fruin [29] and statistical data in the literatures [35], [36].

Table Ⅱ
D. Computational Experiments

Taking the size of evacuee groups as the controllable factor, the computational experiment is designed according to single factor experiment design steps. In order to cover experiment scope as large as possible and draw comparability data, the evacuee group sizes are set from 2 to 8 persons per group and the extreme case which takes all people in each room as one group is also considered. Experiment design is shown in Table Ⅲ.

Table Ⅲ

In order to simplify the study, evacuees are assumed to be all inside rooms before evacuation as shown in Fig. 6. According to Table Ⅱ and Table Ⅲ, computational simulation experiments are performed based on buildingEXODUS platform [29]. 3-D diagrams are shown in Fig. 7, which display with different grouping sizes at the 60th second on the tenth floor.

Fig. 6 Occupants distribution before evacuation
Fig. 7 3-D diagram of the highest floor with all group plans at the 60th seconds
E. Result and Analysis

The experiment results which are the average value of 30 times simulation are shown in Table Ⅳ. Index $\delta$ is defined by (3).

Table Ⅳ

In the expression, the coefficients are determined as 0.8 and 0.2 respectively according to the different effect ratio. It synthetically reflects both the whole evacuation time and the exit use efficiency. The smaller the $\delta$, the better evacuation performance is.

$ \begin{eqnarray} \delta=0.8\times\frac{rset}{1000}+0.2\times ops \end{eqnarray} $ (3)

Diagrams of evacuation time and index $\delta$ are also shown in Fig. 8 (a) and (b) respectively.

Fig. 8 Experiments result

In Fig. 8 we can see that the evacuation efficiency in experiments 2 to 5 is higher than others. In addition, the experiment 3 has the highest efficiency. That is, the 3-person-group strategy has the shortest evacuation time and highest evacuation efficiency in the case, while other strategies with 7 persons or more in one group are with lower evacuation efficiency. In the experiment 1, although the evacuation time is lower than 280 seconds but there is poor balance at exits for high numbers in one group.


In order to guide the actual emergency evacuation processes, management strategies which are valid and easy to carry out have very important meaning in reality. In this paper, from the view of management we studied grouping evacuation strategies combining shortest route based on graph theory in order to improve evacuation efficiency. Based on computational experiments, we obtain quantitative research conclusions. Although the result is got based on a special case, more importantly, it gives the idea and the detailed research approach. In fact, with the special high-rise building, the structure of building is clear, and the number, density and distribution of occupants can all be estimated roughly. Thus we can use the proposed method to provide prearranged planning and find optimal grouping management strategies.

[2] D. Helbing and P. Molnár, "Social force model for pedestrian dynamics, " Phys. Rev. E, vol. 51, no. 5, pp. 4282-4286, May 1995.
[3] D. Helbing and A. Johansson, "Pedestrian, crowd, and evacuation dynamics, " in Encyclopedia of Complexity and System Science, R. A. Meyers, ed. New York, NY: Springer, 2010, pp. 6476-6495.
[4] E. Kirik, T. Yurgelýan, and D. Krouglov, "An intelligent floor field cellular automation model for pedestrian dynamics, " in Proc. Summer Computer Simulation Conf. , San Diego, CA, USA: Society for Computer Simulation International, 2007, pp. 211-216.
[5] P. B. Luh, C. T. Wilkie, S. C. Chang, K. L. Marsh, and N. Olderman, "Modeling and optimization of building emergency evacuation considering blocking effects on crowd movement, " IEEE Trans. Autom. Sci. Eng., vol. 9, no. 4, pp. 687-700, Oct. 2012.
[6] E. R. Galea and J. M. Perez Galparsoro, "A computer-based simulation model for the prediction of evacuation from mass-transport vehicles". Fire Saf. J. , vol.22, no.4, pp.341–366, 1994.
[7] N. Wagner and V. Agrawal, "An agent-based simulation system for concert venue crowd evacuation modeling in the presence of a fire disaster, " Expert Syst. Appl., vol. 41, no. 6, pp. 2807-2815, May 2014.
[8] N. Ishak, R. Khalid, M. A. Baten, M. Kamal, and M. Nawawi, "Queuing network approach for building evacuation planning, " in Proc. 3rd Int. Conf. Quantitative Science and Its Applications, Langkawi, Kedah Malaysia: ICOQSIA, 2014, pp. 566-572.
[9] M. Haghani and M. Sarvi, "Human exit choice in crowded built environments: investigating underlying behavioural differences between normal egress and emergency evacuations, " Fire Saf. J. , vol. 85, pp. 1-9, Oct. 2016.
[10] R. Lovreglio, A. Fonzone, and L. dellÓlio, "A mixed logit model for predicting exit choice during building evacuations, " Transp. Res. A, vol. 92, pp. 59-75, Oct. 2016.
[11] X. L. Wang, W. Guo, Y. Cheng, and X. P. Zheng, "Understanding the centripetal effect and evacuation efficiency of evacuation assistants: Using the extended dynamic communication field model, " Saf. Sci., vol. 74, pp. 150-159, Apr. 2015.[]=citjournalarticle_475436_27
[12] A. Rahman and A. K. Mahmood, "Feasible route determination using ant colony optimization in evacuation planning, " in Proc. 5th Student Conf. Research and Development, Selangor, Malaysia: IEEE, 2007, pp. 1-6.
[13] Q. M. Xie, J. H. Wang, S. X. Lu, and J. L. M. Hensen, "An optimization method for the distance between exits of buildings considering uncertainties based on arbitrary polynomial chaos expansion, " Reliab. Eng. Syst. Saf., vol. 154, pp. 188-196, Oct. 2016.
[14] P. -C. Tsai, C. -M. Chen, and Y. -P. Chen, "PSO-based evacuation simulation framework, " in Proc. IEEE Corgr. on Evolutionary Computation, Beijing, China: IEEE, 2014, pp. 1944-1950.
[15] O. B. Vastberg, H. R. Dong, and X. M. Hu, "Optimal pedestrian evacuation using model predictive control, " in Proc. European Control Conf., Zürich, Switzerland: IEEE, 2013, pp. 1224-1229.
[16] U. Tamima and L. Chouinard, "Framework for earthquake evacuation planning: case study for Montreal, Canada, " Leaders. Manage. Eng., vol. 12, no. 4, pp. 222-230, Sep. 2012.
[17] J. M. Epstein, R. Pankajakshan, and R. A. Hammond, "Combining computational fluid dynamics and agent-based modeling: a new approach to evacuation planning, " PLoS One, vol. 6, no. 5, pp. Article No. e20139, May 2011.
[18] M. H. Nguyen, T. V. Ho, and J. -D. Zucker, "Integration of smoke effect and blind evacuation strategy (SEBES) within fire evacuation simulation, " Simulat. Model. Pract. Theory, vol. 36, pp. 44-59, Aug. 2013.
[19] H. -S. Gan, K. -F. Richter, M. Z. Shi, and S. Winter, "Integration of simulation and optimization for evacuation planning, " Simulat. Model. Pract. Theory, vol. 67, pp. 59-73, Sep. 2016.
[20] M. Haghani and M. Sarvi, "How perception of peer behaviour influences escape decision making: the role of individual differences, " J. Environ. Psychol., vol. 51, pp. 141-157, Aug. 2017.
[21] A. Cuesta, O. Abreu, and D. Alvear, "Methods for measuring collective behaviour in evacuees, " Saf. Sci., vol. 88, pp. 54-63, Oct. 2016.
[22] G. P. Wang, Y. Wang, and J. C. Ren, Graph Theory Algorithm, Implementation and Application. Beijing: Peking University Press, 2011.
[23] S. Derrible and C. Kennedy, "Applications of graph theory and network science to transit network design". Transp. Rev. , vol.31, no.4, pp.495–519, 2011.
[24] S. Stoilova and L. Kunchev, "Application of the graph theory, AHP method and cost benefits analysis for route selection of a road train, " J. Balkan Tribolog. Assoc., vol. 22, no. 1A-Ⅱ, pp. 1041-1056, Apr. 2016.
[25] K. Murota and A. Shioura, "Dijkstraś algorithm and L-concave function maximization, " Math. Program., vol. 145, no. 1-2, pp. 163-177, Jun. 2014.
[26] A. Asghar and S. Amir, "Speeding up the Floyd-Warshall algorithm for the cycled shortest path problem, " Appl. Math. Lett. , vol. 25, no. 1, pp. 1-5, Jan. 2012.
[27] F. Y. Wang, "Artificial societies, computational experiments, and parallel systems:a discussion on computational theory of complex social-economic systems". Compl. Syst. Complex. Sci. , vol.1, no.4, pp.25–35, 2004.
[28] F. Y. Wang, "Parallel control:a method for data-driven and computational control". Acta Autom. Sinica , vol.39, no.4, pp.293–302, 2013.
[29] E. R. Galea, P. J. Lawrence, S. Gwynne, L. Filippidis, D. Blackshields, and D. Cooney, Building EXODUS V6. 2 Technical Manual and User Guide. Greenwich, London, UK: University of Greenwich, 2015.
[30] D. P. Richard, A. R. Paul, and P. F. Glenn P F, "CFAST-Consolidated Model of Fire Growth and Smoke Transport (Version 6) User's Guide, " Technical Report NIST Special 1041r1. USA: National Institute of Standards and Technology, U. S. Department of Commerce, 2013.
[31] N. Shiwakoti, R. Tay, P. Stasinopoulos, and P. J. Woolley, "Likely behaviours of passengers under emergency evacuation in train station, " Saf. Sci. , vol. 91, pp. 40-48, Jan. 2017.[]=citjournalarticle_529444_6
[32] M. Haghani and M. Sarvi, "Following the crowd or avoiding it? Empirical investigation of imitative behaviour in emergency escape of human crowds, " Anim. Behav. , vol. 124, pp. 47-56, Feb. 2017.
[33] Y. L. Hu, F. -Y. Wang, and X. W. Liu, "A CPSS approach for emergency evacuation in building fires, " IEEE Intell. Syst., vol. 29, no. 3, pp. 48-52, May-Jun. 2014.
[34] Y. L. Hu, F. Y. Wang, and X. W. Liu, "ACP-based research on evacuation strategies for high-rise building fire". Acta Autom. Sinica , vol.40, no.2, pp.185–196, 2014.
[35] M. R. Virkler, "Prediction and measurement of travel time along pedestrian routes". Transp. Res. Record, no. 1636, :37-42 , vol.1636, pp.37–42, 1998.
[36] J. X. Wang and B. X. Li, "The reference value of the height and the weight of Chinese people". Radiat. Protect. Med. , vol.13, no.3, pp.3–7, 1993.