Marin Lujak
email: marin.lujak@imt-lille-douai.fr

Stefano Giordani
email: stefano.giordani@uniroma2.it

Centrality Measures for Evacuation: Finding Agile Evacuation Routes

Keywords: centrality measure, betweenness centrality, evacuation betweenness centrality, evacuation centrality, evacuation route, agile evacuation route

In this paper, we study the agility of evacuation routes in relation to dynamically changing unpredictable hazardous conditions in smart space networks. Infrastructure safety conditions may unpredictably change through time. Due to unpredictability, evacuees' safety can get jeopardized at any point of the evacuation route. Thus, it is not sufficient only to find the shortest evacuation routes considering present safety conditions and evacuation flow, but we should also consider other relevant characteristics that make the evacuation routes sufficiently safe through time. With this aim, we propose two new node importance metrics: evacuation betweenness centrality and evacuation centrality, both inspired by betweenness centrality. The first metric represents the fraction of k efficient evacuation routes between all origin-destination pairs different from the given node that pass through that node, while the second represents the importance of the given node for evacuation considering the availability of alternative efficient evacuation paths (routes) from that node towards safe exits. Moreover, given a set of evacuees' positions and safe exits, we find shortest agile evacuation routes, where by agile route we mean the ability to efficiently and safely reroute from intermediate nodes in case of unpredictable safety drops through maximizing the value of the evacuation centrality of the route's intermediate nodes. In addition, we propose an algorithm for that problem and discuss its capability to react to the changes in safety circumstances along recommended routes.

Introduction

Emergencies and disasters occur unexpectedly and disrupt our day-to-day activities and the functioning of a community. They can strike anyone, anytime, and anywhere causing physical and/or environmental damage. Emergencies may be natural or manmade, small scale, as e.g., in a building due to an explosion or fire, or large scale, as, e.g., in a city or a region because of an earthquake, radiological accident, bombardment or dangerous weather system.

Emergency evacuation is the immediate and urgent movement of people away from the threat or actual occurrence of a hazard. In emergency, evacuees should be able to evacuate safely, rapidly, seamlessly, and in a coordinated way following an evacuation route while avoiding hazardous conditions.

To facilitate the efficiency of evacuation, conventional evacuation approaches are based on a static evacuation plan. In the case of building evacuation, it is usually positioned on a limited number of positions within a building. If the evacuation safety conditions permit it, a trained evacuation personnel is usually introduced at a predefined set of critical evacuation points.

Each evacuee should reach his/her exit by following the signs that are attached on the floor or walls in a building. These signs represent the direction of the evacuation route shown on the evacuation plan. If the primary escape route is blocked, there is usually a secondary escape route that is marked on the evacuation plan. In the case both routes are blocked and there is no updated information available, the evacuees are left with no alternative route.

The difficulty with this evacuation approach is that it provides static evacuation routes that do not adapt to real-time changes in evacuation network topology nor to safety changes along the evacuation routes due to the hazard dynamics. Moreover, the static evacuation route information is seldom available to evacuees due to the fact that the evacuation plans are present only at a limited number of positions in a building. This may result in further casualties caused by the ongoing hazard and/or irrational panic-related behaviors.

The objective of this paper is, thus, to study coordination approaches for evacuees responsive to unpredictable dynamically changing hazardous conditions throughout the evacuation area. These approaches should be able to increase evacuees' safety by providing evacuation routes that in the case of an unforeseen hazard along the way will give an evacuee a possibility to reroute to an alternative safe route and thus respond seamlessly to the hazard dynamics and avoid further evacuation casualties.

The concepts of rapidness and seamlessness, which are necessary in this evacuation scenario, are closely related to the concept of agility. Oxford dictionary (2016) describes the term agile as "the ability to move quickly and easily" and "the ability to think and understand quickly". It is a well known concept in many areas, such as, e.g., manufacturing, software development, and business organization, see, e.g., [START_REF] Conboy | Agility from first principles: Reconstructing the concept of agility in information systems development[END_REF][START_REF] Van Oosterhout | Change factors requiring agility and implications for it[END_REF][START_REF] Yusuf | Agile manufacturing:: The drivers, concepts and attributes[END_REF]. In terms of outcomes, agility is a means of a system to swiftly and easily handle continuous and unanticipated change by adapting its initial stable configuration and to effectively manage unpredictable external and internal changes, e.g., [START_REF] Van Oosterhout | Change factors requiring agility and implications for it[END_REF][START_REF] Yusuf | Agile manufacturing:: The drivers, concepts and attributes[END_REF]. Based on this conceptualization and paradigms of agile manufacturing and agile business systems, in this work we propose the concept of agility in evacuation routes and related route recommendation systems.

Agility of an evacuation route assures to an evacuee a high real-time reactivity to safety changes possibly occurring along the route. It requires the ability to reroute from intermediate nodes of a proposed evacuation route to alternative routes towards safe exits. Agile route recommendation systems, hence, should be capable to run in real time in the cycle sense-analyze-decide-act. To achieve it, we need complete, accurate and up-to-the-minute situational awareness along the route. While in the open spaces, GPS and, e.g., 3G and 4G communication can be used, in inner spaces, this requirement can be fulfilled by, e.g., the interaction of ambient intelligence and smartphone technologies. Hence, an agile evacuation route recommendation system should respond quickly in inner and open spaces to sudden changes in evacuation safety conditions caused by a hazard, crowdedness or any other type of requirement or disruption. To the best of our knowledge, the literature on such route recommendation systems is very scarce (Section 2).

We can model evacuation agility of a route (path) in terms of the characteristics of its intermediate nodes. For this scope, in Section 3, we first propose an evacuation network model and then examine relevant centrality measures related with finding agile evacuation routes. In Section 4, we propose two new node importance metrics called evacuation centrality and evacuation betweenness centrality, both inspired by (node) betweenness centrality. Evacuation betweenness centrality represents the fraction of k efficient evacuation paths between all origin-destination (O-D) pairs different from the given node that pass through that node, while evacuation centrality represents the importance of a node for evacuation considering the availability of alternative efficient routes from that node towards safe exits.

Given an evacuation network with a set of evacuees' positions and safe exits, in Section 5 we find agile evacuation routes, where, by agile, we mean the ability to efficiently and safely reroute from intermediate nodes of a route in case of unpredictable safety drops.

An evacuation route computation solution should be scalable and robust. We propose an algorithm that dynamically computes agile evacuation routes. An application example of the algorithm is shown on a realistic small network in Section 6. We conclude the paper and give future research directions in Section 7.

Related work

Building evacuation has been studied over the last decades from different perspectives such as, e.g., evacuees' behaviors, traffic control strategies, sheltering site selection, and route finding for displacement. For example, Pursals and Garzón in [START_REF] Pursals | Optimal building evacuation time considering evacuation routes[END_REF] considered the building evacuation problem and developed a model for selecting the proper routes for movement of people in a building during an emergency situation. Abdelghany et al. in [START_REF] Abdelghany | Modeling framework for optimal evacuation of large-scale crowded pedestrian facilities[END_REF] present a simulation-optimization modeling framework for the evacuation of large scale pedestrian facilities with multiple exit gates. The framework integrates a genetic algorithm (GA) and a microscopic pedestrian simulation assignment model. The GA searches for the optimal evacuation plan, while the simulation model guides the search through evaluating the quality of the generated evacuation plans. Evacuees are assumed to receive evacuation instructions in terms of the optimal exit gates and evacuation start times. The framework is applied to develop an optimal evacuation plan for a hypothetical crowded exhibition hall. A mixed-integer programming solver is used to derive routing plans for sample networks.

Hamacher and Tjandra in [START_REF] Hamacher | Mathematical modelling of evacuation problems: A state of art[END_REF] give an overview of mathematical modelling of evacuation, while a survey of optimization approaches for macroscopic emergency evacuation planning can be found in, e.g., [START_REF] Yusoff | Optimization approaches for macroscopic emergency evacuation planning: a survey[END_REF].

