# Shelter Location-Allocation Problem with Vulnerabilities of Network and Disruption of Shelter During the Response Phase of Disaster

Sweety Hansuwa, Usha Mohan, Viswanath Kumar Ganesan

► To cite this version:

Sweety Hansuwa, Usha Mohan, Viswanath Kumar Ganesan. Shelter Location-Allocation Problem with Vulnerabilities of Network and Disruption of Shelter During the Response Phase of Disaster. IFIP International Conference on Advances in Production Management Systems (APMS), Sep 2021, Nantes, France. pp.705-713, 10.1007/978-3-030-85910-7_74 . hal-03806535

HAL Id: hal-03806535

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

Submitted on 7 Oct 2022

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
<figure><img src="image_2.png" /></figure>

ifip

International Federation for Information Processing

This document is the original author manuscript of a paper submitted to an IFIP
conference proceedings or other IFIP publication by Springer Nature. As such, there
may be some differences in the official published version of the paper. Such
differences, if any, are usually due to reformatting during preparation for publication or
minor corrections made by the author(s) during final proofreading of the publication
manuscript.
Shelter location-allocation problem with
vulnerabilities of network and disruption of shelter
during the response phase of disaster

Sweety Hansuwa¹,², Usha Mohan¹, Viswanath Kumar Ganesan²

¹ Dept of Management Studies, Indian Institute of Technology Madras, Chennai, India.

² Tata Consultancy Services, IITM Research Park, Chennai, India
sweety.hansuwa@tcs.com, ushamohan@iitm.ac.in,
viswanath.ganesan@tcs.com

**Abstract.** In this paper, we define and formulate the shelter location-allocation problem considering both the network vulnerability of the affected area and the shelter's disruption during the disaster management's response phase. We capture the vulnerability metric using the traveling cost and location vulnerability for shelter disruption using the shelter's operating cost. We formulate the problem as a mixed-integer linear programming (MILP) model and present an evacuation plan considering vulnerable network connectivities between the populated areas and the shelter locations. We finally apply and solve the problem using real-life case data obtained during the Nepal earthquake in 2015 and compare our models with Rahman's same data [10]. We demonstrate using the case example the usefulness of our modelling approach and show that we can achieve better results compared to a simulation study.

**Keywords:** shelter location-allocation, mixed-integer linear programming, earthquake.

# 1. Introduction

The year 2020 has witnessed more than 200 natural disasters [4]. The rise in the number of events is 27% in the first half of 2020 compared to 2019. Earthquakes are considered one of the worst natural disasters in the last 30 years. An example of a disaster is the 2004 earthquake and Tsunami and the Haiti earthquake that killed around 220,000 people and 159,000 people, respectively [3]. After a disaster strikes, many organizations need to respond to save peoples' lives and their needs in the affected areas. The selection of shelter locations is essential to relocate the people to a safer place as quickly as possible.

Operations research models have played an extensive role in all phases of disaster management. In particular, a class of models referred to as shelter-location-allocation models is instrumental in disaster management's planning and response stages. In the work, we attempt to answer the following questions:
1. Can we develop and use operation research models for real-life disaster relief and response requirements?

2. Can we improve the quality of the results from a mathematical model evaluating with practical data sets?

3. Is it feasible to build a decision model that can be relevant to practical needs as well as computationally fast?

The answers to the above questions are demonstrated in this work by formulating the problem as a MILP Model for the shelter location-allocation problem with the objectives of minimizing unmet demand, the travelling cost and the travel time. The problem of allocation of shelter locations (or relief centers) to relocate people (or important resources/materials) safely from vulnerable areas in a geography is presented in this work and real life case data has been used to validate the proposed model.

## 2. Literature

The literature has addressed the problem of the selection of candidate shelters using mathematical models. Allocation of evacuees to shelters has been studied using the *p*-median problem, the *p*-center model, and the maximal covering model using single objectives [5]. Alçada-Almeida et al.[1] proposed the multi-objective approach to solve the *p*-median model to select the number of shelters for the evacuation route plans in significant fire incidents. The objectives include minimizing the total distance, the people's risk to reach the shelters using the primary route, the shelters' risk, and the evacuation time from shelters to hospitals. Kilci et al. [7] discussed a mixed-integer model to locate temporary shelters and minimize the shelter area's minimum weight after the occurrence of an earthquake. Cavdur et al. [3] have discussed the temporary facilities' location problem under the demand's uncertainty and proposed the stochastic programming model in two-stage to decide the number of facility's need to open in the first decision, and service decisions next. They discuss the case study by taking up an earthquake event to test the model. Mostajabdaveh et al. [9] have addressed the shelter location for disaster preparedness that considers the efficiency and equity using the Gini index in the objective function. They proposed a mixed-integer programming formulation and a genetic algorithm to compare the performance of the proposed model. Rahman et al. [10] have discussed the post-disaster facility location problem and proposed the simulation approach and analysis between decisions and uncertainty. Yahyaei et al. [11] have discussed the robust relief network design under uncertainty and risk in the shelter and supply facility location. They have proposed the mathematical model and robust optimization programming model while considering the disruption of facility locations and network performance. In our research work, we discuss the shelter-location and allocation problem for the response phase. We consider the disruption of shelter location and the vulnerability of network connectivity. We also discuss the result analysis with real-life data on the Nepal earthquake 2015.

