Loading web-font TeX/Math/Italic
Large-Scale Evacuation Shelter Selection Method Through Iterations of Pedestrian Simulations With Dynamic Congestion Reproduction | IEEE Journals & Magazine | IEEE Xplore

Large-Scale Evacuation Shelter Selection Method Through Iterations of Pedestrian Simulations With Dynamic Congestion Reproduction


The graphical abstract of Congestion-aware Shelter Selection Method.

Abstract:

It is necessary to optimize evacuation guidance to shelters in short evacuation time. The state-of-the-art method based on an idea of combinatorial optimization problems ...Show More

Abstract:

It is necessary to optimize evacuation guidance to shelters in short evacuation time. The state-of-the-art method based on an idea of combinatorial optimization problems related to evacuees’ locations and the capacities of nearby shelters has been developed, while it cannot mitigate the effect of congestion on roads/streets after evacuation starts. In this study, to cover this problem, we develop a new method that utilizes simulations for estimating the effect of congestion on roads/streets during evacuation and reassigning shelters to evacuees based on the simulation results. By iterating this step, our method derives the congestion-aware solutions for shelter selection that can realize more smooth evacuation. To evaluate our method, we conducted multi-agent simulations assuming a disaster situation in a sightseeing spot. Specifically, we examined a hypothetical case scenario involving the evacuation of 30,000 visitors from the Gion Festival. We compared the proposed method with conventional methods, such as the nearest shelter selection method and our previous method. We found that our proposed method reduced average and total evacuation time and congestion on roads compared to the conventional methods including the nearest shelter selection method and our previous method that only employs combinatorial optimization without estimating congestion. From this result, our idea of simulation-based congestion estimation has an impact of easing congestion during evacuation and preventing overcapacity of shelters at the same time. It shows the possibilities of help in developing congestion-aware evacuation strategies in emergency situations of crowded areas like huge cities or sightseeing spots.
The graphical abstract of Congestion-aware Shelter Selection Method.
Published in: IEEE Access ( Volume: 10)
Page(s): 89387 - 89401
Date of Publication: 25 August 2022
Electronic ISSN: 2169-3536

Funding Agency:


CCBY - IEEE is not the copyright holder of this material. Please follow the instructions via https://creativecommons.org/licenses/by/4.0/ to obtain full-text articles and stipulations in the API documentation.
SECTION I.

Introduction

Robust disaster management plans are required to safely evacuate evacuees in the event of disasters such as earthquakes or typhoons. Public organizations provide disaster information [1], [2] and publish hazard maps so that people can implement the best evacuation actions in disaster situations. Many studies have developed evacuation support systems which provide disaster information and automatic disaster detection targeting support in affected areas [3]–​[5]. On the other hand, in the event of a large-scale disaster, it is important to be aware of the extent of damage in areas far from the epicenter as well as in affected areas. In the case of the East Japan earthquake, the transportation was disrupted as far away as the Tokyo metropolitan area, which is a considerable distance from the disaster areas in the Tohoku region. Due to the disruption caused by the earthquake, approximately four million people were unable to return home in the Tokyo metropolitan area [6].

In most evacuation scenarios, evacuees are advised to relocate to the closest shelter from wherever they are at the time [7], [8]. However, under such circumstances, the emergency shelters in areas such as sightseeing spots will likely become overcrowded if evacuees are distributed unevenly throughout the affected area. If evacuees in a crowded area head to the closest shelters at the same time, then some of those shelters will become crowded and unable to accommodate all of the arriving evacuees. In such cases, some evacuees will be rejected from the shelters and they will have to move to other shelters, delaying in evacuation.

To solve this problem, we previously proposed an evacuation shelter selection method that considers the bias of congestion in disaster areas [9]. Specifically, we employed a combinatorial optimization method to identify optimal destinations for each evacuee based on proximity and shelter capacities aimed at avoidance of evacuees rejection by shelters and reduction in evacuation time. This method allows people to evacuate more quickly than the nearest shelter selection method.

Alongside the problems of shelter capacities, several studies on evacuation strategies [10], [11] deal with congestion during evacuation to achieve smooth evacuation. In areas with high population density, particularly, congestion on roads can be caused by evacuees’ behavior. In the case of the East Japan earthquake, due to the disruptions of public transportation, train stations and main thoroughfares were crowded with people in the Tokyo metropolitan area and they struggled to get to safe place [6]. The problem with our previous method [9] is that it selects destinations for each evacuee from only locations of evacuees at the start of evacuation. It does not consider how congestion on roads will be affected by evacuees’ action after evacuees begin to head for the shelters, which can result in delays in evacuation time and discomfort.

In this paper, we propose a new evacuation shelter selection method that considers the relative congestion in disaster areas to minimize evacuation time and mitigate against the congestion on roads that will be caused by the evacuation. Our main target case is an emergency situation in a crowded area like a big city or a sightseeing spot where people including non-residential visitors cannot return home due to sudden disasters.