Choi et al. in [START_REF] Choi | Modeling of building evacuation problems by network flows with side constraints[END_REF] model building evacuations by network flows with side constraints. They consider flow dependent arc capacities and propose greedy algorithms for solving maximum flow, turnstile cost, and minimax problems in some specially structured building networks, as, e.g., path or convergent trees.

Hamacher et al. in [START_REF] Hamacher | On the use of lexicographic min cost flows in evacuation modeling[END_REF] represent building evacuation as a dynamic networkflow problem. They show that lexicographical optimization is applicable in handling multiple objectives as, e.g., minimizing the total evacuation time while avoiding cyclic movements in a building.

In [START_REF] Luh | Modeling and optimization of building emergency evacuation considering blocking effects on crowd movement[END_REF], Luh et al. consider the crowd guidance optimization problem while considering the effect of narrow passages on human behavior. Based on advanced microscopic pedestrian models and simulations, they establish a macroscopic network-flow model introducing a desired flow rate in relation to these factors. They propose a divide-and-conquer approach to reduce computational complexity and to reflect psychological findings. Moreover, they optimize egress routes by using a combination of stochastic dynamic programming and the rollout scheme, and coordinate them a posteriori to meet the total need for joint movement respecting passage capacities.

Conventional emergency evacuation plans often assign evacuees to fixed routes or destinations based mainly on geographic proximity. Such approaches can be inefficient if the roads are congested, blocked, or otherwise dangerous because of the emergency. Han and Yuan proposed in [START_REF] Han | Global optimization of emergency evacuation assignments[END_REF] the concept of most desirable destination for evacuees while exploring the options that allow evacuees flexibility in selecting their exit routes and destinations. This concept recognizes that municipalities responsible for large-scale evacuation have routinely assigned evacuees to routes and destinations based on limited experience and intuition rather than methodical optimization processes. Even with the implementation of dynamic traffic assignment, models that are based on fixed origin-destination tables are inefficient when a destination becomes difficult (or impossible) to access due to congestion or blockage.

Destination assignment and route assignment to enable optimal evacuation operations are interrelated. To optimize the routing problem, one has to know the destinations; to optimize the destination assignment, one has to know the minimal travel time, and hence route assignment to all destinations.

To address the inherent complexity of the problem, Han et al. in [START_REF] Han | Global optimization of emergency evacuation assignments[END_REF] de-vised a framework for simultaneously optimizing evacuation-traffic destination and route assignment. Based on this framework, we can determine the optimal evacuation-destination and route assignment using a one-step optimization procedure.

In [START_REF] Vogiatzis | Evacuation modeling and betweenness centrality[END_REF], Vogiatzis and Pardalos propose a solution method based on an islanding scheme for the problem of efficiently evacuating all people in an urban area from danger to safe zones in the presence of contraflows. The goal is to minimize the number of people who are awaiting rescue, with priority being given to evacuees in more endangered area. This problem is known to be NP-hard. Therefore, the authors use a heuristic approach to decompose the problem into subproblems based on the danger level, the distance from safety, and a combination of the two. They also propose a new decomposition scheme based on group betweenness to divide the flow more evenly towards multiple paths to safety, leading to a more robust evacuation process. The functioning of their approach is shown on a very large scale network representation of the city of Jackonsville, Florida, USA. However, there is no theoretical bound on the algorithm's performance.

In [START_REF] Lujak | Intelligent people flow coordination in smart spaces[END_REF], we propose a pedestrian route recommender system for smart spaces in steady state conditions that recommends the safest routes to pedestrians and simultaneously optimizes conflicting objectives of finding the social optimum and minimizing individual route travel times while considering people flow and fairness, similarly to [START_REF] Lujak | Fair route guidance: Bridging system and user optimization[END_REF][START_REF] Lujak | Route guidance: Bridging system and user optimization in traffic assignment[END_REF]. Moreover, the system considers the influence of stress on human reactions to the recommended routes and iteratively ponders user response to the suggested routes influenced by stress-related irrational behaviors until system acceptable routes are found. However, in the case of a sudden safety drop on a part of the route, it might not be able to guarantee a safe evacuation of the safety jeopardized areas since in the route recommendation, it does not consider the unpredictability of safety conditions. In this case, it might thus result in evacuees' fatalities. Moreover, in [START_REF] Lujak | On avoiding panic by pedestrian route recommendation in smart spaces[END_REF], we consider the influence of affiliate ties among evacuees and their interaction with selfconcerned individuals and model self-concerned and social group behavior via individual and team reasoning. The recommended evacuation routes take in consideration the affiliate ties (e.g., family relations as parents, grandparents, etc., friendship, etc.) present within the evacuation group to guarantee evacuee's compliance with the routes if it is necessary to separate the group in the optimization process.

Lu et al. in [START_REF] Lu | Capacity constrained routing algorithms for evacuation planning: A summary of results[END_REF] focus more on capacity constrained routing algorithms for evacuation planning in large-scale transportation networks. They present a heuristic algorithm called Capacity Constrained Route Planner (CCRP) that produces sub-optimal solution for the evacuation planning problem.

CCRP models capacity as a time series and uses a capacity constrained routing approach to incorporate route capacity constraints. Contrary to the linear programming approach to evacuation that uses time expanded networks to compute the optimal evacuation plan and requires a user provided upper bound on evacuation time, CCRP uses only the original evacuation network and it does not require prior knowledge of evacuation time, therefore, significantly reducing the computational cost compared to linear programming approach that produces optimal solutions.

Andreas and Smith in [START_REF] Andreas | Decomposition algorithms for the design of a nonsimultaneous capacitated evacuation tree network[END_REF] examine the design of an evacuation tree in which evacuation occurs on capacitated arcs with associated penalty that increases with time after the disaster has occurred. They introduce penalties on evacuation arcs that are nondicreasing functions of time. They seek to establish an optimal a priori evacuation tree (evacuation plan) that minimizes the expected evacuation penalty. The solution strategy is based on Benders decomposition, in which the master problem is a mixed-integer program and each subproblem is a time-expanded network flow problem. They provide efficient methods for obtaining primal and dual subproblem solutions and analyze techniques for improving the strength of the master problem formulation, thus reducing the number of master problem solutions required for the algorithm's convergence. They show the efficiency of their methods on a set of randomly generated test instances.

A strong assumption of that work is that at any time during the evacuation, a population at a particular node will always follow the same direction, no matter their origin node, and that direction remains the same in every scenario, or in other words, all evacuees entering a particular node will all leave via the same exit.

This approach is too simplistic as: i) in the case of congested evacuation arcs, the flow demand might be higher than the arc capacity and therefore, the evacuation cannot be performed just through one evacuation route for each node. This assumption considers people flows that do not divide. In the case the flow is larger than the capacity of an outgoing arc, for the efficiency of evacuation, the flow should divide. At the contrary to this approach, we provide a solution that maximizes the number of alternative efficient and safe routes in the case that something goes wrong on the primary evacuation route; ii) it does not respond to the human factors of herding and stampeding especially in the case of high congestion as is the case in capacity constrained evacuation arcs. In the case there are several evacuation routes and/or several exits, this approach seems to be insufficient.

Contrary to the previous work that considers seamlessness as the movement of people on each node toward the same exit and assumes the arcs' capacities to be able to support these flows, in this work, we consider seamlessness in the case of unexpected contingencies on evacuation routes to provide for alternative routes without interruptions assuring perfect and flawless performance without stopping. The aim is to achieve a seamless transition with a continuity of flow.

Therefore, in this paper, we concentrate on evacuation routing in highly unpredictable dynamically changeable hazardous evacuation safety conditions. In this case, it is important to find the shortest safe routes for all evacuees considering other relevant characteristics that make the evacuation route sufficiently safe through time.

Evacuation network model

In this section, we define a generic model of an evacuation area of concern and introduce related terminology and concepts as a base for further sections.

