Keywords

1 Introduction

Natural disasters related to ground movements, such as landslides, can be complicated and unpredictable and, therefore, difficult to risk assess. Landslides can occur in almost every country and can cause significant damage. Also, climate changes may increase the risk: more heavy rain and melting of local permafrost in some mountain areas and variations in ice temperature and local water level can increase the risk of a landslide. Landslides are one of the most relevant geomorphological hazards in a country, because of the high levels of people affected, destruction of assets and disruption of economic and social activities.

Italy is one of the European countries most affected by landslides, with 620,808 landslides in an area of 23,700 km2, which is equal to 7.9% of the national territory (see Fig. 1). These data derive from the project of Inventario dei Fenomeni Franosi in Italy (IFFI Project) carried out by ISPRA (Superior Institute for Protection and Environmental Research) and the Regions and Autonomous Provinces, according to standardized and shared methods. About a third of the total landslides in Italy are rapid kinematic phenomena (collapses, rapid flows of mud and debris), characterized by high speeds, up to a few meters per second, and by high destructiveness, often with serious consequences in terms of loss of human lives. Other types of movements (e.g. slow flows, complex landslides), characterized by moderate or slow speeds, can cause significant damage to residential areas and linear communication infrastructures.

Fig. 1
figure 1

Italian hydrogeological danger distribution

Full size image

The hydrogeological instability essentially includes two categories of events: landslides and floods. To get an idea of the size of the problem, we remember that since the beginning of the century there have been more than 4000 serious hydrogeological instability events that have caused great damage to people, houses and infrastructures, but, above all, they caused about 12,600 dead, missing and injured people and the number of missing people exceeds 700 thousand.

Almost 4% of Italian buildings (over 550 thousand) are located in areas with high and very high landslide danger and more than 9% (over 1 million) in flood areas. So, it is very important to be prepared and to reduce the total time for evacuation of a building in the case of a landslide or any other disaster.

Our aim is to propose an evacuation planning model that optimally assigns the shortest and safest paths, in order to minimize the total evacuation time and save the lives of the occupants. In particular, we propose a multicriteria evacuation model where the population at risk is evacuated, following criteria such as the total travel time and the total delay. We also introduce a measure of the physical difficulties of evacuees and a parameter associated with the severity of the disaster. This allows our model to be flexible and able to handle large-scale problems. In addition, it allows for the applications to different disaster scenarios. The optimization model that we develop is then formulated as a variational inequality (see [10, 12]), and an analysis of associated Lagrange multipliers is provided (see [3,4,5, 15]).

The problem of evacuation plans has been deeply studied in the literature.

In [6], the authors apply network flow techniques to find good exit selections for evacuees in an emergency evacuation and present two algorithms for computing exit distributions using both classical flows and flows over time which are well known from combinatorial optimization.

In [8], the authors present models and algorithms which can be applied to evacuation problems related to building evacuation, but which are applicable also to regional evacuation. For all the models time is the main parameter.

In [9], the authors present two different emergency evacuation models on the basis of the maximum flow model (MFM) and the minimum-cost maximum flow model (MC-MFM), and propose corresponding algorithms for the evacuation from one source node to one designated destination (one-to-one evacuation). Then, they extend the model from one source node to many designated destinations (one-to-many evacuation).

In [11], the authors propose an evacuation model which combines a heuristic algorithm and a network flow control, taking into account routes capacity constraints. They aim at minimizing the total evacuation time for all people.

In [17], a game-theoretical model to study cooperative and competitive behaviors of evacuating people during an emergency is proposed. The authors integrate a game-theoretical model with a cellular automation model of evacuation dynamics, and simulate the motions of crowds based on their competitive and cooperative strategies.

In this paper, for the first time, starting from a network model, we use the variational inequality formulation to obtain a characterization of the optimization problem consisting in minimizing the total evacuation time and, as far as we know, this methodology is innovative compared to the existing ones.

Such a methodology and the related computational procedures have been widely applied to solve real-world problems, such as static and dynamic traffic network equilibrium problems, spatial price equilibrium problems, oligopolistic market equilibrium problems, financial equilibrium problems, migration equilibrium problems, as well as environmental network and ecology problems, supply chain network equilibrium problems, cybersecurity networks, and even the Internet (see, for instance, [1, 2, 7, 12, 13, 15, 16] and the references therein.)