As overcoming the weakness of our previous method [9], we target mitigating against congestion on roads to realize more smooth evacuation in a situation where evacuees are unevenly distributed in disaster areas and must be assigned to shelters to prevent evacuees rejection by shelters. To achieve this task, we have improved our previous method [9], with simulations being repeated in order to mitigate congestion on roads during evacuation. By conducting simulations, we can estimate how long it will take for people to evacuate under the influence of congestion on roads. Then, utilizing the result of this simulation, the method selects shelters for evacuees again so that the evacuation time is shortened (thus congestion on roads is mitigated). After the shelter selection, another simulation will be conducted to estimate evacuation time by reselection of shelters. By repeating these steps, the method finally derives semi-optimal solutions to the shelter selection problem that can be applied to the mitigation of congestion on roads and the reduction of evacuation time. The main contributions of this paper are summarized as follows:

  • First, we newly defined a problem of congestion on roads caused by people’s evacuation alongside overcapacity of shelters in sudden disaster situations of crowded areas. To mitigate the influence of congestion and achieve more smooth evacuation compared to our previous method, we redesigned the new congestion-aware target of shelter selection.

  • Second, we developed a new shelter selection method that repeats simulations of combinatorial optimization for shelters and evacuees based on the previous simulation result. The method derives the solutions for shelter selection that enable people to evacuate in shorter time with fewer congestion.

  • Finally, we evaluated the proposed method by conducting multi-agent simulations for a scenario in which 30,000 visitors to the Gion Festival needed to be evacuated due to a sudden disaster. The results showed that our method effectively reduced the average and total evacuation time of evacuees and that it effectively mitigated congestion in the disaster area.

The remainder of this paper is organized as follows. Section II explains related work on disaster management and congestion estimation. Section III describes our research target and our previous work, which forms the core of the proposed method. Section IV explains the details of the proposed method. Section V evaluates our proposed method. Section VI discusses the results and Section VII concludes the paper.

SECTION II.

Related Work

In this section, we discuss the exiting studies on evacuation guidance and congestion estimation. We then clarify our research goals in this paper.

A. Evacuation Guidance

Japan frequently experiences disasters such as earthquakes and floods. The Japanese Government and local self-governments issue disaster management plans for emergencies, and the Cabinet Office publishes white papers on disaster management [1]. In addition, the Ministry of Land, Infrastructure and Tourism maintains a web site, “Disaster Prevention Portal [2],” which provides information on disasters and disaster prevention manuals.

Numerous studies on natural disasters and emergencies have examined topics such as optimizing evacuation route selection [7], [8], [12], generating evacuation maps [3] and developing disaster communication systems [13]. Kasai et al. [7] have proposed a congestion-aware route selection method in the automatic evacuation guiding utilizing a traffic congestion model and wireless communication with evacuees’ mobile nodes. However, the simulation conducted in their study did not consider the differential capacities of multiple shelters. Oomes et al. [14] have proposed an organization awareness support system that provides users with the ability to visualize disaster impacts and help organizations share disaster information. Fitraianie et al. [15] have proposed an evacuation routing system that recommends an evacuation route after collecting disaster information. Zheng et al. [16] have developed Rescue Wings, a service-oriented system designed to assist victims and emergency responders in disaster rescue operations. Murotsu et al. [17] have developed an evacuation route search algorithm for fire disasters. Zhang et al. [18] have proposed a congestion-aware evacuation routing solution for indoor evacuation using augmented reality devices.

In many studies on disaster events, multi-agent simulation is an essential technique for predicting and assuming the evacuation behavior of people in disaster situations [19], [20]. Mas et al. [19] have developed an evacuation model for tsunamis that considers the number of casualties. Chun et al. [20] have proposed an evacuation simulation framework for optimizing emergency management in urban residential communities. Makinoshima et al. [21] have proposed an evacuation simulation model with parallel computing and applied it to a tsunami evacuation case. Lee et al. [22] formulated a method for resolving decision making problems in disasters using a decentralized and partially observable Markov decision-process model, and have proposed a multi-agent reinforcement learning algorithm augmented by pretraining to tackle the problem. Taga et al. [23] have proposed an evacuation support system using an ad hoc mobile network that enables information sharing when communication infrastructure is not available. HoseinDoost et al. [24] have described a model-driven framework for developing multi-agent systems in emergency response environments, which contains three steps of domain-specific modeling language, a transformation program and a platform for executing the generated code.

Regarding strategies for assigning humans or materials, Delgoshaei et al. [25], [26] have presented a review of human resource planning methods and material transferring on cellular manufacturing systems (CMS) and have proposed a multi-period scheduling method that finds best production strategy of workers assignment and outsourcing [27]. These studies share a topic related to multi-agent based people allocation, while they do not address emergency disaster situations. Sang et al. [28] have proposed a multi-criteria decision making method under fuzzy statement and multi-agent based rescue model using combinatorial auction to decide which volunteers should help which disabled people. This study addresses evacuees allocation in disaster situations, however it does not consider how evacuees’ behaviors can cause congestion on roads and affect evacuation time in areas of high population density.

While numerous emergency response approaches have been developed for disaster situations, these studies explained above have not addressed the evacuation strategies that are employed in situations, such as shelter selection method for large numbers of evacuees in crowded urban areas. In addition, previous studies have not examined how exceeding shelter capacities and refusal to accept arriving evacuees will affect evacuation time.

On shelter selection method, we have proposed a method that utilize combinatorial optimization for shelters and evacuees [9]. Tanaka et al. [29] have also proposed shelter decision methods considering non-cooperative evacuees’ behavior to support “disaster weak,” which are those who have difficulty in evacuating due to their physical abilities, such as the elderly, children, disabled people. However, these previous shelter selection methods [9], [29] do not consider dynamic congestion on roads after people start evacuation. Thus, these methods are not capable of mitigating the influences of congestion during evacuation.

Khalipourazar et al. [30] have also proposed a robust mathematical model for designing a flood evacuation plan. In their case scenario, the target is the optimal number and location of shelters, assigning evacuees and helicopters to shelters, flying path of helicopters to rescue people and the number of people transported by helicopters. They applied their robust model on a case scenario of 2011’s massive tsunami in Ishinomaki City. Still, this study does not cover disaster situations of crowded urban areas in which non-residents like visitors exist and congestion on streets will occur because people have to walk to shelters.

B. Congestion Estimation

