Hassan Idoudi
email: hassan.idoudi@univ-eiffel.fr

Mostafa Ameli
email: mostafa.ameli@univ-eiffel.fr

Cyril Nguyen
email: cyril.nguyen-van-phu@univ-eiffel.fr

Van Phu

Mahdi Zargayouna
email: mahdi.zargayouna@univ-eiffel.fr

IMPACT OF DYNAMIC SHELTER ALLOCATION IN ONLINE POPULATION EVACUATION MANAGEMENT

Keywords: Network evacuation, disaster management, shelter allocation, dynamic traffic assignment

This study proposed a new framework to solve the network evacuation problem, considering a dynamic allocation of evacuees to shelters. Although many studies have been performed on this problem with static settings, there are few studies in the literature that address this problem in a dynamic context. The proposed framework couples and solves the dynamic traffic assignment (DTA) and dynamic shelter allocation problem (SAP) using agent-based dynamic simulation. The model for the SAP aims to satisfy system operator interests by allocating evacuees to shelters in a system optimal manner. The system determines the best shelters for evacuees, and evacuees tend to reach their shelters as fast as possible. Therefore, the DTA model is formulated for the user equilibrium.

It means that all evacuees minimize their own travel time. We validate our methodology on the real network of Luxembourg and evaluate its performance in front of an advanced method that solves the SAP and DTA separately, i.e., the SAP is completely solved before the evacuation process.

The results show that computing dynamic shelter allocation can improve mean evacuation time and significantly reduce the network clearance time compared to the methods with fixed shelter allocation plans. This means that considering the network state in the SAP can provide a more effective evacuation plan. Moreover, we perform a complete analysis for the computation time of the framework and show that solving the dynamic SAP is not computationally expensive compared to the profit providing for the evacuation problem.

INTRODUCTION

