Optimization of Grouping Evacuation Strategy in High-rise Building Fires Based on Graph Theory and Computational Experiments

Yuling Hu,Member,IEEE,and Xiwei Liu,Member,IEEE

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.

I.INTRODUCTION

BUILDING fire is still a serious catastrophe all over the world.On June 14th 2017,the London Grenfell Towerfire 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 buildingfires.

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 II.A case is presented to put into effect and verify our method in Section III.The conclusion is given in Section IV.

II.RESEARCHAPPROACH

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 routeof 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(Vi,Vj).An edge called hasnt 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 Wijis put on edges,the graph is called a weighted graph and Wijis the weight of edge(Vi,Vj).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=[dij](n×n).The relationship follows.

The Floyd algorithm is follows:

Step 1:Set cycle index k=0 and weighted matrix D0=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∞.

...,n.If there is a vertex Vwbetween Viand Vjwhich makes the distance Viw+Vwj＜Vij,then update=

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.

The weight wijbetween 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].

where rset is the total evacuation time,and teiis the ith exit evacuation time,and n is the exit number.

In our computational experiments,rset and ops are weighted as the final experiment index δ 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.

III.APPLICATIONCASE

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

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 thesecond floor is the same,graphs from the third to the eighthfloor are omitted.The graph between the first and the second,the ninth and the tenth floor are shown in Fig.2.

Fig.1.Building layout of the case.

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 highestfloor source vertexes s10-1...s10-19to the safety exits vertexes o1or o2are shown in Table I.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 ITHESHORTESTEVACUATIONROUTE ANDDISTANCE

Fig.3.Description of gas development by CFAST.

B.Fire Scenario

Fire is one regular and sudden disaster in high-rise buildings,which happens much more frequently than earthquake,fl ooding 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.

Representative fire scenarios are set to mimic the buildingfire 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 50000KJ/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 valueswithin 200 seconds.It reflects the uncontrollable characteristic of fire.

TABLE II EVACUEEMOBILITYCAPABILITIES ANDPHYSICALATTRIBUTESRELATIONSHIP

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 CO2concentration of smoke layer in the ignition room,corridor,and staircase of fire floor are shown in Fig.5.You can see,Temp,CO and CO2concentration 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.

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/100m2and 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 II which is based on the empirical values given by Fruin[29]and statistical data in the literatures[35],[36].

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

In order to simplify the study,evacuees are assumed to be all inside rooms before evacuation as shown in Fig.6.According to Table II and Table III,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.

E.Result and Analysis

The experiment results which are the average value of 30 times simulation are shown in Table IV.Index δ is defined by(3).

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 δ,the better evacuation performance is.

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

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

Fig.5.Fire development in the scenario.

TABLE III GROUPINGEVACUATIONDESIGN

Fig.6.Occupants distribution before evacuation.

Fig.7.3-D diagram of the highest floor with all group plans at the 60th seconds.

TABLE IV GROUPEVACUATIONRESULTS

Fig.8.Experiments result.

IV.CONCLUSION

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.