An urgent need exists for the development of a real-time congestion estimation system to predict traffic jams and congestion mitigation. Song et al. [31] have proposed an estimation method that uses pictures of groups of people taken by smartphones. Nishimura et al. [32] have proposed a system for estimating congestion levels and smoothness of pedestrian flows by analyzing walking motion and ambient sound that can be monitored from accelerometers and smartphones. Bellocchi et al. [33] have developed a dynamic model of congestion formation for large-scale urban networks based on a reaction and a diffusion term. Their model presented reproducing link speeds estimated from more than 40 million of GPS coordinates per day of about 20.000 taxis in Shenzhen, China. Weppner et al. [34] have proposed estimating crowd size by scanning Bluetooth devices. They have also proposed a crowd-monitoring method based on tracking consumer devices with WiFi/Bluetooth interfaces [35]. Chan et al. [36] have developed a crowd monitoring system that protects the privacy of evacuees. Specifically, they segmented the crowd into components of homogeneous motion and learned the correspondence between features from the segments and the number of people using Gaussian process regression. Congestion estimation systems based on cameras or data from devices that people have in their possession are often limited in terms of the application and adopttion by privacy concerns and issues with device-possession rate.

Hidaka et al. [37] have developed a system for collecting and curating sightseeing information that enables the creation of interesting tour routes. This study sought to develop a real-time congestion estimation based on a system that is not dependent upon specific devices, is cost effective to deploy and is energy efficient. To satisfy these requirements, Umeki et al. [38] have developed a real-time congestion estimation system that utilizes Bluetooth Low Energy (BLE) with low cost, and is easy to use. Although real-time congestion estimation systems have been developed in various ways, few studies discuss how these systems have effects on optimal shelter selection methods in congested disaster areas.

C. Our Research

To best of our knowledge, few published studies have examined how to assign a large number of evacuees to shelters for outdoor evacuation when exceeding shelter capacities and congestion during evacuation can cause delays in evacuation time. Although we have developed the shelter selection method to deal with the problem of shelter capacities [9], the method did not consider how congestion during evacuation also affects evacuation time. In conventional studies, due to difficulties of estimating congestion in disaster areas, optimal shelter selection that consider congestion during evacuation was a challenging issue. However, as explained above, the widespread use of geographical information services combined with the development of IoT devices has enabled us to perform real-time congestion estimates. Provided a few assumptions have been met, we consider that it is possible to collect congestion information in disaster areas. Therefore, we hypothesize developing a shelter selection method that considers congestion during evacuation is practicable. Based on the above assumption, we assume situations in which evacuees including non-residential people like visitors have to walk to shelters in crowded urban areas far from an epicenter. Then, to address these situations and improve the shortcoming of our previous method on congestion, we develop a shelter selection system for mitigating the effect of congestion during evacuation alongside preventing overcapacity in this study.

SECTION III.

Congestion-Aware Disaster Management

In this study, we develop a shelter selection method considering human congestion during evacuation to minimize evacuation time and congestion in disaster areas. In this section, we discuss the situation scenario that we assume, and our previous work [9] regarding to its target situations, procedure and problem with road congestion during evacuation.

A. Assumptions

We primarily deal with disaster situations in which many pedestrians cannot return home due to the widespread disruption in the disaster areas. In such situations, the evacuees have to find places to stay for at least one day. Cities and towns will open evacuation shelters, which will be divided into two categories: “designated emergency evacuation site” and “designated evacuation shelters.” The designated emergency evacuation sites are evacuation destinations that are used to ensure the safety and wellbeing of people in an emergency. Designated evacuation shelters are intended for temporary stays of people who experience difficulty returning home in disaster situations. In this study, “shelters” for evacuees are referred to as “designated evacuation shelters.”

B. Prerequisites

At present, the widespread use of location-based services and the development of IoT devices and sensors have made it easier to estimate congestion on streets in real-time [34]–​[36]. In our scenario, congestion can be estimated through sensors [38]. Every evacuee has a device, such as a smartphone, in which an application is installed to obtain evacuation instructions. The evacuation system developed in this study obtains the location information of evacuees from their devices. The system estimates the time required for evacuation to shelters for each evacuee based on their current locations. After estimating evacuation time, the system selects the destinations for each evacuee through its own shelter selection algorithm. The evacuees are then informed of the decided destinations and routes by the system, so that they can act to evacuate by following the directions. The architecture of the system is shown in Figure 1. In this study, we assume that such an evacuation shelter decision system is widespread, and that all of the evacuees have devices that can be used to receive evacuation instructions. Discussion of the means, format and details of evacuation guidance is crucial to realization of the system, however it is outside the scope of this study.

FIGURE 1. - System Architecture.
FIGURE 1.

System Architecture.

C. Previous Work

Previously, we have proposed a shelter selection method [9] that considers uneven distribution of evacuees in a disaster area and shelter capacities to minimize evacuation time. In our previous work, we assumed the following situation: Each shelter has a limited capacity for accommodating evacuees. In common evacuation strategies, evacuees are advised to move to the nearest shelters from their locations (hereinafter called the nearest shelter selection method). However, in situations where evacuees are unevenly distributed, shelters may not be able to accommodate all arriving evacuees if they move to the nearest shelters. In such cases, some evacuees may be denied access to those shelters and forced to seek out another shelter that can accept them, causing delays in evacuation time. In the case of Figure 2, two shelters, Shelter A and Shelter B, can accommodate five people each, while eight of the ten evacuees in the area are closest to Shelter A. If the eight evacuees head to Shelter A, three of them will be rejected.

FIGURE 2. - Capacity Exceeding Caused by Uneven People Distribution.
FIGURE 2.

