# Evacuation Planning for Disaster Management by Using the Relaxation Based Algorithm and Route Choice Model

Dedy Hartama, Herman Mawengkang, Muhammad Zarlis, Rahmat Widia Sembiring, Benny Benyamin Nasution, - Sumarno, M. Safii, Indra Gunawan, Eka Irawan, . Saifullah, et al.

► To cite this version:

Dedy Hartama, Herman Mawengkang, Muhammad Zarlis, Rahmat Widia Sembiring, Benny Benyamin Nasution, et al. Evacuation Planning for Disaster Management by Using the Relaxation Based Algorithm and Route Choice Model. 2nd International Conference on Information Technology in Disaster Risk Reduction (ITDRR), Oct 2017, Sofia, Bulgaria. pp.136-144, 10.1007/978-3-030-18293-9_12. hal-02280351

HAL Id: hal-02280351

https://inria.hal.science/hal-02280351

Submitted on 6 Sep 2019

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Evacuation Planning for Disaster Management by Using the Relaxation Based Algorithm and Route Choice Model

Dedy Hartama<fnref n="1" />,<fnref n="3" />, Herman Mawengkang, Muhammad Zarlis, Rahmat Widia Sem-
biring<fnref n="2" />, Benny Benyamin Nasution<fnref n="2" />, Sumarno<fnref n="3" />, M Safii<fnref n="3" />, Indra Gunawan<fnref n="3" />,
Eka Irawan<fnref n="3" />, Saifullah<fnref n="3" />, Irfan Sudahri Damanik<fnref n="3" />, Hartono<fnref n="1" />

**Abstract.** Research in the field of disaster management is done by utilizing information and communication technology. Where disaster management is discussed is about evacuation planning issues. The evacuation stage is a very crucial stage in the disaster evacuation process. There have been many methods and algorithms submitted for the evacuation planning process, but no one has directly addressed evacuation planning on dynamic issues concerning time-varying and volume-dependent. This research will use the Relaxation-Based Algorithm combined with the Route Choice Model to produce evacuation models that can be applied to dynamic issues related to time-varying and volume-dependent because some types of disaster will result in damage as time and evacuation paths are volume-dependent so as to adjust to the change in the number of people evacuated. Disaster data that will be used in this research is sourced from Disaster Information Management System sourced from DesInventar. The results of this study are expected to produce an evacuation planning model that can be applied to dynamic problems that take into account the time-varying and volume-dependent aspects.

**Keywords:** Disaster Management, Evacuation Planning, Time-Varying, Volume-Dependent.

## 1 Introduction

In real life situations, disasters such as floods, earthquakes, hurricanes and terrorist attacks can occur to threaten human life. The evacuation problem has attracted much attention from various researchers. The current modeling approach for evacuation planning can be divided into two categories, namely analytical approach and simulation based approach [1].

An analytical approach has been widely used to generate an optimal evacuation plan for disaster response. The research conducted by [2] illustrates a model to minimize the evacuation path time for emergency evacuation. [3] presented a Two Network Flow method using Dijkstra's algorithm to generate an evacuation plan through minimizing

<footnote n="1">¹Universitas Sumatera Utara</footnote>

<footnote n="2">² Politeknik Negeri Medan</footnote>

<footnote n="3">³ STIKOM Tunas Bangsa Pematang Siantar
dedyhartama@amiktunasbangsa.ac.id</footnote>
the total distance traveled. [4] produced several models that can be applied to evacuation problems in multi-story buildings with an approach that uses the dynamic network flow model. The network flow model was then refined by [5] to identify the optimal evacuation route plan for complicated evacuation route situations. Furthermore, [6] developed the Integrated Lagrangian Relaxation and Tabu Search approach to the problem of optimizing the evacuation routes on land. [7] has conducted research to overcome capacity constraint problem by using heuristic algorithm.

[8] proposed an optimal dynamic traffic assignment formulation system to minimize total evacuation time. [9] has proposed frame work to obtain an optimal route. [10, 11] have proposed stochastic system method-optimal dynamic traffic assignment formulation to improve evacuation model using probabilistic demand constraints. [12] uses a noisy genetic algorithm to design an evacuation path that can save more and more people within a specified time limit. [13] used a heuristic algorithm to optimize the evacuation path associated with the process of endogenous risk minimization in the evacuation process. Research conducted by Li and Ozbay [13] has been able to overcome the problem of uncertainty (uncertainty) in the evacuation process.

