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
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 highrise 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 highrise 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], agentbased 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 highrise 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 Ⅳ.
Ⅱ. RESEARCH APPROACHDue 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 highrise building fire environments which are demonstrated in detail.
A. Graph Theory is Used to Determine Evacuation RouteGraph 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
Firstly, the weighted matrix of weighted graph is defined as
$ \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
Step 2: Set
Step 3: If
For not considering the return phenomenon in evacuation processes, evacuation routes are set as a directed evacuation route graph
$ \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
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
In our computational experiments, rset and ops are
weighted as the final experiment index
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. Highrise Building ConstructionA highrise office building is used as the case. The building has
ten floors. Plan area is about 12500
Download:


Fig. 1 Building layout of the case 
Using above graph theory, we can give a hybrid graph for the case in
which
Download:


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
Fire is one regular and sudden disaster in highrise 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.
Download:


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.
Download:


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
Download:


Fig. 5 Fire development in the scenario 
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 nonrational 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
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 Ⅲ.
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]. 3D diagrams are shown in Fig. 7, which display with different grouping sizes at the 60th second on the tenth floor.
Download:


Fig. 6 Occupants distribution before evacuation 
Download:


Fig. 7 3D diagram of the highest floor with all group plans at the 60th seconds 
The experiment results which are the average value of 30 times
simulation are shown in Table Ⅳ. Index
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
$ \begin{eqnarray} \delta=0.8\times\frac{rset}{1000}+0.2\times ops \end{eqnarray} $  (3) 
Diagrams of evacuation time and index
Download:


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 3persongroup 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.
Ⅳ. CONCLUSIONIn 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 highrise 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.
[1]  http://www.bbc.com/news/ukenglandlondon40271723. 
[2]  D. Helbing and P. Molnár, "Social force model for pedestrian dynamics, " Phys. Rev. E, vol. 51, no. 5, pp. 42824286, May 1995. https://www.mendeley.com/researchpapers/socialforcemodelpedestriandynamics/ 
[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. 64766495. http://www.mendeley.com/research/pedestriancrowdevacuationdynamics 
[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. 211216. https://core.ac.uk/display/22079749 
[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. 687700, Oct. 2012. http://dx.doi.org/10.1109/TASE.2012.2200039 
[6]  E. R. Galea and J. M. Perez Galparsoro, "A computerbased simulation model for the prediction of evacuation from masstransport vehicles". Fire Saf. J. , vol.22, no.4, pp.341–366, 1994. 
[7]  N. Wagner and V. Agrawal, "An agentbased simulation system for concert venue crowd evacuation modeling in the presence of a fire disaster, " Expert Syst. Appl., vol. 41, no. 6, pp. 28072815, May 2014. http://dx.doi.org/10.1016/j.eswa.2013.10.013 
[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. 566572. http://dx.doi.org/10.1063/1.4903638 
[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. 19, Oct. 2016. https://www.scilit.net/article/588c99083fc8b28f5124e55dadcc185f 
[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. 5975, Oct. 2016. http://dx.doi.org/10.1016/j.tra.2016.06.018 
[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. 150159, Apr. 2015. http://www.safetylit.org/citations/index.php?fuseaction=citations.viewdetails&citationIds[]=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. 16. 
[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. 188196, Oct. 2016. 
[14]  P. C. Tsai, C. M. Chen, and Y. P. Chen, "PSObased evacuation simulation framework, " in Proc. IEEE Corgr. on Evolutionary Computation, Beijing, China: IEEE, 2014, pp. 19441950. http://dx.doi.org/10.1109/CEC.2014.6900600 
[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. 12241229. http://www.divaportal.org/smash/record.jsf?pid=diva2:712493 
[16]  U. Tamima and L. Chouinard, "Framework for earthquake evacuation planning: case study for Montreal, Canada, " Leaders. Manage. Eng., vol. 12, no. 4, pp. 222230, Sep. 2012. http://www.mendeley.com/catalog/frameworkearthquakeevacuationplanningcasestudymontrealcanada/ 
[17]  J. M. Epstein, R. Pankajakshan, and R. A. Hammond, "Combining computational fluid dynamics and agentbased modeling: a new approach to evacuation planning, " PLoS One, vol. 6, no. 5, pp. Article No. e20139, May 2011. http://dx.doi.org/10.1371/journal.pone.0020139 
[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. 4459, Aug. 2013. http://www.mendeley.com/catalog/integrationsmokeeffectblindevacuationatrategysebeswithinfireevacuationsimulation 
[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. 5973, 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. 141157, Aug. 2017. http://www.sciencedirect.com/science/article/pii/S0272494417300476 
[21]  A. Cuesta, O. Abreu, and D. Alvear, "Methods for measuring collective behaviour in evacuees, " Saf. Sci., vol. 88, pp. 5463, Oct. 2016. http://dx.doi.org/10.1016/j.ssci.2016.04.021 
[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. 10411056, Apr. 2016. 
[25]  K. Murota and A. Shioura, "Dijkstraś algorithm and Lconcave function maximization, " Math. Program., vol. 145, no. 12, pp. 163177, Jun. 2014. http://www.scititles.com/articles/ea4bded63b6c4852abdbe2a259f007a7 
[26]  A. Asghar and S. Amir, "Speeding up the FloydWarshall algorithm for the cycled shortest path problem, " Appl. Math. Lett. , vol. 25, no. 1, pp. 15, Jan. 2012. http://www.mendeley.com/research/speedingupfloydwarshallalgorithmcycledshortestpathproblem/ 
[27]  F. Y. Wang, "Artificial societies, computational experiments, and parallel systems:a discussion on computational theory of complex socialeconomic systems". Compl. Syst. Complex. Sci. , vol.1, no.4, pp.25–35, 2004. 
[28]  F. Y. Wang, "Parallel control:a method for datadriven 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, "CFASTConsolidated 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. http://www.google.com/patents/US8082132 
[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. 4048, Jan. 2017. http://www.safetylit.org/citations/index.php?fuseaction=citations.viewdetails&citationIds[]=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. 4756, Feb. 2017. http://dx.doi.org/10.1016/j.anbehav.2016.11.024 
[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. 4852, MayJun. 2014. 
[34]  Y. L. Hu, F. Y. Wang, and X. W. Liu, "ACPbased research on evacuation strategies for highrise 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, :3742 , 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. 