If real-time infrastructure information is available to evacuees and they can negotiate their routes, it becomes possible to provide them with personalized dynamically optimized evacuation routes in real time. With this aim, we need indoor and outdoor location systems and tracking technologies that today provide an efficient support for people tracking and counting, see, e.g., [START_REF] Ijaz | Indoor positioning: A review of indoor ultrasonic positioning systems[END_REF][START_REF] Zhang | New object detection, tracking, and recognition approaches for video surveillance over camera network[END_REF]. Therefore, we assume that the evacuees are monitored using real-time location systems and tracking technologies based on, e.g., GPS, Wi-Fi, radio-frequency identification (RFID), received signal strength of RF signals, Bluetooth beacons, wireless local area network (WLAN), ultra-wideband (UWB), and/or a network of cameras. The communication between smart spaces and evacuees can be performed via smart space displays, acoustic signs, smart-phones, etc.

People monitoring permits us both to recognize the evacuees' behavior as to perceive their momentary position, flow and velocity together with their safety conditions. Furthermore, we assume that the evacuee flow demand is defined by the presence of infrastructure occupants at their momentary positions whose evacuation destinations are defined as sufficiently close locations (e.g., building exits) at which evacuees are considered to be safe.

Our aim is, thus, to safely evacuate all the evacuees and if not possible, then, as many evacuees as possible within the allotted upper time limit. This time is usually given by the authorities in charge of evacuation. To this aim, we should find agile evacuation routes toward safe exits that consider evacuation centrality of the routes' intermediate nodes and other relevant characteristics that make the evacuation route sufficiently safe through time.

We represent a smart space evacuation network (building and/or urban district) by a directed graph G = (N, A) (in the following called graph). N is a set of n nodes representing rooms, offices, halls, and in general, any relatively small portion of space within a large building or other large structure delimited by walls or partitions and A is the set of m arcs a = (i, j), i, j ∈ A and i = j, representing walkways, doors, gateways, and passages connecting nodes i and j. Nodes i and j are called tail and head of arc (i, j), respectively.

Each arc (i, j) ∈ A has an associated capacity u ij and (non-negative) cost c ij , which in our case is its travel time t ij (f ij , u ij ). This time depends on the arc's flow f ij and capacity u ij and generally can be seen as an increasing nonlinear function because of the effects of congestion on the arc's travel time (see, e.g., the volume-delay function or link congestion function in [START_REF] Mtoi | Calibration and evaluation of link congestion functions: applying intrinsic sensitivity of link speed as a practical consideration to heterogeneous facility types within urban network[END_REF]). For simplicity and without loss of generality, it is assumed to be integer.

In the case of larger spaces that can host a larger number of people, for simplicity, the same are divided into sections represented by nodes connected by arcs a ∈ A.

We opt for a directed graph representation of the evacuation infrastructure since in the case of bi-directional corridors, roads, and passages, represented by undirected arcs we can easily substitute each arc (i, j) with two directed arcs (i, j) and (j, i).

In this work, we consider a graph model with capacitated arcs and uncapacitated nodes. This approach is not restrictive since one can reduce the node capacity problem to the arc capacity problem (see, e.g., [START_REF] Khuller | Flow in planar graphs with vertex capacities[END_REF]). Therefore, we can adapt the model of uncapacitated nodes representing rooms, offices, halls, etc. to the case with the capacitated nodes in the following way.

Given a flow f in graph G, the flow through node v is defined as a∈δ -(v) f a , where f a is the flow on arc a ∈ δ -(v) entering node v. We say that a flow is feasible if it satisfies the flow-conservation constraints and the arc capacity and the node capacity constraints: according to the latter, the flow through a node v cannot exceed u v . We construct a new digraph H where for every node v ∈ N , there are two nodes: v i and v o linked by arc (v i , v o ) of capacity u vivo = u v . All the arcs outgoing from node v in G, in the transformed graph H originate at node v o , while all the original arcs entering node v are entering into node v i . In this way, any flow in H entering v i must go through arc (v i , v o ) and so the total amount of flow entering v i (or leaving v o ) cannot exceed u v .

Moreover, we assume that the evacuation is performed in stationary conditions of the evacuees' flow. Even though this assumption is strong, it can be applied to the evacuation of large congested spaces, such as, e.g., arenas, concert halls, public offices, and business districts at rush hours.

To simplify the notation, we assume that there is at most one arc in each direction between any pair of nodes. However, in the case there are multiple different physical arcs (e.g. walkways or doors) between two physical nodes, we model them in the following way: in the case of multiple arcs, we divide them by inserting fictitious nodes such that we reduce the multi-graph into a simple graph.

Let O ⊆ N and D ⊆ N be a set of all evacuees' origins and safe exit destinations, respectively. We assume that there are

n O evacuees' origin nodes o ∈ O disjoint from n D safe exit destination nodes d ∈ D, i.e., D ∩ O = ∅, where n O + n D ≤ n.
In order to simplify the graph model, we introduce a fictitious sink node d ∈ N that is adjacent to all the destination nodes (safe exits) by fictitious (dummy) arcs of infinite capacity. In this way, we assume that graph G includes (together with actual nodes) also fictitious sink node d and its incoming dummy arcs. Moreover, let R be a collection of n O sets of evacuees, where set R o contains the evacuees who request to leave origin node o ∈ O to go to any of the safe exits d ∈ D and, hence, towards fictitious sink node d.

Efficient evacuation paths

The concept of a route in graph theory is represented by a path. A (simple) path p is a finite sequence of adjacent distinct nodes connected by a sequence of arcs, each linking two adjacent (different) nodes. From here, we interchangeably use the terms route and path. Total travel time t p of path p is the sum of the travel times of its constituent arcs t ij (f ij , u ij ), with (i, j) ∈ p and f ij being a feasible flow along arc (i, j).

Let P o denote the set of available (simple) evacuation paths acceptable in terms of safety and duration for each evacuation request from node o ∈ O to fictitious sink node d. We call all such paths efficient evacuation paths.

By acceptable in terms of duration, we mean the paths whose travel time (evacuation duration) is not larger than some upper bound t o min • γ o in respect to the minimum path duration t o min among all the paths from evacuation origin node o to fictitious sink node d, where γ o ≥ 1 is an evacuation time tolerance factor for node o. This factor should be designed for each evacuation origin node o ∈ O in such a way that it complies with the constraint γ o • t o min ≤ t evac max . Here, t evac max is the maximum evacuation time of the evacuation network based on the emergency situation at hand, usually given by evacuation authorities.

Let P = o∈O P o be the set of all efficient evacuation paths. Let f p be a feasible flow along path p ∈ P o . Then, all the path flows in P can be gathered in the global path flow vector f O = (f 1 , . . . , f r ), where r = |P |.

Moreover, we define feasible flow f o as a subvector of flows of paths p ∈ P o . In addition, individual travel time of each arc in a path a ∈ p should be such that the flow of people does not cause exagerated delays, i.e.,

t a (f a , u a ) ≤ t arc max , ∀a ∈ p, p ∈ P , (1)
where f a = p∈P :p a f p is the flow of evacuees on arc a. In Formula (1), we limit the search of evacuation paths only to the arcs that are sufficiently fast in terms of travel time and, therefore, introduce an upper bound on an admissible arc's travel time t arc max . In case of contingencies on an assigned path, this implies that the evacuees should be able to reroute to other routes within a reasonable delay. We model this constraint in the following way.

Initially, before finding efficient evacuation paths P , we add to the travel times of too slow arcs that do not comply with (1) a very large value M such that in computing efficient evacuation paths, only in the case there is no alternative faster arc available for a path, a slow arc will be included. On the contrary, if there are arcs available that comply with (1), they will firstly be chosen for an efficient evacuation path.

However, the value of t arc max is related both to the structure of the evacuation network as to the evacuees' maximum allowed travel time on safety -jeopardized arcs. In this light, if all arcs are very large, then putting a too low value on t arc max and relaxing Constraint (1) will result in a too high cost in terms of relaxation penalties, while if t arc max is too high, then all arcs will be acceptable from this point of view.