Research that has been done by some researchers, have not pay attention to side constraint aspects such as distance and cost. [1] has developed [13] research and incorporated it with the Lagrangian Relaxation-Based approach to address side constraint issues in the evacuation process. However, the weakness of [1] is not yet applicable to dynamic issues such as time-varying and volume-dependent. Some types of disasters will result in damage as time increases and evacuation routes are volume-dependent. Research conducted by [1] overrides the time as well as the volumes acceptable to an evacuation route by assuming the number of persons to be evacuated is known.

Reference [9] has resulted in research in selecting routes that are best adapted to the volume or capacity of a route. The results of research from a number of researchers can be summarized in Table 1.

In Table 1, it can be seen that there are 2 (two) objective functions used by a number of researchers, namely: Minimizing the Total Evacuation Time (MTET) and Minimizing the Total Evacuation Distance (MTED) and there are also a number of algorithms used. While the application of the network used also there are 2 (two) forms: Transportation Network and Building Network.

Researchers in this study will use the Relaxation-Based Algorithm combined with the Route Choice Model to produce an evacuation model that minimizes the evacuation time that can be applied to dynamic issues related to time-varying and volume-dependent because some types of disaster will result in damage as time increases and the evacuation route is volume-dependent in order to adapt to changes in the number of people evacuated.

## 2 Evacuation Model With Relaxation-Based Algorithm and Route-Choice Model

Research that has been done by some researchers, have not pay attention to side constraint aspects such as distance and cost. [1] has developed [13] research and incorpo-
rated it with the Lagrangian Relaxation-Based approach to address side constraint issues in the evacuation process. However, the weakness of [1] is not yet applicable to dynamic issues such as time-varying and volume-dependent. Some types of disasters will result in damage as time increases and evacuation routes are volume-dependent. Research conducted by [1] overrides the time as well as the volumes acceptable to an evacuation route by assuming the number of persons to be evacuated is known.

Researchers in this study will use the Relaxation-Based Algorithm combined with the Route Choice Model to produce an evacuation model that can be applied to dynamic issues related to time-varying and volume-dependent because some types of disaster will result in damage as time and evacuation paths are volume-dependent so that it can adapt to changes in the number of people being evacuated.

<table><caption>**Table 1.** Comparative Research Table</caption><thead><tr><th>Objective Function</th><th>Algorithm</th><th>Application-Network</th><th>Side Constraint</th><th>Uncertainty</th><th>Publication</th></tr></thead><tbody><tr><td>MTET</td><td>NETVACI</td><td>T</td><td>No</td><td>No</td><td>Sheffi et al. (1982)</td></tr><tr><td>MTED</td><td>Dijkstra's Algorithm</td><td>T</td><td>No</td><td>No</td><td>Yamada (1996)</td></tr><tr><td>MTED</td><td>CPLEX Solver</td><td>T</td><td>No</td><td>No</td><td>Cova and Johnson (2003)</td></tr><tr><td>MTET</td><td>Heuristic Algorithm</td><td>B</td><td>No</td><td>No</td><td>Lu et al. (2003, 2005)</td></tr><tr><td>MTET</td><td>Heuristic Algorithm</td><td>T</td><td>No</td><td>No</td><td>Sbayti and Mahmassani (2006)</td></tr><tr><td>MTET</td><td>DYNASMART-P</td><td>T</td><td>No</td><td>No</td><td>Han et al. (2006)</td></tr><tr><td>MTET</td><td>LIPSOL Solver</td><td>T</td><td>No</td><td>No</td><td>Chiu and Zheng (2007)</td></tr><tr><td>MTET</td><td>P-Level Efficient Points</td><td>T</td><td>No</td><td>Yes</td><td>Yazici and Ozbay (2007)</td></tr><tr><td>MDEF</td><td>Noisy Genetic Algorithm</td><td>B</td><td>No</td><td>Yes</td><td>Miller-Hooks and Sorrel (2008)</td></tr><tr><td>MTET</td><td>GAMS Slover</td><td>T</td><td>No</td><td>Yes</td><td>Ng and Waller (2010)</td></tr><tr><td>MTET</td><td>Heuristic Algorithm</td><td>T</td><td>No</td><td>Yes</td><td>Li and Ozbay (2014)</td></tr><tr><td>MTET</td><td>Relaxation-Based Algorithm</td><td>T</td><td>Yes</td><td>Yes</td><td>Wang et al. (2016)</td></tr></tbody></table>

## 2.1 Heuristic Algorithm

The heuristic algorithm for the evacuation planning process was first introduced by [13] and this algorithm is a type of algorithm that uses the objective function of MTET with its ability to handle uncertainties in the evacuation process. The stages of the Heuristic Algorithm in the disaster evacuation process can be seen in Fig. 1.
<figure><img src="image_2.png" /><figcaption>Fig. 1. Flowchart Stages of Heuristic Algorithm</figcaption></figure>

