Building evacuation: Principles for the analysis of basic structures through dynamic flow networks
Universitat Politècnica de Catalunya (Spain)
Received: November 2012
Accepted: July 2013
CasadesúsPursals, S., GarrigaGarzón, F. (2013). IBuilding evacuation: Principles for the analysis of basic structures through dynamic flow networks. Journal of Industrial Engineering and Management, 6(4), 831859. http://dx.doi.org/10.3926/jiem.635

Abstract:
Purpose: The main purpose of this paper is to perform an analysis of the factors determining the architectural configuration of buildings for the mobility of people, using dynamic flow networks and considering group formation in the evacuation process.
Design/methodology/approach: For a long time it has been considered that once an evacuation begins, movement on the evacuation route mainly obeys mechanical factors; people occupy the free spaces which lead to evacuation more or less automatically. However, recent research has emphasized the need to consider people’s behavior; one of the aspects considered in this work is group formation, with its significant influence on the evacuation process. In positions of convergence and their branches things become considerably more complicated; as well as occupants’ behavioral aspects other relevant factors such as the geometry of the premises are critical in this process. Authors propose models, in which nodes are strategically placed, besides taking into consideration aspects of behavior. Several cases are analyzed.
Findings: The solution proposed in this paper is to analyze the problem through dynamic flow networks, using a macroscopic model in a deterministic environment in which the evolution of the quantities characterizing the problem at regular intervals is represented, obtaining a reasonably accurate and reliable understanding of the development of the evacuation.
Originality/value: A precise model of evacuation routes, convergence points and branches which includes a consideration of occupants’ behavior is obtained using stochastic models with microscopic analysis, in which people’s behavior is considered individually, this solution is complex, difficult to apply with many occupants and in large enclosures, and also, this way does not lead to optimal solutions.
Keywords: building evacuation, evacuation optimization, optimal evacuation of buildings

1. Introduction
The problem of building evacuation has been dealt with extensively from different viewpoints: Construction/Fire Safety, mathematics, and psychology/behavioral sciences, highlighting different classifications for each subject, so the field of mathematics may consider a classification of continuous or discrete models, stochastic or deterministic, heuristic, or simulation models which in turn may be deterministic or stochastic. Moreover, models which include individuals are called microscopic models, whereas macroscopic models are those which analyze groups of people. As far as the scope is concerned, it is customary to deal with the evacuation of buildings, sports facilities, ships, trains and urban areas separately. A comprehensive reference on the problem can be found in EVACMOD, a website where much of the uptodate information available on the evacuation of buildings can be found.
The problem of evacuating buildings was born along with large buildings and the assessment of people’s safety. Starting in the seventies with the study of cases in which research is conducted on incidents using scientific methodology; Bryan’s (1983) work being pioneering. These works have been developed over time with highly relevant results, leading to numerous publications, the most noteworthy of which is that by the multidisciplinary team under the auspices of NIST which conducted a detailed study of the September 11, 2001 attacks in New York. The importance of these studies is that from them arise relevant conclusions from which technical requirements and safety standards are adopted in buildings across the world.
In the eighties the study of dimensions and the movement of people begin, and the first mathematical formulations that provide estimates for evacuation times appear. A solid reference on the dimensions of individuals and the movement of people in buildings can be found in works undertaken by Fruins (19711987) in the U.S.A; Pauls (1984) in Canada and Predtechenskii and Milinskii (19691978) in the Soviet Union. Among the most important recent models on human locomotion are Weidmann and Buchmueller (2007), Nelson and MacLennan (1996) and Kholshenikov, Shields, Boyce and Samoshin (2009).
Among mathematical models, the problem of building evacuation evolves decisively when using flow networks, which is thanks to Berlin (1980). The first formulation of the problem to be optimized was by Francis (1981), and later Francis together with Chalmet and Saunders (1982) suggest the optimization of building evacuation networks by incorporating dynamic flow networks, so that later Francis and Kisko (1985) develop the first version of EVACNET software, an application that determines evacuation times and the optimal distribution of occupants towards the exits. Years later Choi, Hamacher and Tüfekci (1988) consider flow networks with capacity constraints and arcs with variable capacity, also, in the nineties work by Hope and Tardos (1994) is relevant as they present algorithms applicable to different dynamic flow networks, generally quickest flow for problems with multiple source nodes; dynamic lexicografic maximum flow problem and the earliest arrival flow problem, making it possible to determine the maximum number of people evacuated from a specified area. Meanwhile, Hamacher and Tjandra (2001) provide a collection of mathematical models developed building evacuation until that date. Tjandra and Hamacher (2003) solve the evacuation of buildings where the number of occupants is not known, the earliest arrival flow capacity model with time dependent problems. These same authors address multiobjective problems that determine the evacuation of premises establishing priority for occupants closest to risk points. Baumann and Skutella (2009) develop a polynomial algorithm that solves the earliest arrival flow with multiple source nodes and a destination node, considering the problem of continuous flow. Kamiyama, Katoh and Atsushi (2008) develops algorithms for the implementation of the solutions presented by Hope and Tardos. More recent work such as by Fang, Zong, Li and Xiong (2011) used genetic or ant colony algorithms to be optimized in large sports venues.
Continuing in the field of mathematical modeling, another perspective for studying the problem of evacuating buildings is that of physical models, the first in this field being fluid dynamics and gas kinetic models, in which they compare the movement of people with fluid dynamics or gas flow, and Henderson (1974) draws an analogy between the mass of people and the physical principles of gases by adapting Maxwell Boltzmann functions. A remarkable aspect of these models is Social Force Models in which it is considered that the movement of people is due to social forces and individual’ goals, and the authors who start this work are Helbing and Molnar (1995). Currently these microscopic models have been extensively developed so that as well as considering purely physical aspects they also incorporate aspects of people's behavior, which makes them extremely interesting models. Also within the field of physical models we find Cellular Automaton whose first models were by Fukui and Ishibashi (1999) and Blue and Adler (2000), and which are dynamic models that discretize space, so individuals are considered as particles with a degree of freedom that occupy discrete space elements called cells and can move to neighboring cells with certain transition probabilities according to preset goals.
In recent years software simulation applications have flourished in the study of building evacuation, among which we might mention: AENEAS, ALLSAFE, CRISP, EGRESS, EXITT, EVACSIM, EVI, EXIT89, EXODUS, GRIDFLOW, LEGION, MAGNETIC MODEL, PATHFINDER, PEDFLOW, PEDGO, PEDROUTE, SIMULEX, SIMWALK, STEPS, TIMTEX, TSEA, WAY OUT. Among the huge number of published papers it is worth referring to the work by Gwynne (2009) who demonstrates that simple modeling of the physical aspects does not adequately reproduce the building evacuation process in situations in which people’s behavior is implicit, a concept, the study of behavior, which is nothing new, as Frantzich and Benthorn (1999) published a paper on how the occupants of an IKEA store in Helsingborg Sweden made a choice of exits. Also, Galea, Sharp and Lawrence (2008) investigated the factors that determine the flow ratio at junctions, and more recently Köster Seitz, Treml, Hartmann and Klein (2011) analyzed the formation of groups in the evacuation process. All this suggests that the current trend is in multidisciplinary models, mathematical models that incorporate and attempt to reproduce individuals’ behavior, one of which is the formation of groups referred to in this paper.
2. Defining structures in buildings
In order to study the evacuation of buildings the basic structures need to be defined: evacuation routes, confluences and branches (see Figure 1). Many buildings can be modeled by only considering these three elements.
A circulation route is a set of dependent units placed successively from a source to a destination, linked by consecutive arcs. The joining of various routes or exit areas that converge in one place leads to a confluence, similarly, when a single unit or circulation route diverges into several separate routes a branch is formed.
Figure 1. Evacuation route, confluence, and branch
To model the problem of architectural design elements which make up the basic structures of the evacuation system a descriptive analysis of each situation is undertaken and then represented by a flow network. The static flow network consists of nodes and arcs, the node elements being busy at the outset or at any time during the evacuation process, while the arcs represent the circulation elements (corridors, stairwells, hallways, etc.).
The dynamic network used to represent the process of evacuating the building is defined from the static network. The modeling adopted is that presented by Francis et al. (1982) with some special features that provide a more accurate modeling which allows for the consideration of behavioral elements such as group formation. The nodes are not located in the center of the premises but rather at specific points in the network, so there is a greater correspondence between architectural elements and their representation, in this way a corridor in a building is defined by a node and an arc. In an identical manner to that used in conventional networks h periods of magnitude δ are considered, for example 50 periods of 10 seconds, 100 periods of 5 seconds 100, etc. To construct the dynamic network, h copies of the static network are made and they represent the building and expand in time periods, the initial period starts at the moment 0 and the final period ends at the moment T, where T = h × δ . For each node j of the static model, (h + 1) copies are made and are positioned sequentially and numbered from left to right according to the index i of the corresponding period by correlated natural numbers 0, 1, 2,. . . h, then a similar procedure for the arcs, each arc (j–j´) representing the displacement of occupants from j to j' starting in period i, h copies are made, the required number to model the displacement of all occupants from the source node j to the destination j´. There are also arcs (jj) called retention arcs which represent the development of the occupation of node j.
A diagram of the basic network variables can be seen in Figure 2, enclosures k_{j} and capacity enclosures c_{j} are variables which characterize the nodes, while flow capacity c_{jj} (people per period) and circulation time t_{jj} (periods) are variables belonging to the arcs.
Figure 2. Basic network variables
The capacity of enclosures c_{j} depends on the effective surface area of the enclosure as well as the size of the occupants and the separation between them reflected as occupying density d_{j}.