Moreover, by acceptable in terms of safety, we mean the paths whose overall safety is above some minimal safety level sufficient for survival. The problem of finding safe routes (paths) is related with minimizing the risks caused by possible threats present on the evacuation paths. Path safety S p , for each path p ∈ P o , where o ∈ O, is defined by the safety S a of its constituent arcs a ∈ p and is jeopardized by the safety conditions of its unsafe arcs A cr p = {a ∈ p|S a < S cr }.

Then, the safety of path p can be computed, e.g., as a minimal value of its arcs' safeties, i.e., S p = min a∈p S a .

If any of the path's constituent arcs a ∈ p suffers a safety drop under the threshold value S cr , i.e., S a < S cr , the harmful effects may threaten the evacuees' lives and path p is not safe for passage. Therefore, proposed evacuation paths p ∈ P o for o ∈ O should all satisfy safety conditions S p ≥ S cr . Hence, in the computation of safe paths, only safe arcs of a graph are considered, i.e., the set of arcs A saf e = {a ∈ A|S a ≥ S cr }.

In this work, we do not concentrate on the ways to find such efficient paths, but we assume that a set of efficient paths is known and given a priori.

Aggregation of evacuation requests on arcs

While evacuation requests R o d = R o are clearly defined for each node o ∈ O, we need to disambiguate the evacuation requests in the case there are evacuees present in the spaces represented by arcs a ∈ A.

For simplicity, there are two possible modelling approaches for this case: i) these requests are added to the closest node incident with that arc or ii) a node is added to the arc at the actual position of the evacuee(s), thus representing evacuee(s) request(s) at their actual position.

In the first case, we can use the Voronoi diagram principle where all the evacuees closest to a node are added to that node's evacuation request, while in the second case, we can use some of the clustering techniques to accumulate the evacuation requests of geographically close evacuees. Then, a node represents an evacuation request of one or more geographically close evacuees. Since such a node is mobile due to the movement of evacuees along the path, the structure of graph G is changing dynamically through time depending on the positions of each and every evacuee in the evacuation network. Moreover, in this case, the number of evacuation requests n O is not related with the cardinality of the node set N , but with the number of evacuees in the evacuation network. The exact number of evacuation requests represented by evacuation nodes defined in this way is determined by the vicinity and geographical distribution of the evacuees. Geographically close evacuees may be considered by a single evacuation request node if the evacuees are within a limited travel time away from one another.

This modelling option results in the presence of static nodes N and arcs A representing the structure of the evacuation space, and the introduction of mobile evacuation request nodes O representing the evacuees' requests.

We might use different clustering techniques for the definition of the evacuees' groups and their distribution based on the similarity factor that should be dynamically adaptable to each case. However, due to the introduced additional complexity of this approach and for simplicity, we opt for the first approach where the demand is added to the closest incident node of an arc. Thus, evacuation requests are related to a set of static nodes N and they change dynamically through time as the evacuation progresses.

Related centrality measures

Generally, centrality measures indicate the most important nodes of a network, see, e.g., [START_REF] Borgatti | A graph-theoretic perspective on centrality[END_REF][START_REF] Friedl | A critical review of centrality measures in social networks[END_REF]. Centrality is a concept that has been worked on since 1950's with various extensions. There exist various categories of centrality, such as, e.g., degree, closeness, harmonic, betweenness, eigenvector, Katz, PageRank, and percolation centrality (see, e.g., [START_REF] Brandes | Centrality measures based on current flow[END_REF][START_REF] Crucitti | Centrality measures in spatial networks of urban streets[END_REF][START_REF] Landherr | A critical review of centrality measures in social networks[END_REF][START_REF] Opsahl | Node centrality in weighted networks: Generalizing degree and shortest paths[END_REF]). These centrality measures have been proposed for the analysis of different networks, as are, e.g., social, urban and electrical networks (see, e.g., [START_REF] Brandes | Centrality measures based on current flow[END_REF][START_REF] Crucitti | Centrality measures in spatial networks of urban streets[END_REF][START_REF] Alahakoon | K-path centrality: A new centrality measure in social networks[END_REF][START_REF] Marsden | Egocentric and sociocentric measures of network centrality[END_REF][START_REF] Jackson | Social and economic networks[END_REF][START_REF] Hines | A centrality measure for electrical networks[END_REF][START_REF] Latora | A measure of centrality based on network efficiency[END_REF]).

Everett and Borgatti in [START_REF] Everett | Extending centrality, Models and methods in social network analysis[END_REF] discuss extending centrality in three directions: i) from an individual to a group of actors within the network, ii)from a single to two-mode data in which the data consist of a correspondence between two kinds of nodes, iii) to examine the core-periphery structure of a network.

In this paper, we apply the concept of centrality measures to evacuation networks. Some of the measures relevant to the computation of evacuation paths (paths) are node degree, eigenvector, and betweenness centrality. In the continuation, we describe these measures in detail and point their flaws from the evacuation point of view. Then, we propose two new centrality measures for the evacuation path optimization: evacuation betweenness centrality and evacuation centrality, and discuss their application in the evacuation setting. Moreover, we propose the optimization model for finding the nodes' evacuation centrality.

Degree centrality

The degree centrality C d (i) of node i ∈ N is simply the degree of the node, i.e., the number of arcs incident to that node (see, e.g., [START_REF] Freeman | Centrality in social networks conceptual clarification[END_REF]). In directed graphs, we can either use the in-degree, the out-degree, or their combination as the degree centrality value. When we combine in-degrees and out-degrees, we are basically ignoring arc directions.

In general, nodes with a higher degree centrality tend to be used by more paths. However, connections of a node with the neighboring nodes that are a part of the shortest paths to safe exits are more important than others. Since the degree centrality does not guarantee the connectedness of a node to safe exits, it cannot be used in the computation of efficient evacuation paths.

Eigenvector centrality

A step forward the evacuation path's efficiency guarantee is the eigenvector centrality of a node [START_REF] Bonacich | Factoring and weighting approaches to status scores and clique identification[END_REF][START_REF] Bonacich | Power and centrality: A family of measures[END_REF], which depends both on the number and the importance of its adjacent nodes. In general, adjacency of a node to nodes that are themselves adjacent to more important nodes will give a node more importance.

While node degree centrality counts walks of (geodesic) unitary length from a node, the eigenvalue centrality takes into consideration walks of length infinity. Eigenvalue centrality is the expected frequency of visits of a node i ∈ N of an infinite random walk over graph G = (N, A). It can only be calculated for connected undirected graphs and strongly connected digraphs. More formally, if we let Ad = (a i,j ) be the adjacency matrix of graph G = (N, A), eigenvector centrality C e (i) of node i ∈ N is given by:

C e (i) = 1 λ j∈N \{i} a ij C e (j), ∀(i, j) ∈ A (2)
where λ = 0 is a constant. In matrix form, we have λC e = Ad • C e . Hence the centrality vector C e is the eigenvector of the adjacency matrix Ad associated with the eigenvalue λ. If we choose λ as the largest eigenvalue in absolute value of matrix Ad, then as a result of Perron-Frobenius theorem, if matrix Ad is irreducible (i.e., the graph is (strongly) connected), then the eigenvector solution C e is both unique and positive.

The nodes with a high eigenvector centrality values, then, will be traversed by more paths. Moreover, nodes with a high eigenvector centrality are graph hubs and their presence is crucial in maintaining the paths among all other nodes. However, a high eigenvector centrality value of a node does not guarantee the existence of efficient evacuation paths from that node towards safe exits. Additionally, a high eigenvector centrality value of a node might be a root to panic and a related herding problem [START_REF] Lujak | Intelligent people flow coordination in smart spaces[END_REF] in the case of high people flows traversing the node. Therefore, eigenvector centrality does not characterize sufficiently the importance of the nodes for evacuation. Since we want to guarantee the efficiency of evacuation towards a limited set of safe exit nodes, as such, it can not be directly used as a parameter for evacuation optimization.