Capacity Exceeding Caused by Uneven People Distribution.

To deal with this problem, the main idea of the method is to use a combinatorial optimization method using the number of evacuees and shelter capacities as variables (hereinafter called COP method). Algorithm 1 shows how evacuees are assigned to shelters. The system predicts evacuation time for each evacuee to each shelter. To be specific, time is calculated from the distance of the evacuees’ locations to the shelters. The predicted time data will be used to generate an evacuation time list ({VTable} ) like Table 1. As the input of Algorithm 1, the group of evacuees({I} ), the group of shelters({J} ), {VTable} , and the group of shelter capacities({C_{J}} ) are given. The system decides the destinations for each evacuee and produces Shelter Selection List({X_{IJ}} ) from the input. As shown in line 1 of Algorithm 1, {VTable} is sorted in ascending order for each shelter. Table 1 is rearranged as shown in Table 2 in this procedure.

TABLE 1 Evacuation Time List
Table 1- 
Evacuation Time List
TABLE 2 Evacuation Time List Sorted in Ascending Order
Table 2- 
Evacuation Time List Sorted in Ascending Order

Algorithm 1 Procedure of COP Method

Input:

{I} : Group of Evacuees, {J} : Group of Shelters, {VTable} : Evacuation Time Table involved with {I} and {J} , {C_{j}} (j \in J) : Capacity of Shelter {j}

Output:

{X_{IJ}} : Shelter Selection List

1:

{VTable} \leftarrow SortArc(VTable) // Sort the list in ascending order for each shelter

2:

while |I| > 1 do

3:

i,j \leftarrow GetMinimumuEvacuationTime(VTable)

4:

{X_{ij}} \leftarrow 1

5:

{VTable} \leftarrow RemoveEvacuee(VTable, i, I)

6:

{C_{j}} \leftarrow {C_{j}} - 1

7:

if {C_{j}} = 0 then

8:

{VTable} \leftarrow RemoveShelter(VTable, j, J)

9:

end if

10:

end while

After producing evacuation time list, shelter selection will be started. Considering whether the algorithm can be realistically adopted in disaster situations, quick instructions will be required and the destinations decided by the method should be acceptable for individual evacuees. When one shelter is relatively close to an evacuee, he/she will not try to get to other distant shelters. In such a situation, evacuees are not always obedient to instructions and each can take an action for his/her own rather than the whole, even if the optimal solutions are presented. In light of the above, we designed a heuristic algorithm that preferentially selects the set of an evacuee and a shelter with the minimum evacuation time of all.

As shown in line 3 of Algorithm 1, the set of an evacuee({i} ) and a shelter({j} ) with the minimum evacuation time in {VTable} will be chosen, then the evacuee({i} ) is assigned to the shelter({j} ). Taking Table 2 as an example, for Evacuee_1 to reach Shelter_2 will take 10 minutes, which is the minimum of all elements in the list. Thus, Shelter_2 is assigned as the destination for Evacuee_1. After the destination is decided, as shown in Line 5, the evacuee({i} ) is removed from {VTable} and the group of evacuees({I} ). If {C_{j}} becomes 0, the elements associated with the shelter are removed from {VTable} and the group of shelters({J} ). In the example of Table 2, Shelter_2 reaches its capacity as Evacuee_1 is assigned to Shelter_2. Thus, the elements associated with Evacuee_1 or Shelter_2 are deleted from the list. This procedure is repeated until the destinations for all evacuees are selected (|{I}| = 0). Following the assignment for Evacuee_1, for Evacuee_2 to reach Shelter_3, 15 minutes is the minimum of the remaining elements, Shelter_3 is therefore set as the destination for Evacuee_2. In the same way, Evacuee_4 is assigned to Shelter_1 and Evacuee_3 is assigned to Shelter_1 and the shelter selection process is terminated. COP method can reduce evacuation time compared to the nearest shelter selection method.

D. Limitations of Previous Work

COP method predicts evacuation time based only on the distance of the evacuees’ locations to the shelters. In other words, the method does not consider how congestion may affect people’s routes once they start to evacuate. Congestion on roads can impede quick smooth evacuation, then evacuees will have to take more time than predicted to reach destinations. To avoid disturbance in evacuation, it is needed to estimate evacuation time taking into account the effects of road congestion. Nevertheless, as the state of congestion in disaster areas changes dynamically as evacuees move, an accurate grasp of congestion is difficult.

To predict the impact of disasters and evacuation behavior of people, simulations are widely utilized in many studies [39], [40]. Thus, we place simulations as the solution to deal with the effects of dynamic changes of congestion in disaster areas. In the next section, we explain our new shelter selection method that considers the effects of congestion utilizing simulations.

SECTION IV.

Proposed Method

In this section, we propose a new evacuation shelter selection method that considers the effect of congestion in disaster areas during evacuation. The limitation of the COP method is that it does not consider how congestion affects the routes selected as optimal ones by the system. We modified our previous COP method to develop a new method, which we named the “Congestion-aware COP” method (hereinafter called CACOP method). The key points of CACOP method are as follows:

  • Utilizing simulation results of COP method for congestion estimation.

  • Reperforming the procedures of COP method under the influence of this estimation.

  • Deriving semi-optimal solutions for shelter selection that mitigate effects of congestion by iterating the two steps above.

Algorithm 2 shows the procedure of CACOP method.

SECTION Algorithm 2

Procedure of CACOP Method

Input:

{I} : Group of Evacuees, {J} : Group of Shelters, {VTable} : Evacuation Time Table involved with {I} and {J} , {C_{j}} (j \in J) : Capacity of Shelter {j}

Output:

X_{IJ} : Shelter Selection List

1:

{X_{IJ}} \leftarrow COP(I,J,VTable,{C_{j}} )

2:

{VTable} , {T_{I0}} \leftarrow SimulateEvacuation({X_{IJ}}) // Conduct a Simulation based on the result of COP Method

3:

{AGAIN} \leftarrow TRUE

4:

{N} \leftarrow 0

5:

while {AGAIN} do

6:

{N} \leftarrow {N} + 1

7:

{X_{IJ}} \leftarrow COP(I,J,VTable,{C_{j}} )

8:

{VTable} , {T_{IN}} \leftarrow SimulateEvacuation({X_{IJ}})

9:

{AGAIN} \leftarrow FALSE

10:

for i < |I| do

11:

{r_{i}} \leftarrow \dfrac {{T_{iN}} - {T_{i{N-1}}}}{{T_{i{N-1}}}}

12:

if |{r_{i}}| > 0.01 then

13:

{AGAIN} \leftarrow TRUE

14:

end if

15:

end for

16:

end while

1) CONDUCT A SIMULATION AND UPDATE THE EVACUATION TIME TABLE

Similarly to COP method, CACOP method requires information on evacuees and shelters and an evacuation time table as input. As shown in line 1 of Algorithm 2, the first thing CACOP method does is shelter selection following COP method. Then, a simulation is conducted based on the shelter selection result. Due to congestion on roads, evacuees will take more time to evacuate than predicted. In the simulation conducted, evacuation time will be different from the predicted time because congestion on roads will adversely affect the evacuees’ actions. To consider the impact of congestion in shelter selection, we reproduce {VTable} based on the simulation result and update the elements in the list. When the simulation is terminated, the evacuation time each evacuee took in the simulation is recorded as {T_{I0}} and {VTable} is revised(Shown in line 2 of Algorithm 2).

Table 3 shows an example of how the elements are updated after the simulations. In the first shelter selection, Shelter_2 is selected as the optimal destination for Evacuee_1 and the evacuation time is predicted to be 10 minutes. In contrast to the initial prediction, Evacuee_1 arrives at the shelter in 25 minutes in the simulation. After the simulation, the predicted evacuation time to Shelter_2 for Evacuee_1 is updated to 25 minutes. Then, as in Step 1, each evacuee’s destination is selected using COP method based on the updated evacuation time list.

TABLE 3 Revised Evacuation Time List
Table 3- 
Revised Evacuation Time List
TABLE 4 Parameter Settings
Table 4- 
Parameter Settings

After updating the evacuation time list, the method selects shelters for each evacuee based on the updated {VTable} (line 5 of Algorithm 2). Then, as shown in line 6 of Algorithm 2, a simulation for the new shelter selection result is conducted. When the simulation is terminated, {VTable} is updated and the evacuation time for each evacuee in the simulation is recorded. In Table 3, Evacuee_1 heads for Shelter_3 following the new shelter selection. After the second simulation, Sim_1, the predicted evacuation time to Shelter_3 for Evacuee_1 is updated to 40 minutes.

2) ITERATING SIMULATIONS TO DERIVE THE SEMI-OPTIMAL SOLUTION

For each evacuee, {r_{i}} , the change rate of evacuation time, is given. The change rate is calculated from the evacuation time in the latest simulation result, {T_{iN}} , and that in the previous result, {T_{i{N-1}}} (line 11 of Algorithm 2). If the change rate of one evacuee is higher than 1%, the process of shelter selection and a simulation will be resumed. In other words, the iteration stops when the change rate for all evacuees is less than 1%. When all of the steps are completed, the final result of the shelter selection and the evacuation time is considered as the definitive result of CACOP method.

SECTION V.

Evaluation and Results

To evaluate whether the proposed method is effective, we conducted a multi-agent simulation assuming the Gion Festival as the simulation scenario.

A. Evaluation Environments

For the evaluation simulations, we used Scenargie, the simulation framework and Scenargie Multi-Agent Extension Module produced by Space-Time Engineering Japan Inc [41], [42]. The source codes for the simulation system are written in C++ and we implanted the module for shelter selection into the original Scenargie codes. We used a desktop computer which has following specifications.

  • OS: CentOS Linux 7

  • Memory: 128GB

  • CPU: Intel Core i7-6850K 3.60GHz 12cores

As an example of crowded sightseeing spots, we selected the Gion Festival, which is one of the largest festivals in Japan. Geographic information system (GIS) data were obtained from OpenStreetMap.1 The Gion Festival is held during July annually. The days of Yamahoko parade, which are the 17th, Sakimatsuri and the 24th, Atomatsuri, are the highlight of this festival. According to several articles [43]–​[46], approximately 150,000 visitors attended the festival in two days, July 17 and 24, 2019. The breakdown of the visitors is as follows: 120,000 people on the 17th and the remaining, 30,000 on the 24th. Based on this fact, we chose Atomatsuri on July 24 as the simulation scenario and set 30,000 agents in the simulation map. Figure 3 shows the whole of the simulation map.

FIGURE 3. - Whole of Simulation Map.
FIGURE 3.

Whole of Simulation Map.

B. Parameters and Settings for Simulations

Here we present the parameter settings of agents and environments. These settings cover the following parameters: 1) walking speed; 2) initial locations; 3) shelter capacity; 4) evacuee behaviors.

1) Walking Speed

Based on some existing simulation experiments [9], [29], evacuees are assumed to follow the road network and we set the standard walking speed of evacuees as follows:\begin{equation*} {v} = {1.0 \sim 1.5\,[\text {m/s}]}.\tag{1}\end{equation*}

View SourceRight-click on figure for MathML and additional features.