This paper's contribution introduces the vulnerability metric in the traveling cost and another metric for shelter's disruption and shelter's operating cost. The first metric
evaluates the network vulnerability that considers a network's susceptibility between locations and the shelters during response. The traveling cost computes based on distance, and the network vulnerability captures the actual condition among locations and evaluates the total travel cost between locations. The second metric discussed is the shelter's operating cost that considers shelter conditions after a disaster and computes the actual operating cost to open a shelter.

### 3. Problem description and assumptions

This section discusses the problem statement and assumptions for the shelter-location and allocation problem for a disaster response phase. Also, we present the mixed-integer linear programming model, along with the descriptions of parameters, variables, constraints, and objective function.

#### Sets and indexes

* *I* a set of affected locations that require evacuation

* *i* index for affected locations

* *J* a set of potential shelter locations

* *j* index for potential shelter locations

* *N* a set of nodes (*I* ∪ *J*)

* *L* a set of capacity level of shelter locations

#### Parameters

* *d*<sub>*i*</sub> number of affected people at location *i*

* *d*<sub>*i*,*j*</sub> distance between location *i* to shelter *j* before disaster

* *d*'<sub>*i*,*j*</sub> distance between location *i* to shelter *j* after a disaster

* *cap*<sub>*j*,*l*</sub> the capacity of a shelter *j* with capacity level *l*

* *f*<sub>*j*,*l*</sub> the operating cost of a shelter *j* with capacity level *l*

* *c*<sub>*i*,*j*</sub> the travel cost between location *i* to shelter *j* per kilometer

* *penalty*<sub>*i*</sub> the penalty cost on unmet demand at location *i*

* *v*<sub>*i*,*j*</sub> the vulnerability between location *i* to location *j*, i.e. *v*<sub>*i*,*j*</sub> ∈ [0,1]

* *r*<sub>*j*</sub> disruption level of shelter *j*, i.e. *r*<sub>*j*</sub> ∈ [0,1]

* *M* positive big number

The shelter location and allocation problem in the evacuation planning is defined and considering the network's vulnerability and shelter's disruption for the disaster response phase. Network vulnerability concepts are captured in our model as opening up shelter locations near the affected location is not feasible. The evacuation process becomes critical when a network is most susceptible to travel between two nearest locations, affecting travel costs. The actual shelter situation is known after the disaster strikes, and it may not be the same as considered during the planning stage. To operate
at the total capacity, consider the additional operational cost. We present the model and first discuss the definition of network vulnerability. Mattsson and Jenelius [8] have studied vulnerability based on topology-based and system-based metrics. Topology-based vulnerability indices discuss the transportation network in terms of connectivity and efficiency without considering its congestion. Gu et al. [6] discuss the topology-based efficiency indices (TEI) between two points i and j for a network by equation (1)

$$TEI = \frac{\sum_{i \neq j \in N(\frac{1}{d_{i,j}} - \frac{1}{d_{i,j}^t})} 1}{|N|(|N| - 1)} \frac{\sum_{i \neq j \in N d_{i,j}} 1}{\sum_{i \neq j \in N d_{i,j}} 1} \quad (1)$$

We compute the network vulnerability among locations in terms of the topology-based efficiency indices as discussed in equation (1). Hence, the network vulnerability $v(i,j)$ between location i to location j as defined in the following equation.

$$v(i, j) = \frac{\left(\frac{1}{d_{i,j}} - \frac{1}{d_{i,j}^t}\right)}{\frac{1}{d_{i,j}}} \quad \forall i \in I, j \in J \quad (2)$$

The list of assumptions considered for our problem definition is:

1. A set of shelters with location definitions and their available capacities (in terms of the number of people) with associated operating costs are known.