Betweenness centrality

Betweenness centrality [START_REF] Freeman | A set of measures of centrality based on betweenness[END_REF] is a concept that is closer to the efficiency of evacuation paths and is a departure point in our proposition of the evacuation centrality metrics. It is defined as the fraction of shortest geodesic paths from origins s ∈ N to destinations t ∈ N , where s = t, that pass through node i ∈ N , where i = s = t is an intermediate node of the path, i.e.:

C b (i) = s∈N t∈N σ st (i) σ st , ∀i = s = t ∈ N, (3)
where σ st (i) is the number of shortest geodesic paths (the paths with the minimum number of arcs) from s to t that pass through intermediate path's node i. Moreover, σ st is the total number of shortest geodesic paths from s to t. Betweenness centrality is, therefore, an indicator of the frequency a node serves as a connection on the shortest geodesic paths between any two other nodes. That is, we find the shortest geodesic path (or paths) between every pair of nodes, and calculate the fraction of these paths that node i lies on. Betweenness centrality can be computed in O(nm) and O(nm + n 2 log n) computation time on unweighted and weighted networks, respectively, where m is the number of arcs, and n the number of nodes [START_REF] Brandes | A faster algorithm for betweenness centrality[END_REF].

Note that traditional betweenness centrality metric for both nodes and arcs only accounts for the total number of paths going through a given individual node or arc, respectively. In [START_REF] Everett | The centrality of groups and classes[END_REF], betweenness together with degree centrality are extended to apply to groups and classes. The group betweenness centrality measure enables us to understand not only the centrality of a single node, but also the centrality of specific parts of the graph.

However, betweenness centrality does not consider the amount of data or traffic passing through a particular node or arc. Consequently, the current definition of betweenness centrality is able to capture the structural properties of the underlying network but is unable to depict the behavioral or operational characteristics of actual network traffic passing through the network. Therefore, in [START_REF] Maqsood | Congestion-aware core mapping for network-on-chip based systems using betweenness centrality[END_REF], Maqsood et al. propose a modified betweenness centrality metric to depict the operational and dynamic characteristics of the system in terms of actual amount of network traffic traversing through nodes and arcs. To achieve the aforementioned goal, they incorporate an additional parameter, i.e., the amount of data exchanged between the nodes.

If we imagine crowd flowing between nodes in the network and always taking the shortest possible geodesic path, then betweenness centrality measures the fraction of that crowd that will flow through i on its way to wherever it is going. Even though this measure might be relevant to application scenarios where all arcs have the same cost (travel time), the issues with the usage of betweenness centrality in evacuation are related with the definition of distance and the origindestination pairs. In particular, we are concerned with the shortest evacuation time and not the shortest geodesic distance. Moreover, we are not interested in all origin destination pairs, but only in a limited subset of evacuees' origins O and safe exits D. In the following, we deal with these two issues.

Proposed centrality measures

Based on the previous analysis of the centrality measures, here we propose two new centrality measures for evacuation routing: evacuation betweenness centrality, and evacuation centrality.

Evacuation betweenness centrality

If we substitute the geodesic distance with a path cost (e.g., travel time) t p ≥ 0, most probably there will be only one shortest path for every pair of nodes. This is why here we present a modification of betweenness centrality that considers all the k od = | Pod | distinct efficient evacuation paths for each (o, d) pair, with o ∈ O and d ∈ D. We call this measure evacuation betweenness centrality (C EB ). For the computation of evacuation betweenness centrality, we use

C EB (i) = o∈O\{i} d∈D\{i} σ od (i) σ od , ∀i ∈ N, (4)
where σ od = k od and σ od (i) ≤ k od is the cardinality of the subset of k od efficient evacuation paths that pass through node i.

If node i has a high evacuation betweenness centrality C EB (i) defined in this way, it serves as a connection to many other evacuation origin nodes on efficient evacuation paths towards their safe exits, and therefore, is an important evacuation hub or gateway. In the following we give details on finding node's evacuation betweenness centrality.

Let d G (s, t) denote the shortest path distance (or cost, or travel time as in our case) between nodes s ∈ O and t ∈ D. It is well known from the Bellman criterion that a node v ∈ N lies on a shortest path between nodes s and t if and

only if d G (s, t) = d G (s, v) + d G (v, t).
We extend this criterion for our purposes as follows. If we consider evacuation paths with length (cost or travel time) tolerance factors α and β, where α > 0 and β = α • d G (s, t), then we have the following theorem. Theorem 1. A node v ∈ N lies on a path from node s to node t of length (cost or travel time) not greater than (1 + α)d G (s, t) if and only if the following inequality is satisfied:

(1 + α) • d G (s, t) ≥ d G (s, v) + d G (v, t). (5)
Proof. Given the paths P (s, v) and P (v, t) of length l(P (s, v)) and l(P (v, t)), respectively, let P (s, t) = P (s, v) P (v, t) be the path from s to t passing through node v, obtained from the composition of P (s, v) and P (v, t), of length l(P (s, t)) = l(P (s, v))+l(P (v, t)). If l(P (s, t)) is not greater than (1+α)d G (s, t), then Inequality (5) follows since l(P (s, v)) ≥ d G (s, v) and l(P (v, t)) ≥ d G (v, t). Viceversa, assume that Inequality ( 5) is valid, then the path P * (s, v) P * (v, t) obtained by the composition of the shortest path P * (s, v) from s to v and the shortest path P * (v, t) from v to t is of length not greater than (1 + α)d G (s, t) and passes through node v.

Let Ψ α st (v) be the number of efficient evacuation paths with length at most (1 + α) • d G (s, t), or d G (s, t) + β that pass through node v. Assuming w.l.o.g. that β as well as all the arcs' travel times are integer, we have:

Ψ α st (v) = 0, if d G (s, t) + β < d G (s, v) + d G (v, t) β h=0 σ h sv β-h =0 σ vt , otherwise, (6)
where σ h sv is the number of efficient evacuation paths from s to v of cost (travel time) exactly d G (s, v) + h. Moreover, let Ψ α st be the total number of paths from s to t with cost at most

(1 + α) • d G (s, t), or d G (s, t) + β.
Given the number Ψ α st (v) of efficient evacuation paths for each pair (s, t), the pair-dependency δ α st (v) of pair (s, t) ∈ V on an intermediary node v ∈ V is the fraction of the number Ψ α st of α-efficient evacuation paths between s and t that pass through v:

δ α st (v) = Ψ α st (v)/Ψ α st . (7)
By α-efficient evacuation paths, we mean the paths considered safe whose travel time is at most α • d G (s, t).

To obtain the evacuation betweenness centrality measure of a node v, we simply have to sum the pair-dependences of all pairs on that node,

C EB (v) = s =v =t∈N δ α st (v). ( 8
)
Efficient evacuation paths depend on the travel times that, at their turn, depend on evacuation flows. Therefore, we should (re-)compute evacuation betweenness centrality whenever the flows change. Since based on given arcs' travel times (that are related to a given flow) we can compute efficient evacuation paths in polynomial time (assuming that the number of efficient paths is bounded from above by a polynomial of the number of arcs and nodes), we can assume in our application case in large building networks that we are able to (re)compute evacuation betweenness centrality in near-real time or at least in a period shorter than the one required for significant evacuation flow changes.

We notice that nodes with a high evacuation betweenness centrality might be difficult for crowd coordination since these are intersections with crowd flow in possibly multiple directions. This fact increases the probability of the occurrence of herding. Therefore, special attention should be given to the crowd coordination at these nodes. To avoid this flaw, we propose in the following a different measure of centrality called evacuation centrality.

Evacuation centrality