(1) 
Flow capacity c_{jj’} of an arc or peak flow depends on the minimum effective width w_{ejj´} between the units j and j´ and on the maximum flow that can be registered on this path. The minimum effective width has been defined by Pauls (1984).

(2) 
Flow capacity t_{jj’} of the occupants in premises or a group, between nodes (jj´) depends on the distance l_{jj}, and the average flow speed v_{jj´} which is developed on the path, and is expressed in periods.

(3) 
To estimate the size of the occupying densities, flows and displacement speeds it is possible to use occupancy and locomotion models provided by Fruins (19711987).
3. Dynamic analysis of circulation routes
As already defined, an evacuation route is a set of n dependent units (n ≥ 3) located successively and connected by (n1) arcs. Figure 3 shows an evacuation route made up of a source node or several circulation nodes A, B, C, D, E, F, and a destination node DS which can be accessed from the arcs OA, AB,..., FDS. In origin of evacuation nodes the occupying densities, the physical conditions of the circulation route (horizontal flow, ramp, stairs, etc.), as well as the personal characteristics of the occupants determine displacement speeds towards the next node.
Figure 3. Architectural configuration of an evacuation route
The dynamic analysis of circulation routes is divided into three parts: a descriptive analysis of the problem which allows for the observation of the physical conditions that determine the development of the evacuation, followed by the variables observed being placed in the dynamic network, and finally obtaining the resultant mathematical relations from the process.
3.1. Descriptive analysis of circulation in an evacuation route
To perform the analysis the simplest circulation route is used, that formed by a source node O occupied by k_{O} people, a single movement node A of length L in which two sections of lengths l_{1} y l_{2} are considered, a section l_{3} representing the length taken up by the delay, a destination node DS, an arc OA which connects the source node O with the circulation A and another ADS which links A with the destination DS. It is assumed that the capacity of circulation in the corridor c_{OA} is superior to that of the exit c_{ADS}, giving rise to the existence of delays, and it is considered that the corridor has a capacity c_{A}, in a way that access to it can be affected.
The initial circulation times between OA and ADS are the variables τ_{OA} and τ_{ADS} which are considered to be of periods 2 and 1 respectively. Figure 4 shows the development of the evacuation in a deterministic context without delays at the outset and assuming constant flow, and three stages can be observed: a transitory exit process from source node O, a stationary circulation process in the corridor A, and a transitory occupation process of the destination DS.
In the first period x_{OA}(1) people are leaving the source node O and access the corridor A with a flow value x_{OA}(1) the maximum possible c_{OA}, the flow capacity value between O and A. See Figure 4 in which the first half of corridor A is occupied, the people who have left O at the end of the first period find themselves halfway along the route as the circulation time is two periods.
In the second period the x_{OA}(1) people from the first period that were occupying the first half of the corridor move to the second half and others x_{OA}(2) access the corridor requiring immediate calculation of occupancy the areas O and A at the end of the period every time it is observed that the entire surface of the corridor has been occupied; presumably having not reached maximum occupancy c_{A}. If the circulation time τ_{OA} is of two periods, when they have elapsed, the first occupants who had left the premises at source O in the first period, at the end of the second period have reached the exit area A.
Figure 4. Descriptive analysis of the development of circulation in an evacuation route
Finally, in the third period there is an entry flow x_{OA}(3) in corridor A and an exit flow x_{ADS}(3), the difference between the number of people entering the corridor and those that leave is the increase in occupation recorded during the period. In the following periods until the corridor reaches its maximum capacity the process is transitory, in each period corridor occupation increases until it reaches its maximum capacity at which time the next stage, defined as the stationary process, begins. When the corridor reaches its capacity c_{A} the process becomes stationary, the same number of people enter the corridor as leave it, a situation which is maintained for a few periods. In the final periods when no entries are recorded into corridor A the process is once again transitory. Finally when there are no occupants in O to maintain a stable circulation flow the process is once again transitory, corridor A is emptied from its maximum capacity, the occupants from A start occupying DS.
Papers that have studied the formation of groups often begin with the phrase "Families survive together or die together", as it is an undeniable fact that people affected by an evacuation process may be individuals subject to a specific group be it family, friends or an organization. If when modeling an evacuation route the initial formation of groups is taken into account the situation becomes more complex (see Figure 5), where it can be seen that in the source the k_{O} occupants are forming different groups, in the moments when the occupants are in area A the groups remain in occupancy densities lower than expected.
Figure 5. Initial formation of groups in the evacuation process of a single route
Group formation can be modeled using macroscopic models, the exit vector values of the area should take the values corresponding to this situation. When working with fine networks, reduced time intervals, the differences to microscopic models are irrelevant.