2. A set of connectivity between various locations and the shelter locations and their vulnerabilities are available and computed using equation (2).

3. The number of people to be evacuated from each affected location is known.

4. The disruption level of each shelter is known.

### Decision Variables

$x_{j,l}$ is a binary variable, and its value equal to 1 if a shelter j with the capacity level l is selected to open, 0 otherwise.

$y_{i,j}$ is a binary variable, and its value equal to 1 if affected location i is assigned to shelter j, 0 otherwise.

$z_{i,j}$ is an integer variable and represents the number of people evacuated from location i to shelter j.

$w_i$ is an integer variable and represents the unmet demand at location i.

$t_{i,j}$ is a continuous variable and represents the traveling cost between location i to location j.

## 3.1 Mixed-integer linear programming (MILP):

The first term of the objective function is to minimize the total cost of operating a shelter while considering the disruption level of shelter. The operating cost is increased by $(1 + r_j)$ with a level of shelter disruption. The second term is to minimize the total transportation cost that depends on the distance and the network's vulnerability between locations i and j. The third term is to minimize the total penalty cost on unmet demands.

$$\text{Minimize} \sum_{j \in J} \sum_{l \in L} f_{j,l} (1 + r_j) \times x_{j,l} + \sum_{i \in I} \sum_{j \in J} t_{i,j} + \sum_{i \in I} \text{penalty}_i \times w_i \quad (3)$$
subject to the constraints presented in equations (4) to (12)

Constraint (4) ensures only one type of capacity level to be selected when a shelter is opened.

$$ \sum_{l \in L} x_{j,l} \leq 1 \quad \forall j \quad (4) $$

Constraint (5) ensures that maximum p facilities are opened.

$$ \sum_{j \in J} \sum_{l \in L} x_{j,l} \leq p \quad (5) $$

Constraint (6) ensures each location should be allocated to exactly one shelter.

$$ \sum_{j \in J} y_{i,j} = 1 \quad \forall i \quad (6) $$

Constraint (7) ensures that location's assignment to shelter only if it is open.

$$ y_{i,j} \leq \sum_{l \in L} x_{j,l} \quad \forall i, \forall j \quad (7) $$

Constraint (8) ensures that the demand of the number of people to evacuate should be satisfied.

$$ \sum_{j \in J} z_{i,j} + w_i = d_i \quad \forall i \quad (8) $$

Constraint (9) allocation of demand to the shelter if location i is allocated to shelter j.

$$ z_{i,j} \leq M \times y_{i,j} \quad \forall i, \forall j \quad (9) $$

Constraint (10) the total evacuated people allocated to the shelter should be less than shelter capacity.

$$ \sum_{i \in I} z_{i,j} \leq \sum_{l \in L} c a p_{j,l} \times x_{j,l} \quad \forall j \quad (10) $$

Constraints (11)-(12) computes the transportation cost if location i is allocated to shelter j while considering the vulnerability of the network between location i to shelter j. The vulnerability of the network increases the additional cost of transportation cost by $(1 + v_{i,j})$.

$$ t_{i,j} \geq c_{i,j} \times d_{i,j} \times (1 + v_{i,j}) - M \times (1 - y_{i,j}) \quad \forall i, \forall j \quad (11) $$

$$ t_{i,j} \leq c_{i,j} \times d_{i,j} \times (1 + v_{i,j}) + M \times (1 - y_{i,j}) \quad \forall i, \forall j \quad (12) $$

## 4. Results and case study

This study uses the data discussed by Rahman et al.[10]. Rahman et al. [10] formulate the problem to minimize the unmet demand, uncovered demand points, and the maximum travel time. A simulation study has been performed using the post-disaster operational scenario on Nepal Earthquake in 2015 in their work. This study used data with 30 demand points/locations, 20 facilities as shelter locations (or facilities), and disruption factors for all nodes. The disruption factor is computed for each node based on the distance to the epicenter, and the range of factors is defined between 1 to 2. The distance between various locations before a disaster is computed using the open-source routing machine (OSRM-open street map) as data of latitude and longitude given by Rahman et al. [10]. The operating cost is the same across all shelters, and definitions are taken from the Cap_61 instance of Mostajabdaveh et al. [9]. The travel cost is considered among locations based on the data provided by Rahman et al. [10]. We consider the best estimate of transport cost of 10 USD per 1000 KG per hour. The
penalty cost for unmet demand is defined as equal to ten thousand times the operating cost of a shelter in our experimental results.