When an unpredicted hazard occurs on a part of an evacuation path, the same gets unsafe and impassable. If, in the computation of an evacuation path, we do not consider this fact and the related possibility to reroute to other efficient evacuation paths on its intermediate nodes, then, in case of contingency, rerouting towards safe areas might be impossible causing imminent evacuees' fatalities. Similar case may occur on condition of a too high flow of evacuees that might saturate evacuation paths and cause panic. Therefore, for intermediate nodes of each evacuation path, we need to find a sufficient number of dissimilar efficient evacuation paths towards safe exits, preferably within the maximum time of evacuation given for a specific emergency case. Two paths between the same origin and destination node are called dissimilar if they contain at least one arc that is different from one another. The concept of dissimilarity can be approached from the point of view of the number and the length or cost of shared arcs; for more details see, e.g., [START_REF] Caramia | On the selection of k efficient paths by clustering techniques[END_REF][START_REF] Caramia | On the selection of k routes in multiobjective hazmat route planning[END_REF]. In that respect, we define the evacuation centrality as follows.

Definition 4.2. Evacuation centrality C (i) of node i is a parameter that represents the importance of node i for evacuation. The value of the evacuation centrality of a node is the number of available sufficiently dissimilar efficient evacuation paths.

While evacuation betweenness centrality considers all O-D pairs, and therefore favors hub nodes for evacuation (thus increasing flow and possibly congestion on these nodes), evacuation centrality considers only efficient evacuation paths that start at a node of interest and that obviously can include other efficient evacuation paths starting at the succeeding nodes closer to safe exit(s). Here, we are not interested in the number of efficient evacuation paths from the nodes that are further away from the node of interest in respect to the safe exits, but the number of such paths on the nodes that are closer to safe exit(s) than the node of interest.

Efficient evacuation paths should be sufficiently fast and safe for passage. However, the safety of a path is a dynamic concept that may vary through time due to the hazard dynamics. In the case that a (presently) efficient evacuation path gets unsafe due to the hazard's progress, a path that is only marginally different from it may become equally unsafe. By providing as dissimilar paths as possible, we minimize the chance of casualties in the case that a specific area gets hazardous. Hence, it is desirable to generate a number of efficient evacuation paths that are as different as possible topologically.

K-shortest path algorithms find a large number of alternative paths. However, many of these alternative paths are likely to share a large number of arcs. The smaller the number of shared arcs among the paths, the higher the total potential evacuation capacity between an origin and a destination node. The reason is that the concentration of the evacuees on a low number of arcs might provoke congestion that lowers the travel times of these arcs, and therefore lowers the travel times of all paths that pass through them. Hence, the task is to generate as many paths as possible with acceptable travel times that have as few common arcs as possible. Therefore, evacuation paths should be as dissimilar as possible, and in the best case, they should be arc-disjoint.

The problem of finding the (maximum) number of arc-disjoint paths, among a set P of given efficient evacuation paths from node s ∈ N \ d to fictitious sink node d, can be modelled as a maximum flow network problem, as follows. Let x p be a non-negative flow variable related to path p ∈ P and let K be a free variable. Moreover, let Φ be the [|A| * | P |] arc-path incidence matrix and Φ the arc-path incidence matrix Φ restricted only to the non-dummy arcs. Then, the mathematical formulation is:

(Z) v(s) = max K (9)
subject to p∈P j:(i,j)∈A

φ (i,j),p x p - h:(h,i)∈A φ (h,i),p x p =      K, if i = s 0, if i ∈ N \{s, d} -K, if i = d (10)
Φ x P ≤ 1 (11)
x p ≥ 0, ∀p ∈ P .

The objective function ( 9) to be maximized represents the total network flow originating from source s (entering in d) in our maximum network flow model. Constraints [START_REF] Luh | Modeling and optimization of building emergency evacuation considering blocking effects on crowd movement[END_REF] refer to the network's flow conservation requirement, while [START_REF] Han | Global optimization of emergency evacuation assignments[END_REF] limits the flow x p on non-dummy arcs to be at most 1. Since it is well known that the optimal solution of maximum network flow problem is integer in the case of integer arc capacities, then at the optimum, variables x p will assume integer values, i.e., value 0 or 1. Therefore, x p represents the selection choice for the path: 1 if the path is selected, and 0 otherwise. In this light, (11) limits from above the number of paths on each arc to be at most 1, which implies that the value of K represents the number of arc-disjoint paths.

The actual number of arc-disjoint efficient evacuation paths v(s) for generic node s ∈ N might be very low since it depends on the topology of the graph. It will be limited from above by the number of outgoing arcs from source s and the sum of the numbers of incoming arcs to all sink nodes d ∈ D. This is why we opt for finding a number of sufficiently dissimilar efficient evacuation paths from each node s to node d. For this aim, we introduce a penalized objective function ( 13) that takes into consideration the violation of Constraint [START_REF] Han | Global optimization of emergency evacuation assignments[END_REF], and solve the following problem to get K sufficiently dissimilar efficient evacuation paths:

z s (λ A ) = max K -λ A T y A (13)
subject to p∈P j:(i,j)∈A

φ (i,j),p x p - h:(h,i)∈A φ (h,i),p x p =      K, if i = s 0, if i ∈ N \{s, d} -K, if i = d (14)
y A ≥ Φ x P -1 (15)
y A ≥ 0 (16)
x p ∈ {0, 1}, ∀p ∈ P ,

where A ∈ A is a subset of real arcs excluding the set of dummy arcs incoming to d and y A is a vector composed of non-negative variables related to a multiple usage of each arc a ∈ A by paths p ∈ P . Moreover, λ A is a non-negative penalty vector of cardinality |A | for using each arc a ∈ A more than once. In this way, we penalize a multiple usage of arcs by multiple paths.

The model will return a maximum number of dissimilar efficient evacuation paths K (of length at most t evac max ). This strategy is in line with our necessity to reroute more frequently in case of emergency. It is easy to demonstrate that z s (λ A ) ≥ v(s) for any λ A ≥ 0.

This problem is a mixed integer program and to reduce the computing time required to solve it, we solve a linear relaxation of the former obtained by relaxing the binary constraints on the x p variables in Constraint [START_REF] Lu | Capacity constrained routing algorithms for evacuation planning: A summary of results[END_REF] in the following way:

0 ≤ x p ≤ 1, ∀p ∈ P . (18)
In fact, we are not interested in the structure (i.e., the constituent arcs) of dissimilar paths, but in the maximum number K of the same. Therefore, we can approximate the computation by assuming that path variables are continuous. Finally, for the best approximation, we resolve a dual of the former problem, i.e.,

s = min z s (λ A ) (19) subject to λ A ≥ 0. (20)
Note that the value of s is an upper bound on the number of dissimilar paths from s to d and, therefore, also on the number of arc-disjoint paths. Then, we can take the value of s as an evacuation centrality value C (s), i.e., C (s) = s for each node s ∈ N .

Finding agile evacuation routes

Once we find the evacuation betweenness centrality and evacuation centrality measures for each node of the graph, the objective for each evacuation request on each of the nodes o ∈ O is to find an agile evacuation route (path) to dummy node d and, therefore, to one of safe exits d ∈ D. An agile evacuation route is a path that maximizes the combined value of the intermediate nodes' centrality measures. By using an agile evacuation route, an evacuee is able to reroute in the case of contingency on any of the intermediate nodes of the route.

There are various ways to combine the proposed centrality values of the path's intermediate nodes. The most common way is to sum them, thus having an overall measure of the benefit for the path. From the sum, it is easy to obtain a path's mean value. However, optimizing the mean value is not acceptable in the evacuation paths whose success is based both on the worst-off and the average evacuation centrality of the path. This is because by optimizing the mean value, the optimum is usually accompanied by a few nodes with the worst-off values that, in the case of a hazard progression, may put the safety of the evacuees in jeopardy. Moreover, in the case of the evacuation betweenness centrality, with the maximization of the sum of the centralities of intermediate path's nodes, we usually force the usage of several graph hubs along the path with very high evacuation betweenness centrality values.