Natural disasters endanger the life of the entire population of the devastated areas. The frequency of natural disasters is increasing, causing more deaths and destroying the environment (Zuckerman et al.,[START_REF] Zuckerman | From natural disaster to pandemic: a health-system pharmacy rises to the challenge[END_REF]. In order to mitigate or avoid losses caused by disasters, the best way is to evacuate the people from the affected areas to safe areas or shelters. Evacuation orders are then crucial and should be effective in order to execute the evacuation process safely. Evacuation plans directly depend on the type of disaster. In addition, the objectives of the plan can be targeted based on the disaster type. The most frequently used objectives in the development of evacuation models are as follows: minimizing the total or the mean evacuation time (Hajjem et al., Bayram and Yaman, Bayram et al., 2-4), minimizing the network clearance time (Hsu and Peeta,[START_REF] Hsu | Risk-based spatial zone determination problem for stage-based evacuation operations[END_REF], (Lim et al.,[START_REF] Lim | Reliability analysis of evacuation routes under capacity uncertainty of road links[END_REF], (Zhao et al.,[START_REF] Zhao | Optimizing one-way traffic network reconfiguration and lane-based non-diversion routing for evacuation[END_REF], and minimizing the total travelled distance (Sheu and Pan, 8),(Alçada-Almeida et al., [START_REF] Alçada-Almeida | A multiobjective approach to locate emergency shelters and identify evacuation routes in urban areas[END_REF]. The network clearance time is the time that the last evacuee in the network leaves the hazardous zone and reaches safety. The total evacuation time is defined as the sum of all travel times of all evacuees. This is a measure of how long the evacuee spends in the hazardous area in total and gives us an evaluation of how successful the evacuation operation was.

The evacuation time depends on two choices of evacuees: the locations of shelters and the evacuation route toward the selected shelter. (Sherali et al.,[START_REF] Sherali | A location-allocation model and algorithm for evacuation planning under hurricane/flood conditions[END_REF] developed a model for shelter selection to tackle the problem of determining shelter locations in order to have a successful evacuation plan with minimum evacuation time.

The route choice models of evacuees used in the literature are based on three principles: user equilibrium (UE) known as Nash Equilibrium, system optimum (SO), and the nearest allocation (NA) approach. The difference between these models relies on the evacuees' behaviors. In the Nash Equilibrium model, each traveler aims to minimize his individual travel time. From the system point of view, the preferred goal to achieve is to minimize the total evacuation time. Under the SO principle, travelers may not be assigned to the fastest route for the benefit of the overall system, which could be difficult to accept by evacuees. The NA model aims to assign evacuees to the shortest path based on the distance between the origins (hazardous zone) and the destination (shelters). Obviously, such a model could not lead to acceptable results by both evacuees or system operators.

Mathematically speaking, finding UE or SO route choices for evacuees is known as traffic assignment problems. The traffic assignment models are classified into two main categories: static and dynamic models. Static traffic assignment (STA) models suppose that link flows and link travel times are time-independent, while, in dynamic traffic assignment (DTA) models, the link flow and link travel times are time-dependent (Daskin,[START_REF] Daskin | Urban transportation networks: Equilibrium analysis with mathematical programming methods[END_REF]. Despite the fact that static models are usually employed for planning problems, they cannot correctly describe traffic congestion because they do not consider capacity constraints and spillbacks. DTA models aim to capture the dynamic relationships between paths, time, and network characteristics (Levin et al.,[START_REF] Levin | Improving the convergence of simulation-based dynamic traffic assignment methodologies[END_REF]. Since the 1970s, DTA models have been used to analyze long-term and short-term planning problems (Han et al.,[START_REF] Han | Formulation, existence, and computation of boundedly rational dynamic user equilibrium with fixed or endogenous user tolerance[END_REF]. A traffic assignment model can be flow-based or trip-based. FLow-based models determine the flow on each path, while trip-based models specify the number of travelers (particles) on each path, making the traffic assignment problem much harder because it must be solved in a discrete setting (Ameli,[START_REF] Ameli | Heuristic Methods for Calculating Dynamic Traffic Assignment[END_REF].

This study aims to propose an evacuation model capable of dynamically assigns evacuees to the best shelter taking into account the current traffic conditions of congestion measured by travel time. Our model uses simulation-based DTA in order to consider traffic dynamics during the evacuation periods. In our model, we solve the two problems: (i) shelter allocation problem (SAP) to minimize the total travel time (under SO) and (ii) traffic assignment for UE considering the travelers' selfish behavior. However, we perform UE assignment in evacuee routing. And this is because users are likely to accept the system suggestion for shelters as they do not have enough information about shelters capacity and characteristics. Meanwhile, for route choice they tend to behave greedily and go for their own individual interests by minimizing their own travel time.

Note that our model covers both types of decisions that could be conflicting. To this end, we propose a simulation-based framework to combine and solve the SAP and the DTA. In addition, we compare the efficiency of our methodology with existing models by using performance measures, e.g., mean evacuation time, network clearance time, and average speed. Note that similar to most evacuation planning models in the literature, and as suggested by FEMA [START_REF] Fema | Developing and Maintaining Emergency Operations Plans[END_REF], our model is generic and not related to a precise type of disaster.

Our methodology consists of creating a linear formulation of the shelter allocation, taking into account the number of opened shelters and their capacity, and deploying the C-logit model used for DTA. We have created a flowchart that explains every step of our solution and the methodology adopted. Finally, we have developed a test case using the city of Luxembourg and compare it to existing models.

The rest of the paper is organized as follows. In the next section, we review the literature on network evacuation problems, focusing on shelter allocation and traffic assignment. Then, we highlight our contributions to the literature. In Section "Problem Formulation", we define our problem formally and present the model used by the simulator. In Section "Methodological Framework", we present the framework to solve the evacuation problem. The section "Numerical Experiments" is dedicated to present our case study and optimization scenarios. We discuss the results in Section "Results" and present the concluding remarks in the last section.

LITERATURE REVIEW AND CONTRIBUTION STATEMENT

In the literature, many studies focus on evacuation models. They solve both shelter allocation or/and traffic assignment to minimize the evacuation time or any user's cost or system benefit. In this section, we revised the related works to this study. (Sherali et al.,[START_REF] Sherali | A location-allocation model and algorithm for evacuation planning under hurricane/flood conditions[END_REF] used a p-median model for shelter site selection with a traffic assignment model that assigns evacuees to the routes in a SO manner. This model aims to minimize the evacuation time of people moving from hazard zones to shelters. To solve this problem, they have used a heuristic algorithm. In addition, they have used a static traffic assignment model to solve the routing problem, which is incapable of capturing the real state of congestion and the dynamics of traffic evolution.

Flood disasters happen in many places and the reaction of evacuees responds dynamically to changing conditions. Therefore, (Gama et al.,[START_REF] Gama | A multi-period shelter location-allocation model with evacuation orders for flood disasters[END_REF] proposed a multi-period location-allocation model based on capacitated p-median problem considering conditions changing. Their goal was to minimize the overall network distance traveled by evacuees to reach shelters. To solve the proposed formulation of the problem, they have used a simulated annealing approach. For routing purposes, they have used the distance between hazardous nodes and shelters. The major critic of this study is the difficulty of solving the complex problem within a reasonable time (Ma et al.,[START_REF] Ma | Site selection models in natural disaster shelters: a review[END_REF]. 4) proposed a non-linear mixed-integer program to formulate a static Constrained System Optimal (CSO) with an additional constraint related to tolerance level, assuming that evacuees accept to be assigned to routes that rely on a tolerance level. They have proposed a scenario-based approach to minimize the total evacuation, making decisions on two variables: shel-ter selecting variable and path assignment variable. Furthermore, the authors evaluate their model with a fairness measure. They solved the problem with an exact method called second-order cone programming. The results are generated for Sioux Falls network, the Istanbul European and Istanbul Anatolian networks under earthquake conditions. This study represents the most advanced approach in solving the STA coupled with the SAP.

Bayram et al. (

Many studies used simulation-based traffic assignment models to represent the network evacuation problem in a realistic way. However, to the best of our knowledge, there is no study in the literature that addresses and solves the SAP and the DTA simultaneously. For example, Peeta and Mahmassani (18) created DTA models for the objective of system optimal (SO) and user equilibrium (UE) with a given shelter allocation using an iterative search solution employing the simulator DYNASMART (Jayakrishnan et al.,[START_REF] Jayakrishnan | An evaluation tool for advanced traffic information and management systems in urban networks[END_REF]. They compute new travel times and assign travelers based on the new travel times using the method of successive averages (MSA). (Zhang et al.,[START_REF] Zhang | Optimization model for regional evacuation transportation system using macroscopic productivity function[END_REF] proposes a method to optimize productivity (the greatest utilization of the available network capacity) using phased (considering time intervals) evacuation process before hazard occurrence and user equilibrium constraints for routing using the TRANSIMS simulator. But TRANSIMS has not received good exposure, and its capabilities are unknown to many researchers in the transportation field (Jeihani,[START_REF] Jeihani | A review of dynamic traffic assignment computer packages[END_REF]. Besides, (Zhu et al.,[START_REF] Zhu | Hurricane evacuation modeling using behavior models and scenario-driven agent-based simulations[END_REF] have used Matsim to compute simulation-based DTA. They have used a study to estimate socioeconomic parameters included in the process of evacuee decision-making, proposing a method for generating the evacuation demand. (Liu and Lim,[START_REF] Liu | Integration of spatial analysis and an agent-based model into evacuation management for shelter assignment and routing[END_REF] proposes a scenario-based strategy to route people and to select shelters. The 2011 Brisbane flood event is considered in this paper. A simulation of scenarios was conducted using an agent-based simulation of households. The shelter assignment was based on the shortest distance between hazardous nodes and shelters, and routing was statically resolved based on the shortest distance. All the mentioned studies either use a give shelter allocation or solve DTA and SAP separately. This study aims to fill this gap by combining and solving both the DTA and the SAP.

The main contributions of this study are (i) investigate the impact of the dynamic shelter allocation on the online network evacuation problem; (ii) develop a novel model to couple the SAP and the DTA problem, which offers for the first time to formulate a fully simulation-based dynamic evacuation problem that integrates system operators' decision to choose the allocation of evacuees to shelters and evacuees interests while selecting their routes to shelters. Moreover, our model considers the dynamic location-allocation model distinguished from most models in the literature that solves the problem in a static setting. The proposed model is a multi-period model that combines system operators and user needs. Besides, we considered the problem with a real network of Luxembourg city and without any assumption of super origin/sink.

PROBLEM FORMULATION

An evacuee has two main decisions to be made in network evacuation problems: (i) Which shelter to choose as the destination, and (ii) Which route to choose in order to reach the destination. By taking into account all evacuees, the first decision problem is the SAP and the second one is the DTA problem. We aim to formulate the SAP satisfying the system operators interests (SO) in order to minimize the total evacuation time. However, the DTA problem is formulated to address the UE.

In a sense, this scenario is equivalent to a real-world scenario wherein the vehicles are guided by the system to choose their shelter (destination) as they do not have the information about the shelter conditions and capacities. Afterward, they choose their path toward their chosen shelters selfishly in order to reach the shelter with minimum travel time.

Let us define our evacuation problem on a directed graph representing a traffic network G = (N, A), where N is the set of nodes, A is the set of edges (links). We define O as the set of origin nodes that determines the risky zone to be evacuated and S as the set of destination nodes that represent safe locations, i.e., shelter sites. Without loss of generality, we assume that O and S are disjoint subsets of N (O, S ⊂ N). We denote by w o the amount of demand of each origin o, o ∈ O, this demand represents the number of vehicles that should be evacuated. We note by x os the integer decision variable that determine the number of evacuees allocated to the pair having origin o and destination s. We define the binary variable y s as the decision variable of the selection of shelter s. The t * os is the minimum travel time between origin o and destination s. In most studies, the calculation of travel time is based on a static formulation of the traffic assignment problem that uses a convex travel time function (BPR function) Bayram [START_REF] Bayram | Optimization models for large scale network evacuation planning and management: A literature review[END_REF]. In our case, we aim to use a dynamic simulator to provide us the real-time information for the travel time. Therefore, t * os is a given parameter at time of solving this problem. This transforms the model to the linear setting, thus, we can formulate this problem with linear integer programming. We define c s as the capacity of shelter s and M as the maximum allowable number of opened shelters. The full list of the important notations of this paper is presented in table 1.

s.t. ∑ s∈S x os = w o ; ∀o ∈ O, (2)
∑ o∈O x os ≤ c s y s ; ∀s ∈ S, (3)
∑ s∈S y s ≤ M, (4)
x os ≤ w o y s ; ∀o ∈ O, ∀s ∈ S, (5)

x os ≥ 0; ∀o ∈ O, ∀s ∈ S, (6)
y s ∈ {0, 1}; ∀s ∈ S. (7)
Objective function (1) represents the system operator's objective. We minimize the total travel time of evacuees from all origins to all chosen shelters. Constraints [START_REF] Hajjem | Intelligent indoor evacuation guidance system based on ant colony algorithm[END_REF] ensures that all the demand from origin node o is evacuated. Constraints (3) forbids assigning evacuees to shelters exceeding the specified shelters capacity (C s ). Constraints (4) specifies a fixed number of open shelters. Constraints (5) forbids assigning evacuees to non-opened shelters. Constraints ( 6) and ( 7) are variable restrictions.

Note that the presented model is categorized as an NP-hard problem Sherali and Nordai [START_REF] Sherali | NP-hard, capacitated, balanced p-median problems on a chain graph with a continuum of link demands[END_REF]. The SAP provides us the demand from each origin o to each shelter s, i.e, OD matrix for the DTA model. C denotes the set of origin-destination pairs, C ⊂ S × O. As mentioned before, in order to successfully formulate each part of our model, we need, not only determine the shelter allocation in a system optimal fashion but also route evacuees from risky zones to specified shelters in a way that they satisfy the UE conditions. We define the UE conditions based on the Wardrop [START_REF] Wardrop | Road paper. some theoretical aspects of road traffic research[END_REF] first principle. While we solve the SAP at a given time, the DTA problem has to be solved time-dependently. In other words, we consider the same graph G with the time dependent demand of each origin. The finite time period of interest is the planning horizon H defined as the total duration considered. This total duration is discretized into a set of small time intervals indexed by α (α ∈ T = {α 0 , α 0 + η, α 0 + 2η, . . . , α 0 + Mη} and α 0 + Mη = H) .η is the duration of the time intervals. Note that the departure time of evacuees are fixed in this study. In addition, the minimum path travel time is defined as the shortest path. In this study, we use trip-based simulator in which each traveler is a particle in the network. Thus The dynamic traffic network equilibrium conditions with given travel demand and the users' departure time for the aforementioned traffic network equilibrium problem are Ameli et al. [START_REF] Ameli | Cross-comparison of convergence algorithms to solve trip-based dynamic traffic assignment problems[END_REF]: The C-logit model is based on the logit model (Cascetta et al.,[START_REF] Cascetta | A modified logit route choice model overcoming path overlapping problems. Specification and some calibration results for interurban networks[END_REF] with the assumption that all route alternatives travel times are identically and independently distributed Gumbel variates (Daskin,[START_REF] Daskin | Urban transportation networks: Equilibrium analysis with mathematical programming methods[END_REF]. C-logit presents a probability Pr(k) for selecting paths the formula is shown below:

t α tr,p -t α c * ≥ 0 ; ∀c ∈ C, p ∈ P α c , α ∈ T (8) n Tr α p (t α tr,p -t α c * ) = 0 ; ∀c ∈ C, p ∈ P α c , α ∈ T (9
pr(k) = exp [θ • (t k -CF k )] ∑ h∈P c,α exp [θ • (t h -CF h )] ∀k ∈ P c,α , ∀c ∈ C (12)
θ denotes dispersion parameter of the travel time perception among vehicles. t k represents the travel time on path k. the set P c,α is the route set for c OD pair.

CF k is the "commonality factor" of the route k that determines the degree of overlap between the current path and all alternative routes. this commonality factor is calculated using the following formula:

CF k = β 0 ln ∑ h∈P c ID hk t 0.5 h • t 0.5 k γ ( 13
)
ID hk represents an identical part between Path h and k The respective unit can be travel time or other measurements. In this paper, travel time is adopted. t h and t k denote the travel time of Path h and k respectively. β 0 and γ are calibration parameters.

In this section, we presented the formulation for the two models to be solved for the network evacuation problem. As mentioned before, finding the optimal solution for both problems (SAP and DTA) at the same time is hard to achieve, so indicators are required to measure the distance between the solutions and the optimal solution.

Solution quality indicators

In this section, we define the metrics that are used to evaluate the optimality of our solution and monitor the network performance. We have used the network clearance time as a metric to compare the quality of solutions obtained with different optimizers. The clearance time is defined as the arrival time of the last evacuee to her shelter. This gives us information about the rapidity of the evacuation process. Note that the best solution method provides the earliest clearance time.

We have also used the mean evacuation time which is defined as the mean over of all evacuees travel time. Besides, we have made use of the network speed, which is the mean speed of the network on all simulation time steps, to quantify the network usage (Vickrey,[START_REF] Vickrey | Types of congestion pricing models[END_REF].

Moreover, in order to evaluate the quality of the DTA solution, we define the average travel delay, which is the mean amount of delay compared to the best evacuee of each OD pair. We have calculated this measure to compare the effectiveness of UE assignment. in other words, minimum value of this measure shows that all users of the OD pair have almost the same travel time.

AT D = ∑ α∈H ∑ c∈C ∑ p∈P α c t α tr,p -t α tr,c * ∑ o∈O w o (14)
We have also calculated an indicator called the average evacuation delay, representing the mean amount of delay over the best evacuee of each origin. This indicator is meaningful in the context of evacuation problems because the ultimate goal of each evacuee is to reach any shelter as soon as possible.

AED = ∑ α∈H ∑ o∈O ∑ s∈S ∑ p∈P α c t α tr,p -t α o * ∑ o∈O w o (15)
where t α tr,p denotes the minimum travel time of the evacuation trip from origin o. Note that at the pure UE state, ATD and AED are equal to zero; however, with the trip-based setting and network dynamics, it is not trivial for the UE solution.

METHODOLOGICAL FRAMEWORK

The process of solving our model is composed of three main parts: the SAP problem, the DTA optimization computing and the traffic simulation running. Here, we present the sequence of execution of each step. These steps are solved in a time dependent manner. In each time period, we optimize all of these parts iteratively based on the data provided by the dynamic simulation until all the demand is satisfied. According to the states of art, these steps are solved together using a The steps of the framework is detailed below:

1

Step 1. Initialization: a. Population distribution: the number of people that should be evacuated from each node. b. Network map: the city map represented as a graph via a network file. c. Risk zone: the set of all origins that will be considered. d. Destination nodes set: the set of shelters. nodes.

Step 2. Selecting origin nodes: This step corresponds to selecting nodes of the current time period, beginning with the highly risky nodes. This step offers us the possibility to have dynamic origin node adding. In fact, as hazards progress, we can add new origin nodes which are not known at the beginning of the evacuation.

Step 3. Shelter location-allocation problem: This is the first optimization problem following the SO principle and solving the above linear formulation. In fact, the objective of this layer is to assign users to the right destination. The output of this step is the demand profile defining the origin-destination pair with the number of users of each pair (OD matrix).

Step 4. Initial assignment: This step consists of the All-or-Nothing assignment and the initialization of the iteration index.

Step 5. Dynamic traffic simulation: In this step, we simulate each vehicle from their origin to the planned shelter by Step 3 based on the path that is determined from Step 4 or Step 9.

Note that any trip-based dynamic simulator can be used in this step.

Step 6. Updating travel time information: This step is for updating the users travel time and path travel time based on the result of the simulator. Moreover, we calculate all metrics for the solution quality and network performance.

Step 7. UE convergence check: Check if the quality of the UE solution (ATD) is below a threshold or not. OR Is the maximum number of iteration is reached or not. The second condition is designed to skip the infinite loop problem when arriving at the optimal solution. If we converge, we go to Step 10; otherwise, we go to the next step.

Step 8. Update the iteration index: This step is for calculating the new iteration number.

Step 9. Traffic assignment (second layer of optimization): The reassignment procedure follows the C-logit mechanism to generate routes to be simulated.

Step 10. Global convergence check: This step checks if all the demand is evacuated or not. If that is true, we had to end the all process. Otherwise, we go to the next step.

Step 11. Update the planning time interval In this step, we change the planning time interval and move to the next departure time interval (α + 1).

NUMERICAL EXPERIMENTS

In the previous section, we presented our framework to solve the online evacuation problem with dynamic shelter allocation. Here, we tend to apply the methodology to a real network in order to validate our solution method.

Case study

We implement our framework in order to solve the evacuation problem on the network of the LuST scenario (Figure 2a), representing the city of Luxembourg (Codeca et al.,[START_REF] Codeca | Luxembourg SUMO Traffic (LuST) Scenario: 24 hours of mobility for vehicular networking research[END_REF]. We create a demand profile based on synthetic data of the evacuation scenario. All simulations are performed on a laptop with a 1.7 GHz. and 16 GB of RAM. To solve the simulation-based DTA problem, we used the SUMO simulator and its C-logit optimization function (Lopez et al.,[START_REF] Lopez | Microscopic Traffic Simulation using SUMO[END_REF]. We used Sumo as a microscopic agent-based simulator. We set 1 second as the simulation time-step. In addition, to tackle the shelter location-allocation problem, the ILOG CPLEX version 12.9 is used. According to the size of the network, we set the duration of each departure time interval (η) to 10 minutes for the simulation. The demand at each node is 200 vehicles at each time period. We have four origin nodes selected and four shelters each with capacity of holding 1500 evacuees.

Therefore, the total demand is 600 vehicles per origin for the planning horizon (H).

Simulation-based optimization scenarios

In this study, we design two scenarios to investigate the impact of the dynamic SAP on the online evacuation planning problem. The scenarios are detailed below:

• Scenario 1: This scenario includes our proposed framework (illustrated in Figure 1) that sequentially solves the shelter allocation and the traffic assignment coupled in a loop on multiple time intervals.

• Scenario 2: This scenario represents one of the complete existing approaches to address the evacuation problem in the literature via DTA (proposed by (Hsu and Peeta, 5)). In each departure time interval, the DTA problem is solved without modifying the choice of shelters, i.e., the SAP is chosen shelters from the beginning on the basis of free-flow links speed. Note that several studies choose the shelters based on euclidean distance or network distance, which is not realistic compared to this setting as they do not take into account the characteristics of the network, e.g., road capacities.

RESULTS

In this section, the results for the two scenarios are presented. The two scenarios were run on the same evacuation demand, source nodes, and the same shelter set. We consider multiple performance measures used in the literature to evaluate the efficiency of the solution method in each scenario. We use the metrics defined in the subsection "Solution quality indicators". Table 2 presents the results for the two scenarios. The results show a significant improvement in the quality of the final solution obtained by our model compared to the second model. For instance, the reduction of 40 minutes (32%) in the network clearance time. This shows that allocating users to different shelters considering the network congestion improves the evacuation operation. The high congestion level around shelters during the evacuation could explain this difference. With fixed shelter choices in all time intervals, we will have more congestion in edges leading to these shelters, but having different shelters at each state, taking into account the network state, will ensure that we will assign evacuees to the closest shelters in terms of time-dependent shortest path and not the closest shelter(s) in terms of distance or free-flow travel time. The reduction of mean evacuation time in table 2 approves that the dynamic allocation improves the evacuation planning solution. In addition, it also provides better AED for evacuees (37%). The improvement amount is even higher for ATD, 44% reduction, which shows that the DTA solution of our method is closer to the UE solution.

Figure 3a presents the evolution of the number of vehicles evacuating in the network. The network is empty at the beginning; thus, for the first time interval, we have the same solution of the SAP for both scenarios. Then the two curves are separated because we have different shelters allocation approaches. In addition, the curve that represents our proposed method is arriving at the final state of zero running vehicle before the second curve, proving that the network clearance time is decreased compared to the other method.

The evolution of the mean speed in the evacuation process is presented in Figure 3b. The maximum speed of the network is the mean free-flow speed (73 km/h) achieved when the network is empty. At the beginning of the evacuation, the network speed for Scenario 1 is less than Scenario 2, but shortly after, it increases and stays higher than scenario 2 until the end of the process. It means that Scenario 1 uses the capacity of the network better than Scenario 2 and finishes the evacuation process faster.

The DTA is solved to find the UE state. Most studies used AT D to describe the quality of the solution. AT D could be seen as the mean distance between the travel time of users and the minimum travel time of that OD pair. In figure 4a, we can have an idea about the evolution of this measure over two last time intervals because, at the end of the first interval, no vehicles arrive at their destination. Besides, the difference in AT D between the scenarios is becoming larger in the third time period, indicating that having flexible shelter allocation offers evacuees the possibility of reducing their travel time by changing their choice of destination.

Figure 4a presents AED for the two last interval. Recall that the main difference compared to the average travel delay is that the user delay is calculated w.r.t minimum evacuation time of all users from the same origin. In other words, we compute the average difference between the travel time of each user and the shortest travel time having the same origin node. Similar to figure 4a, AED delay has the same shape as AT D, and this proves that our method is better than the second method even for the destination-free measure.

Figure 4c compares the number of evacuees that arrived at shelters in each time interval.

Our proposed method evacuates vehicles faster than the second scenario by using the remaining capacity of the network capacity, and that is why in Scenario 1, more evacuees finish their travel in the second interval.

Moreover, we measure the computation time (CT) for both optimization scenarios (see table 3). The results show that there is no large difference between the two scenarios, and this is explained by the fact that the dynamic shelter allocation optimizer does not require a long time to provide the results. Note that the shelter location-allocation is a simple linear formulation solved 3, the CT of the shelter allocation is defined only for the first scenario because the second scenario does not consider it. Note that a small difference in the DTA calculation is due to the probabilistic nature of the C-logit model. It is worth mentioning that the CT needed for DTA calculation in the last stage is lower because the SAP generates an allocation that is less computationally expensive for the DTA.

As we can see in table 3, the major part of the CT belongs to the DTA calculation. Therefore, it is worth performing a sensitivity analysis on DTA iteration because the number of iterations directly impacts the CT.

Convergence analysis

This section analyzes the effect of changing the number of iterations in the DTA calculation on the final solution. We perform our comparison based on performance measures like the clearance time and the mean evacuation time. Table 4 present the results for four values for the number of iterations. Value 1 represents the scenario wherein we use the All-or-Nothing assignment. The results show that we have minimized a mean evacuation time and converge in 10 iterations in both cases. However, for a large number of iterations (20 or 30), there is an oscillation in the value of measures even there is a higher value of mean evacuation time. This is expected because we aim to achieve the UE, not the SO. Therefore, our algorithm minimizes the individual travel time, and that could have a negative effect on the whole system performance. The results can be viewed from another angle. Table 4 shows that by increasing the number of iterations to search for the optimal solution for the UE, we decrease the network production factors. From these results, we can conclude that if we fix the iteration number between 10 and 20, we could have a good evacuation plan for this test case from both points of view, users and the system.

CONCLUSION

Catastrophes threaten the entire population of the devastated areas and put them in high-risk situations. In order to avoid life losses caused by these disasters, the best way is to evacuate people from areas considered as risky zones to safe areas. This paper focuses on solving network evacuation problems. Modeling and optimizing this problem efficiently can help us not only to save more lives, but also to help evacuees to evacuate from hazardous areas as fast as possible.

In this study, we perform a literature review and analyze the different approaches and models used in the research field for evacuation planning. We have found that the evacuation problem is composed of two main parts: the route choice and the shelter choice of evacuees. For the first part, known as traffic assignment, two types of models are used: STA and DTA models. Researchers have made good progress using the static formulation for the network evacuation problem, especially when having a shelter allocation model. However, there are few studies about the evacuation problem in the dynamic context for both traffic routing and shelter allocation. This study proposed a planning framework to solve the dynamic network evacuation problem, including shelter allocation problem and dynamic traffic assignment.

In order to solve the evacuation problem dynamically, we have solved the problem in multiple departure time intervals by considering the system optimum principle for the SAP and the user equilibrium principle for the DTA problem. For calculation of the vehicle evacuation time,

we have considered a trip-based dynamic simulator that provides us the travel information every second. We apply our methodology to the real network of Luxembourg and compare it with a model using fixed shelters. The results show that the proposed model outperforms the model with fixed shelter by more than 30% reduction in network clearance time. It means that using dynamic allocation can improve the evacuation process because it gives us an opportunity to provide the optimal evacuation plan considering the dynamics of the network. Besides, the analysis on the computation time proves that solving the online SAP needs tiny computational resources, while it significantly reduces the duration of the evacuation process. The second main finding of this study is that using an online shelter allocation model can also use better the production capacity of the traffic network (Figure 3).

Moreover, we have conducted a sensitivity analysis on the maximum number of iterations used in DTA calculation. The results show that with a reasonable number of iteration, we can find a plan closer to UE in terms of delay. For future works, we aim first to evaluate our framework performance to large-scale real network evacuation scenarios. Second, we want to extend the current framework to solve the SAP and DTA problem together in an online setting. An interesting extension of our framework is to consider the capacity of shelters in a dynamic way, taking into account the outflow rate of each shelter. Another direction for the research can be addressing multiple hazard zones by mimicking the hazard evolution.

  ) n Tr α p ≥ 0 ; ∀p ∈ P α c , α ∈ T (10) Equation 8 ensures the definition of the shortest path. Equation 9 is the main condition of the UE which guarantees that all users travel on shortest path with minimum travel time at UE state. The non-negativity of n Tr α p is hold by equation 10. Lu et al. (29) proved that in the tripbased setting, solving the UE problem is equivalent to solve a non-linear problem to minimize the user delay function. The delay is defined as the difference between the user travel time and the shortest path travel time on the same c. Therefore, the solution to this UE problem is equivalent to solve the following variational inequality Sbayti et al., Ameli et al. (30, 31): p * n(Tr c )n(Tr * p ) ≥ 0 (11) where n(Tr * p ) is the optimal number of trips on path p and t * tr,p . is the optimal travel time of trips on path p. n(Tr c ), n(Tr * p ) ∈ H . H is a set feasible solution satisfying the equilibrium.In the simulation-based DTA, at each departure time interval, we tend to attain the UE state so that each vehicle could not reduce their trip travel time by changing the chosen route. To achieve this condition, we iteratively run both phases optimization and simulation. The optimization determines the route choice of vehicles and in the simulation part, we simulate the trajectories on paths by executing a dynamic simulation of vehicles taking specified routes. The model used to assign users to the route is the C-logit mechanism(Cascetta et al.,[START_REF] Cascetta | A modified logit route choice model overcoming path overlapping problems. Specification and some calibration results for interurban networks[END_REF].

  static traffic assignment model as a single level problem like Bayram et al. (4) and Bayram and Yaman (3) or bi-level programming problem firstly proposed by (Von Stackelberg, 34) (see e.g., Ng et al., Li et al., Kongsomsaksakul et al., Xu et al. (35-38)).In the dynamic setting, Hsu and Peeta[START_REF] Hsu | Risk-based spatial zone determination problem for stage-based evacuation operations[END_REF] proposed the most complete setting for dynamic network evacuation problem. They have defined multiple time intervals and solved the problem in time periods and evolving state of the network. While they do consider the problem of risk determination based on risk estimation, they do not consider the SAP in their methodology. In fact, their study could be compared to solving DTA in SO manner having multiple time intervals with fixed shelter allocation solution from the beginning of the process. Here, we aim to solving the shelter allocation and evacuation routing using simulation-based DTA in time intervals to capture the evolving state (congestion) of the network, creating an evacuation plan with flexible shelter allocation. The proposed methodology by this study is presented in Figure1.

FIGURE 1 :

 1 FIGURE 1: flowchart of the solving the evacuation problem

  (a) Luxembourg mapping data ©Google 2021 (b) Luxembourg sumo city network (c) Luxembourg sumo city network hazard nodes

FIGURE 2 :Figure 2

 22 FIGURE 2: Evacuation network map

  (a) Number of active users in the network variation (b) Network mean speed variation

FIGURE 3 :

 3 FIGURE 3: Performance measures variation

FIGURE 4 :

 4 FIGURE 4: Delay and number of arrival measures variation

TABLE 1 :

 1 List of trips which travel for c on path p in departure time interval α, Tr α Experienced travel time of trip tr on path p in departure time α. -allocation problem under different types of hazards like hurricanes, typhoons, tsunamis, etc Ma et al.[START_REF] Ma | Site selection models in natural disaster shelters: a review[END_REF]. due to its global objective that makes it applicable in most cases of hazard. This global objective prioritizes efficiency and fairness over users preferences by minimizing the overall evacuation time which represents the SO Here, the mathematical model for the SO

	P α c P α c	*	Set of paths for c in departure time interval α. Set of shortest paths for c in departure time interval α.
	p p Tr α	Index of path, p ∈ P α c .
	Tr α p	p ⊂ Tr α c .
	tr		Index of trip, tr ∈ Tr α c .
	t α tr,p
	t α * c	Minimum experienced travel time for c in departure time interval α.
	n(A)	Cardinality of set A.

Table of notations O Set origin nodes, subset of set of nodes, O ⊂ N. S Set destination nodes, subset of set of nodes, S ⊂ N. o Index of origin node, o ∈ O. s Index of destination node, s ∈ S. t * os Minimum experienced travel time form origin o and destination s. t os Experienced travel time form origin o and destination s. w o Amount of demand from origin o. c s Capacity of shelter s, limit number of evacuee allocated to shelter s. M Maximum number of open shelters. C OD pairs, subset of origin × destination nodes, C ⊂ O × S. c Index of origin-destination (OD) pair, c ∈ C, c = os. * Index of shortest path, p * ∈ P α c * . c List of trips which travel for c in departure time interval. α. The goal of the SAP is to calculate the SO. The solution of this problem is the allocation of evacuees to shelters for the minimum total evacuation time (TET) based on the current travel time from risky nodes to shelters. The p-median model is the most common approach to represent the shelter location

TABLE 2 :

 2 Performance metrics

	Metrics	Scenario 1 Scenario 2
	Network clearance time(s)	4956.00	7320.00
	Mean evacuation time(s)	1296.77	2028.75
	Average travel delay (ATD)	599.03	1069.66
	Average evacuation delay (AED)	696.14	1110.59

TABLE 3 :

 3 Computation time of the solution methods

	α Computation time [s]	Scenario 1 Scenario 2
	1	Shelter location allocation DTA Calculation	0.09 80.99	-81.41
	2	Shelter location allocation DTA Calculation	0.09 102.02	-103.55
	3	Shelter location allocation DTA Calculation	0.09 229.10	-430.01

TABLE 4 :

 4 The impact of the number of DTA iterations on the final solution.

	Number of iterations		1	10	20	30
	Network clearance time [s]	Scenario 1 Scenario 2	8087 8425	4956 7320	4740 7307	5282 7386
	Mean evacuation time [s]	Scenario 1 3429,69 2409,93 2392,35 2457,73 Scenario 2 4205,69 3369,16 3365,08 3376,42

CONFLICT OF INTEREST

The authors declare no potential conflict of interests.

AUTHOR CONTRIBUTION STATEMENT

All the authors have contributed to all aspects of this study, ranging from the conception and design of the methodology, analysis and interpretation of the results and discussion, and the manuscript preparation.