We also emphasize that variational inequality theory has revealed to be a powerful instrument in order to study complex decision-making behavior on networks, with the associated nodes, links, and induced flows. Therefore, characterizing our problem as a variational inequality, we may have recourse to all the well-established tools of the variational inequality theory, and ensure existence of solutions, qualitative analysis, and computational results.

The structure of this paper is as follows. In Sect. 2, we present the evacuation model and derive the variational inequality formulation. In Sect. 3, we provide a numerical example. Finally, we present our conclusions in Sect. 4.

2 The Mathematical Model

We consider a network as the one depicted in Fig. 1, where there is a building with I different rooms which are connected with J different stairs. Since different rooms are likely to share a part of their path towards the stairs as well as the existence of multiple floors leads to divide the stairs into pieces between the floors so that different levels of congestion on each piece are taken into account, we are considering a graph with transit nodes between rooms and stairs (the meeting points) and between stairs and exits (the lobbies). In turn, from the stairs it is possible to reach H different exit points. Normally, people will choose the closest stairs or exits, but, in case one of such points is particularly crowded or congested or blocked due to the disaster, then the evacuees can also choose alternative exits. The links between the first and the second level of nodes in the network represent all the possible connections between the rooms of the building and the stairs, as well as the links between the second and the third level of nodes in the network represent all the possible connections between the stairs and the final exits of the building (Fig. 2).

Fig. 2
figure 2

Building network

Full size image

We denote by \(p_i^l\) the initial population in room A i, i = 1, …, I of type l, l = 1, …, L and by \(\displaystyle P = \sum _{l=1}^L \sum _{i=1}^n p_i^l\) the total population present in the building. Indeed, in our model we distinguish different types of individuals, in relation to their physical abilities. So, the apex l, l = 1, …, L represents the different types of evacuated people. Moreover, let \(f_{ij}^l\) and \(g_{jh}^l\) be the flows of evacuees of type l in a time unit from A i to S j and from S j to U h, for i = 1, …, I, j = 1, …, J, and h = 1, …, H, respectively. Since in a building the stairs are usually narrow spaces, we assume that u j is the maximum allowed capacity in S j, j = 1, …, J. So, the following condition has to be satisfied:

$$\displaystyle \begin{aligned} {\sum_{l=1}^L \sum_{i=1}^I \beta_{ij}^l f_{ij}^l \leq u_j, \quad \forall j=1, \ldots, J,}\end{aligned} $$
(1)

where \(\beta _{ij}^l\) indicates the portion of people of type l that decide to evacuate from room A i using the stair S j. Further, we denote by \(t_{ij}^l\) the travel time spent by a person of type l to go from A i to S j through one of the meeting points M r, r = 1, …, R and we assume it is a function of the flow of people from A i to S j:

$$\displaystyle \begin{aligned}t_{ij}^l = t_{ij}^l(f_{ij}^l), \quad i=1, \ldots, I, \,\, j=1, \ldots, J, \,\, l=1, \ldots, L.\end{aligned}$$

Analogously, we denote by \(\tau _{jh}^l\) the travel time spent by a person of type l to go from S j to U h through one of the lobbies L b, b = 1, …, B and we assume it is a function of the flow of people from S j to U h:

$$\displaystyle \begin{aligned}\tau_{jh}^l = \tau_{jh}^l(g_{jh}^l), \quad j=1, \ldots, J, \,\, h=1, \ldots, H, \,\, l=1, \ldots, L.\end{aligned}$$

Now, we introduce the delay functions which involve time, associated with the links from A i to S j and from S j to U h, respectively, and we assume they depend on the flows on the links, namely:

$$\displaystyle \begin{aligned} \begin{array}{rcl}R_{ij}^{1 {l}} = R_{ij}^{1 {l}}(f_{ij}^l) \mbox{ and } R_{jh}^{2 {l}} = R_{jh}^{2 {l}}(g_{jh}^l), \quad i=1, \ldots, I,\\ \,\, j=1, \ldots, J, \,\, h=1, \ldots, H, \,\, l=1, \ldots, L.\end{array} \end{aligned} $$

In addition, we consider two coefficients α l, σ ∈ [0, 1] representing the measure of the physical difficulties for an evacuee of type l and the severity of the disaster, respectively.

We group all the functions and parameters in Table 1.

Table 1 Functions and parameters
Full size table

The purpose of our model is to minimize the total evacuation time, denoted by ET(f, g), given by the sum of the total travel times and the total delay. Hence, we are interested in solving the following optimization problem:

$$\displaystyle \begin{aligned} \begin{array}{rcl}{} \min ET(f,g) & = &\displaystyle \min \left \{\sum_{l=1}^L \left[\sum_{i=1}^I\sum_{j=1}^J t_{ij}^l(f_{ij}^l) f_{ij}^l+\left (1+\alpha^l \right )\sum_{j=1}^J\sum_{h=1}^H \tau_{jh}^l(g_{jh}^l) g_{jh}^l \right. \right.\notag\\ & &\displaystyle \left. \left.+\sigma\sum_{i=1}^I\sum_{j=1}^J R_{ij}^{1l}(f_{ij}^l) f_{ij}^l+ \sigma \sum_{j=1}^J\sum_{h=1}^H R^{2l}_{jh}(g_{jh}^l) g_{jh}^l \right ]\right\} \end{array} \end{aligned} $$
(2)

under (1) and the following constraints:

$$\displaystyle \begin{aligned} {\sum_{l=1}^L} \sum_{i=1}^n f_{ij}^l \geq {\sum_{l=1}^L} \sum_{h=1}^k g_{jh}^l,\, \forall j=1,\ldots,J; \end{aligned} $$
(3)
$$\displaystyle \begin{aligned} {\sum_{j=1}^J f_{ij}^l \leq p_i^l, \quad \forall i, \, \forall l;} \end{aligned} $$
(4)
$$\displaystyle \begin{aligned} { \sum_{j=1}^J f_{ij}^l \geq .5 p_i^l, \quad \forall i, \, \forall l;} \end{aligned} $$
(5)
$$\displaystyle \begin{aligned} {\sum_{j=1}^J \sum_{h=1}^H g_{jh}^l \geq .5 p_i^l, \quad \forall l;} \end{aligned} $$
(6)
$$\displaystyle \begin{aligned} f_{ij}^l\geq 0, \quad \forall i, \, \forall j, \, \forall l; \quad g_{jh}^l\geq 0, \quad \forall j, \, \forall h, \, \forall l. \end{aligned} $$
(7)

Constraint (3) states that, for every index j, the sum of the flows of people from any room A i to S j exceeds the sum of the flows of people of all types l from S j to any exit U h. Constraint (4) establishes that people moving on all the links cannot exceed the total population on the building. With constraints (5) and (6) we guarantee that at least 50% of persons evacue from every room and from the building, respectively. Finally, constraints (7) are the nonengativity conditions of the flows.

Let us define the set of constraints as the feasible set \(\mathbb K\) given by:

$$\displaystyle \begin{aligned} \begin{array}{rcl} {} {\mathbb K} & = &\displaystyle \bigg \{ (f,g) \in {{\mathbb R}^{IJL + JHL}}: \, f_{ij}^l \geq 0, \,\, \forall i, \, \forall j, \, \forall l; \,\, g_{jh}^l \geq 0, \,\, \forall j, \, \forall h, \, \forall l; \\ & &\displaystyle {\sum_{l=1}^L} \sum_{i=1}^I \beta_{ij}^l f_{ij}^l - u_j \leq 0, \,\, \forall j; \,\, {\sum_{l=1}^L} \sum_{h=1}^k g_{jh}^l - {\sum_{l=1}^L} \sum_{i=1}^I f_{ij}^l \leq 0,\,\, \forall j; \\ & &\displaystyle \sum_{j=1}^J f_{ij}^l - p_i^l \leq 0,\,\, \forall i, \, {\forall l}; \,\, {.5 p_i^l - \sum_{j=1}^J f_{ij}^l\leq 0, \,\, \forall i, \, \forall l}; \,\, {.5 p_i^l - \sum_{j=1}^J\sum_{h=1}^H g_{jh}^l \leq 0, \,\, \forall l} \bigg \} \end{array} \end{aligned} $$

and assume that the travel time and delay functions multiplied by the respective flows are continuously differentiable and convex. Then, since the set \(\mathbb K\) is closed, bounded, and convex, applying the classical theory on the variational inequalities (see, for instance, [10] or [12]), problem can be characterized by means of the following variational inequality:

(8)

Now, taking into account the Lagrange multipliers associated with the constraints defining the feasible set \(\mathbb K,\) and using the same technique as in [1, 2, 13, 16], we obtain an important result.

We can consider the following Lagrange function:

where V (f, g) is the left-hand side of (8) and \(f \in {\mathbb R}^{IJL}\), \(g \in {\mathbb R}^{JHL},\)\(\gamma \in {\mathbb R}^{IJL}_+\), \(\delta \in {\mathbb R}^{JHL}_+\), \(\eta \in {\mathbb R}^J_+,\)\(\vartheta \in {\mathbb R}^J_+,\)\({\lambda \in {\mathbb R}^{IL}_+,}\)\(\mu \in {\mathbb R}^{IL}_+,\)\(\nu \in {\mathbb R}^L_+.\)

Then, the following result holds true.

Theorem 1

If\((f^*, g^*) \in {\mathbb K}\)is a solution to variational inequality (8), then the Lagrange multipliers\(\bar \gamma \in {\mathbb R}^{IJL}_+\), \(\bar \delta \in {\mathbb R}^{JHL}_+\), \(\bar \eta \in {\mathbb R}^J_+,\)\(\bar \vartheta \in {\mathbb R}^J_+,\)\(\bar \lambda \in {\mathbb R}^{IL}_+,\)\(\bar \mu \in {\mathbb R}^{IL}_+,\)and\(\bar \nu \in {\mathbb R}^L_+\)do exist, and for all i, j, h, and l, the following conditions hold true:

Moreover, the strong duality also holds true; namely:

$$\displaystyle \begin{aligned}{V(f^*, g^*) = \min_{\mathbb K} V(f,g) = \max_{(\gamma, \delta, \eta, \vartheta, \lambda, \mu, \nu) } \quad \inf_{(f,g)} {\mathscr L} (f, g, \gamma, \delta, \eta, \vartheta, \lambda, \mu, \nu). }\end{aligned}$$

3 Numerical Illustration

In order to validate our model, we now provide a small numerical example.

We consider a public building with a street-level floor and two floors above. We assume that 100 persons are located in the second floor of the building and are distributed in three different rooms. A landslide impacts the area of the building, so that people have to evacuate, choosing one of the two existing stairs that leads to three possible exits. We also suppose that there are two types of people, according to their physical difficulties. The parameter values are:

$$\displaystyle \begin{aligned} \begin{array}{rcl} & &\displaystyle (p_i^1)_{i=1,\ldots,3}=(10,20,20),(p_i^2)_{i=1,\ldots,3}=(15,15,20),\\& &\displaystyle \alpha_1=0, \,\alpha_2=0.3, \, \sigma=0.5,\,u_1=15,\,u_2=15,\, \beta_{ij}^l=0.35,\, \forall i,j,l. \end{array} \end{aligned} $$

The total travel time and the delay functions are reported in Tables 2 and 3.

Table 2 Travel times and delay functions for occupants of type 1
Full size table
Table 3 Travel times and delay functions for occupants of type 2
Full size table

We solved the resulting variational inequality applying the extragradient method with constant step length as in [14] (see also [7]), implemented as M-script files of MatLab. We note that our problem satisfies the assumptions needed to ensure the existence of solutions as well as the convergence of the algorithm.

In Fig. 3, we represent the network topology of the building on the left, and the optimal path distribution on the right. The optimal evacuation flows are given in Table 4. The total evacuation time, namely the value of the objective function ET(f ∗, g ∗) (see objective function (2)) is 8.3833 h. This value takes into account that displacements and ground movements, due to the landslide, may cause structural damages to the building (extensive cracks, distorsions in pillars and columns, tilting of floors and walls, obstructed doors, etc.). This makes the evacuation time increase. Finally, we note that all the people in the building are able to evacuate.

Fig. 3
figure 3

Network topology and evacuation paths of the example

Full size image
Table 4 Optimal flows on the paths used for evacuation
Full size table

4 Conclusions

In this paper, we introduced an evacuation planning model that identifies the optimal flows of people who must be evacuated from a building after a landslide. The multicriteria objective of the problem was to minimize both the total travel time and the total delay, which were influenced by the physical difficulties of evacuees and the severity of the disaster. We then proposed a variational inequality formulation of the model and provided its dual problem. In addition, we showed an alternative formulation based on the Lagrange multipliers associated with the constraints. They may have a crucial role in order to capture and predict the variation in the escape speed. Finally, we provided a numerical example that emphasized how the model developed in this paper can be used by policy-makers to plan emergency evacuation after a natural disaster.

Future research may include extending this framework to assess sinergies among individuals who could act as a group/coalition.

The results in this paper add to the growing literature of operations research for management of evacuation plans.