The MILP model has been implemented in OPL CPLEX 12.8, and the models have been executed using a computing processor with Intel Xeon 2.4 GHz (dual core) and 64 GB RAM. The solution obtained with the data as mentioned earlier using the MILP model is presented in Table 1 for different *p*-values. The *p*-values indicate the number of shelter locations chosen from the defined data sets on Nepal Earthquake data 2015. We observe that the objective function value decreases with increased *p*-values. The objective function value includes the transportation cost, shelter operating cost, and penalty cost. The results in Table 1 observe that the transportation cost has decreased and shelter operating cost increased with increased *p*-values. The objective function becomes constant at maximum *p*-values equal to 7 (chosen six locations of facilities in solution) and same with the transportation cost and shelter operating cost for Nepal Earthquake data 2015. We further discuss the MILP model solution for the maximum *p*-values equal to 10 in Table 2 for the increased demand of location from the nominal value. We consider the five levels (10%, 30%, 50%, 70%, 90%) for increased demands of locations and discuss the results in Table 2. We observe that the objective function values increased with the increased demands and the same with the transportation cost and shelter operating cost.

<table><caption>**Table 1.** Results obtained using MILP formulation with various number of shelter locations</caption><thead><tr><th>p-value</th><th>Objective function value</th><th>Transportation cost</th><th>Shelter operating cost</th><th>Facilities chosen</th></tr></thead><tbody><tr><td>3</td><td>231632.6</td><td>196895.2</td><td>34737.3</td><td>8, 10, 18</td></tr><tr><td>4</td><td>200548</td><td>155879.9</td><td>44668.03</td><td>8, 10, 12, 18</td></tr><tr><td>5</td><td>189974.2</td><td>132344.9</td><td>57629.34</td><td>8, 10, 12, 13, 18</td></tr><tr><td>6</td><td>187778.7</td><td>120273.8</td><td>67504.88</td><td>8, 9, 10, 13, 14, 18</td></tr></tbody></table>

<table><caption>**Table 2.** Results obtained using MILP formulation with *p* value = 10</caption><thead><tr><th># of facilities open</th><th>Demand increased (in %)</th><th>Objective function value</th><th>Transportation cost</th><th>Shelter operating cost</th><th>Facilities chosen</th></tr></thead><tbody><tr><td>6</td><td>10</td><td>199806.1</td><td>132301.2</td><td>67504.8</td><td>8, 9, 10, 13, 14, 18</td></tr><tr><td>6</td><td>30</td><td>223860.9</td><td>156356</td><td>67504.8</td><td>8, 9, 10, 13, 14, 18</td></tr><tr><td>7</td><td>50</td><td>247815.8</td><td>170380.2</td><td>77435.6</td><td>8, 9, 10, 12, 13, 14, 18</td></tr><tr><td>7</td><td>70</td><td>270533.2</td><td>193097.6</td><td>77435.6</td><td>8, 9, 10, 12, 13, 14, 18</td></tr><tr><td>7</td><td>90</td><td>293250.5</td><td>215814.9</td><td>77435.6</td><td>8, 9, 10, 12, 13, 14, 18</td></tr></tbody></table>

We compare the solution on the data sets considering the unmet demand, travel costs, and travel time as given in Rahman et al. [10] using the constraints defined in our MILP model. The data used for our experimentation for comparison of results consists of the
logistics requirements for transportation of relief materials post-disaster in Nepal. First, we compute the objective function values for the facilities chosen by Rahman et al. [10] and then compare them with the MILP model. Table 3 presents the comparison against results obtained using both models. We observe that the first objective function of the unmet demand solution has improved for the MILP model compared to Rahman et al. [10].

The second objective function, the travel/transportation cost solution of MILP, increases as compared to the objective function value of Rahman et al. [10]. Still, the unmet demand for Rahman et al. [10] solution is 7205910, which means that the solution is satisfied only 62.096% of the total demand. The MILP solution has met 99.90% of total demand. The third objective function, the travel time, is comparable to approximate near Rahman et al. [10], and the difference between the total travel of both models is 9.3%. The MILP model satisfied 99.69% of total demand, and Rahman et al. [10] met 98.60%. It is observed that the MILP formulation solved using CPLEX Solver provides significantly better values for the selection of facilities. Table 4 gives the disruption indices of the 20 locations, and we can see that the MILP model chooses the locations with low vulnerability.

