# Multi-period Shelter Location-Allocation Problem with Network and Location Vulnerabilities for the Response Phase of Disaster Management

Sweety Hansuwa, Usha Mohan, Viswanath Kumar Ganesan

► To cite this version:

Sweety Hansuwa, Usha Mohan, Viswanath Kumar Ganesan. Multi-period Shelter Location-Allocation Problem with Network and Location Vulnerabilities for the Response Phase of Disaster Management. IFIP International Conference on Advances in Production Management Systems (APMS), Sep 2022, Gyeongju, South Korea. pp.510-517, 10.1007/978-3-031-16407-1_60. [https://doi.org/10.1007/978-3-031-16407-1_60](https://doi.org/10.1007/978-3-031-16407-1_60)

HAL Id: hal-05386136

https://inria.hal.science/hal-05386136v1

Submitted on 27 Nov 2025

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.
# Multi-period Shelter Location-Allocation Problem with Network and Location Vulnerabilities for the Response Phase of Disaster Management

Sweety Hansuwa<fnref n="1" />,<fnref n="2" />✉, Usha Mohan<fnref n="1" />, and Viswanath Kumar Ganesan<fnref n="2" />

**Abstract.** Natural disasters and man-made calamities are a significant threat in many geographical locations worldwide. The administrative mechanism must plan and ensure the safety as well-being of the humans and other living creatures (or other essential resources) by being prepared during the disaster. This work presents a multi-period shelter location and allocation model that determines when and where to open shelters on the planning horizon. In our work, we define location and network vulnerabilities to measure the impact of a disaster in each geography. We use these vulnerabilities to formulate a Mixed Integer Linear Programming Model (MILP) for the shelter location and allocation problem. We present an extended linear relaxation heuristic and solve the problem using the real-life case data obtained from the major flooding event in and around the Chennai Metropolitan Development Area.

**Keywords:** Multi-period allocation problem · Shelter location problem · MILP

## 1 Introduction

The beginning of the year 2022 witnessed around 67 natural disasters. According to the Emergency events database (EM-DAT) statistics, there were 9080 natural disasters from 2001 to 2022. Hence, it is essential for governments worldwide to plan relief operations and effectively manage these disasters in the best possible way. This paper examines two critical dimensions of the relief operations, i.e., shelter (or depot) location selection and allocation of people (or/and other essentials) to safe locations. In our study, we attempt to answer the following questions:

1. Can we design and develop mathematical formulations as multi-period models for real-life disaster relief operations?

2. Can we develop scalable solutions that can quickly solve larger practical instances and provide quality solutions?

<footnote n="1">¹ Department of Management Studies, Indian Institute of Technology, Madras, Chennai, India
sweetyhansuwaiitb@gmail.com</footnote>

<footnote n="2">² Tata Consultancy Services, IITM Research Park, Chennai, India</footnote>
The answers to the above questions are demonstrated in this work by formulating the problem as a MILP Model for the multi-period shelter location-allocation problem considering the impact of the disaster as network and location vulnerabilities with the objectives of minimizing unmet demand and the traveling cost. We consider the multiple periods to capture the real-life decision during a rolling horizon approach. That helps in the decision-making process in disaster management. We propose an extended linear relaxation heuristic (ELRH) to solve the problem on real-life case data obtained from the major flooding event in the latter part of 2015 in and around the Chennai Metropolitan Development Area.

## 2 Literature Review

The shelter location problem has been studied in the literature to provide safer places for evacuees, humanitarian relief operations, medical facilities, inventory management, etc. Shelters (or depots) during the disaster are typically selected among government schools, community halls, public places, etc., that are safe and less vulnerable to the impact of a disaster. Amideo et al. [1] present a review of disaster management using OR and evaluate the shelter location and evacuation routing problems in disaster response. Duhamel et al. [2] discuss the multi-period location-allocation model movement of the affected population assigned to a safer place during the response phase to maximize the assistance to the affected people. Vahdani et al. [7] discuss the multi-period location-routing model for relief distribution while considering the situation of roads after a disaster. Hansuwa et al. [3] formulate the shelter location-allocation problem considering the vulnerabilities of the demand locations and their network connectivities for disaster management's preparedness and response phase. They propose a linear relaxation heuristic (LRH) and compare the heuristic performance with the scenario-based formulation. In this paper, we further extend the work on the shelter location-allocation problem with multiple periods and consider location and network vulnerabilities for the response phase of a disaster. We present an extended LRH to solve the large-scale problems and demonstrate the performance of the heuristic using real-life data.

## 3 Multi-period Shelter Location-Allocation Problem

This section presents the problem description, assumptions, and the mixed-integer linear programming (MILP) formulation for the multi-period shelter location-allocation (MPSLA) problem for the response phase of disaster management, along with the descriptions of parameters.

### Indices

* *i* the index for affected locations

* *j* the index for shelter locations

* *k* the index for capacity levels of shelters

* *t* the index for time periods
Sets

$I$ the set of affected locations

$J$ the set of shelter locations

$K$ the set of capacity levels of shelter

$T$ the set of time period level of planning horizon

Parameters

$\gamma_i$ the penalty cost on unmet demand at location $i$

$c_{j,k}$ the capacity of a shelter $j$ at capacity $k$

$f'_{j,k}$ the fixed cost of opening a shelter $j$ at capacity $k$

$\theta_{i,j}$ the cost of travel/km between location $i$ to shelter $j$

$d_{i,j}$ the distance between location $i$ to shelter $j$ before disaster

$d'_{i,j}$ the distance between location $i$ to shelter $j$ after disaster

$\vartheta_i^t$ the vulnerability at location $i$ in the time period $t$, i.e. $\vartheta_i^t \in [0, 1]$

$b_i^t$ the number of affected people at location $i$ in the time period $t$

$V_{i,j}^t$ the network vulnerability between location $i$ to shelter $j$ in the time period $t$

$B$ the total budget

$M$ a big positive number

Shelter location-allocation (SLA) problems select a safer place for evacuees and assign them to the nearest location. Earlier studies to our understanding solve the SLA problem without considering multiple periods and vulnerabilities of the geographies. In this work, we attempt to address this research gap by considering multiple periods in the planning horizon and using both location and network vulnerabilities. The location or network vulnerabilities may not remain the same as during a disaster. The location vulnerability is defined at four levels for our study based on the Greater Chennai Corporation Report [4]. This work defines network vulnerability based on the definition presented by Gu et al. [5]. Gu et al. [5] discuss the topology-based efficiency indices (TEI) between two points $i$ and $j$ for a network by Eq. 1. We compute the network vulnerability ($V(i, j)$) among locations in terms of the topology-based efficiency indices as discussed in the following Eq. 2.

$$TEI = \frac{1}{|N| \cdot (|N| - 1)} \frac{\sum_{i \neq j \in N} \left( \frac{1}{d_{i,j}} - \frac{1}{d'_{i,j}} \right)}{\sum_{i \neq j \in N} \left( \frac{1}{d_{i,j}} \right)} \quad (1)$$

$$V(i, j) = \frac{1}{2} \frac{\sum_{i \neq j \in N} (d'_{i,j} - d_{i,j})}{\sum_{i \neq j \in N} (d'_{i,j})} \quad \forall i \in I, \forall j \in J \quad (2)$$

The following is the list of assumptions for our problem definition.

1. A set of susceptible locations and their respective vulnerabilities are available for each period before the start of the response phase of a disaster.

2. A set of shelters with location definitions and their available capacities (in terms of the number of people) with the associated one-time fixed cost of opening the shelters are known.
3. A set of connectivities between various locations and the shelter locations are known and the network vulnerabilities are computed using Eq. 2 for different periods.

4. The shelters are available and can be opened during all time periods. The closure of shelters is not considered in the scope of the model.

5. The number of people to be evacuated from each vulnerable inhabited location is known.

6. The total budget available to open and operate the shelters at various locations is pre-defined.

## 3.1 Multi-period Shelter Location-Allocation Formulation

This section presents the MPSLA formulation.

Decision variables

$x_{j,k}^t$ is equal to 1 if shelter j with capacity k in the time period t is open, 0 otherwise

$y_{i,j}^t$ is equal to 1 if location i is assigned to shelter j in the time period t, 0 otherwise

$z_{i,j}^t$ a fraction of demand at location i assigned to shelter j in the time period t

$w_i^t$ the unmet demand at location i in the time period t

$\beta_{i,j}^t$ the cost of travel between location i to shelter j in the time period t

The objective function present in the Eq. 3. The first term minimizes transportation costs that depend on the distance and the network's vulnerability between locations i and j in the planning horizon. The second term minimizes the total penalty cost on unmet demands while considering the vulnerability levels of the demand locations. The penalty cost is increased by $(1+\vartheta_i^t)$ with a level of vulnerability of the demand location. Thus, we define the objective function as:

$$ \text{minimize} \quad \sum_{t \in T} \sum_{i \in I} \sum_{j \in J} \beta_{i,j}^t + \sum_{t \in T} \sum_{i \in I} \gamma_i \times (1 + \vartheta_i^t) \times w_i^t \quad (3) $$

subject to the constraints presented in Eqs. 4 to 15.

Constraint 4 ensures only one capacity level is selected when a shelter is opened.

$$ \sum_{k \in K} x_{j,k}^t \le 1 \quad \forall j, \forall t \quad (4) $$

Constraint 5 ensures that once a shelter opens on the planning horizon, it should remain open for successive periods.

$$ \sum_{k \in K} x_{j,k}^t \ge \sum_{k \in K} x_{j,k}^{t-1} \quad \forall j, t = 2, \dots, |T| \quad (5) $$

Constraint 6 ensures the total cost of opening a shelter should be less than the entire budget available.

$$ \sum_{t \in T} \sum_{j \in J} \sum_{k \in K} f_{j,k} \times x_{j,k}^t \le B \quad (6) $$
Constraint 7 ensures each demand location should be allocated to exactly one shelter.

$$ \sum_{j \in J} y_{i,j}^{t} = 1 \quad \forall i, \forall t \qquad (7) $$

Constraint 8 ensures that the demand location's assignment to shelter only if it is open.

$$ y_{i,j}^{t} \leq \sum_{k \in K} x_{j,k}^{t} \quad \forall i, \forall j, \forall t \qquad (8) $$

Constraint 9 ensures that the demand of the number of people to evacuate should be satisfied.

$$ \sum_{j \in J} z_{i,j}^{t} + w_{i}^{t} = b_{i}^{t} + w_{i}^{t-1} \quad \forall i, \forall t \qquad (9) $$

Constraint 10 ensures the initial unmet demand is assumed to be zero.

$$ w_{i}^{0} = 0 \quad \forall i \qquad (10) $$

Constraint 11 ensures the allocation of demand to the shelter only if it is open.

$$ z_{i,j}^{t} \leq M \times y_{i,j}^{t} \quad \forall i, \forall j, \forall t \qquad (11) $$

Constraint 12 ensures the total evacuated people allocated to the shelter should be less than the shelter's total capacity.

$$ \sum_{i \in I} z_{i,j}^{t} \leq \sum_{k \in K} c_{j,k} \times x_{j,k}^{t} \quad \forall j, \forall t \qquad (12) $$

Constraint 13 computes the worst case scenario while computing the cost of transportation 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 by $(1+V_{i,j}^t)$.

$$ \beta_{i,j}^{t} \geq \theta_{i,j} \times d_{i,j} \times (1+V_{i,j}^{t}) - M \times (1-y_{i,j}^{t}) \quad \forall i, \forall j, \forall t \qquad (13) $$

$$ w_{i}^{t} \geq 0 \quad \beta_{i,j}^{t} \geq 0 \quad z_{i,j}^{t} \geq 0 \quad \forall i, \forall j, \forall t \qquad (14) $$

$$ x_{j,k}^{t} \in \{0, 1\} \quad y_{i,j}^{t} \in \{0, 1\} \quad \forall i, \forall j, \forall k, \forall t \qquad (15) $$

## 4 Extended Linear Relaxation Heuristic (ELRH)

The MPSLA formulation presented in the previous section is a NP-hard problem. Several well-known solution methods are available to solve large-scale MILP formulations. Relaxation methods, particularly linear programming relaxations of MILP, are popular methods for solving large-scale problems. This section presents a heuristic approach using linear programming relaxation for the MPSLA formulation to develop a usable
and feasible solution. The binary and specific integer variables in the MPSLA formulation are relaxed to linear variables. The proposed approach solves the MPSLA using a mathematical solver by relaxing the binary and specific integer variables in an iterative process. The variables $\bar{x}_{j,k}^t$, $\bar{y}_{i,j}^t$ are defined as linear variables in relaxed MPSLA formulation and solved as a linear programming problem. Subsequently the $\bar{x}_{j,k}^t$ values are rounded off to the nearest integer, either 1 or 0, when the values of $\bar{x}_{j,k}^t$ It is greater than or less than 0.5, respectively, by considering locations starting with lower fixed cost values for opening the shelter and selecting the locations with the next higher fixed costs. The preset values of shelter location selection variables are used as input to the original two-stage stochastic model by setting $\bar{x}_{j,k}^t = 1$, when the $\bar{x}_{j,k}^t > 0.5$ and otherwise, we set $\bar{x}_{j,k}^t = 0$. The solver is terminated when the optimality gap between the best MPSLA model bound and the objective function value falls below 10%. The pseudo-code present in Table 1.

<table><caption>**Table 1.** Extended linear relaxation heuristic</caption><thead><tr><th colspan="2">Extended linear relaxation heuristic</th></tr></thead><tbody><tr><td>Step 1</td><td>Solve the linear relaxation of the MPSLA model (define all binary decision variables as linear variables) and let the output be defined as a solution represented using (x&#773;<sub>j,k</sub><sup>t</sup>, y&#773;<sub>i,j</sub><sup>t</sup>)</td></tr><tr><td>Step 2</td><td>Define the x&#773;<sub>j,k</sub><sup>t</sup> values as 0 or 1 (x&#773;<sub>j,k</sub><sup>t</sup>, is greater than or less than 0.5 respectively) using the output from relaxed MPSLA formulation<br>Step 2.1 Sort all the shelter locations in ascending order of budgetary values for all x&#773;<sub>j,k</sub><sup>t</sup> &gt; 0.5<br>Step 2.2 Check the feasibility of constraint (6) by incrementally including each new shelter location from the above-sorted list, and the included shelter locations variables are set as 1<br>Step 2.3 The new representation of the set binary variables is defined as x&#773;<sub>j,k</sub><sup>t</sup> = 1 when x&#773;<sub>j,k</sub><sup>t</sup> &gt; 0.5 otherwise x&#773;<sub>j,k</sub><sup>t</sup> = 0</td></tr><tr><td>Step 3</td><td>The MPSLA formulation is solved again with the constraints 4–13, and the constraint (16) by using the predefined values of x&#773;<sub>j,k</sub><sup>t</sup> from Step 2.3<br>x<sub>j,k</sub><sup>t</sup> ≥ x&#773;<sub>j,k</sub><sup>t</sup> ∀i, ∀j, ∀k (16)</td></tr><tr><td>Step 4</td><td>Terminate the solver and print the solution when the optimality gap falls below less than 10%</td></tr></tbody></table>

## 5 Case Study: Chennai Flood 2015

The performance of the ELRH is evaluated using real-life instances obtained during the major flooding event in and around the Chennai Metropolitan Development Area in 2015. CPLEX OPL 12.8 has been used to solve the relaxation of the proposed MILP model in ELRH. The input parameters are population size in the inhabited locations, the vulnerability of locations, vulnerability between inhabited locations and the shelter locations, and the distance between them.
## 5.1 Data of Chennai Flood 2015

The data used in our experimental study is taken from Greater Chennai Corporation (GCC, 2018) [4]. The number of shelters opened was 176 during the 2015 floods in Chennai, and more than 1.2 lakhs of people were evacuated and accommodated in these shelters for more than 20 days (GCC, 2018 [4]). We have selected 172 shelters (and data were not available for four shelters) with defined capacities given in the source and 184 inhabited locations as demand locations representing inhabited areas for our study. The shelter capacities in terms of the number of people and the fixed cost are defined similarly for our use case as represented in *Cap. 61* instance of [6]. The data generation for our use cases is defined for a planning horizon of 2 days by considering the flood a natural disaster. The first 48 h (2 days) are crucial during a disaster. The parameter values for the model are taken from the data sets obtained during the Chennai floods of 2015. The demand values are assumed as given for the first day and are reduced by 20% for the second day. We assume that the impact of disaster is more on the initial day and decreases in the following days due to relief operations. We compute the distance based on the network sampling algorithm as discussed by [3].

## 5.2 Budgets

In our model, we have defined budgets that will capture a monetary value available with the administrative mechanism to effectively plan the deployment of resources during the response phase of a disaster. Hence we define the budgetary spend as a one-time opening cost in our data set. We have generated five scenarios for various budgetary values. We are taking the cost to open the first capacity level of shelter from the *Cap. 61* instance of [6]. We have assumed that the cost of opening a shelter doubles when the shelter is opened with twice the capacity. We have assumed the three levels of shelter capacities (*c*, 2*c*, 3*c*) where *c* indicates the capacity and is set a value as 7500. The budgetary levels varied in our experiments from the total cost of opening all the shelters to at least capacity considering 2 days in the planning horizon.

## 5.3 Computational Results

For our computational study, the number of demand locations(*I*), the number of shelter locations (*J*), and the number of periods (*T*) are 184, 172, and 2 days, respectively. We see that from our experiments in Table 2, the proposed ELRH uses minimal computational effort to get feasible solutions that do not substantially affect the budgetary limits defined for various use cases. The least budget limit is $ 1 million, and the demand satisfied for each level of location's vulnerability is less than 95% for each period. We observe that with the increase in the budget level to $ 3 million, the demand satisfied for across all levels of the location's vulnerability was found to be greater than 99.99%. As the budget levels increased, the demand satisfied was maximum, and the number of shelters used increased to meet the population's relocation needs. The impact of bringing down the budgetary values from $ 3 million to lower values do not significantly increase the computational time of the proposed algorithm except for the first case where the time limit is set to 2 hrs.
<table><caption>**Table 2.** Experimental results of ELRH</caption><thead><tr><th rowspan="2">Budget available (in million $)</th><th colspan="3">No of shelters open at varied capacity levels (t=1)</th><th colspan="3">No of shelters open at varied capacity levels (t=2)</th><th colspan="2">Demand satisfied (%)</th><th rowspan="2">Budget used (in million $)</th><th rowspan="2">Objective value</th><th rowspan="2">Computational time (s)</th></tr><tr><th>L</th><th>M</th><th>H</th><th>L</th><th>M</th><th>H</th><th>t=1</th><th>t=2</th></tr></thead><tbody><tr><td>1.0</td><td>8</td><td>21</td><td>4</td><td>7</td><td>20</td><td>5</td><td>99.99</td><td>100</td><td>0.9975</td><td>261827615.12</td><td>7200</td></tr><tr><td>1.5</td><td>18</td><td>22</td><td>9</td><td>18</td><td>18</td><td>12</td><td>100</td><td>100</td><td>1.5</td><td>6771413.36</td><td>663.0</td></tr><tr><td>2.0</td><td>27</td><td>30</td><td>12</td><td>23</td><td>28</td><td>13</td><td>100</td><td>100</td><td>1.995</td><td>4738844.35</td><td>282.45</td></tr><tr><td>2.5</td><td>36</td><td>45</td><td>11</td><td>25</td><td>41</td><td>14</td><td>100</td><td>100</td><td>2.4975</td><td>3865419.22</td><td>120.56</td></tr><tr><td>3.0</td><td>36</td><td>59</td><td>12</td><td>30</td><td>56</td><td>14</td><td>100</td><td>100</td><td>3.0</td><td>3480247.23</td><td>161.33</td></tr></tbody></table>

Lowest: L; Medium: M; High: H

## 6 Conclusion

This study presents a MILP model for the MPSLA problem, and a linear relaxation heuristic is proposed to solve the problem. The formulation and proposed heuristic have been solved using real-life case data obtained during the major flooding event in and around the Chennai Metropolitan Development Area in 2015. We can extend the current research by considering stochastic aspects of the MPSLA problem and exploring the use of metaheuristics and other solution approaches.

## References

1. Amideo, A.E., Scaparra, M.P., Kotiadis, K.: Optimising shelter location and evacuation routing operations: the critical issues. Eur. J. Oper. Res. **279**(2), 279–295 (2019)

2. Duhamel, C., Santos, A.C., Brasil, D., Châtelet, E., Birregah, B.: Connecting a population dynamic model with a multi-period location-allocation problem for post-disaster relief operations. Ann. Oper. Res. **247**(2), 693–713 (2016). https://doi.org/10.1007/s10479-015-2104-1

3. Hansuwa, S., Mohan, U., Ganesan, V.K.: Scenario-based stochastic shelter location-allocation problem with vulnerabilities for disaster relief network design. Eur. J. Ind. Eng. (2022). in press, Accepted Manuscript

4. Greater-Chennai-Corporation. Disaster management plan (2018). https://chennaicorporation.gov.in

5. Gu, Y., Fu, X., Liu, Z., Xu, X., Chen, A.: Performance of transportation network under perturbations: reliability, vulnerability, and resilience. Transp. Res. Part E: Logist. Transp. Rev. **133**, 1–16 (2020)

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

7. Vahdani, B., Veysmoradi, D., Shekari, N., Mousavi, S.M.: Multi-objective, multi-period location-routing model to distribute relief after earthquake by considering emergency roadway repair. Neural Comput. Appl. **30**(3), 835–854 (2016). https://doi.org/10.1007/s00521-016-2696-7