Another possible approach to obtaining agile evacuation paths is through maximizing the minimum centrality of intermediate nodes of the path. This approach would provide a good solution if the requirement on minimal value of the centrality of all path's nodes were to be satisfied. Unfortunately, by optimizing paths based on their nodes' worst-off performance, we deteriorate paths' overall performance and thus, their average intermediate nodes' centralities.

The balance between optimizing the path's nodes' worst off and mean evacuation centrality is given by the maximization of the product of the nodes' individual evacuation centrality values. A high product value, when it is defined in terms of benefits, is an indication of both good mean value and worst off value, i.e. paths with a high product value are both locally (at an individual node) and globally (at the level of a path) good solutions. Furthermore, a product combines good mean and worst off behavior since it reaches the maximum when the centrality values are high and distributed equally over all the path's nodes. Moreover, in the case of evacuation betweenness centrality, if we use the maximization of a product of the path's nodes' centrality values, we facilitate the usage of multiple hubs with balanced, more equally distributed values, which means more equally distributed evacuees' flow over the network.

Since the value of agility of an evacuation route should not depend on the number of its constituent nodes, in the following, we consider the normalized product (i.e., geometric mean) of evacuation centralities of the tail nodes of the route's constituent arcs. We refer to tail nodes since we want to reroute from the tail node of an arc in the path when the arc becomes unsafe. Therefore, given evacuation route p ∈ Po , we compute its agility ∆(p) as follows:

∆(p) = |(i,j)∈p| (i,j)∈p C (i). ( 21
)
Depending on the evacuation demand, the determination of a single path might not be sufficient to evacuate all the evacuees. Hence, the objective is to find a subset P * (o) ⊆ Po of best agile evacuation paths, i.e., efficient evacuation paths with largest agility for each evacuation origin o ∈ O. Generally, finding a path that maximizes the combination of its intermediate arcs' and/or nodes' attributes corresponds to finding a longest path evaluated on the basis of these attributes, which, in contrast to the shortest path problem, is well known to be NP-hard. However, here we have at the disposal |p| efficient evacuation paths p ∈ Po for each o ∈ O, so the computation is done in an exhaustive manner for all the given paths. In the following, we concentrate on the computation of agile evacuation paths.

Agile evacuation route algorithm

In this section, we present the approach for the computation and assignment of agile evacuation paths. The overall decision for the assignment of evacuees to evacuation paths can be seen in Algorithm 1 and is divided into 3 phases: i) EvacuationCentrality(G, D, S, γ), line 2, that computes evacuation centrality values for each node of the evacuation network resolving ( 19)-( 20 Evacuation centrality computation. First the preprocessing of a graph is performed in the following way. The travel times t a of all arcs a ∈ A cr with safety S a < S cr are multiplied by a very large number M Scr/Sa , i.e., t a = t a • M Scr/Sa . Then, we add a very large number M to the travel time t a of each arc with the travel time t a larger than t arc max : t a = t a + M , such that at the end if there is an arc that is unsafe and too large, its total travel time is t a = t a • M Scr/Sa + M .

Then, for each node v ∈ N , we compute up to k paths towards a dummy node d through, e.g., the distributed k-shortest path algorithm [START_REF] Holzer | Optimal distributed all pairs shortest paths and applications[END_REF]. This results in a set of as efficient as possible evacuation paths Pv for each node v ∈ N .

Subsequently, ( 19)-( 20) is solved for each node v ∈ N to find its own evacuation centrality value. The search for evacuation centrality value is equivalent to the maximization of the number of as dissimilar as possible efficient evacuation paths starting with a set of available efficient evacuation paths.

Agile evacuation route computation. For each origin o ∈ O, within the set of efficient evacuation paths Po , we find a subset of agile evacuation paths AG o to a dummy node d, and, therefore, to a set of safe exits d ∈ D. We do so by computing agility for efficient evacuation paths p ∈ Po , Formula [START_REF] Mtoi | Calibration and evaluation of link congestion functions: applying intrinsic sensitivity of link speed as a practical consideration to heterogeneous facility types within urban network[END_REF]. Then we choose a sufficient number of agile evacuation paths to efficiently respond to the evacuation demand.

Path assignment to evacuees. From the set of agile evacuation paths AG o computed for each origin o ∈ O, each evacuee in R o is then assigned one of these paths based on his/her evacuation preferences and constraints. For further details on matching evacuation paths with the evacuees preferences and constraints see, e.g., [START_REF] Lujak | A distributed architecture for real-time evacuation guidance in large smart buildings[END_REF].

Application example on a use-case

We demonstrate the functionality of the proposed approach by means of a simple case study example in Figure 1, which is a modified version of the example appearing in [START_REF] Lujak | Intelligent people flow coordination in smart spaces[END_REF].

Given is an evacuation network (graph) G = (N, A) with 9 nodes (N = {1, 2, . . . , 9}) that represent 5 different physically limited spaces (halls) (A-D), a lobby E, and an evacuation staircase F, as seen in Figure 1. This layout can be a representation, for example, of a movie multiplex with 4 different movie theaters.

Halls A, B, and D and staircase F are each one represented by one node since their total surface is sufficiently small, while due to a too large size, hall C and lobby E are represented by two and three nodes, respectively. When needed, we will denote the part of spaces represented by different nodes as, e.g., E 5 (subarea of lobby E represented by node 5).

A separate arc in each direction is created for every two communicating adjacent evacuation spaces and, correspondingly, graph's nodes. For simplicity, in Figure 1, we draw just outgoing arcs from the nodes representing the halls A-D to the nodes in the lobby space E, and similarly, from the nodes in lobby E to node 9 (the staircase F). Given are arcs' travel times t ij [sec], and arcs' safeties S ij for all arcs (i, j) as seen in Figure 1. The safety values in the Figure represent an emergency situation that is detailed in the following.

Let us assume that the critical safety both for arcs and paths is S cr = 0.5. Initially, during the normal operation of the building and before any incident started, safety of all areas of the building was intact and its value was 1, i.e. S A = S B = S C2 = S C3 = S D = S E5 = S E6 = S E7 = S F = 1, which translates into the value of the safety of all the arcs in the graph equal to 1. Additionally, we assume that a given safety of an area represented by a node induces the same safety value for all incoming arcs to that node.

Due to a malfunction on an electrical installation, a fire began at hall A. Therefore, shortly after the incident, the safety of hall A fell to 0.46 (below S cr ) and the building must be evacuated. The fire starts to extend to the neighboring halls B, D, and E 7 (since the walls and doors are not fire-proof). Thus, the safeties of these halls are starting to decrease and momentarily their values are S B = 0.8, S D = 0.7 and S E7 = 0.8. In particular, the safeties of the incoming arcs of node 7 fall to 0.8, however higher than the arcs' critical safety. The rest of the building spaces maintain their safety value intact, including areas E 5 and E 6 (since the fire propagates from the left part of the lobby E and is still not detected in these areas).

Moreover, given is the tolerance factor for the maximum allowed evacuation path cost (travel time), γ = 1.2. The objective is to find agile evacuation paths towards safe exits for all evacuation demands.

In the following, we analyze the case study network and present the functioning of our solution approach for finding agile evacuation paths.

Firstly, each node with present evacuation requests finds efficient and safe evacuation paths. In any case, the travel time of efficient evacuation paths cannot surpass the tolerance factor γ • [START_REF] Yusoff | Optimization approaches for macroscopic emergency evacuation planning: a survey[END_REF][START_REF] Hamacher | Mathematical modelling of evacuation problems: A state of art[END_REF], [START_REF] Hamacher | Mathematical modelling of evacuation problems: A state of art[END_REF][START_REF] Hamacher | On the use of lexicographic min cost flows in evacuation modeling[END_REF] with travel time t p 2 8,9 =75 sec. Similarly, we analyze the rest of the nodes of the graph and based on the number of efficient evacuation paths, we derive the values of evacuation centrality measure for each node, assuming for simplicity that all the efficient evacuation paths are sufficiently dissimilar (Table 1).

Table 1: Evacuation centrality measure values for the building network in Figure 1 Node, i ∈ N 1 2 3 4 5 6 7 8 9 Evacuation Centrality, C (i) 4 3 2 5 1 1 1 2 1 Next, based on the evacuation centrality measure values of the nodes of the network, we find agile evacuation paths from evacuation origin nodes 1, 2, 3, 4, and 8 by applying Formula (21) for the calculation of agility of the evacuation paths. The resulting agility values of the efficient evacuation paths are presented in Table 2. The paths with a maximum value of agility are: i) for node 1, paths p 1 1,9