## 2.2 System Constraint on Evacuation Process

There are a number of constraints that are considered in the evacuation process, as follows [1]. The mathematical parameters used for constraints can be seen in Table 2.

**Flow Balance Constraint.** Flow Balance Constraint is a constraint related to the origin region (Origin $O_k$) and Destination Region (Destination $D_K$). Flow Balance Constraints are used to generate paths using Eq. 1

$$ \sum_{(i,j) \in A} x_{ij}^{ks} - \sum_{(j,i) \in A} x_{ji}^{ks} = \begin{cases} 1, & i = 0_k \\ -1, & i = D_k, & k = 1, 2, \dots, K, s = 1, 2, \dots, S \\ 0, & \text{otherwise} \end{cases} \quad (1) $$

**Capacity Constraint.** Capacity Constraint will be applied to a number of agents through a link in a scenario with the aim of ensuring travel efficiency and avoiding congestion. The Capacity Constraint can be seen in Eq. 2.
$$ \sum_{k=1}^{K} x_{ij}^{ks} \leq u_{ij}^{s}, \forall (i, j) \in A, s = 1, 2, \dots, S \quad (2) $$

**Side Constraint.** Side Constraint is used to ensure the total load required for an agent K does not exceed the upper limit of the required resources. This can be seen in Eq. 3.

$$ \sum_{(i,j) \in A} x_{ij}^{ks} \cdot w_{ij}^{kl} \leq w^{kl}, s = 1, 2, \dots, S, \quad k = 1, 2, \dots, K, l = 1, 2, \dots, L \quad (3) $$

<table><caption>**Table 2.** Subscript and Mathematical Parameters Used</caption><thead><tr><th>Symbol</th><th>Definition</th></tr></thead><tbody><tr><td><i>N</i></td><td>The Set of Nodes</td></tr><tr><td><i>A</i></td><td>The Set of Links</td></tr><tr><td><i>i</i>,<i>j</i></td><td>The Index of Nodes, <i>i</i>, <i>j</i> &isin; <i>N</i></td></tr><tr><td>(<i>i</i>,<i>j</i>)</td><td>The Index of Directed Links, <i>i</i>, <i>j</i> &isin; <i>A</i></td></tr><tr><td><i>s</i></td><td>The Index of Scenario</td></tr><tr><td><i>S</i></td><td>The Number of Scenarios</td></tr><tr><td><i>k</i></td><td>The Index of Agent</td></tr><tr><td><i>K</i></td><td>The Total Number of Agents</td></tr><tr><td><i>l</i></td><td>The Index of Side Constraint</td></tr><tr><td><i>L</i></td><td>The Total Number of Side Constraints</td></tr><tr><td><i>u</i><sub><i>ij</i></sub><sup><i>s</i></sup></td><td>The Capacity of link (<i>i</i>, <i>j</i>) in Scenario <i>s</i></td></tr><tr><td><i>t</i><sub><i>ij</i></sub><sup><i>ks</i></sup></td><td>The Travel Time of Agent <i>k</i> on link (<i>i</i>,<i>j</i>) in scenario <i>s</i></td></tr><tr><td><i>p</i><sub><i>s</i></sub></td><td>The Probability in Scenario <i>s</i></td></tr><tr><td><i>w</i><sub><i>ij</i></sub><sup><i>kl</i></sup></td><td>The <i>l</i>-th Resource Weight of Agent <i>k</i> on link (<i>i</i>,<i>j</i>)</td></tr><tr><td><i>w</i><sup><i>kl</i></sup></td><td>The Upper Limit of the <i>l</i>-th Resource for agent <i>k</i></td></tr></tbody></table>

## 2.3 Lagrangian Relaxation

The Lagrangian Relaxation model is used to overcome side constraint problems in the evacuation process. Lagrangian Relaxation is used to correct the gap between the lower bound and upper bound of the relaxation model. The lower bound will be applied to the objective value generated from the relaxation model and the upper bound will be used for the objective value generated from the original model.

The objective value of the original model can be calculated using eq. 4

$$ E(X, s) = \sum_{k=1}^{K} \sum_{(i,j) \in A} t_{ij}^{ks} \cdot x_{ij}^{ks}, s = 1, 2, \dots, S \quad (4) $$

The objective function used is the time-based objective function so that the maximum time for the entire scenario can be calculated using Eq. 5.

$$ E_{max}(X) = \max_{1 \le s \le S} E(X, s) \quad (5) $$
Since there are several applicable scenarios, the final objective value of the original model can be formulated using Eq. 6.