(4) 
At a source node with an occupancy K_{O} in which m groups form, the occupants of the various groups complete the occupation of the node, a fact shown in the expression (4). There are situations in which groups that form initially are numerous, consisting of more than twenty people, for example this situation occurs in the evacuation of large venues visited by school groups; in such cases an alternative solution to the problem is to consider each group as a source node. Another commonly observed situation consists of the formation of groups according to the circulation speed during the evacuation process which is relevant in situations in which evacuation routes are relatively long.
People’s individual displacement speed is a random variable, a stochastic process that corresponds to a normal distribution. On long routes it has been observed as a standard that three groups usually form: an initial group in which faster moving people are placed, a large middle group consisting of people who move more slowly due to their fitness level, attitude to the process of evacuation or impossibility of overtaking, and a final group with people moving at a slower rate. Considering these three displacement speeds for each group, it is possible to model in dynamic network giving the situation shown in Figure 6.
Figure 6. Groups forming in the evacuation route due to the speed of movement
In the solution proposed for these cases, modeling using a dynamic network, you lose the identity of the groups as the model used is a macroscopic model, but the incidence of this effect is taken into account in the evacuation process.
3.2. Dynamic network of an evacuation route
Figure 7 shows the dynamic network corresponding to the evacuation route analyzed, the first row of the figure corresponds to the initial instants 0, δ, 2δ, ..., iδ and the end of each period (I + 1)δ. The second row, the corresponding period 1, 2, i, ..., h. On the left the static network is represented using the symbol corresponding to each node, its name and characteristics. In the center, the quantities that characterize the development of the evacuation in the dynamic network, kj(i) represents the occupancy of the area j at the end of period i, x_{jj´}(i) the number of people moving from j to j' in period i, y_{jj´}(i) the number of people arriving at node j from j during period i, and q_{j}(i) the number of people waiting in area j at end of period i.
Figure 7. Dynamic network values for a single route
In the representation of the dynamic network the descriptive analysis undertaken in the previous section is shown, analyzing occupancy, flows and delays.
3.2.1. Flow Analysis
In the dynamic network circulation flows OA are observed, between the source node O and the end of the corridor A, and circulation flows ADS between the exit of corridor A and the destination DS. x_{OA´}(1) is the number of people moving from O to A in the first period and y_{O}_{‑}_{A}(3), y_{OA}(3) = x_{OA´}(1+2) represent arrivals at A from O during the third period as a circulation time of two periods is assumed. In the initial periods y_{OA}(1) e y_{OA}(2) are zero as in these periods there are no arrivals at A.
With regard to circulation towards DS, x_{ADS´}(1) y x_{ADS´}(2) have zero values since there are no occupants at A. In the third period x_{ADS´}(3) takes the capacity value c_{ADS} for the path between A and DS, and since the circulation time is of a period the resulting arrivals are y_{ADS}_{´}(4). If there are situations of group formation, the exit flows from each node x_{jj´} will represent that situation.
3.2.2. Analysis of occupancy and delays
In this analysis it is worth distinguishing between evacuation source nodes, circulation nodes and evacuation destination nodes. In the source node O it is observed that k_{O}(0) represents the initial occupation of this area, k_{O}(1) the occupancy at the end of the first period, k_{O}(2) the occupancy at the end of the second period, and so on until reaching the moment when no occupants remain k_{O}(n) = 0 at which time the evacuation from the area is complete. In the intermediate node occupancy k_{A}(0) is the initial value, with k_{A}(1) representing occupancy at the end of the first period. The occupancy of an intermediate node has two components: the people who are circulating and those who are delayed. People that are circulating are those who abandoned O in the first period x_{OA´}(1), and those who are delayed q_{ADS´}(i), in this case q_{ADS´}(1) = 0 since no occupant has reached the exit, which makes it impossible for any delays to exist. In the second period occupancy k_{A}(2) is determined by x_{OA´}(1) y x_{OA´}(2), people who have accessed A during the first and second periods respectively, in this case there are again no people delayed q_{ADS´}(2) = 0. Throughout the third period x_{OA´}(1) people reach the end of A; who are those who left O during the first period, ie y_{OA}(3), of all these people x_{ADS}(3) go towards DS. The difference between the arrivals and departures [y_{OA´}(3) – x_{ADS}(3)] are the people who are delayed q_{A´}(3). The occupation of A defined by k_{A}(3) is given by the sum of the people waiting at the end of the period q_{A´}(3) and those who have accessed A defined by x_{OA´}(2) y x_{OA´}(3).
With respect to the occupancy of destination node DS, there are q_{DS´}(·) people waiting and x_{A‑DS}(i) people abandoning A circulating to the safe destination DS. The occupancy of DS at the end of period h is represented by k_{DS}(h), occupancy that matches the initial occupancy k_{O}(0) since it corresponds to the end of the evacuation. While q_{A}(i) is a delay, q_{DS}(i) represents the people waiting at destination DS. Knowing the delays at the end of each period facilitates the analysis of the impact of these delays on the development of the evacuation, so for example, long waits can generate occupants’ nervousness, which is extremely important to know in an emergency situation. The analysis of the circulation in a corridor and its representation through a dynamic network allows us to know the process of evacuation in an evacuation route.
3.3. Relations describing circulation in an evacuation route
The physical quantities which define the parameters of the dynamic network can be seen in Figure 8 where an occupied enclosure O is shown with access to a circulation route A and destination DS. The exit capacity of the source node is determined by the physical widths w_{OA} y w_{A–DS}, and circulation times are determined by the length of the routes l_{OA} y l_{A–DS} respectively.
Figure 8. Dynamic network values for a single route
The dynamic network values described in the following expressions correspond to occupancies, flows and delays. When quantifying occupancies a distinction is made between source nodes, circulation nodes and destination nodes. The occupancy of an evacuation origin area k_{O}(i) at the end of a period i is the same as the occupancy recorded in the previous period k_{O}(i1) minus the people who have left the area x_{Oj}(i) during the period i.