<table><caption>**Table 3.** Compare the MILP with the same objective function of Rahman et al. [10]</caption><thead><tr><th>Objective function (p=4)</th><th>Objective values from (Rahman et al.)</th><th>Facility chosen (Rahman et al. 2019)</th><th>Objective values from MILP Model</th><th>Facility chosen</th></tr></thead><tbody><tr><td>Unmet Demand</td><td>115940.00</td><td>4, 8, 12, 13</td><td>50360.0</td><td>3, 8, 13, 16</td></tr><tr><td>Travel cost</td><td>87937.89</td><td>2, 4, 15, 17</td><td>245673.1</td><td>8, 10, 12, 18</td></tr><tr><td>Travel time</td><td>186978.00</td><td>4, 8, 13, 20</td><td>204423.3</td><td>8, 12, 13, 20</td></tr></tbody></table>

<table><caption>**Table 4.** Facility location's disruption (Rahman et al. [10])</caption><thead><tr><th>Facility</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th><th>9</th><th>10</th></tr></thead><tbody><tr><td>Disruption</td><td>0.9</td><td>0.49</td><td>0.19</td><td>0.46</td><td>0.88</td><td>0.39</td><td>0.10</td><td>0.35</td><td>0.21</td><td>0.8</td></tr><tr><td>Facility</td><td>11</td><td>12</td><td>13</td><td>14</td><td>15</td><td>16</td><td>17</td><td>18</td><td>19</td><td>20</td></tr><tr><td>Disruption</td><td>0.86</td><td>0.32</td><td>0.73</td><td>0.43</td><td>0.46</td><td>0.34</td><td>0.47</td><td>0.46</td><td>0.12</td><td>0.19</td></tr></tbody></table>

## 5. Conclusion

This paper presents a shelter location-allocation problem for the response phase to minimize operating cost, travel cost, and penalty cost on unmet demand. This paper introduces the vulnerability metric in the traveling cost and shelter's disruption metric for shelter's operating cost. We proposed a MILP model, and evaluate the results of the model using case data from Nepal earthquake occurred in 2015. We do evaluate the
performance of the proposed MILP model with the results of simulation study [10]
based on the post-disaster facility location decisions for the Nepal earthquake. Our
future research is exploratory, and the current study can be extended to study multi-
period dimensions thus leveraging the dynamic nature of the real-life requirements for
planning and deployment needs. There is a potential need to leverage heuristic
approaches to solve large instances and study the uncertainty parameters using robust
optimization.

References

1. Alçada-Almeida, L., Tralhão, L., Santos, L., Coutinho-Rodrigues, J.: A multi-objective approach to locate emergency shelters and identify evacuation routes in urban areas. Geographical Analysis 41(1), 9–29 (2009).

2. Cavdur, F., Kose-Kucuk, M., & Sebatli, A.: Allocation of temporary disaster response facilities under demand uncertainty: An earthquake case study. International Journal of Disaster Risk Reduction 19, 159–166.

3. Downearth organization:2020, https://www.downtoearth.org.in/news/natural-disasters/new-study-can-help-improve-earthquake-prediction-72275, last accessed on 01-04-2021.

4. Global Catastrophe Recap: First Half of 2020, AON Solutions, https://www.downtoearth.org.in/news/climate-change/more-than-200-natural-disasters-across-world-in-1st-half-of-2020-72445, last accessed on 30-03-2021.

5. Hakimi, S.L.: Optimum Locations of Switching Centers and the Absolute Centers and Medians of a Graph. Operations Research 12(3), 450–459 (1964).

6. Gu, Y., Fu, X., Liu, Z., Xu, X., Chen, A.: Performance of transportation network under perturbations: Reliability, vulnerability, and resilience. Transportation Research Part E: Logistics and Transportation Review 133, 1–16 (2020).

7. Kilci, F., Kara, B. Y., Bozkaya, B.: Locating temporary shelter areas after an earthquake: A case for Turkey. European Journal of Operational Research 243(1), 323–332 (2015).

8. Mattsson, L. G., Jenelius, E.: Vulnerability and resilience of transport systems - A discussion of recent research. Transportation Research Part A: Policy and Practice 81, 16–34 (2015).

9. Mostajabdaveh, M., Gutjahr, W. J., Sibel Salman, F.: Inequity-averse shelter location for disaster preparedness. IISE Transactions 51(8), 809–829 (2019).

10. Rahman, M. T., Majchrzak, T. A., Comes, T.: Deep uncertainty in humanitarian logistics operations: decision-making challenges in responding to large-scale natural disasters. International journal of emergency management 15(3), 276-297 (2019).

11. Yahyaei, M., Bozorgi-Amiri, A.: Robust reliable humanitarian relief network design: an integration of shelter and supply facility location. Annal of Operations Research 283, 897–916 (2019).