$$ \min Z = \sum_{s=1}^{S} \sum_{k=1}^{K} \sum_{(i,j) \in A} p_s \cdot t_{ij}^{ks} \cdot x_{ij}^{ks} \quad (6) $$

In the relaxation model there are some additional constraints that can be given that can be symbolized by α, β, γ so that the objective value of the relaxation model can be calculated using Eq. 7.

$$ \textbf{Relaxed Model :} \left\{ \begin{array}{l} \min \ R(\alpha, \beta, \gamma) \\ \text{s.t. Constraints (1)and (5)} \end{array} \right. $$

Where

$$ \left\{ \begin{array}{l} R(\alpha, \beta, \gamma) = \sum_{k=1}^{K} \sum_{s=1}^{S} \sum_{(i,j) \in A} p_s \cdot t_{ij}^{ks} \cdot x_{ij}^{ks} + \sum_{s=1}^{S} \sum_{(i,j) \in A} \alpha_{ij}^{s} \left( \sum_{k=1}^{K} x_{ij}^{ks} - u_{ij}^{s} \right) \\ \qquad + \sum_{k=1}^{K} \sum_{s=1}^{S} \sum_{l=1}^{L} \beta_{l}^{ks} \left( \sum_{(i,j) \in A} x_{ij}^{ks} \cdot w_{ij}^{kl} - w^{kl} \right) \quad (7) \\ \\ + \sum_{k=1}^{K} \sum_{(i,j) \in A} \left( \sum_{s=1}^{S-1} \gamma_{ij}^{ks} (x_{ij}^{ks} - x_{ij}^{k,s+1}) + \gamma_{ij}^{ks} (x_{ij}^{ks} - x_{ij}^{kl}) \right) \end{array} \right. $$

## 2.4 Relaxation-Based Algorithm

Relation-Based Algorithm was proposed by [1] and is the result of integration between Heuristic Algorithm with Lagrangian Relaxation. A small gap between the lower bound and the optimal objective value of the original model will result in a high quality solution. The stages of the Relaxation-Based Algorithm are as follows.

**Step 1: Initialization.** Let iteration number $\mu = 1$. Initialize the Lagrangian Multiplier Vectors $(\alpha, \beta, \gamma)$

**Step 2: Solve the relaxed model.**

**Step 2.1:** Compute the optimal solution $X$ of SP1 by the label-correcting algorithm; calculate the objective value of relaxed model, denoted by Lower Bound (LB).

**Step 2.2:** Evaluate whether the solution $X$ achieved by **Step 2.1** is feasible for the original model. If the solution is feasible, go to **Step 4**; otherwise go to **Step 3**.

**Step 3: Implement Adjustment Heuristic.** Execute the adjustment heuristic to deal with the infeasibility until a feasible solution $X'$ is obtained

**Step 4: Update relative gap.**

**Step 4.1:** Compute the objective value of the original model, which is denoted as the Upper Bound (UB).

**Step 4.2:** Compute the relative gap between the Upper and Lower Bounds, which is calculated by $RG=(UB-LB)/UB$
**Step 5: Update Lagrangian Multipliers.** Update Lagrangian Multipliers $\alpha_{ij}^s, \beta_l^{ks}, \gamma_{ij}^{ks}, \forall (i, j) \in A, s = 1, 2, \dots, S, k = 1, 2, \dots, K, l = 1, 2, \dots, L$ by using the sub-gradients below:

$$\nabla R_{\alpha_{ij}^s} = \sum_{k=1}^{K} x_{ij}^{ks} - u_{ij}^s$$

$$\nabla R_{\beta_l^{ks}} = \sum_{(i,j) \in A} x_{ij}^{ks} w_{ij}^{kl} - w^{kl}$$

$$\nabla R_{\gamma_{ij}^{ks}} = x_{ij}^{ks} - x_{ij}^{ks+1}, s = 1, 2, \dots, S-1$$

$$\nabla R_{\gamma_{ij}^{ks}} = x_{ij}^{ks} - x_{ij}^{kl}$$

**Step 6: Termination condition test.** If the relative gap RG is less than the predetermined value or $\mu > \mu_{max}$ (a predetermined maximum iteration number), stop; otherwise, let $\mu \leftarrow \mu + 1$, go to **Step 2**

## 2.5 Route Choice Model

Route Choice Model (RCM) proposed by [9] by incorporating an approach in choosing the route best adapted to the volume or capacity of a route. The RCM approach is based on the Available Evacuation Route Set (AERS). The basic idea is that when a scenario is selected for a criterion it must first be calculated the capacity of a route. The stages in the Route Choice Model process are as follows.

1. Take all possible routes on AERS.

2. Determine the parameters to consider in the AERS, including: radius between evacuees, mass M of evacuees, and velocity.

3. Select 5 (five) best route from AERS to make the route set (route set)

## 2.6 Integration between Relaxation Based Algorithm with Route Choice Model

The basic idea of integration of the Relaxation Based Model with the Route Choice Model is to select all available routes on AERS that meet the requirements and also include additional parameters used in the Route Choice Model as the new hard constraint for the Relaxation Based Algorithm.

# 3 Research Methodology

The stages of research conducted by researchers from this study can be seen as a whole in Fig. 2.

# 4 Result and Discussion

Researchers in this study used the Relaxation-Based Algorithm combined with the Route Choice Model to produce an evacuation model that minimizes evacuation time that can be applied to dynamic issues related to time-varying and volume-dependent
because some types of disaster will result in damage as time increases and the evacuation route is volume-dependent in order to adapt to changes in the number of people evacuated.

Our paper has not provided relevant terms such as strategy, measure, situation and the interconnections of these terms in the implementation of this model. The importance of this research for future studies is that the results indicate that the evacuation process much consider about distance and cost and can be applied in dynamic issues involving time-varying and volume-dependent

<figure><img src="image_3.png" /><figcaption>Fig. 2. Research Methodology</figcaption></figure>

**5 Conclusion**

The conclusion of this research are as follows. First, In the evacuation process, it is necessary to consider a number of side constraints such as distance and cost and also produce evacuation models that minimize evacuation time that can be applied to dynamic issues involving time-varying and volume-dependent. Second, it is confirmed that the resulting model using the Relaxation-Based Algorithm combined with the Route Choice Model have produced an evacuation model that can be applied to dynamic issues related to time-varying and volume-dependent because some types of disasters will result in damage as time increases and the evacuation path is volume -dependent so that it can adjust to changes in the number of people being evacuated.
References

1. Wang, L., Yang, L., Gao, Z., Li, S., and Zhou, X: Evacuation Planning for Disaster Responses: A Stochastic Programming Framework. Transportation Research Part C 69, 150-172 (2016).

2. Sheffi, Y., Mahmassani, H., Powell, W.B.: A transportation network evacuation model. Transp. Res. Part A: Policy Pract. 16 (3), 209–218 (1982).

3. Yamada, T.: A network approach to a city emergency evacuation planning. Int. J. Syst. Sci. 27 (10), 931–936 (1996).

4. Hamacher, H., Tjandra, S.: Mathematical modeling of evacuation problems: a state of art. Berichte des Frauenhofer ITWM, No. 24 (2001).

5. Cova, T.J., Johnson, J.P.: A network flow model for lane-based evacuation routing. Transp. Res. Part A: Policy Pract. 37 (7), 579–604 (2003).

6. Xie, C., Turnquist, M.A.: Lane-based evacuation network optimization: an integrated granngian relaxation and tabu search approach. Transp. Res. Part C: Emerg. Technol. 19 (1), 40–63 (2011)

7. Lu, Q., Huang, Y., Shekhar, S: Evacuation planning: a capacity constrained routing approach. In: Intelligence and Security Informatics. Springer, Berlin, Heidelberg, pp. 111–125 (2003)

8. Sbayti, H., Mahmassani, H.S.: Optimal scheduling of evacuation operations. Transp. Res. Rec.: J. Transp. Res. Board 1964 (1), 238–246 (2006).

9. Han, L.D., Yuan, F., Chin, S., Hwang, H.: Global optimization of emergency assignments. Interfaces 36 (6), 502–513 (2006).

10. Yazici, M.A., Ozbay, K.: Impact of probabilistic road capacity constraints on the spatial distribution of hurricane evacuation shelter capacities. Transp. Res. Rec.: J. Transp. Res. Board 2022, 55–62 (207)

11. Yazici, M.A., Ozbay, K., 2010. Evacuation network modeling via dynamic traffic assignment with probabilistic demand and capacity constraints. Transp. Res. Rec.: J. Transp. Res. Board 46 (2196), 11–20 (2010)

12. Miller-Hooks, E., Sorrel, G.: Maximal dynamic expected flows problem for emergency evacuation planning. Transp. Res. Rec.: J. Transp. Res. Board 44 (2089), 26–34 (2008)

13. Li, J., Ozbay, K.: Evacuation planning with endogenous transportation network degradations: a stochastic cell-based model and solution procedure. Networks Spatial Econ., 1–20 (2014)