(5) 
The occupancy of an intermediate node k_{A}(i) at the end of period i corresponds to the occupancy of the previous period k_{j}(i) plus the incorporations y_{j´j}(i) minus the exits registered x_{jj´´}(i) during that period.

(6) 
Finally, the occupancy of a destination node k_{DS}(i) at the end of period i is equivalent to the occupancy recorded in the previous period k_{DS}(i1) plus any incorporations y_{jDS}(i) registered during that period.

(7) 
At every moment the flows x_{jj´}(i) are at the maximum possible corresponding to the capacity c_{jj´} of the route jj´ if there is a sufficient number of occupants to start the evacuation, and taking into account the formation of groups in the evacuation process. The following expression shows an exit flow from a source node.

(8) 
While at an intermediate node the expression is transformed as follows:

(9) 
With regard to the delays q_{j}(i) which are recorded in the area j corresponding to the value in the previous period q_{j}(i1) plus the increment of the difference between entries y_{j´j}(i) and exits x_{j´j}(i) during the period.

(10) 
Delays are a very important element in the study of this problem, which makes it an essential area of study.
3.4. Numerical applications for the study of an evacuation route
Below is an analysis corresponding to the evacuation of premises with occupied by 198 people. Figure 9 shows the dynamic network as well as a presentation of the calculations undertaken, while Figure 10 shows a table of the results. This example uses periods of 10 seconds, with maximum flows of 15 and 12 people / period, constant circulation times of 2 and 1 respectively, where delays at the initiation of the evacuation are not supposed and the capacity of A is not considered significant.
Figure 9. Dynamic network of an evacuation route used as an example
The figure shows how in each period 15 people leave the source node until we reach period 13 when the evacuation of O is finalized, just as it is shown that in each period 12 people head to the destination DS leaving three people trapped in A for each period, while an increase in occupancy is observed at the destination, the evacuation ending after 20 periods, giving an evacuation time of 200 seconds. Occupancy of O decreases, while occupancy of DS increases, and A reaches a maximum value of 63 people.
The representation of the evacuation route through a dynamic network uncovers the calculation process of the evacuation. In the example a deterministic model has been used in which circulation obeys the conditions of hydraulic flow, the exit flows from the source node and the exit flows from A are constant, these flows are not altered by the destination node capacity, and also delays occur in A. The results table shows in detail the values which characterize the process and from which a graphical analysis of the results can be made if deemed appropriate.
Figure 10. Example: Table of results of the dynamic network of an evacuation route
4. Dynamic analysis of confluences
In buildings there are locations where the confluence of movement from several areas occur or the confluence of several evacuation routes go into one. Movement through confluences is complex because there are many possible configurations depending on the geometrical conditions of the area. Figure 11 shows three possible configurations: perpendicular flows, opposing flows and adjacent flows.
Figure 11. Examples of confluence configurations
When, after a confluence, movement continues to form a single flow it is known as a simple confluence.
The existence of groups has a major effect on the confluence, there are situations in which the group has a significant effect on its operation, it has been observed in residential compounds that when families are involved in the evacuation process groups are maintained, whereas if there is no link between the individuals in the groups at the confluence the situation is more orderly.
Figure 12 shows the confluence in C of three evacuation routes, after which the occupants proceeding from areas O1, O2 and O3, continue along a single route to the enclosure A and from there to the destination DS. Flows are considered to be onedirectional, the mix of people from different areas is fluid and there are no preestablished priorities, simply allowing for the mix of entry or arrival flows at the confluence leading to a single exit flow . This example shows a triple confluence where there are flows perpendicular (O2O1 y O3O2) and linear flows in the opposite direction (O1O3).
Figure 12. Simple confluence
Research by Galea et al. (2008) on the movement on stairs in buildings in which the respective floors intersect, has found that the specific entry flow to the stairs decreases if the stair flow increases. Similarly it is observed that with high movement densities that don’t reach saturation, the specific entry flow to stairs is at maximum if the connection to the staircase landing is adjacent to the movement. When access to the stairs from a floor is linear and against the circulation, speed of movement on the stairs is noticeably reduced.
At a confluence the condition of flow continuity between the entry and the exit are established. If the number of people x_{e} who access the confluence and who leave it x_{s} are expressed in terms of specific flows f_{e} and f_{s} and with effective step widths w_{e} y w_{s}, the specific exit flow f_{s} is determined as shown by expression (11). If this specific exit flow value f_{s} is less than the maximum flow f_{MAX}, this value is valid, however, if this value exceeds the maximum flow it will be physically impossible and the flow will correspond to the value of maximum flow, the occupants being trapped at the confluence.