Moreover, according to a document published by the Cabinet Office of Japan2 and an artice by Fruin (May, 1984),3 the actual walking speed affects congestion on roads. Thus, the actual walking speed {V_{i}} was set as follows:\begin{align*} {V_{i}} = \begin{cases} {v_{i}} & ({p_{i}} < 1.5) \\ {v_{i}} - ({v_{i}} - 0.1) \times \frac {p - 1.5}{4.5} & (1.5 \leq {p_{i}} < 6) \\ 0.1 & (6 \leq {p_{i}}) \end{cases}\tag{2}\end{align*}

View SourceRight-click on figure for MathML and additional features. where {v_{i}} is the standard walking speed of evacuee {i} . Here, {p_{i}} is the population density on the road where evacuee {i} exists. {p_{i}} is defined as follows:\begin{equation*} {p_{i}} = \frac {PR}{rw \times rl}\, [\text {people/$m^{2}$}]\tag{3}\end{equation*}
View SourceRight-click on figure for MathML and additional features.
where {PR} is the number of people on the road, {rw} [m] is the road width and {rl} [m] is the road length. Values of both {rw} and {rl} were obtained from road objects in the OpenStreetMap dataset.

2) Initial Locations

In the festival, many of the visitors are assumed to gather in specific areas. On July 24, two float parades, Hanakasa and Yamahako, go through the streets. Figure 3 shows the whole of simulation map. Each of the two arrows shown in red and blue shows the route taken by each parade. Intersections in the map are illustrated by red circles. In our scenario, we assumed the visitors gather around the courses to view the parade. Therefore, the area around the parade routes is divided into four areas (Area 1, Area 2, Area 3, and Area 4). Each area is indicated by green, purple, light blue, and orange areas, respectively. We used five groups of evacuees, each of which had following initial location:

  • Group 1: 4,000 people will start from Area 1

  • Group 2: 8,000 people will start from Area 2

  • Group 3: 4,000 people will start from Area 3

  • Group 4: 4,000 people will start from Area 4

  • Group 5: The rest, 10,000 people, will start from random points around the whole map.

Figure 4 shows two examples for distribution of evacuees in the whole map. Each map is divided in squares of 500m \times500\text{m} . The number in a square represents how many evacuees exist on the roads in the square. The color of a square depends on the number of evacuees.

FIGURE 4. - Distribution of Evacuees at the Beginning of Evacuation.
FIGURE 4.

Distribution of Evacuees at the Beginning of Evacuation.

3) Shelters

Based on the shelter map published by Kyoto City,4 we set 32 shelters as destinations in our evaluation scenario map. Each shelter has an entrance based on the actual building. In the case of the 2011 Tohoku earthquake, shelters in Tokyo were 5 to 10 times over capacity. In our previous study [9] and that of Tanaka et al. [29], they conducted simulations at five time as the actual shelter capacities in Kyoto considering this fact. Based on the fact in the East Japan earthquake and the experiment settings in the previous studies [9], [29], we therefore set the capacities of shelters to five times the original capacities indicated on the shelter map for Kyoto City. The total capacity of all shelters in the evaluation scenario was thus 54,835.

4) Behavior of Evacuees

When evacuees are informed of their destination, evacuees move to their assigned shelters along the shortest path. If evacuees are refused at shelters, then they restart their evacuation and make their way to the next closest shelter. Evacuees who do not follow evacuation instructions will randomly come from groups of evacuees whose decided shelters are not the nearest ones. These evacuees will move to their nearest shelters first. Figures 5 and 6 show how the population density of the roads changes as the simulations proceed in two different cases. At the beginning of an evacuation, evacuees are scattered in the whole area (shown in Figures 5-(a) and 6-(a) of the case example A and B). Figures 5-(b) and 6-(b) show proceeding evacuation. Some evacuees are moving to shelters, and others have finished evacuation. Lastly, the end of evacuation, when all evacuees are in shelters, is illustrated in Figures 5-(c) and 6-(c).

FIGURE 5. - Simulation Flow (Example A).
FIGURE 5.

Simulation Flow (Example A).

FIGURE 6. - Simulation Flow (Example B).
FIGURE 6.

Simulation Flow (Example B).

5) Congestion Value for Evacuees

To evaluate how crowded where each evacuee exists is, the variable, {c_{i}} , that represents congestion on a road is given for each evacuee {i} . As the indicator of congestion, {p_{i}} population density of roads used for setting walking speed was defined as congestion value.

C. Comparison Methods

Each pattern of the method is simulated in 20 cases with different initial location sets. We briefly describe each method and scenario in the following sections.

1) Nearest Shelter Selection Method

All evacuees move to their nearest shelters by selecting the shortest route. When an evacuee arrives at a shelter, the evacuee can enter the shelter if there is sufficient space. If a shelter is filled to capacity, then the evacuee will have to move to another shelter nearest to that point. In this experiment, “succeeding in entering a shelter” implies that the “evacuation is complete.” When all of the evacuees complete their evacuations, the simulation will end.

2) COP

The evacuation system calculates predicted evacuation time from the current positions of evacuees to the entrances of shelters and selects shelters for individual evacuees in the procedure described in Section III. Then, the system informs each evacuee of where to go via their devices. Evacuees move to their assigned destinations using the short distance. Once all of the evacuees finishes evacuating, the simulation is terminated. The results derived by the simulations of this method are positioned as the ones of the non-congestion-aware method and become the baseline for CACOP method.

3) CACOP

The destinations for all evacuees are assigned using in the procedure described in Section IV. Once the process of CACOP completed, the final simulation result is taken as the evaluation result. We also evaluate a scenario in which evacuees who do not follow the assigned evacuation instructions. The proportion of evacuees who do not follow the evacuation instructions, {r} , is set as 20%, 40%, 60%, 80%. As in the case of nearest shelter selection method, if evacuees are rejected by shelters, the evacuees are assumed to move to the next nearest shelter from their current location. When all of the evacuees finishes evacuating, the simulation is terminated.

