=Paper=
{{Paper
|id=Vol-2146/paper02
|storemode=property
|title=Applying a network flow model to quick and safe evacuation of people from a building: a real case
|pdfUrl=https://ceur-ws.org/Vol-2146/paper02.pdf
|volume=Vol-2146
|authors=Claudio Arbib,Henry Muccini,,Mahyar T. Moghaddam
|dblpUrl=https://dblp.org/rec/conf/rsff/ArbibMM18
}}
==Applying a network flow model to quick and safe evacuation of people from a building: a real case==
https://ceur-ws.org/Vol-2146/paper02.pdf
Applying a network flow model to quick and safe
evacuation of people from a building: a real case
Claudio Arbib, Henry Muccini, Mahyar Tourchi Moghaddam
Department of Information Engineering, Computer Science and Mathematics
University of L’Aquila – Via Vetoio, Coppito – 67100 L’Aquila, Italy
{claudio.arbib, henry.muccini}@univaq.it; mahyar.tourchimoghaddam@graduate.univaq.it
Abstract
We present a computational component that allows to evaluate the
minimum time necessary to evacuate people from a place (e.g., a
public building). The space and time dimension are discretized
according to metrics and models in literature. The component for-
mulates and solves a linearized, time-indexed flow problem [3] on
a network that represents feasible movements of people monitored
at a suitable frequency. This computational component is the core
part of an IoT infrastructure aimed at monitoring crowds in public
spaces for planning evacuation paths. The CPU time to solve the
model is compliant with real-time use. An application of the al-
gorithm to a real location with real data is described, and diverse
uses of the methodology are presented.
Keywords: Safe evacuation; Network optimization; Emergency
handling; Linear programming.
1 Introduction
Crowded public venues are significantly under risk, and casualties may be caused by hazards of various
nature and possible consequent overcrowding. Evacuation plans are becoming more and more elaborated,
and restrictive regulations are imposed by law both in normal exercise of public services and when organizing
public events. A good evacuation plan takes into account different types of crises and emergencies (e.g.,
earthquake, fire, ...), different scenarios, and different risks. Safe and first aid zones are carefully identified,
c by the paper’s authors. Copying permitted for private and academic purposes.
Copyright ©
In: G. Di Stefano, A. Navarra Editors: Proceedings of the RSFF’18 Workshop, L’Aquila, Italy, 19-20-July-2018, published at
http://ceur-ws.org
as well as evacuation paths to safe areas1 .
While very elaborated, standard emergency plans may still suffer of limitations. First, they are mostly
design-time and do not take real-time data into account. Consequently, an emergency plan may suggest
people in an auditorium to move to the outside park when fire originated right in that area; or, it may
suggest evacuation routes that are currently not walkable. Secondly, once paths from buildings to external
safe areas are drawn, directions for their use are normally care of human operators — when available — and
are based on a partial view on how emergency is constraining the building area. Third, while the release of
an evacuation plan may take weeks and requires external reviewers for approval, only few people typically
(and unfortunately) read them2 .
To cope with the above issues, this paper uses a run-time network flow model that, based on both design
(e.g., building dimension and structure, room capacities, door capacities) and run-time information (e.g.,
current amount of people in the building, in specific rooms and corridors) easily acquired via IoT devices, may
support the quick evacuation of people in case of hazard. The model, developed in the late eighties [3], has a
combinatorial nature, as it decomposes both space (building plan) and time dimension into finite elements:
unit cells and time slots. The building topology is then represented as a graph with nodes corresponding to
cells, and arcs to connections between adjacent cells. Run-time data are used to create an acyclic digraph that
models all the feasible transitions between adjacent cells at any given time slot, given the current occupancy
status of each cell. Minimizing the total evacuation time corresponds then to solve a mathematical program
that, in the final refinement, has the form of a linear optimization problem.
In the present context, an optimal solution does not have — of course — a big prescriptive validity:
in other words, optimal flows through the building might in general be difficult to implement in practice
(in case of risk, people tend to move quite unpredictably). The interest of an optimal solution mainly lies
in its numerical value, that is the minimum amount of time necessary, in ideal conditions, to let a given
distribution of people out of the place. This number can be used to monitor safety conditions from time to
time. In fact, the main plus with respect to standard evacuation plans, are:
i) Optimal solutions can continuously be updated thanks to the efficient mathematical structure of the
problem, so evacuation guidelines can be adjusted according to visitors positions that evolve over time. ii)
In this way, evacuation plans can be based on real-time information. Just to indicate one advantage, paths
that become suddenly unfeasible can automatically be discarded by the system. iii) The model can be
incorporated into a mobile app supporting emergency units to evacuate closed or open spaces. iv) Problem
solutions for different time horizon provide a Pareto frontier that relates available time to the best possible
people outflow in the given conditions. All that given, our overall view (backed up by ongoing work) is to
integrate the mathematical model and algorithm here proposed with an IoT infrastructure and a mobile app.
The paper is organized as follows. Literature is briefly discussed in Section 2. Section 3 presents the flow
model. Section 4 refers on how model parameters should be set up to deal with real cases. The application
of the model to a real exhibition venue is presented in Section 5, while the IoT architecture including the
flow model component is presented in Section 6. Conclusions are finally drawn in Section 7.
1 The evacuation plan adopted during the Researchers Night event, hosted in the city of L’Aquila in 2016 (NdR2016) can be
found at http://tiny.cc/ResearchersNight2016.
2 The evacuation plan for the NdR2016 event was downloaded from website/mobile applications prepared for the event just
36 times against 5700 total visitors.
2 Literature review
Evacuation routing problems (ERP) for large scale roads and buildings are complex and subject to various
modeling issues. In literature, the ERP is addressed by either static or dynamic algorithms. Indeed, a static
network cannot properly model time related constraints, and a dynamic view can then be obtained by a sort
of time expanded network that models flows over time. Choi et al [3] model building evacuation by dynamic
flow maximization, considering variable capacities on some arcs as a function of flows in incident arcs. Taneja
et al. [15] propose a more sophisticated bi-level network-based optimization model where an Interior Point
algorithm is used to determine an optimal capacity arrangement for an efficient crowd evacuation. Chen et
al. [2] propose a flow control algorithm that calculates evacuation paths depending on building plan and
total number of evacuees. Computation in this case aims at minimizing total evacuation time and assigning
an optimal number of evacuees to each evacuation path. However, as network size increases, the flow model
can no longer be solved in reasonable time.
Recent research bases evacuation planning on a transshipment problem. For instance, Schloter et al. [14]
study two classical flow models in order to deal with crowd evacuation planning: one algorithm aims at
finding the best transshipment as a convex combination of simple lex-max flows over time; a second one
computes earliest arrival transshipments that maximize the flow towards the sink for every point in time.
Other papers propose a hybrid optimization-simulation approach. To quote an example, Abdelghany
et al. [1] integrates a genetic algorithm with a microscopic pedestrian simulation assignment model. The
genetic algorithm looks for an optimal evacuation plan, while simulation guides the search by evaluating
the quality of the plans generated. The obtained plan is claimed to outperform conventional plans that
implement nearest-gate immediate evacuation strategies.
One of the most crucial issues addressed in the recent literature is the ability of finding good feasible
solutions in short time. In general, a trade-off is observed between complex models that accurately describe
the scenario, but cannot be solved quickly and thus call for heuristics (so loosing accuracy of solution
and situation assessment), and simpler models that can be solved quickly and exactly, but lack from the
viewpoint of scenario description. In this perspective, however, Choi et al.’s early paper [3] still provides
in our mind a good starting point. Limited to a theoretical analysis at publication time, this paper now
deserves reconsideration in the light of the progress done in LP solution tools. Nowadays solvers, in fact,
get easily rid of very large problems in fractions of seconds: dealing with more variables helps on one hand
obtain enough resolution to model the necessary details (in terms of both discretization and non-linearities);
on the other hand, quick re-computation allows to cope with data that dynamically change over time.
3 A flow model to minimize total evacuation time
3.1 Building topology and crowd flows
The following network construction basically follows [3]. The topology of the building to be evacuated is
described by a graph G = (V, A) that in [3] is called static network. Nodes of G correspond to the unit
cells i obtained by embedding the building into a suitable grid, see e.g. Figure 1. Grid geometry and size
lead to different levels of accuracy. We do not discuss this issue in detail. We just observe that, in general,
cells may have different shapes or sizes: for the purpose of our work what is important is that every cell
can approximately be traversed, in any direction, in a single time slot. Cell 0 conventionally represents the
outside of the building, or in general a safe place. Safe places can even be disconnected areas, but as their
II
I
III IV
Figure 1: Room embedding into a bee-nest grid.
capacity is assumed large enough to guarantee safety, we will represent them all by a single cell (therefore
what we assume about cells traversing time does not apply to cell 0). Arcs of G correspond to passages
between adjacent cells: the passage has full capacity if cells share a boundary not interrupted by walls, and
a reduced capacity otherwise. With no loss of generality, arcs are supposed directed. Let us denote:
T = {0, 1, . . . , τ }, set of unit time slots;
yit = state of cell i ∈ V at time t ∈ T , that is, the number of persons that occupy i at t: this number is a
known model parameter for t = 0 (in particular, y00 = 0) and a decision variable for t > 0;
ni = capacity of cell i: it measures the maximum nominal amount of people that i can host at any time (in
particular, n0 ≥ i yi0 ); this amount depends on cell shape and size; if cells can be assumed uniform
one can set ni = n for all i ∈ V, i ∕= 0.
xtij = how many persons move from cell i to an adjacent cell j in (t, t + 1]: this gives the average speed at
which the flow proceeds from i to j;
cij = capacity of the passage between cell i and cell j: this is the maximum amount of people that, indepen-
dently on how many persons are in cell j, can traverse the passage in the time unit (independence on
cell occupancy means neglecting system congestion: we will consider this issue later).
The flow model uses an acyclic digraph D with node set V × T and arc set
E = {(i, t) → (j, t + 1) : ij ∈ A, t ∈ T }
Referred to as τ -time or dynamic network in [3], D models all the feasible transitions (moves between adjacent
cells) that can occur in the building in the time horizon T . Transitions are associated with the x-variables
defined above, whereas y-variables define the occupancy of each room (and of the building) from time to
time. The x- and y-variables are declared integer and subject to the following constraints:
yjt − yjt−1 − xt−1
ij + xt−1
ji = 0 j ∈ V, t ∈ T, t > 0 (1)
i:ij∈A i:ji∈A
0 ≤ xtij + xtji ≤ cij t ∈ T, ij ∈ A (2)
0 ≤ yit ≤ ni t ∈ T, i ∈ V (3)
Equation (1) is just a flow conservation law: it expresses the occupancy of cell j at time t as the number
yjt−1 of persons present at time t−1, augmented of those that during interval (t−1, t] move to j from another
cell i ∕= j, minus those that in the same interval leave cell j for another room i ∕= j. Box constraints (2), (3)
reflect the limited hosting capability of the elements of G.
cij – cij'
cij – nj' ujt–1
cij
cij' – cij"
cij' cij' – vjt–1
nj" – nj'
cij"
cij"
cij" – nj – nj" wjt–1
ujt–1 vjt–1 wjt–1 yjt–1
0 nj' nj" nj
Figure 2: Congestion curve and a linearization.
3.2 Maximizing outflow in a given time
To model the relation between time and people outflow, one can try to maximize the number of persons
evacuated from the building within τ :
max y0τ (4)
This is the Max Flow Problem (MFP) considered in [3]. To find the minimum total evacuation time, one can
solve an MFP for different τ , looking for the least value that yields a zero-valued optimal solution. To reduce
computation time, this optimal τ can be computed by logarithmic search. The method can thus provide the
decision maker with the Pareto-frontier of the conflicting objectives min{τ }, max{y0τ }. The linear structure
of the model allows its solution with a large number of variables. Adding variables can help improve model
granularity by reducing space and time units (e.g., counting people every 5 seconds instead of every minute).
More importantly, it can also help approximate the non-linearities of arc capacities. In fact, cij constant
in (2) fails to model congestion, that is a situation in which the speed at which the system empties is a
decreasing function of room occupancy. A more accurate model of congestion requires arc capacity to be a
concave decreasing function of room occupancy, see Figure 2. Linearizing concavity one can rewrite
yit−1 = ut−1
i + vit−1 + wit−1 xtij = φtij + χtij + ψij
t
(5)
with ut−1
i , vit−1 , wit−1 non-negative and subject to upper bounds
ut−1
i ≤ n′i vit−1 ≤ n′′i − n′i wit−1 ≤ ni − n′i (6)
Arc capacity constraints (2) are then replaced by
cij − c′ij t−1
0 ≤ φtij ≤ cij − uj (7)
n′v
c′ij − c′′ij t−1
0 ≤ χtij ≤ c′ij − ′′ v
nj − n′j j
c′′ij
t
0 ≤ ψij ≤ c′′ij − wt−1
nj − n′′j j
Consistency of the φ, χ and ψ variables with the x flow variables requires χ = 0 (ψ = 0) if φ (if χ) does not
saturate its capacity. This is ensured, at optimality, by the properties of basic solutions. After rephrasing
(7):
0 ≤ φtij φtij + aij ut−1
j ≤ cij (8)
0 ≤ χtij χtij + a′ij vjt−1 ≤ c′ij
t
0 ≤ ψij t
ψij + a′′ij wjt−1 ≤ c′′ij
where
cij − c′ij c′ij − c′′ij c′′ij
aij = a′ij = a′′ij =
n′j n′′j − n′j nj − n′′j
and aij < a′ij < a′′ij , we observe the following fact (that can be generalized to any piecewise linear approxi-
mation of the congestion curve).
Proposition 1. Suppose that, in a feasible solution, ūti < n′i and v̄it > 0. Let
δ = min{n′i − ūti , v̄it }
Then a solution with uti = ūti + δ, vit = v̄it − δ and the other components unchanged is also feasible and no
worse than the given one.
Proof. See [3]
It is worth mentioning that, the polyhedron in the new varables is not necessarily integral. For large flows,
however, the linear relaxation provides a sufficiently good approximation to an optimal integer solution.
4 Setting model parameters
To get a reliable model, parameters must be set to numbers that reflect reality. Those numbers depend on
several considerations, the most relevant being: model granularity, walking velocity in various conditions (on
a flat, on staircases etc.), door (and staircase) entrance capacities, room (and staircase) capacities.
4.1 Model granularity
The issue of model granularity touches both spatial and temporal units, and affects the shape and size of the
unit cells in which the building is decomposed, as well as the slots that form the evacuation time horizon.
As described in the previous sections we embed the building plan into a grid, whose cells are assumed
isometric: that is, can be crossed in any direction in the same amount of time. That amount will define
the time slot duration, and cells will be regarded as virtual unit rooms that communicate one another via
physical or virtual (i.e., open space) doors, see Figure 1.
Grid geometry can vary. Ideal isometric cells are circles, but circles are not embeddable into a grid with
adjacent cell sides. Hexagon cells are a good compromise between isometry and plan embedding. However,
in our study case we found room sizes and shapes well compatible with a square grid where each room is
split into an integer number of cells.
4.2 Walking velocity
The cornerstone on which the length of each unit time slot in T — and consequently its reciprocal, the
monitoring frequency — is established, is the free flow walking velocity, i.e. the speed at which humans prefer
to walk in non-congested and non-hampered conditions. Clearly, its value varies for different categories of
people (child, adult, elderly, disable etc.) and slope (flat, upstairs, downstairs). This parameter is important
to perceive the distance that an individual can possibly walk during a specific period of time. Through its
evaluation one can define the cells in which an area is to be divided for best approximation of traveling time.
Table 1 reports different evaluations of pedestrian free flow velocity found in literature.
Table 1: Pedestrian free flow velocity.
Flat (m/s) Reference Stairs (m/s) Reference
under 65 over 65 up down
1.36 Fruin 1971 [6] 0.56 0.65 Fruin 1971 [6]
1.36 Weidmann 1993 [17] 0.61 0.69 Weidmann 1993 [17]
1.25 0.97 Knoblauch et al. 1996 [9] 0.8 ± 0.19 Kratchman 2007 [10]
1.042 - 1.508 0.889 - 1.083 TranSafety Inc. 1997 [16] 0.59 0.76 Jiang et al. 2009 [7]
1.20 Ye et al. 2008 [18] 0.81 ± 0.13 Fang et al. 2012 [5]
0.83 0.86 Patra et al. 2017 [12]
We assume the free flow walking speed for a flat surface equal to 1.25 m/s. Furthermore, in our study, the
flow is rarely upward and almost all people are supposed to go to safe places located at the building ground
floor: for this situation, we consider a downstream free flow speed of 0.76 m/s.
4.3 Door capacity
The capacity of a door depends on such various aspects as user composition, door type (always open, open
when used, turnstile), crowdedness and, last but not least, door width. A study by Daamen et al. [4] focuses
on the relationship between door capacity, user composition and stress level, arguing an average 2.8 persons
per second for a 1-meter width door (p/m/s). Peschl [13] found 2.25 p/m/s. Public authorities fix different
standards for door capacities: for example, the Dutch Ministry for Housing, Regional Development and the
Environment allows considering a maximum of 90 persons per meter width during a safe escape time of one
minute; the same flow rate is suggested by the Japanese building standard law.
Experiments conducted by Kretz et al. [11] demonstrate a linear decrease of the capacity with increasing
bottleneck width (ranging from 2.2 p/m/s for 40 cm to 1.78 p/m/s for 70 cm width) as long as only one
person at a time can pass. Larger doors, however, are credited a constant value of 1.8 p/m/s.
None of the aforementioned studies considers bidirectional flow through doors, and so do we in our
optimization model: in fact, although bidirectional flows are in principle possible, they will never occur in
an optimal solution even without considering flow rate reductions due to collisions.
We assume 1.2 p/m/s for every door, meaning that a maximum number of 6 persons can pass through a
1-meter width door per time slot (5 seconds). We also assume capacity proportional to door width.
Staircase capacity is treated differently. Fruin [6] measures a maximum flow capacity of 5.5881 persons/s
for a 5.6 width staircase, i.e., about 1 p/m/s. Weidmann [17] obtains 0.85 p/m/s for the same parameter.
We stay at Fruin’s estimate and use 1 p/m/s for each staircase in our example.
4.4 Cell capacity
The pedestrian density is the number of persons per square meter monitored at any time. This information
is crucial for crowd safety and evacuation performance, as movements are dramatically reduced in highly
dense areas. As density increases, pedestrian movements become constrained and flow rate consequently
decreases. According to UK fire safety regulations, the maximum allowed density corresponds to 0.3 square
Figure 3: Embedding of Palazzo Camponeschi’s plan into a square grid: ground floor up-left; first floor down-right.
meters per standing person, a value that increases to 0.5 for public houses, to 1.0 for dining places, to 2.0
for sport areas and to 6 for office areas. In our case study — gallery indoor space — the maximum capacity
of each cell is calculated by assuming 0.8 square meters per visitor, that is 1.25 persons per square meter.
5 Example of application
Using the measures discussed in the previous section, we next describe an application of the model of Section
3.2 to the safe evacuation of Palazzo Camponeschi, a building in l’Aquila (Italy) normally used for exhibitions.
Safety conditions of the building, which consists of 31 rooms including corridors, are supervised by L’Aquila
Fire Brigade. Rooms sizes vary in a large range, and so the average time of a person to cross them from
door to door is required. As explained in §3.1, we split each room in unit cells, each behaving as a (virtual)
quasi-square room that can be traversed in a unit time slot. In practice, we embedded the building plan into
a quasi-square grid as shown in Figure 3.
The embedding results in a graph with 109 nodes (Figure 4) corresponding to the cells of Figure 3 and
including node 0 as safe place. Adjacent cells are linked by 259 arcs which allow people flow inside the
building. All arcs are assumed bidirectional except the three towards the safe place. A time slot corresponds
to the time required for crossing one cell: using average free flow speeds from §4.2 and considering cell
size, we obtained time slots of 5 seconds each, and therefore the monitoring frequency. Door capacities vary
according on size and features. As a rule of thumb, no more than 6 persons can pass through a 1-meter width
door per monitoring frequency. Since downward free flow speed on stairs is lower than on a flat, staircase
and related arc capacities are reduced to 5 persons/meter every 5 seconds.
We next report the simulation of an emergency occurring in two different conditions in terms of building
occupancy (Scenarios 1 and 2) and route prescription. In both simulations, we computed the minimum time
0
49 46 45 40 39 34 33 28 27 22 21 16 15 10 9 4 3
50 47 44 41 38 35 32 29 26 23 20 17 14 11 8 5 2
48 43 42 37 36 31 30 25 24 19 18 13 12 7 6 1
102 101 100 103 104 105 106 107 108
98 97 92 91 86 85 80 79 74 73 68 67 62 61 56 55 51
99 96 93 90 87 84 81 78 75 72 69 66 63 60 57 54 52
95 94 89 88 83 82 77 76 71 70 65 64 59 58 53
Figure 4: Network associated with the plan of Figure 3.
required to N persons, randomly distributed in the building room, for reaching a safe place. The code for
simulation was written on OPL language and solved on CPLEX version 12.8.0. We ran all the experiments
on a Core i7 2.7GHz computer with 16Gb of RAM memory under Windows 10 pro 64-bits.
Table 2: Evacuation and computation time - Scenario 1: a) ideal flows; b) prescribed routes.
τ evacuees (a) CPU Time (a) evacuees (b) CPU Time (b)
1 30 0,29 sec 30 0,29 sec
2 60 0,43 sec 60 0,43 sec
3 90 0,42 sec 90 0,21 sec
4 120 0,36 sec 120 0,37 sec
5 150 0,39 sec 150 0,28 sec
6 180 0,43 sec 180 0,34 sec
7 210 0,59 sec 210 0,32 sec
8 240 0,68 sec 240 0,28 sec
9 270 0,50 sec 270 0,31 sec
10 300 0,81 sec 300 0,32 sec
11 330 0,61 sec 330 0,43 sec
12 360 0,93 sec 360 0,37 sec
13 390 1,10 sec 390 0,56 sec
14 420 0,82 sec 417 0,45 sec
15 450 0,95 sec 442 0,46 sec
16 480 1,06 sec 467 0,48 sec
17 510 1,15 sec 492 0,48 sec
18 528 1,15 sec 511 0,54 sec
19 524 0,65 sec
20 528 0,56 sec
In the first simulation we suppose an initial occupancy of N = 528: this datum comes from an experiment
performed in L’Aquila during the Researchers Night event on 29 September 2017, when the simultaneous
presence of 528 people in Palazzo Camponeschi was recorded as peak value.
We solved problem (1)-(8) for τ = 1, 2, . . . until a solution of value N is found. Table 2 reports the number
of evacuees (column 2) at each τ and the computation time of each resolution step (column 3). In terms of
evacuation time, everyone has reached a safe place in 1 minute and 30”. As shown in the table, computations
require 1.15 seconds (presolve included) in the worst case and are therefore totally compliant with real-time
applications.
In a second scenario, we repeated the simulation doubling the number of people in the building. In this
180
160
people not yet evacuated
140
120
Scenario 1: 528 individuals
100
80
60
40
20
0
60 65 70 75 80 85 90 95 100 time (seconds)
all paths (ideal) shortest paths
300
people not yet evacuated
250 Scenario 2: 1,056 individuals
200
150
100
50
0
130 135 140 145 150 155 160 165 170 175 180 185 190 195 200 time (seconds)
Figure 5: Ideal evacuation and evacuation along shortest paths in two scenarios.
case everyone can reach a safe place after 36 time slots, i.e., 3 minutes. Also in this case computation time
is definitely short, being always under 3.39 seconds including presolve.
This first simulation depicts an ideal situation in which flows autonomously choose the best among all
the available routes in the building. Of course, managing such an ideal evacuation is not easy and perhaps
unpractical. As a general practice, in fact, evacuation is conducted through pre-determined routes. In a
second simulation, then, we suppose that the prescribed evacuation routes are the shortest paths from any
cell to the safe place. In this situation, evacuating 528 (1056) individuals takes of course more time: 1 minute
and 40” (3 minutes and 20”).
By comparing this simulation to the previous one, we observe that people flows plainly for some time
(1 minute and 5” in the first scenario, 2 minutes and 10” in the second). After that time, shortest routes
start experiencing congestion, and evacuation is slowed down. The phenomenon is illustrated in the charts
of Figure 5: as one can expect, the tail of people still in the building increases with initial occupancy.
6 An IoT Evacuation Handling Infrastructure
The mathematical model and algorithm described in this paper are part of an IoT infrastructure for evacu-
ation handling. The IoT infrastructure, whose architecture is sketched in Figure 6, is designed to collect the
required run-time data. It is studied to be tolerant to faults (therefore to guarantee correct response also
in emergency case), performant (in terms of computational time and resources), and to include both situa-
tional awareness sensors (such as disaster detectors, people counters, DVR cameras, and RFID technologies
to count the number of people in closed spaces, to get information about their velocity, and direction) and
actuators (e.g., to close or open windows or doors, to display evacuation information). The computational
component adopted, that is the subject of the present paper, will thus become the central element that,
while inputting situational awareness information, will provide evacuation recommendations.
This information is going to be displayed into a mobile app. The main goal of the application, to be run
on a tablet, is to show a 2D-representation of the monitored space providing also contextual data on where
Figure 6: Architecture of the IoT infrastructure.
the crowd is at any time, and how it moves in normal and emergency cases. In this line, we have recently
implemented the visualization of the crowd heat-map on mobile devices. Given such a visualization, actuators
might be piloted directly from the mobile app in order to direct people through the fastest evacuation path.
While we do not expect, neither wish to, remove humans from the decision process, our project wants
to support their decisions by providing run-time information — that could be unavailable otherwise — by
periodically re-calculating best evacuation paths or evaluating minimum evacuation time under conditions
that can vary from time to time. Just to list a couple of possibilities, (a) new sources of emergencies can be
shown at run-time, (b) unexpected human behaviors can be taken into account.
7 Conclusions
This work uses a run-time network flow model for supporting the rapid evacuation of people from a building
in case of emergencies. The model takes as input both static information (such as building dimension and
structure, room capacities, door capacities) and run-time information (such as number of people in the
building, number of people in specific rooms and corridors) acquiring it through IoT devices.
The building topology is described by a graph. Run-time data are used to create a time-indexed acyclic
digraph that models all the feasible transitions between adjacent rooms at any time. Minimizing the total
evacuation time corresponds to solve max flow problems with non-linear capacities that model congestion.
Preliminary evaluations have been conducted on a real case.
Future work includes to: i) enrich the model with further design-time and run-time information to make
the evacuation plan more accurate; ii) empirically evaluate the model in extensive scenarios, and to compare
estimated vs. real data (as, e.g., those generated during evacuation tests); iii) complete the realization of
the IoT infrastructure and app mentioned in Section 6 using the computational component here developed.
References
[1] Abdelghany A, Abdelghany K, Mahmassani H, Alhalabi W. Modeling framework for optimal evacuation
of large-scale crowded pedestrian facilities, European Journal of Operational Research 237, 3 (2014)
1105-1118
[2] Chen P. H., Feng F. A fast flow control algorithm for real-time emergency evacuation in large indoor
areas, Fire Safety Journal 44, 5 (2009) 732-740
[3] Choi W, Horst W H, Suleyman T. Modeling of building evacuation problems by network flows with side
constraints, European Journal of Operational Research 35, 1 (1988) 98-110
[4] Daamen W, Hoogendoorn SP. Emergency door capacity: influence of door width, population composi-
tion and stress level, Fire Technology 48, 1 (2012) 55-71
[5] Fang ZM, Song WG, Li ZJ, Tian W, Lv W, Ma J, Xiao X. Experimental study on evacuation process
in a stairwell of a high-rise building, Building and Environment 47 (2012) 316-321
[6] Fruin, JJ. Pedestrian planning and design, Metropolitan Association of Urban Designers and Environ-
mental Planners, New York, 1971
[7] Jiang CS, Deng YF, Hu C, Ding H, Chow WK. Crowding in platform staircases of a subway station in
China during rush hours, Safety Science 47, 7 (2009) 931-938
[8] Hoogendoorn SP, Daamen W. Pedestrian behavior at bottlenecks, Transportation Science 39, 2 (2005)
147-159
[9] Knoblauch R, Pietrucha M, Nitzburg M. Field studies of pedestrian walking speed and start-up time,
Transportation Research Record: Journal of the Transportation Research Board 1538 (1996) 27-38.
[10] Kratchman JA An investigation on the effects of firefighter counterflow and human behavior in a six-
storey building evacuation Thesis (2007)
[11] Kretz T, Grünebohm A, Schreckenberg M. Experimental study of pedestrian flow through a bottleneck,
Journal of Statistical Mechanics 10 (2006) P10014
[12] Patra M, Sala E, Ravishankar KVR. Evaluation of pedestrian flow characteristics across different facil-
ities inside a railway station, Transportation Research Procedia 25 (2017) 4763-4770
[13] Peschl IASZ. Evacuation Capacity of Door Openings in Panic Situations, Bouw 26 (1971) 62-67 (in
Dutch)
[14] Schloter M, Skutella M Fast and memory-efficient algorithms for evacuation problems, Proceedings of
the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (2017) 821-840
[15] Taneja L, Bolia N. B. Network redesign for efficient crowd flow and evacuation, Applied Mathematical
Modelling 53 (2018) 251-266
[16] TranSafety Inc. Study compares older and younger pedestrian walking speeds, Road Management &
Engineering Journal (1997)
[17] Weidmann, U. Transporttechnik der Fußgänger: transporttechnische Eigenschaften des
Fußgängerverkehrs (Literaturauswertung), IVT Schriftenreihe 90 (1993) (in German)
[18] Ye J, Chen X, Yang C, Wu J. Walking behavior and pedestrian flow characteristics for different types of
walking facilities, Transportation Research Record: Journal of the Transportation Research Board 2048
(2008) 43-51