(11) 
With this simple approach some issues remain undefined, in this paper we intend to analyze them by conducting a descriptive analysis of the situation and its subsequent representation in a dynamic flow network, as has been done in the evacuation routes.
4.1. Descriptive analysis of confluence movement
A case analysis is made of two areas O_{1} and O_{2} occupied by people k_{O1} and k_{O2} respectively, with an area A in which flows merge occurs giving access to evacuation point DS. Significant factors considered within this process are physical characteristics of the occupants and confluence surface, given that both factors determine its full capacity c_{O1O2A}, as well as access route lengths l_{O1A} and l_{O2A} and the physical conditions of movement which determine the travel time to confluence τ_{O1A} and τ_{O2A}. This supposes a value of 2 and 1 respectively. Route length l_{ADS} gives rise to supposed flow capacity τ_{ADS} of 1 period. The movement capacities in confluence c_{O1A}, c_{O2A} for entrances and c_{ADS} for exit depend on effective minimum widths w_{O1A}, w_{O2A} and w_{ADS} respectively. Figure 13 shows the descriptive process analysis without taking jams at the start of evacuation into account.
Figure 13. Process in a simple confluence
In the first period, x_{O1A}(1) people coming from source node O_{1} and x_{O2A}(1) people coming from O_{2} head towards confluence A. If flow capacities O_{2} are of 1 and 2 periods, the x_{O2A}(1) people coming from O_{2} arrive at the confluence at the end of the first period whereas those x_{O1A}(1) coming from O_{1} can be found halfway along their route, where these arrivals are y_{O2A}(2) and y_{O1A}(3) supposing capacity c_{A} is not reached.
Throughout the second period, the x_{O2A}(1) people who left O_{2} during the first period arrive at A giving rise to the x_{ADS}(2) people who leave the confluence to head towards destination DS. The x_{O1A}(1) people coming from O_{1} are circulating in the confluence, this being the flow capacity of 2 periods. x_{O2A}(2) people coming from O_{2} and x_{O1A}(2) people coming from O_{1} commence evacuation. During this period flows x_{O1A}(1) and x_{O2A}(2) merge with x_{ADS}(2) people leaving the confluence simultaneously. The difference between entrances and exits are the q_{A}(2) people held up. Occupancy of A is determined by the flow balance and people held up. People in movement and those waiting are also taken into account.
In the third period, the situation is similar to that in the previous period as a mergence of flows between occupants coming from O_{1} and O_{2} takes place. Two entrance flows and one exit flow proceed through the confluence. Occupancy in confluence A increases until reaching full capacity, the point at which the transitory period finalizes and the stationary period commences.
In the stationary period, the number of people entering the confluence corresponds to the number of people leaving it. The difficulty arises when determining the number of people coming from O_{1} and O_{2} who have access to it. A simple solution consists in each period of establishing the proportion taken from access width. In other cases access configuration or personal characteristics of the occupants are also taken into consideration. These values, which are habitually defined via the confluence loading function Φ_{C}, are adjusted using evacuation simulations.
Figure 14. Existence of groups in a confluence process
A transitory process arises when no occupants remain in source nodes O_{1} and O_{2} whereas a resulting transitory emptying process arises when no further occupants enter the confluence. A maximum number of people leave the confluence periodonperiod until no occupants are left.
In a simple confluence the mergence between occupants develops in an orderly way with no preestablished priorities. If, on the other hand, we analyze the existence of groups in a confluence process, it can be seen that priorities between these groups are often established. People entering a confluence in an automatic way respect the groups by prioritizing the movement of a specific group, such as in Figure 14 where the occupants of O1 give priority to the group proceeding from O2. Although those situations in which a total respect for established groups occurs have been verified in hotel evacuations, there is a noticeable uncertainty over whether this process observed in relatively nonsevere situations would be maintained in emergency situations.
4.2. Dynamic network of a confluence
Figure 15 shows the dynamic network which enables the study of a simple confluence evacuation. Both the initial and final moments of each period and the periods corresponding to the network are shown at the top of the figure, an outline of the static network is shown on the left, and the values characterizing the development of the evacuation within the dynamic network are shown in the centre. Said values are: occupancies k_{j}(i), exit flows x_{jj´}(i), arrival flows y_{jj´}(i), and the number of people waiting at the end of the corresponding period q_{j}(i).
Figure 15. Values of a simple confluence dynamic network
4.2.1. Flow analysis
Two exit flows x_{O1A}(1) y x_{O2A}(1) corresponding to those people leaving O_{1} and O_{2} respectively can be observed in the first period. In the second period what can be seen is an arrival flow y_{O1A}(2), corresponding to those people who have left node O_{1} in the first period, together with four exit flows. The first of these exit flows x_{O1A}(1) refers to those people who have left O_{1} at the start of the first period and who have arrived at A at the end of the second period, where the exits of O_{1} and O_{2} in this period are x_{O2A}(2) y x_{O1A}(2 ). Finally x_{ADS}(2) people leave A to head towards destination DS.
Three arrival flows are produced during the third period, two towards node A, these being y_{O1‑A}(3) and y_{O2A}(3), and a third y_{ADS}(3) towards destination DS. As in the previous period, four exit flows take place: x_{O1A}(2), x_{O1A}(3), x_{O2A}(3), and x_{ADS}(3). This process continues period‑on‑period until evacuation is completed.
4.2.2. Occupancy and congestion analysis
Initial occupancy in evacuation source nodes are given as k_{O1}(0) and k_{O2}(0) and occupancies at the end of the first period are given as k_{O1}(1) and k_{O2}(1). Occupancy in any noninitial node is given by people who are either moving along or waiting. Finally, occupancy of confluence node A is k_{A}(1).
Congestion is expressed as q_{A}(i) and q_{DS}(i), where q_{A}(i) is people held up in A and q_{DS}(i) is people found at destination DS.
4.3. Mathematical relationships describing confluence movement
In order to establish the implicit mathematical relationships in a confluence, its physical conditions and principal values need to be taken into account. Figure 16 shows passage widths w_{O1A} and w_{O2A} which give confluence access and width of confluence exit w_{ADS}. On the other hand, route times are given by route lengths l_{O1A}, l_{O2A}, and l_{ADS}, personal characteristics of the occupants, and physical conditions of movement.
Figure 16. Example of a confluence
Following on from this, the principal mathematical relationships established in the dynamic network, the corresponding expressions for node occupancy, and flows are then defined. What can be seen is that the expressions given for the study of congestion in an evacuation route are identical thus occupancy of the origin evacuation nodes k_{Oj}(i) is given by the occupancy registered in the previous period k_{Oj}(i1) minus the people who have left the node in the present period x_{OA}(i).

