Hassan Idoudi

Mostafa Ameli

Cyril Nguyen Van Phu

Abderrezak Rachedi

Simulation-based Optimization Framework for Stage-based Evacuation Planning

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

This study proposes a new framework to solve the road 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. We couple and solve 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 determining the best shelters for evacuees, and evacuees tend to reach their shelters as fast as possible. We validate our methodology on the real network of Luxembourg City and evaluate its performance in front of one of the advanced methods in the literature. The results show that calculating dynamic shelter allocation improves mean evacuation time and significantly reduces the network clearance time compared to the methods with fixed shelter allocation plans.

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 [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. The evacuation plans and their objectives directly depend on the type of disaster. The most frequently used objectives in the development of evacuation models are the minimization of the total or the mean evacuation time [START_REF] Bayram | Shelter location and evacuation route assignment under uncertainty: A benders decomposition approach[END_REF], and the minimization of the network clearance time [START_REF] Hsu | Risk-based spatial zone determination problem for stagebased evacuation operations[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. The authors in [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.

Mathematically speaking, finding the user equilibrium (UE) or the system optimum (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 [START_REF] Ameli | Multi-attribute, multi-class, tripbased, multi-modal traffic network equilibrium model: Application to large-scale network[END_REF]. Static models are usually employed for planning problems, and they cannot correctly describe traffic congestion because they do not consider capacity constraints and spillbacks [START_REF] Ameli | Day-to-day multimodal dynamic traffic assignment: impacts of the learning process in case of non-unique solutions[END_REF].

This study aims to propose an evacuation model capable of dynamically assigning evacuees to the best shelter taking into account the current traffic conditions measured by travel time. Our model uses simulation-based DTA to consider traffic dynamics during the evacuation periods. In our model, we solve the two problems: (i) the shelter allocation problem (SAP) to minimize the total travel time (under SO) and (ii) the traffic assignment problem for UE considering the travelers' selfish behavior. We perform UE assignment in evacuees routing, because they are likely to accept the system suggestion for shelters as they do not have enough information about shelters capacity and characteristics. While 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. Hence, 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) as suggested by [START_REF] Fema | Developing and maintaining emergency operations plans[END_REF], and similarly to most evacuation planning models in the literature. 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 developed a test case using the city of Luxembourg and compare it to existing models.

The remainder of the paper is organized as follows. In the next section, we present the framework to solve the evacuation problem. In section 3, we present the scenarios that will be used for our experiment. In section 4, we present our case study and optimization scenarios before presenting concluding remarks in section 5.

METHODOLOGY

The process of solving our model is composed of three main steps: the SAP problem solving, the DTA optimization and the traffic simulation execution. These steps are performed in a timedependent 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.

The authors in [START_REF] Hsu | Risk-based spatial zone determination problem for stagebased 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 with an evolving state of the network. While they do consider the problem of risk determination based on risk estimation, the authors do not consider the SAP in their methodology. In fact, their study could be compared to solving DTA with SO having multiple time intervals with fixed shelter allocation solution from the beginning of the process. In the present work, we aim to solve 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 Figure 1. The solution method starts with Initialization and solves the SAP for the first time interval. The results of the SAP is used as the input of the DTA. The DTA calculation under UE is started by the all-or-nothing assignment. Then the dynamic simulation is executed, and the travel time are updated for all users. Afterward, we check the convergence test for the UE conditions. If we do not converge, we reassign the users to the path based on the C-logit mechanism and rerun the simulation. The simulation-based DTA is continued until the convergence. Then methods checks if all demand is served or not. If yes, the process is finished, otherwise, it goes to the next departure time interval.

The steps of the framework is detailed below:

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. 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 a facility location 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 tripbased 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).

CASE STUDY

We implement our framework on the network of the LuST scenario (Figure 2a), representing the city of Luxembourg [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 [START_REF] Lopez | Microscopic traffic simulation using sumo[END_REF]. In addition, to tackle the shelter location-allocation problem, the ILOG CPLEX version 12.9 is used.

Figure 2 presents the real network of Luxembourg with the size of 155.95 km 2 and the traffic network graph considered by SUMO for dynamic simulation. We examine a hypothetical threat in the center zone affecting people of that region colored in red in figure 2b. We do not assume a super origin (source) node in this study. Multiple origin nodes are considered as the evacuation sources in the risk zone, as described in figure 2c. Vehicles, carrying people, should be evacuated to shelters, colored in green in figure 2b, located at the periphery of the network. 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 [START_REF] Hsu | Risk-based spatial zone determination problem for stagebased evacuation operations[END_REF]). In each departure time interval, the DTA problem is solved without modifying the choice of shelters.

RESULTS AND DISCUSSION

In this section, the results for the two scenarios are presented. The two scenarios were executed 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. 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. 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.

We have calculated the average evacuation delay, representing the mean amount of delay over the best evacuee of each origin. The reduction of mean evacuation time in table 2 approves that the dynamic allocation improves the evacuation planning solution. In addition, the improvement amount is high 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.

CONCLUSIONS

Disasters threaten the entire population of the concerned areas and put them in high-risk situations.

In order to avoid life losses,the best way is to evacuate people from the risky areas to safe zones. This paper focuses on solving the related network evacuation problems. Modeling and optimizing this problem efficiently can help people to evacuate from hazardous areas as fast as possible and save lives.

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. To calculate the vehicle evacuation time, we have considered a trip-based dynamic simulator that provides 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%, in terms of reduction in network clearance time. It means that using dynamic allocation can improve the evacuation process because it gives an opportunity to provide the optimal evacuation plan considering the dynamics of the network. For future works, we aim first to evaluate our framework performance to large-scale real network evacuation scenarios. Second, we plan to extend the current framework to solve the SAP and DTA problem together in an online setting.

Figure 1 :

 1 Figure 1: flowchart of the solving the evacuation problem

  Figure 2: Evacuation network map

  Figure 3: Network performance measures

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