=Paper=
{{Paper
|id=Vol-1778/AmILP_7
|storemode=property
|title=Evacuation Centrality: Agile Evacuation Routing in Unpredictable Hazardous Conditions
|pdfUrl=https://ceur-ws.org/Vol-1778/AmILP_7.pdf
|volume=Vol-1778
|authors=Marin Lujak,Stefano Giordani
|dblpUrl=https://dblp.org/rec/conf/ecai/LujakG16
}}
==Evacuation Centrality: Agile Evacuation Routing in Unpredictable Hazardous Conditions==
https://ceur-ws.org/Vol-1778/AmILP_7.pdf
Evacuation Centrality: Agile Evacuation Routing in
Unpredictable Hazardous Conditions
Marin Lujak 1 and Stefano Giordani 2
Abstract. In this paper, we study the agility of evacuation routes or walls. If the primary escape route is blocked, there is usually a
in relation to dynamically changing unpredictable hazardous con- second escape route, which is marked on an evacuation plan. More-
ditions. Infrastructure safety conditions may unpredictably change over, if visibility is limited due to smoke, evacuees should follow the
through time. Due to unpredictability, evacuees’ safety can get jeop- emergency lights situated close to floor level.
ardized at any point of the evacuation route. Thus, it is not sufficient The routes in evacuation plans are predefined and static. In the
only to find the shortest evacuation route considering present safety case there is a blockage of these routes, evacuees are provided with
conditions, but we should also consider other relevant characteristics no alternatives. Moreover, since the evacuation plans are randomly
that make the evacuation route sufficiently safe through time. With present in the evacuation infrastructure, evacuees might not get the
this aim, we propose a new node importance metric called evacuation necessary evacuation information. This may have hazardous conse-
centrality, inspired by betweenness centrality. The node evacuation quences and may result in panic.
centrality is a parameter that represents the importance of the node The concepts of rapidness and seamlessness, which are necessary
for evacuation considering the availability of alternative safe and effi- in evacuation, are closely related to the concept of agility. Oxford
cient routes from that node towards safe exits. Relatedly, we propose dictionary (2016) describes the term agile as “the ability to move
the concept of agility of an evacuation route, which represents the quickly and easily” and “the ability to think and understand quickly”.
ability of a route to efficiently and safely reroute from the route’s It is a well known concept in many areas, such as, e.g., manufac-
constituent nodes in case of contingencies. Given a building network turing, software development, and business organization, see, e.g.,
with a set of evacuees’ positions and safe exits, we mathematically [2, 12, 13]. In terms of outcomes, agility is a means of a system to
formulate the problem of finding agile evacuation routes. In addition, swiftly and easily handle continuous and unanticipated change by
we propose a solution method for that problem. The functioning of adapting its initial stable configuration and to effectively manage un-
the proposed method is demonstrated by means of a case study. predictable external and internal changes, e.g., [12, 13]. Based on
this conceptualization and paradigms of agile manufacturing and ag-
ile business systems, in this work we propose the concept of agility
1 Introduction in evacuation routes and route recommendation systems.
Emergencies or disasters occur unexpectedly and disrupt human ac- Agility of an evacuation route assures to an evacuee a high reactiv-
tivities and cause physical and/or environmental damage. They can ity to safety changes possibly occurring along the route. It expresses
strike anyone, anytime, and anywhere. Emergencies may be natural the ability to reroute from intermediate nodes to alternative routes to-
or manmade, small scale, as e.g., in a building due to an explosion or wards safe exits. Agile route recommendation systems, hence, should
fire, or large scale, as e.g., in a city or a region because of a radiolog- be capable to run in real time in the cycle sense-analyze-decide-act.
ical accident, bombardment or dangerous weather system. To achieve it, we need complete, accurate and up-to-the-minute situa-
Emergency evacuation is the immediate and urgent movement of tional awareness along the route. While in the open spaces, GPS and
people away from the threat or actual occurrence of a hazard. In this e.g., 3G and 4G communication can be used, in inner spaces, this
situation, evacuees should be able to evacuate safely, rapidly, seam- requirement can be facilitated by the interaction of ambient intelli-
lessly, and in a coordinated way through an evacuation space while gence and smartphone technologies. Hence, an agile evacuation route
avoiding hazardous conditions. recommendation system should respond quickly in inner and open
Traditional evacuation approaches are based on the following pro- spaces to sudden changes in evacuation safety conditions caused by
cedure. In the case of an imminent or ongoing danger, evacuation a hazard, crowdedness or any other type of requirement or disruption.
is organized by a trained personnel that coordinates the evacuation To the best of our knowledge, the literature on such route recommen-
process on critical evacuation points. In larger watercrafts, these are dation systems is very scarce (Section 2).
dedicated areas where evacuees must assemble in case of emergency We model evacuation agility of a route in terms of the character-
(assembly stations). Each evacuee should reach his/her assembly sta- istics of its intemediate nodes. For this scope, we examine relevant
tion or exit by following the escape route shown on a plan which is node centrality measures and propose new node importance metrics
usually positioned on a limited number of positions in the building, called evacuation centrality in Section 3. The evacuation centrality
and the signs in the corridors and stairs that are attached on the floor is a measure that represents the importance of a node for evacuation
considering the availability of alternative temporally efficient safe
1 CETINIA, University Rey Juan Carlos, Madrid, Spain, Email: routes from that node towards safe exits.
marin.lujak@urjc.es Given a building network with a set of evacuees’ positions and
2 Dept. of Enterprise Engineering, University of Rome “Tor Vergata”, Rome,
safe exits, in Section 4 we mathematically formulate the problem of
Italy, Email: stefano.giordani@uniroma2.it
finding agile evacuation routes, where by agile we mean the ability predictability of safety conditions. In this case, it might thus result in
to efficiently and safely reroute from the route’s constituent nodes in evacuees’ fatalities. Moreover, in [8], we consider the influence of af-
case of unpredictable safety drops. We conclude the paper in Section filiate ties among evacuees and their interaction with self-concerned
6. individuals and model self-concerned and social group behavior via
individual and team reasoning. The recommended evacuation routes
take in consideration the affiliate ties to guarantee evacuee’s compli-
2 Related work ance with the routes.
Building evacuation has been studied over the last decades from The aforementioned papers assume steady evacuation state and do
different perspectives such as, e.g., evacuees’ behaviors, traffic co- not treat the safety dynamics in transitory evacuation safety condi-
ordination strategies, and evacuation route optimization, see, e.g. tions. Therefore, in this paper, we concentrate on evacuation routing
[1, 3, 8, 9, 10, 11]. For example, Pursals and Garzon in [11] con- in highly unpredictable dynamically changeable hazardous evacua-
sidered the building evacuation problem and developed a model for tion safety conditions. In this case, it is important to find the shortest
selecting the proper routes for movement of people in a building dur- safe routes for all evacuees considering other relevant characteristics
ing an emergency situation. Abdelghany et al. in [1] present a simula- that make the evacuation route sufficiently safe through time.
tion - optimization modeling framework for the evacuation of large -
scale pedestrian facilities with multiple exit gates. The framework in- 3 Centrality measures for evacuation routing
tegrates a genetic algorithm (GA) and a microscopic pedestrian sim-
ulation - assignment model. The GA searches for the optimal evac- Generally, centrality measures indicate the most important nodes of a
uation plan, while the simulation model guides the search through network. Some of the measures relevant for the computation of routes
evaluating the quality of the generated evacuation plans. Evacuees are node degree, eigenvector, and betweenness centrality. In the fol-
are assumed to receive evacuation instructions in terms of the opti- lowing, we describe the relevance of these measures to evacuation
mal exit gates and evacuation start times. The framework is applied routing and identify their flaws in this respect.
to develop an optimal evacuation plan for a hypothetical crowded ex-
hibition hall. A mixed-integer programming solver is used to derive 3.1 Degree centrality
routing plans for sample networks.
Conventional emergency evacuation plans often assign evacuees The degree centrality Cd (i) of node i ∈ N of a graph G = (N, E),
to fixed routes or destinations based mainly on geographic proxim- where N is a set of nodes and E is a set of edges, is the number
ity. Such approaches can be inefficient if the roads are congested, of arcs incident to the node. In directed graphs, we can either use
blocked, or otherwise dangerous because of the emergency. Han and the in-degree, the out-degree, or their combination as the degree cen-
Yuan proposed in [3] the concept of most desirable destination for trality value. When we combine in-degrees and out-degrees, we are
evacuees. This concept recognizes that municipalities responsible for basically ignoring arc directions.
large-scale evacuation have routinely assigned evacuees to routes and In general, nodes with a higher degree centrality tend to be used
destinations based on limited experience and intuition rather than by more paths. However, connections of a node with the neighbor-
methodical optimization processes. Even with the implementation of ing nodes that are a part of the shortest paths to safe exits are more
dynamic traffic assignment, models that are based on fixed origin- important than others. Since the degree centrality does not guarantee
destination tables are inefficient when a destination becomes difficult the connectedness of a node to safe exits, it cannot be used in the
(or impossible) to access due to congestion or blockage. In [3], op- computation of efficient safe evacuation routes.
tions that allow evacuees flexibility in selecting their exit routes and
destinations are explored.
3.2 Eigenvector centrality
Destination assignment and route assignment to enable optimal
evacuation operations are interrelated. To optimize the routing prob- A step forward the evacuation route’s efficiency guarantee is the
lem, one has to know the destinations; to optimize the destination as- eigenvector centrality of a node, which depends both on the num-
signment, one has to know the minimal travel time, and hence route ber and the importance of its adjacent nodes. In general, adjacency
assignment to all destinations. of a node to nodes that are themselves adjacent to more important
To address the inherent complexity of the problem, Han et al. in nodes will give a node more importance.
[3] devised a framework for simultaneously optimizing evacuation- While node degree centrality counts walks of (geodesic) unitary
traffic destination and route assignment. Based on this framework, length from a node, the eigenvalue centrality takes into considera-
we can determine the optimal evacuation-destination and route as- tion walks of length infinity. It is the expected number of visits to a
signment using a one-step optimization procedure. node i ∈ N of an infinite random walk over graph G = (N, A). It
In [7], we propose a pedestrian route recommender system for can only be calculated for connected undirected graphs and strongly
smart spaces in steady state conditions that recommends the safest connected digraphs. More formally, if we let Ad = (ai,j ) be the
routes to pedestrians and simultaneously optimizes conflicting objec- adjacency matrix of graph G = (N, A), eigenvector centrality Ce (i)
tives of finding the social optimum and minimizing individual path of node i ∈ N is given by:
travel times while considering people flow and fairness, similarly
to [5, 6]. Moreover, the system considers the influence of stress on 1 X
Ce (i) = ai,j Ce (j), (1)
human reactions to the recommended routes and iteratively ponders λ
j∈N \{i}
user response to the suggested routes influenced by stress-related ir-
rational behaviors until system acceptable routes are found. However, where λ 6= 0 is a constant. In matrix form, we have λCe = Ad·Ce .
in the case of a sudden safety drop on a part of the route, it might Hence the centrality vector Ce is the eigenvector of the adjacency
not be able to guarantee a safe evacuation of the safety jeopardized matrix Ad associated with the eigenvalue λ. If we choose λ as the
areas since in the route recommendation, it does not consider the un- largest eigenvalue in absolute value of matrix Ad, then as a result
of Perron-Frobenius theorem, if matrix Ad is irreducible (i.e., the Thus, we modify the betweenness centrality measure in the fol-
graph is (strongly) connected), then the eigenvector solution Ce is lowing way. If we substitute the geodesic distance with a path travel
both unique and positive. time cp ≥ 0, most probably there will be only one fastest path for
The nodes with a high eigenvector centrality values, then, will be every pair of nodes. This is why, here, we present a modification
traversed by more paths. Moreover, nodes with a high eigenvector of betweenness centrality that considers kod distinct temporally ef-
centrality are network hubs and their presence is crucial in maintain- ficient paths for each (o, d) pair, with o ∈ O and d ∈ D. Here, by
ing the paths among all network nodes. However, a high centrality kod temorally efficient paths, we mean the number of distinct paths
value of a node does not guarantee the existence of fast and safe of travel time at most, e.g., γ ·cod
min , where γ ≥ 1 is a maximum evac-
paths from that node towards safe exits. Additionally, a high eigen- uation route travel time tolerance factor and cod min the travel time of
vector centrality value of a node might be a root to panic and a related the path with the minimum travel time for (o, d) pair. In more detail,
herding problem [7] in the case of high people flows traversing the we define the evacuation centrality as follows.
node. Therefore, eigenvector centrality does not characterize suffi-
ciently the importance of the nodes for evacuation. Since we want Definition 3.1. Evacuation centrality C (i) of node i is a parameter
to find safe and fast evacuation paths towards a limited set of safe that represents the importance of node i for evacuation. The value
exit nodes, as such, it can not be directly used as a parameter for of the evacuation centrality of the node is the number of the safest
evacuation route optimization. sufficiently dissimilar (simple) temporally efficient paths from that
node towards safe exits constrained by the paths’ total cost (travel
time) cmax , i.e., cp ≤ cmax .
3.3 Betweenness centrality
In Definition 3.1, cmax is the maximum building’s evacuation
Betweenness centrality is a concept that is closer to the efficiency of
time.
evacuation routes and is a departure point in our proposition of the
evacuation centrality metrics. It is defined as the fraction of shortest
geodesic paths between nodes different than i ∈ N that i is a part of: 4 Agile evacuation routes: problem formulation
X X σod (i) If real-time infrastructure information is available to evacuees and
, ∀i 6= o 6= d ∈ N, (2) they can negotiate their routes, it becomes possible to provide a se-
o∈N d∈N
σod
lection of optimized routes. Therefore, we assume that the evacuees
where σod (i) is the number of shortest geodesic paths (the paths with are monitored by strategically positioned sensors as, e.g., cameras,
the minimum number of arcs) between origin node o and destination and are communicated with via smart space displays, acoustic signs,
node d and i ∈ N is an intermediate node of the path. Moreover, σod smart-phones, etc. Monitoring permits us both to recognize the evac-
is the total number of shortest geodesic paths between o and d. uees’ behavior as to perceive their momentary position and flow to-
Betweenness centrality is, therefore, an indicator of the frequency gether with their safety conditions. Furthermore, we assume that the
a node serves as the “bridge” on the shortest geodesic paths connect- evacuee flow demand is defined by the presence of infrastructure oc-
ing any two other nodes of the graph. That is, we find the shortest cupants at their momentary positions whose evacuation destinations
geodesic path (or paths) between every pair of nodes, and calculate are defined as the safe exits at which evacuees are considered to be
the fraction of these paths that node i lies on. If we imagine crowd safe.
flowing between nodes in the network and always taking the short- Our aim is, thus, to safely evacuate all the evacuation requests and
est possible geodesic path, then betweenness centrality measures the if not possible, then, as many people as possible within the allotted
fraction of that crowd that will flow through i on its way to wherever time period. To this aim, we should find agile evacuation routes to-
it is going. ward safe exits that consider evacuation centrality of the routes’ con-
Even though this measure might be relevant to the use cases with stituent nodes and other relevant characteristics that make the evacu-
constant arcs’ costs, the issues with the usage of betweenness cen- ation route sufficiently safe through time.
trality in evacuation are related with the definition of distance and
the origin-destination pairs. In particular, we are concerned with the 4.1 Evacuation network model
lowest evacuation time and not the shortest geodesic distance. More-
over, we are not interested in all origin destination pairs, but only in We represent a smart space evacuation network (building and/or ur-
a limited subset of evacuees’ origins O ⊂ N and safe exits D ⊂ N . ban district) by a directed graph G = (N, A), where N is a set of n
In the following, we deal with these two issues. nodes representing rooms, offices, halls, and, in general, a relatively
small portion of space within a building or other structure separated
by walls or partitions from other parts. In the case of larger spaces
3.4 Proposed evacuation centrality measure
that can host a larger number of people, for simplicity, the same are
When an unpredicted hazard occurs on a part of the evacuation route, divided into sections represented by nodes completely connected by
the same gets unsafe and impassable. If, in the computation of an arcs a ∈ A, where A is the set of m arcs a = (i, j). Here, nodes
evacuation route, we do not consider this fact and the related pos- i, j ∈ N and i 6= j represent physical or conceptual portals, doors,
sibility to reroute to other safe evacuation routes on its intermedi- and gateways connecting nodes i and j. Each arc (i, j) ∈ A has an
ate nodes, then, in case of contingency, rerouting towards safe areas associated cost cij , which in our case is its travel time tij . Moreover,
might be impossible causing imminent fatalities. Similar may occur each arc has also an associated safety Sij ∈ [0, 1]. Considering a
in the case of a too high flow of evacuees that might overload an critical safety value S cr , where 0 < S cr < 1, an arc is considered
evacuation route and cause panic. Therefore, for constituent nodes safe if Sij > S cr .
of each evacuation route, we need to find a sufficient number of the We opt for a directed graph representation of the evacuation in-
safest, dissimilar, and simple paths towards safe exits whose travel frastructure since in the case of bi-directional corridors, roads, and
time is preferably within some given maximum evacuation time. passages, we can easily reduce the undirected graph to the digraph by
connecting two adjacent nodes with an arc in each direction, while the length of path p is limited by the maximum building’s evacuation
in the case of unidirectional roads, representing the direction by an time cmax . Note that this formulation produces an unbounded lin-
(undirected) edge is not possible. ear program if there are negative cycles and under this condition the
Let O ⊆ N and D ⊆ N be the set of all evacuees’ origins and safe problem is in general NP-hard. However, in the case of evacuation
exit destinations, respectively. We assume that there are nO evac- network, all the arcs’ costs (travel times) are greater or equal to zero,
uees’ origin nodes o ∈ O disjoint from nD safe exit destination so we avoid this problem.
nodes d ∈ D, where nO + nD ≤ n. Finding the maximum number of arc-disjoint simple shortest
For the definition of origin-destination demand, we introduce fic- paths might result in a very limited number of solutions since the
titious sink node dˆ ∈ N that is adjacent to all the destination nodes number of arc-disjoint paths depends on the topology of the graph.
(safe exits) by fictitious (dummy) arcs. In this way, we assume that It will be limited from above by the number of outgoing arcs from
graph G includes (together with actual nodes) also fictitious node origin o and the number of incoming arcs to d. ˆ This is why we
dˆ and its incoming dummy arcs. Then, let w ∈ W be a generic opt for finding a number of sufficiently dissimilar paths for each
evacuation request from node o ∈ O to fictitious sink node d, ˆ i.e., evacuation origin-destination (O-D) pair. To this aim, a penalized
w = (o, d),ˆ where W is the set of all such evacuation requests. objective function, which takes into consideration the violation of
Moreover, let R be a vector of cardinality nO representing evac- Constraint (5) becomes:
uation requests from origins O towards fictitious safe exit d, ˆ where
Rodˆ = Rw entry indicates the demand of evacuees in unit time pe-
T
riod who request to leave origin node o ∈ O to go to any of the safe z(λA ) = max K − λA yA (7)
exits d ∈ D and, hence, to fictitious destination d.ˆ
Then a simple path p is a finite sequence of adjacent distinct nodes subject to
connected by a sequence of arcs, each connecting two adjacent (dif-
ferent) nodes. Its total travel time cp is composed of the travel times X X X
of the connecting arcs cij (xij ), where xij is people flow on arc φ(i,j),p xp − φ(h,i),p xp =
(i, j) ∈ p. Moreover, we define xp as a flow along path p ∈ Pw , p∈P j:(i,j)∈A h:(h,i)∈A
where Pw is a set of simple safe paths for evacuation request w
from origin o ∈ O to dummy node dˆ of travel time cp ≤ γcpmin . K,
if i = o
0, ˆ
if i ∈ N \{o, d} (8)
Furthermore, let safety S p of path p be the lowest safety value of
−K, if i = dˆ
the constituent arcs of the path, i.e., S p = mina∈p Sa . We search
for the safest paths, i.e., the paths whose safety S p ∈ [0, 1] is rela-
p
tively high and preferably higher than some critical safety Scr , where
p yA ≥ ΦxP − 1 (9)
0 < Scr < 1. Path p is considered safe if all its constituent arcs are
safe, i.e., if Sa > S cr for all a ∈ p.
yA ≥ 0, (10)
4.2 Finding node’s evacuation centrality measure
To determine evacuation centrality of each node, we need to xp ∈ {0, 1}, ∀p ∈ Pw , (11)
determine the maximum number of dissimilar simple paths from
origin node o to safe exits (destination nodes) i ∈ D subject to the where yA is a vector composed of non-negative variables related
condition that the cost cp of each path be not greater than a specified to a multiple usage of each arc a ∈ A by paths p ∈ Pw . λA is a non-
value, i.e., cp ≤ γcpmin . Mathematical formulation of this (maximum negative penalty vector of cardinality |A| for using each arc a ∈ A
network flow) problem is as follows: more than once. In this way, we penalize a multiple usage of arcs by
multiple paths.
(Z) Since we are not interested in the structure (i.e., the constituent
arcs) of dissimilar paths, but in the maximum number K of the same,
m = max K (3)
we can approximate the computation by assuming that path variables
subject to are continuous and, by doing so, we substitute Constraint (11) with
the following:
X X X
φ(i,j),p xp − φ(h,i),p xp = 0 ≤ xp ≤ 1, ∀p ∈ Pw . (12)
p∈P j:(i,j)∈A h:(h,i)∈A
Finally, for the best approximation, we resolve a dual of the former
K,
if i = o problem, i.e.,
0, ˆ
if i ∈ N \{o, d} (4) C = min z(λA ) (13)
ˆ
−K, if i = d
subject to
P λA ≥ 0. (14)
Φx ≤ 1 (5)
Note that the value of C is an upper bound on the number of
dissimilar paths and, therefore, also on the number of arc disjoint
xp ≥ 0, ∀p ∈ Pw , (6)
paths.
where Φ is the [|A| ∗ |PW |] arc-path incidence matrix and Pw is a The model will return a maximum number of dissimilar paths (of
set of simple safe paths from origin o ∈ O to dummy node dˆ of cost length at most cmax . It is easy to demonstrate that z(λA ) ≥ m for
cp ≤ γcpmin . In particular, γcpmin ≤ cmax , i.e., the upper bound on any λA ≥ 0.
4.3 Finding agile evacuation routes traditional models. It enables pedestrians to follow a proposed path
by following visual, tactile, acoustic or audio-haptic signals. Vector
Once we find the evacuation centrality measure value for each node gkA = [g1k , . . . , g|E|
k
] specifies an egress decision at each passageway
of the evacuation network, we can proceed with finding agile evac-
for routes k ∈ P̄w , ∀w ∈ W . These decisions, when filtered for each
uation paths for each evacuation origin node o ∈ O i.e., each node
member of route k ∈ P̄w for each O-D pair w ∈ W depending on
with present evacuees. The formula for the computation of agility Λp
his/her affiliate ties, provide an individual’s route plan.
of a path p is the following one:
A possible rereouting recommended by the system is performed
sY in regular time intervals by the algorithm’s execution considering the
Λp = |p| C (a), (15) evacuees’ momentary positions. The evacuees are given only a nec-
a∈p essary information of the next part of the route to pass, without satu-
rating them with the unnecessary route information that may change
where |p| is the number of nodes in the path. We opt for the formula- through time.
tion of agility by using geometric mean since it balances the average
and minimum values of the evacuation centralities of the path’s con-
stituent nodes. Moreover, let Λcr be a critical agility value, such that 5 Case Study
a route is considered sufficiently agile if Λp ≥ Λcr .
We demonstrate the functionality of the proposed approach by means
After computing agility of each available path, we recommend to
of a simple case study example in Figure 1, which is a modified ver-
evacuees only the paths that are sufficiently agile.
sion of the example appearing in [7].
Moreover, we propose to find routes over arcs that are sufficiently
short in terms of travel time and, therefore, introduce an upper bound
on an admissible arc’s cost (e.g., travel time) carc
max such that:
ca (xa ) ≤ carc
max , ∀a ∈ A. (16)
The value of carc
max is related both to the structure of the evacuation
network as to the evacuees’ maximum allowed travel time on each
arc. In this light, if we introduce (16) into the path’s optimization
constraints, if all arcs are very large, then putting a too low value
on carc
max and relaxing (16) will result in a too high cost in terms of
relaxation penalties, while if carc
max is too high, then all arcs will be
acceptable from this point of view.
Since (16) introduces further complexity to the problem since it
might give non-integer solutions, we opt for a modelling approach
that multiplies the costs of the arcs that do not comply with (16) with
a very high number M such that in the case there is no alternative
arc for the computation of a shortest path, these origin-destination
pairs include the arcs with such high arcs’ values. On the contrary,
if there are arcs available that comply with Constraint (16), they will
be taken into consideration first for finding evacuation paths.
4.4 Proposed agile evacuation route Figure 1: A simple case-study example of an evacuation network
recommendation system
The objective of the proposed agile evacuation route recommenda-
tion system is to find agile evacuation routes for all pedestrians. Given is an evacuation scenario of a building network with 6 nodes
We assume the presence of a set of node agents N who communi- and 7 arcs, as seen in Figure 1. The network contains two evacuation
cate and compute pedestrian routes in a distributed manner similar to origin nodes, o1 and o2 , two transit nodes, 3 and 4, and two evacu-
[6]. Pedestrians request their route from the smart space node agent ation destination nodes (safe exits) d1 and d2 . Moreover, given are
closest to the origin of their evacuation (origin agent o). Based on the arcs’ travel times cij , [min], and arcs’ safeties Sij for all arcs (i, j)
total evacuation demand expressed in terms of person flow per time as seen in Figure 1. Note that all the arcs of the network have fixed
unit, each origin agent o tries to achieve a sufficient number of short- travel times except for the arcs (o1 , d1 ) and (o2 , d2 ) whose travel
est paths towards a dummy destination node d. ˆ This demand is made times depend on the flows of people on these arcs.
by the persons starting the evacuation on o and the paths are com- Let us assume that the critical safety both for arcs and paths is
puted through, e.g., modified Yen’s loopless k-shortest path routing Scr = 0.55 such that our case-study evacuation scenario contains all
algorithm [4]. safe arcs. Moreover, given is the tolerance factor for the maximum
After the traffic assignment is made for O-D pairs, the latter decide allowed evacuation route cost (travel time), γ = 1.2. The objective
on the pedestrians’ assignment to the paths based on relevant social is to find agile evacuation paths towards safe exits for all evacuation
welfare parameters that guarantee equality through an iterative auc- demands.
tion. The negotiation through auctions is local between each origin In the following, we analyze the case study network and find the
agent and the persons starting their travel at that origin, similar to [6]. value of evacuation centrality measure C for each node. Evacuees
Guidance gak is considered a decision variable for each arc a ∈ from all origins can use all safe exits for their evacuation based on
A and each path k ∈ P̄w , w ∈ W instead of flow rate xa as in their personal preferences and overall safety constraints. If there does
not exist any path p from a node to any of safe exits with S p > Scr , value Λp1 = Λp2 = 4, 472. Other three paths have the path agility
this approach will propose the least unsafe paths. value Λp = 3, 936.
Evacuees are located at the evacuation origin nodes o1 and o2 The critical agility of the evacuation paths is assumed to be Λcr =
and have available two safe exits for evacuation (evacuation desti- 2, so all the paths are sufficiently agile for evacuation. For origin o2 ,
1
nation nodes). Starting at node o1 , there are two O-D pairs available, the two paths with the highest evacuation
1
values are po2 d2 = (o2 , d2 )
(o1 , d1 ) and (o1 , d2 ). For the evacuees at node o2 , there are two pos- and po2 d1 = (o2 , 3), (3, o1 ), (o1 , d1 ) , both with the value Λp1 =
sible evacuation O-D pairs, (o2 , d1 ), and (o2 , d2 ). For each of the Λp2 = 4, 472. These paths are first recommended to evacuees.
pairs (o1 , d1 ) and (o2 , d2 ), there are three simple paths available. For
the pairs (o1 , d2 ) and (o2 , d1 ), there are four simple paths available
6 Conclusions
for each pair.
In any case, the travel time of temporally efficient paths can- In this work we studied the agility of evacuation routes in relation to
not surpass the tolerance factor γ · cod min in respect to the fastest dynamically changing unpredictable hazardous conditions in smart
path. Therefore, temporally efficient paths for O-D pair (o1 , d1 ) are spaces. We analyzed node’s degree, eigenvalue, and betweenness
p1o1 d1 = (o1 , d1 ) with travel time cp1 = 6xo1 d1 and po1 d1 =
2
centrality measure and proposed the term of evacuation centrality re-
(o1 , 3), (3, 4), (4, d1 ) with travel timecp2 = 60. Path p3o1 d1 = lated with the node’s importance for evacuation. Moreover, we intro-
(o1 , 3), (3, o2 ), (o2 , d2 ), (d2 , 4), (4, d1 ) with travel time cp3 = duced and defined the term of agility in evacuation routes and math-
7xo2 d2 +110 is not temporally efficient. As a consequence, the travel ematically formulated agile evacuation route problem and discussed
time for O-D pair (o1 , d1 ) will be no more than 60 min. its capability to adjust to possible contingencies through time.
Depending on flow xo2 d2 on arc (o2 , d2 ), the shortest paths In future work, we intend to analyze in depth the efficiency of
for O-D pair (o2 , d2 ) will be p1o2 d2 = (o2 , d2 ) with travel time our approach related with unpredictable safety drops through simu-
cp1 = 7xo2 d2 and p2o2 d2 = (o2 , 3), (3, 4), (4, d2 ) with travel time lations on building networks of varying complexity. Related is the
cp2 = 70. Path p3o2 d2 = (o2 , 3), (3, o1 ), (o1 , d1 ), (d1 , 4), (4, d2 ) issue of scalability. We plan to evaluate real-time responsiveness of
with travel time cp3 = 6xo1 d1 + 110 is not temporally efficient so our approach to varying number of evacuees and a varying size of the
that the travel time for O-D pair (o2 , d2 ) will be no more than 70 evacuation network.
min.
For O-D pair o1 − d2, temporally efficient paths are p1o1 d2 =
ACKNOWLEDGEMENTS
(o1 , d1 ), (d1 , 4), (4, d2 ) with travel time cp1 = 6xo1 d1 + 55,
p2o1 d2 = (o1 , 3), (3, o2 ), (o2 , d2 ) withtravel time cp2 = 7xo2 d2 +
This work has been partially supported by the Autonomous Re-
55, and p3o1 d2 = (o1 , 3), (3, 4), (4, d2 ) with travel time cp3 = 65. gion of Madrid through grant “MOSI-AGIL-CM” (P2013/ICE-3019)
Path p4o1 d2 = (o1 , d1 ), (d1 , 4), (4, 3), (3, o2 ), (o2 , d2 ) with travel co-funded by EU Structural Funds FSE and FEDER, “SURF”
time cp4 = 6xo1 d1 + 7xo2 d2 + 65 is not temporally efficient due to (TIN2015-65515-C4-4-R) funded by the Spanish Ministry of Econ-
its too high travel time in any case of the flows on arcs (o1 , d1 ) and omy and Competitiveness, and by an STSM Grant from COST Ac-
(o2 , d2 ). Thus, O-D pair (o1 , d2 ) has three temporally efficient paths tion IC1303.
available whose traversal time will be no more than 65 min.
Similarly, O-D pair o2 − d1 , depends on flows on arcs
REFERENCES
(o1 , d1 ) and (o2 , d2 ). Temporally efficient paths will be p1o2 d1 =
[1] Ahmed Abdelghany, Khaled Abdelghany, Hani Mahmassani, and Wael
(o2 , 3), (3, o1 ), (o1 , d1 ) with travel time cp1 = 6xo1 d1 + 55,
Alhalabi, ‘Modeling framework for optimal evacuation of large-scale
p2o2 d1 = (o2 , d2 ), (d2 , 4), (4, d1 ) withtravel time cp2 = 7xo2 d2 +
crowded pedestrian facilities’, European Journal of Operational Re-
55, and p3o2 d1 = (o2 , 3), (3, 4), (4, d1 ) with travel time cp3 = 65. search, 237(3), 1105–1118, (2014).
The travel time on these paths will be no more than 65 min. On the [2] Kieran Conboy, ‘Agility from first principles: Reconstructing the con-
other hand, path p4o2 d1 = (o2 , d2 ), (d2 , 4), (4, 3), (3, o1 ), (o1 , d1 ) cept of agility in information systems development’, Information Sys-
with travel time cp4 = 6xo1 d1 +7xo2 d2 +65 will not be used since it tems Research, 20(3), 329–354, (2009).
[3] Lee D Han, Fang Yuan, Shih-Miao Chin, and Holing Hwang, ‘Global
is not temporally efficient. Similarly, we analyze the rest of the nodes optimization of emergency evacuation assignments’, Interfaces, 36(6),
of the network and based on these numbers, in Table 1, we give the 502–513, (2006).
values of evacuation centrality measure of each node. [4] Eugene L Lawler, ‘A procedure for computing the k best solutions to
discrete optimization problems and its application to the shortest path
problem’, Management science, 18(7), 401–405, (1972).
[5] Marin Lujak, Stefano Giordani, and Sascha Ossowski, ‘Fair route guid-
Table 1: Evacuation centrality measure values for the network in Figure 1 ance: Bridging system and user optimization’, in 17th International
IEEE Conference on Intelligent Transportation Systems (ITSC), pp.
Node o1 o2 3 4 d1 d2 1415–1422. IEEE, (Oct 2014).
Evacuation Centrality 5 5 4 3 4 4 [6] Marin Lujak, Stefano Giordani, and Sascha Ossowski, ‘Route guid-
ance: Bridging system and user optimization in traffic assignment’,
Neurocomputing, 151(1), 449–460, (2015).
Here, the computation of the evacuation centralities for safe exit [7] Marin Lujak and Sascha Ossowski, ‘Intelligent people flow coordina-
nodes d1 and d2 is found counting only the number of the safest tion in smart spaces’, in Multi-Agent Systems and Agreement Tech-
nologies: 13th European Conf., EUMAS 2015, and 3rd Int. Conf., AT
temporally efficient simple paths towards the other safe exit. 2015, Revised Selected Papers, eds., Rovatsos M. et al., volume 9571
Based on the evacuation centrality measure values of the nodes of LNCS, 34–49, Springer, (2016).
of the network, we find agile evacuation paths by applying Formula [8] Marin Lujak and Sascha Ossowski, ‘On avoiding panic by pedestrian
(15) for o1 and o2 since momentarily these are the nodes with present route recommendation in smart spaces’, in Proceedings of the 4th Int.
evacuees. Black Sea Conf. on Comm. and Networking. IEEE, (2016, In Press).
[9] Pamela Murray-Tuite and Brian Wolshon, ‘Evacuation transportation
We find the two paths with the highest value: p1o1 d1 = (o1 , d1 ) modeling: An overview of research, development, and practice’, Trans-
2
and path po1 d2 = (o1 , 3), (3, o2 ), (o2 , d2 ) , both with path agility portation Research Part C: Emerging Technologies, 27, 25–45, (2013).
[10] Adam J Pel, Michiel CJ Bliemer, and Serge P Hoogendoorn, ‘A review
on travel behaviour modelling in dynamic traffic simulation models for
evacuations’, Transportation, 39(1), 97–123, (2012).
[11] Salvador Casadesús Pursals and Federico Garriga Garzón, ‘Optimal
building evacuation time considering evacuation routes’, European
Journal of Operational Research, 192(2), 692–699, (2009).
[12] Marcel van Oosterhout, Eric Waarts, and Jos van Hillegersberg,
‘Change factors requiring agility and implications for it’, European
Journal of Information Systems, 15(2), 132–145, (2006).
[13] Yahaya Y Yusuf, Mansoor Sarhadi, and Angappa Gunasekaran, ‘Ag-
ile manufacturing:: The drivers, concepts and attributes’, International
Journal of production economics, 62(1), 33–43, (1999).