(12) 
Occupancy in confluence k_{A}(i) corresponds with occupancy in the previous node k_{A}(i1) increased by arrivals produced during the present period y_{OjA}(i) minus exits registered x_{ADS}(i).

(13) 
Finally, occupancy of destination node k_{DS}(i) is given by occupancy registered in the previous period k_{DS}(i1) increased by arrivals produced during period y_{ADS}(i).

(14) 
While the intermediate node has not yet reached full capacity, movement flows x_{OA}(i) will be at their highest possible c_{OA}. However, when the confluence reaches saturation, it is complex to predict the number of people proceeding from the source nodes who will head towards it. A reasonable formula, therefore, is the proportionality criterion of access widths applied period‑onperiod.

(15) 
Movement towards destination node x_{ADS}(i) will be the highest possible c_{ADS} at all times.

(16) 
Following group formation, the process is similar to that in a simple confluence. What must be highlighted is the behavior of the proportionality function Φ_{OjA} which commonly takes the form Φ_{OjA}(i) using values 0 or 1 with the finality of establishing priorities between occupants from O1 and O2. This is known as the trafficlight function.
4.4. Numerical application for confluence study
Below is an example of the evacuation of two areas occupied by 110 and 165 people respectively. The evacuation routes from the source nodes have a capacity of 8 and 12 people per period and the access route to its destination has a capacity of 18. This thus causes a jam in the confluence. Figure 17 shows the corresponding dynamic network in which the development of confluence occupancy in the occupancy of A can be seen. It also states that following 18 periods all the occupants in their entirety can be found in destination DS.
Occupancy of O_{1} and O_{2} reduces periodonperiod whereas that of destination DS increases. What can also be seen is confluence occupancy which is at its highest in the fourteenth period. This entirely takes place in the established conditions of constant flows.
Figure 17. Example of a confluence dynamic network
The values given in the dynamic network can be arranged in a table (Figure 18) to enable a detailed analysis. This table can then be used to produce various analytical calculations and graphs, such as diagrams of occupancy or flows registered at each exit.
Figure 18. Example of a confluence result table
5. Dynamic analysis of branches
A branch (Figure 19) occurs when the occupants of a building are able to choose between several movement areas in order to continue their route towards an evacuation destination. Figure 19 shows a simple branch in which the occupants of area O reach area R from which they have the option of choosing between two alternative passage routes taking them either to destination DS_{1} or DS_{2} There is always a reason as to why these occupants head towards either DS_{1} or DS_{2}, although no supposition can be made beforehand in favor of either DS_{1} or DS_{2}.
Figure 19. Example of a branch
Several authors, such as Predtechenskii and Milinskii (19691978), Frantzich and Benthorn (1999), etc, have rigorously studied movement conditions within a branch. It is worth highlighting investigations carried out by Chen, Li and Zhang (2012) in which they reproduce the passage and exit selections in branches in particular building types using simulation models based on cellular automatas.
5.1. Descriptive analysis of movement in a branch
The process used in the study of branches has been identical as that followed in the study of evacuation routes and confluences, a detailed analysis of evacuation development, its representation through a dynamic network, and the deduction of the principal mathematical relationships. Figure 20 considers an area O occupied by k_{O} people with access to an area A in which the branch is produced giving access to two circulation routes heading towards destinations DS_{1} and DS_{2}. Considered significant in this process are actual branch configuration, its physical characteristics, personal characteristics of the occupants, and knowledge the occupants have of the building thus conditioning them to head towards one or other destination. Access capacity of the branch is given by c_{OA} and its exit capacity is given by c_{ADS1} and c_{ADS2}. The moment the branch occurs is established at the precise moment of arrival of τ_{OA}. Likewise, τ_{ADS1} and τ_{ADS2} set the destination in the same way as travel times. It is supposed that the value of flow capacity is of one period, no delays occur at the start of evacuation, and also that a group of people are ready at O to commence evacuation.
Figure 20 shows the descriptive analysis of the process. In the first period, x_{OA}(1) people coming from source node O head towards branch A; if flow capacity τ_{OA} is of one period, at the end of said period these people will arrive at the branch point giving rise to y_{OA}(2) arrivals, thus producing a branch in the following period. It is supposed that capacity c_{A} is not reached. In the second period, x_{OA}(2) people coming from source node O will head towards branch A. Likewise, the people arriving at confluence y_{OA}(2) select the evacuation route which leads them to destination DS_{1} or DS_{2}, where x_{ADS1}(2) is the people heading towards DS_{1} and x_{ADS2}(2) is those heading towards DS_{2}, occupying routes ADS1 and ADS2 respectively.
Occupancy k_{A}(2) of branch A is evaluated using the people in movement together with those held up. If there were a difference between entrance and exits, there would be q_{A}(2) people held up in A. If flow capacity τ_{ADS1} y τ_{ADS2} is of one period, at the end of said period y_{ADS1}(3) and y_{ADS2}(3) will arrive at DS_{1} and a DS_{2} respectively.
Figure 20. Analysis of the branch process
In the third period, the exit flow from source node x_{OA}(3) and the exit flows from A towards destinations x_{ADS1}(3) and x_{ADS2}(3) must be taken into consideration. Said flows will develop identically to those described in previous sections. Those people leaving the source in the previous period y_{OA}(3) arrive at the branch and y_{ADS1}(3) and y_{ADS2}(3) people are incorporated heading towards the destination. Occupancy within the area of branch A increases until reaching full capacity, at which time the transitory filling period of the branch finalizes and the stationary period commences. In said stationary period, the number of people entering the branch corresponds with those who leave. The difficulty arises in determining the number of people heading towards each destination DS_{1} and DS_{2}. A simple solution is to establish proportionality in each period from access widths and in other cases access configuration or personal characteristics of the occupants. These values are very often adjusted using evacuation simulations and are generically indicated using the exit function of branch Φ_{R}. A transitory process results once again when no occupants remain in source node O. Finally, when no further occupants enter, the branch enters a transitory emptying process in which a maximum number of people leave to head towards one of the destinations until no occupants are left.
Figure 21. Existence of groups in a branch process
When considering occupant groups in the branches, maintenance of groups must be referred to. In a simple branch it has been considered that an orderly distribution is undertaken in which occupants can head towards either O_{1} or O_{2} indistinctively. When groups have been formed, however, these groups are maintained and the entire cluster heads to one or the other destination. This situation takes place above all in the evacuation of hotels as it is obvious to consider that the family group is maintained. A similar situation occurs in groups made up of schoolchildren and has even been observed in exhibition halls in any nature of groups. It can be seen in Figure 21 that occupants remain in groups in their respective destinations DS1 and DS2. It is logical to assume that this process observed in nonsevere situations would be maintained in emergency situations. Pressure is lower than in confluences.
5.2. Dynamic network in a branch
Figure 22 gives a representation using a dynamic network. What can be seen on the left of the graph is the static network outline and in the centre are the values characterizing evacuation development in the dynamic network. k_{j}(i) gives area occupancy j at the end of period i, x_{jj´}(i) the number of people who move from j to j´ in period i, y_{jj´}(i) gives the number of people who arrive at node j´ after leaving j during period i, and finally q_{j}(i) gives the number of people held up in area j at the end of period i.
By analyzing flows, what can be seen in the first period is how x_{OA}(1) people leave source node O and how a flow of people leave O in this period x_{OA}(2) and a flow of x_{OA}(1) people from the previous period. This gives rise to y_{OA}(2) arrivals in the period and generates flows x_{ADS1}(2) and x_{ADS2}(2). The process continues while occupants remain in the origin areas of evacuation. Likewise, what can also be seen are occupancies of the four areas O, A, DS_{1} and DS_{2} periodonperiod, recording jams in area A.
Figure 22. Values of a simple branch dynamic network
5.3. Mathematical relationships describing movement in a branch
Flows, occupancies and jams are given by values presented in Figure 23. The route, therefore, from source node O to the centre of the branch is given by l_{OA}, where the route to each destination is l_{ADS1} and l_{ADS2} respectively. Personal characteristics of the occupants and physical conditions of movement determine the average speed reached along each route. Path capacity is given by minimum effective widths w_{jj´}, where path width giving access to the branch is w_{OA} and widths giving access to destinations is w_{OA}, respectively.
The modelling of branches is complex as personal characteristics and branch configuration are taken into account. It is a contrasted fact that in emergency situations occupants tend to use evacuation routes they are familiar with. Their familiarity with the building is therefore decisive. The most significant physical aspects are signage, lighting conditions and alarm system characteristics. Given the complexity and number of factors, the modelling of evacuation using flow networks with branches must be experimented in order to gain approximations which enable the most plausible forecasts possible.
Figure 23. Values of a simple branch dynamic network
The exit flow from source node x_{OA}(i) will be the highest possible at all times.