D. Evaluation Indicators

To evaluate the different methods, we employed the following evaluation metrics.

1) Average Evacuation Time

In disaster situations, delays in evacuation constitute large risks for evacuees. Consequently, in most disaster management studies, shorter evacuation times are considered optimal. When an evacuee finishes evacuating, the time is taken as the evacuees’ evacuation time. The average evacuation time of all evacuees in each pattern is defined as the result.

2) Total Evacuation Rate

During the simulations, the time at which a certain percentage of evacuees have evacuated is recorded. When all of the people have finished evacuating, the total evacuation rate is taken as 100%.

3) Total Congestion Values

For the proposed method, CACOP, and the previous method, COP, we estimated congestion values in disaster area to evaluate how well the proposed method can mitigate congestion during evacuation. A congestion value is assigned to evacuees and the definition of congestion is same as in equation (3), which is explained in V-B1. We measured the sum of congestion values for all evacuees at 10 second intervals until the simulation is terminated.

E. Results

1) Average Evacuation Time

Figure 7 shows the average evacuation time for all of the evacuees and for every simulation pattern. The value obtained for the nearest shelter selection method is 1155.05 seconds, which is the highest of all. The average evacuation time obtained for COP method is 541.46 seconds, which is less than half of that obtained for the nearest shelter selection method.

FIGURE 7. - Average Evacuation Time.
FIGURE 7.

Average Evacuation Time.

For CACOP method, the average evacuation time is 535.51 seconds when all of the evacuees follow the assigned evacuation instructions. Compared to COP method, the average evacuation time is reduced slightly by approximately 1%.

We also evaluated the scenario in which some evacuees did not follow the assigned instructions. As the number of non-cooperative evacuees increases, the average evacuation time rises. When the non-cooperative rate {r} is 20%, the average evacuation time is 643.54 seconds. When {r} is 80%, the average evacuation time is 1023.88 seconds.

Compared to the nearest shelter selection method, CACOP method can reduce the average evacuation time, even when many evacuees did not follow the assigned evacuation procedure.

Figure 8 shows the average evacuation time obtained for COP and CACOP methods in each of the 20 cases. A reduction in the average evacuation time was observed in all cases. We conducted a t-test for the result of the average evacuation time. A comparison of the average evacuation times by t-test showed that the differences between methods was significant(t(19) = 41.49, ** p <.001).

FIGURE 8. - Average Evacuation Time for Every Case (COP vs CACOP).
FIGURE 8.

Average Evacuation Time for Every Case (COP vs CACOP).

2) Total Evacuation Rate

Figure 9 shows the results of changes in the total evacuation rate for each pattern. For the nearest shelter selection method, all of the evacuees finished their evacuations in 5,216 seconds. The total evacuation time for COP method is 2,509 seconds, while that of CACOP method is 2,209 seconds, which is approximately 12% shorter than that of COP method.

FIGURE 9. - Total Evacuation Rate.
FIGURE 9.

Total Evacuation Rate.

COP and CACOP methods are capable of evacuating 99% of evacuees in about 1,650 seconds, when all evacuees are cooperative. When CACOP method is applied and the non-cooperative rate is 20%, 95% of evacuees can be evacuated in 2,000 seconds. The higher the non-cooperative rate, the fewer evacuees can be evacuated quickly. When the rate is 80%, 17% of the people fail to be evacuated in 2,000 seconds. The nearest shelter selection method can evacuate fewer than 80% of the people in 2,000 seconds.

Figure 10 shows the evacuation time calculated by COP method without considering the effect of congestion and the total evacuation time results of COP and CACOP methods for all 20 cases. A reduction in total evacuation time is observed in all of the cases. When total evacuation times were compared by a t-test, the results showed that the difference between methods is significant({t} (19) = 18.62, ** {p} <.001). About gaps between the primal calculated time by COP and required total evacuation time, CACOP reduced the gaps by 31.6% on average compared to COP.

FIGURE 10. - Total Evacuation Time for Every Case (COP (No Congestion-aware) vs. COP vs. CACOP).
FIGURE 10.

Total Evacuation Time for Every Case (COP (No Congestion-aware) vs. COP vs. CACOP).

3) Congestion Values for Evacuees

Figure 11 shows how the total congestion value for the entire disaster area changes every 10 seconds in Case 1. Overall, compared to COP method, CACOP method reduced the total congestion value. The total congestion value of COP method peaks at 1,320 seconds with a value of 17,005.8, whereas using CACOP method, the total congestion value peaks at 1,220 seconds with a value of 9,542.77.

FIGURE 11. - Changes in Total Congestion Value (Case 1).
FIGURE 11.

Changes in Total Congestion Value (Case 1).

Figure 12 shows the average total congestion values obtained for each of the 20 cases using the COP and CACOP methods. The range in the congestion values of the 20 cases was marked, ranging from 3429.3 to 3974.5 in COP methods and from 2347.1 to 2878.9 in CACOP method. Comparing these methods, the congestion values was reduced by 24% to 32.5%.

FIGURE 12. - Average of Total Congestion Value for Every Case (COP vs. CACOP).
FIGURE 12.

Average of Total Congestion Value for Every Case (COP vs. CACOP).