and p 2 1,9 , ii) path p 1 2,9 for node 2, iii) path p 1 3,9 for node 3, iv) paths p 1 4,9 and p 2 4,9 for the evacuees starting their evacuation at node 4, and v) path p 1 8,9 for the evacuees on node 8. The selection of a set of the efficient evacuation paths with the highest agility and their assignment to evacuees should follow in a coordinated way considering evacuation demands and arcs' capacities to avoid panic-related behaviors influenced by congestion.

Conclusions

In hazardous events, hazard can spread throughout an evacuation network in an unpredictable way. This is why, in this paper, we proposed the concept of agile evacuation routes in relation to dynamically changing unpredictable safety conditions along these routes. By agile, we mean the ability to efficiently and safely reroute from intermediate nodes of an evacuation route in case of unpredictable safety drops.

For the computation of the agility of an evacuation route, we introduced a mathematical model that is based on two new node centrality measures: evacuation betweenness centrality and evacuation centrality.

Evacuation betweenness centrality of a node is a measure that represents the fraction of efficient evacuation paths between all origin-destination pairs (different from the node in question) that pass through that node. Here, efficient evacuation paths are defined as the paths that are acceptable (or feasible) with respect to safety and travel time thresholds. We defined evacuation centrality of a node, on the other hand, as a measure that represents the importance of a node for evacuation. The value of the evacuation centrality of a node is the number of efficient evacuation paths from that node.

Moreover, we defined an agile evacuation route as a route that maximizes the combined value of evacuation centrality measures of the nodes along the path. We discussed possible ways of formulating an agile evacuation route problem and presented the formulation through the maximization of a normalized product of evacuation centralities of the nodes along the route towards safe exit nodes. Moreover, we gave a case-study example of finding agile evacuation routes on a simple evacuation network.

Finally, the evacuation should be coordinated in order to avoid congestion and panic-related behaviors. The number of efficient evacuation paths from an evacuation origin to safe exits not only depends on the evacuation network's topology, but is also proportionally related to the (present) safety conditions along the evacuation paths. The nodes that have a very low number of such paths will have a low evacuation centrality value relative to other nodes. Additionally, the less agile evacuation paths (the paths with a lower combined value of their nodes' evacuation centrality values) will be more prone to hazard in case of contingencies. Therefore, we might consider the priority of evacuation by ordering assigned agile evacuation paths based on their non-decreasing path agility values, and the preference might be given to the evacuees on the evacuation paths with the least agility. We might do so since the paths with the least agility value have the lowest number of alternatives (and in the worst case none) in case of contingencies. Even though the topic is of interest, the details on evacuation coordination avoiding congestion and panic-related behaviors are out of scope of this work. However, in the future work, we will investigate in more detail how evacuation can be ordered based on the agility value of efficient evacuation paths.

Moreover, in future work, we plan to develop a distributed multi-agent based architecture for the recommendation of agile evacuation routes to evacuees. Additionally, we intend to perform thorough experiments on complex evacuation networks to test the performance of the proposed solution approach in real-world like context.

Definition 4 . 1 .

 41 Evacuation betweenness centrality C EB (i) of node i is a parameter that represents the fraction of k od efficient evacuation paths between all origin-destination (O-D) pairs (o, d) where o ∈ O and d ∈ D, both different from i ∈ N that i is a part of.

  ) through a subgradient algorithm, ii) AgileEvacuationP aths(O, P , C ), line 3, that finds a set of agile evacuation paths AG o for each evacuation origin node o ∈ O based on the nodes' evacuation centrality values found previously and the graph structure, and iii) P athAssignment(R o , AG o ), line 4, that assigns the set of agile evacuation paths AG o computed previously in line 3 to a set of evacuees R o present at each origin node o ∈ O. Algorithm 1: Agile evacuation path computation and assignment to evacuees Input: G; R; O; D; S; γ Output: {R, AG} 1 initialization: AG ← ∅ 2 {N, C } ← EvacuationCentrality(G, D, S, γ) 3 {O, AG} ← AgileEvacuationP aths(O, P , C ) 4 {R o , AG o } ← P athAssignment(R o , AG o ), for all o ∈ O 5 return {R, AG}

Figure 1 :

 1 Figure 1: Example of an evacuation network modelling from the smart building floor plan. Arc labels consist of two numeric values: average travel time t [sec] and safety S [0,1]

  t o min in respect to the fastest path, where t o min is the evacuation time of the fastest evacuation path for evacuation origin o ∈ O. Therefore, efficient evacuation paths for O-D pair (1, 9) are p 1 1,9 = (1, 7), (7, 9) with travel time t p 1 1,9 =80 sec, p 2 1,9 = (1, 6), (6, 9) with travel time t p 2 1,9 =85 sec, path p 3 1,9 = (1, 7), (7, 6), (6, 9) with travel time t p 3 1,9 =90 sec and path p 4 1,9 = (1, 6), (6, 7), (7, 9) with travel time t p 4 1,9 =95 sec. All other paths for this O-D pair including the path p 5 1,9 = (1, 7), (7, 6), (6, 5), (5, 9) with travel time t p 5 1,9 =100 sec are not efficient. As a consequence, the evacuation time for O-D pair (1, 9) will not be greater than 95 sec. There are three efficient evacuation paths available for O-D pair (2, 9): p 1 2,9 = (2, 3), (3, 5),(5, 9) with travel time t p 1 2,9 =82 sec, p 2 2,9 = (2, 5), (5, 9) with travel time t p 2 2,9 =90 sec, and p 3 2,9 = (2, 3), (3, 5), (5, 6), (6, 9) with travel time t p 3 2,9 =92 sec. O-D pair (3, 9) will have only two available efficient evacuation paths: p 1 3,9 = (3, 5), (5, 9) with travel time t p 1 3,9 =70 sec and p 2 3,9 = (3, 5), (5, 6),(6, 9) with travel time t p 2 3,9 =80 sec. Efficient evacuation paths for O-D pair (4, 9) are p 1 4,9

Table 2 :

 2 Agility values of efficient evacuation paths for the building network in Figure1

	Evacuation Efficient	Constituent Ev. centrality C	Path's
	origin	evacuation arcs' tail	of constituent	agility
	node	path	nodes	arcs' tail nodes	value
	1	p 1 1,9 p 2 1,9 p 3 1,9 p 4 1,9	1, 7 1, 6 1, 7, 6 1, 6, 7	4, 1 4, 1 4, 1, 1 4, 1, 1	2.000 2.000 1.587 1.587
	2	p 1 2,9 p 2 2,9 p 3 2,9	2, 3, 5 2, 5 2, 3, 5,6	3, 2, 1 3, 1 3, 2, 1, 1	1.817 1.732 1.565
	3	p 1 3,9 p 2 3,9	3, 5 3, 5, 6	2, 1 2, 1, 1	1.414 1.260
	4	p 1 4,9 p 2 4,9 p 3 4,9 p 4 4,9 p 5 4,9	4, 6 4, 5 4, 6, 7 4, 5, 6 4, 6, 5	5, 1 5, 1 5, 1, 1 5, 1, 1 5, 1, 1	2.236 2.236 1.710 1.710 1.710
	8	p 1 8,9 p 2 8,9	8, 7 8, 7, 6	2, 1 2, 1, 1	1.414 1.260

Acknowledgements. This work has been partially supported by an STSM Grant from COST Action IC1303.