(17) 
At the branch exit, the relation of flows is assumed proportional to their widths. This operates correctly when the occupants are familiar with the area and thus find one or the other exit indistinctive. Function Φ_{R} is taken following trials.

(18) 
When groups have been formed, the process is similar to that in a simple branch. The proportionality function Φ_{A–DSj} takes the values 0 or 1 to establish distribution of occupants heading towards DS1 or DS2.
5.4. Numerical application of the branch study
Figure 24 shows flows, occupancies and jams periodonperiod corresponding to the evacuation of an area occupied by 200 people with a path capacity of 15 people per period to the branch area and from the branch to each destination of 8 and 5 people per period respectively, with flow capacities of one period being in the three arcs.
As in previous examples, the network values have been arranged in a table (Figure 25) in order to enable result analysis. What can be seen is how source node O_{1} remains occupied until period 14, in which the last 5 occupants are evacuated. Likewise, what can also be seen is that the branch node remains occupied until period 17, in which 3 people head towards destination DS_{1} and 2 towards destination DS_{2}. At the end, 123 people can be found in destination DS_{1} and 77 in destination DS_{2}.
Figure 24. Example of a branch
In the same way as occupancies are analyzed, flows can also be observed. In the first period, 15 people can be seen to move from source node O_{1} until branch A, a further 15 people leave node O_{1} in the second period, 8 people head towards DS_{1} and 5 towards DS_{2}, etc. Flows can thus be observed periodonperiod and jams can also be seen in a similar way; 2 people are held up in the second period, 4 in the third, 6 in the fourth and so on therefore reaching a maximum value of 26 in period 14.
Figure 25. Example of branch result table
6. Conclusions
A proposal is put forward in this paper for the resolution of building evacuation problems using dynamic flow networks within deterministic surroundings. It shows that when operating rigorously an excellent model is achieved. Dynamic flow networks are a powerful tool which enable a precise and complete formalization of the building evacuation problem and which give satisfactory results, as seen in the proposed examples. Although the numerical problem acquires a different value, the solution in buildings of big dimensions has exactly the same detail, consistency and precision as those presented in this paper.
Among the most relevant contributions is the way in which the representation of the building using a flow network is carried out. The nodes are situated strategically in order to achieve optimal modeling, thus, for instance, a passageway is represented using a node and an arc. The node is situated at the end of the passage in the direction of movement while the arc represents movement between it and the previous node. A direct relationship between architectural factors and the network it represents is achieved enabling the given results to have a physical sense with an immediate interpretation. When this proposal is applied to circulation routes, confluences and branches, it improves classical networks which situate nodes in the centre of areas and the arcs are also limited to showing passage between one another.
Another significant contribution has been the consideration of behavioral aspects. Although various microscopic models consider individual behavior, there is a lack of knowledge of behaviors such as group formation, differences in movement speeds, and confluence and branch behaviors in macroscopic models. This is considered to be of great interest due to the difficulty in the study of problems in buildings with a large number of occupants. This paper studies behavioral aspects using dynamic network flows.
Finally, mathematical expressions have been adapted from classical networks to the modeling proposed in this paper and also to the inclusion of behavioral aspects of the individuals subjected to the evacuation process.
References
Baumann, N., & Skutella, M. (2009). Solving evacuation problems efficiently: Earliest arrival flows with multiple sources. Mathematics of Operations Research, 34, 499512. http://dx.doi.org/10.1287/moor.1090.0382
Berlin, G.N., (1980). A network analysis of building egress system. ORSA/TIMS meeting Washington.
Blue, J.V., & Adler, J.L. (2000). Cellular automata microsimulation of bi directional pedestrian flows. J. Trans. Research Board, 1678, 135141. http://dx.doi.org/10.3141/167817
Bryan, J.L. (1983). A Review of the Examination and Analysis of the Dynamics of Human Behavior in the Fire at the MGM Grand Hotel, Clark Country, Nevada, as Determined from a Selected Questionnaire Population. Fire safety Journal, 5, 233240. http://dx.doi.org/10.1016/03797112(83)900218
Chen, Ch., Li, J., & Zhang, D. (2012). Study on evacuation behaviors at a Tshaped confluence by a forcedriving cellular automata model. Physica A: Statistical Mechanics and its Applications, 391(7).
Choi, W., Hamacher, S., & Tufekci, S. (1988). Modelling of building evacuation problems by network flows with side constraints. European Journal of Operational Research, 35, 98110. http://dx.doi.org/10.1016/03772217(88)903827
EVACMOD. http://www.evacmod.net/.
Fang, Z., Zong, X., Li, Q., & Xiong, S. (2011). Hierarchical multi objective evacuation routing in stadium using ant colony optimization approach. Journal of Transportation Geography, 19, 443451. http://dx.doi.org/10.1016/j.jtrangeo.2010.10.001
Francis, R.L. (1981). A Uniformity principle for evacuation route allocation. Journal of Research of National Bureau of Standards, 86, 509513. http://dx.doi.org/10.6028/jres.086.023
Francis, R.L., Chalmet, L.G., & Saunders, P. B. (1982). Network models for building evacuation. Management Science, 28, 86105. http://dx.doi.org/10.1287/mnsc.28.1.86
Francis, R.L., & Kisko, T.M. (1985). EVACNET+: A Computer program to determine Optimal building evacuation plans. Fire Safety Journal, 9, 211220. http://dx.doi.org/10.1016/03797112(85)900098
Frantzich, H., & Benthorn, L. (1999). Managing evacuating people from facilities during a fire emergency. Facilities, 17(9), 325330.
Fruins, J.J. (19711987). Pedestrian planning and design. Elevator World. Library of Congress Catalog, number 70159312.
Fukui, M., Ishibashi, Y. (1999). Jamming transition in cellular automaton models for pedestrian on passageway. J. Phys Soc, 68: 3738. http://dx.doi.org/10.1143/JPSJ.68.3738
Hamacher, H.W., & Tjandra, S.A. (2001). Mathematical Modelling of Evacuation Problems: A State of Art. Reports of the ITWM, 24.
Helbing, D., & Molnar, P. (1995). Social force model for pedestrian dynamics. Physical Review E, 42824286. http://dx.doi.org/10.1103/PhysRevE.51.4282
Henderson, L.F. (1974). On the fluid mechanics of human crowd motion. Transportation Research, 8, 509515. http://dx.doi.org/10.1016/00411647(74)900276
Hope, B., & Tardos, E. (1994). Polynomial time algorithms for some evacuations problems. Proceedings of the Fifth Annual SIAM Symposium on Discrete Algorithms, 433441.
Galea, E.R., Sharp, G., & Lawrence, P.J. (2008). Investigating the Representation of Merging Behavior at the FloorStair Interface in Computer Simulation of MultiFloor Building Evacuation. Journal of Fire Protection Engineering, 18, 291316. http://dx.doi.org/10.1177/1042391508095092
Gwyne, S. (2009). Safety in numbers. How human being react to fire. Magazine Significance, March, 1419.
Kamiyama, N., Katoh, N., & Atsushi, T. (2008). An efficient algorithm for the evacuation problem in certain class of networks with uniform pathlengths. Discrete Applied Mathematics.
Kholshenikov, V.V., Shields, T.H., Boyce, K.E., & Samoshin, D.A. (2009). Recent developments in pedestrian flow theory and Research in Russia. Fire Safety Journal, 43, 108118. http://dx.doi.org/10.1016/j.firesaf.2007.05.005
Köster, G., Seitz, M., Treml, F., Hartmann, D., & Klein, W. (2011). On modeling the influence of group formations in a crowd. Contemporary Social Science, 6(3), 397414. http://dx.doi.org/10.1080/21582041.2011.619867
Nelson, H.E., & McLennan, H.A. (1996). Emergency Movement. The SFPE Handbook of Fire Protection Engineering, 32863295.
Pauls, J.L. (1984). The movement of people in buildings and design solutions for means of egress. Fire Technology, 20(1). http://dx.doi.org/10.1007/BF02390046
Predtechenskii, W.M., & Milinskii, A.I. (19691978). Planning for foot traffic flow in buildings. Amerind Publishing Co. New Delhi., National Bureau of Standards, U.S. Dep. Commerce, PB‑294 993T.
Tjandra, S.A., & Hamacher, H.W. (2003). Dynamic Network Optimization with Application to the Evacuation Problems. PhD thesis, Technische Universität Kaiserslautern, Germany.
Weidmann, U., & Buchmueller, S. (2007). Parameters of pedestrians, pedestrian traffic, and walking facilities. Swiss Federal Institute of Technology  Institute for Transport Planning and Systems, Zurich.
This work is licensed under a Creative Commons Attribution 4.0 International License
Journal of Industrial Engineering and Management, 20082021
Online ISSN: 20130953; Print ISSN: 20138423; Online DL: B287442008
Publisher: OmniaScience