Figure 13 shows the maximum total congestion value obtained for each of all the 20 cases using COP and CACOP methods. A marked reduction was observed in the total congestion value of all 20 cases. The highest total congestion value for COP method was observed from 1,250 seconds to 1,350 seconds, with the highest peaks ranging from 14,367 to 18,575.9. On the other hand, highest total congestion value for CACOP method was observed from 1,120 seconds to 1,240 seconds, with the highest peaks observed in the range from 7,409.3 to 10,877.5. The change rate ranged from 24.2% to 57.8%.

FIGURE 13. - Maximum Total Congestion Value for Every Case (COP vs. CACOP).
FIGURE 13.

Maximum Total Congestion Value for Every Case (COP vs. CACOP).

4) Simulation Iterations

We also evaluated how many simulation iterations are required until CACOP results are derived in each of the 20 cases. Through the experiments for the 20 cases, the maximum number of simulation iterations is 48 with approximately 128 minutes of computational time, while the minimum is 22 with approximately 61 minutes of computational time.

SECTION VI.

Discussion

We focused on the delays in evacuation time caused by congestion and how these delays can be mitigated. To develop the proposed method, we revised COP method, by adding steps to reflect the effect of congestion in shelter selection. Specifically, evacuation simulations were used to estimate congestion and for producing a congestion-aware evacuation time lists, which were used to select shelters in a way that reflected the simulation result.

Regarding the results of the average evacuation time and change in the total evacuation rate, the difference between the performances of CACOP and COP was small. The proposed method assigns evacuees to shelters in a way that attempts to avoid congestion during evacuation. Compared to COP method, some evacuees will be assigned to more distant shelters when using CACOP method; this difference in the assigned distance accounts for the slight difference in the evacuation times estimated for the two methods.

In contrast, regarding the maximum total congestion value during evacuation, CACOP is capable of reducing the total congestion value by an average of 47%. As shown in Figure 11, the total congestion value was greatly mitigated during overall evacuation.

As explained above, there is a slight difference in the evacuation times obtained between COP and CACOP methods. However, at the same time, congestion during evacuation is drastically reduced. In other words, CACOP method can help people to evacuate almost as quickly as COP method with less stress, and fewer burdens caused by congestion. About the gaps between non-congestion-aware calculated time and required evacuation time, CACOP shortened evacuation time delays due to congestion by 31.6 %. Considering these gaps to be the effect of congestion, CACOP has realized more congestion-free evacuation guidance.

From the simulation results for evacuating 30,000 attendees at a simulated Gion Festival, we consider that the new method will have a marked impact in terms of congestion mitigation in places with high population densities such as urban areas or sightseeing spots.

When disasters occur in crowded areas, particularly in unfamiliar places, such as sightseeing spots or festivals, returning home is impossible and people will struggle to find where shelters are. In such situations, they will be endangered without evacuation guidance and congestion on roads/streets induced by evacuees’ behavior can cause secondary damage. Simulations outline how evacuation time will become under heavy congestion on streets and can provide clues for building evacuation strategies. In disaster situations of crowded areas, like our case scenario, the simulation system is assumed to be operated by public organizations such as cities or governments, and companies for technical assistance. Private groups like event planners can utilize the system by cooperating with these organizations. In a huge city like Tokyo or New York, evacuation guidance will be possible by operating the system in each segment of cities. In this way, our simulation-based shelter selection method will contribute to disaster prevention as a concept of smart-city model. Furthermore, the method can be extended to handle more severe disaster situations like tsunamis with different parameter settings. However, the limitations of the proposed method are as follows:

  • The shelter selection method cannot be deployed if communication networks are disrupted, sensors are faulty, or roads are impassible.

  • In our scenario, evacuees take short-distance routes to their destinations. We must consider how evacuees can take different routes to shelters in a way that can mitigate congestion more effectively.

  • Our system does not consider disorders in disaster environments such as road disruptions once shelters have been assigned. It cannot enable evacuees to see other candidates destinations when responding to dynamic disaster situations.

Another issue is that our proposed method employs heuristic procedures although we adopted such procedures due to its tractability, low computational time and human behavior. Still, the method cannot derive mathematically optimal solutions. There is room for consideration in developing shelter selection methods which evacuate people in shorter average or total evacuation time under situations with different conditions or parameter settings.

SECTION VII.

Conclusion

In this paper, we have proposed an evacuation shelter selection method to realize mitigating congestion that will be caused by the evacuation. We enhanced our previous method by adding steps to account for the effect of congestion in shelter selection so that evacuees can avoid congestion during evacuation. The findings of this study are as follows:

  • We conducted a simulation of COP method, which is our previous shelter selection procedure considering shelter capacities and predicted evacuation time, to estimate how congestion on roads affect evacuation. Based on the result of this simulation, we select shelters for individuals with the effect of congestion considered. After repeating this step several times, our method derives congestion-aware solutions for the shelter selection, which can reduce congestion during evacuation drastically compared to our previous non-congestion-considered method.

  • We conducted multi-agent simulations for an evacuation scenario involving 30,000 visitors to the Gion Festival. The results showed that our method could be used to mitigate congestion in and disaster areas in an evacuation time similar to that of COP method. The decrease rate of the average total congestion value ranged from 24% to 32.5%, while that of the highest total congestion value ranged from 24.2% to 57.8%.

This paper has shown simulation-based estimation of the effects of congestion and how it works for realizing quick and smooth evacuation. We consider our idea of congestion-aware shelter selection can contribute to developing evacuation strategies in sudden disaster cases. To achieve more practical methods for evacuation, how simulations and the whole instruction systems should be operated in real cases must be investigated. Also, in the future, we will develop more effective methods that can realize quicker and smoother evacuation by considering additional factors and problems in disaster situations.

ACKNOWLEDGMENT

(Kazuhito Umeki and Tomoki Tanaka contributed equally to this work.)

References

References is not available for this document.