# Optimization Model Based on Reachability Guarantee for Emergency Facility Location and Link Reinforcement

Authors: Wuyang Yu; Jijun Liu
Journal: Journal of Advanced Transportation
 (2020)

---

## Abstract

The reasonable location of emergency facilities plays an important role in both predisaster service and postdisaster relief. Moreover, damage to the transportation network often affects the accessibility of demand points, which can seriously hamper timely rescue operations. Reasonable location of emergency facilities and reinforcement of fragile roads are two important strategies to improve the reachability of demand points. In this paper, we proposed a biobjective optimization model to determine locations of emergency facilities and links to be reinforced given a limited budget. Each demand point is allocated a primary facility and a backup facility, the former can provides normal service, and the latter is prepared for postdisaster relief. One goal of the model is to minimize the operating cost of normal services, and another goal is to maximize the reachability guarantee of demand points. The novelty and contribution of this paper are that we defined the reachability by introducing damage tolerance instead of link failure probability. Based on this, we defined the reachability guarantee to deal with the worst scenario of disasters. By embedding the max-flow problem of the reachability guarantee into the emergency facility location problem, the locations of emergency facilities and links to be reinforced can be determined simultaneously. The methodology is applied to a simplified Sioux Falls transportation network. Results such as the trade-off curve of two goals, budget efficiency, and the effect of reinforcement demonstrated the effectiveness of the model.


---

## Body

## 1. Introduction

According to the statistics of the International Disaster Database, the average number of recorded natural disasters event per annum of the nearly 10 years is about 333, almost twice as many as in the 1980s [1]. The sharp increase in natural disasters has highlighted the importance of disaster mitigation and preparedness [2], as the target of mitigation is to reduce the vulnerability of the affected regions, and the aim of preparedness is to facilitate emergency response and relief by using available resources.The reasonable location of emergency facilities plays an important role in both predisaster service and postdisaster response. Suitable prepositioned emergency facilities can help the government to launch rescue efforts as quickly as possible during the response stage [3]. Moreover, damage to the transportation network often affects the accessibility of demand points, which can seriously hamper timely rescue operations [4]. For example, a total of 24 highways were affected by the Wenchuan Earthquake in 2018, and 161 national and provincial arterial highways, 8618 rural roads, 6140 bridges, and 156 tunnels were damaged; these interrupted roads made rescue efforts extremely difficult [5]. Since the strategy to reinforce fragile roads is very useful to improve the accessibility of demand points after a disaster, an important problem in the preparation stage is how to determine the locations of emergency facilities and links to be reinforced given a limited budget?Due to the high degree of uncertainty in the location and severity of natural disasters, in most cases, the failure of the affected transportation network is unpredictable. Therefore, almost all current studies that related to the abovementioned problem involve randomness or uncertainty. Most of these studies are based on similar assumptions that network links have homogeneous or heterogeneous failure probabilities. This kind of assumptions implies that the interruption of the link is caused by its own failure, but it is actually caused by the damage that the link sustains beyond its tolerance. Therefore, the interruption of a link is the result of a specific disaster on this link. To deal with the uncertainty in the interruption of a link from this perspective is the motivation of this article. In this paper, we proposed a biobjective optimization model to determine locations of emergency facilities and links to be reinforced given a limited budget. Each demand point is allocated a primary facility and a backup facility, and the former can provide normal service and the latter is prepared for postdisaster relief. One goal of the model is to minimize the operating cost of normal services, and another goal is to maximize the reachability guarantee of demand points.The remainder of this paper is organized as follows. In Section2, we review the relevant literature on facility location problem with uncertainty. In Section 3, we define some notions such as reachability, reachability guarantee, and operating cost. In Section 4, we propose a biobjective model to determine locations of emergency facilities and links to be reinforced given a limited budget. In Section 5, we apply our model to a simplified Sioux Falls transportation network. Finally, we conclude the paper in Section 6.


## 2. Literature Review

Over the last two decades, abundant research works have been published on the location problems of emergency facilities [2, 6]. The potential for failure of emergency facilities and network links are two important types of uncertainty, and these are the two topics closely related to our article. This section categorizes the literature according to these two topics together with the Q-coverage location problem.


### 2.1. Facility Failure Uncertainty

Plenty of literature studied the facility location problem under the assumption of disruptions occur at facilities, the reliable facility location problem. Drezner’s research [7] may be the first study on the reliable facility location problem, where the p-median and p-center problems are studied by considering the possibility of failure of one or more facilities. Under the assumption that different facilities have an identical failure probability, Snyder and Daskin [8] presented stochastic location models to locate these unreliable facilities. Berman et al. [9] further studied the reliable facility location problem on the network and presented an efficient heuristic algorithm. Their study reveals that the optimal location of facilities is closely related to the failure probability of the facilities. Cui et al. [10] proposed discrete and continuous reliable facility location models by relaxing the assumption of identical failure probability. Lu and Sheu [11] proposed a robust vertex p-center model to locate urgent relief distribution centers. In their paper, fixed intervals instead of probability distributions are used to represent uncertain travel times. Albareda-Sambola et al. [12] introduced the facility capacity into a reliable facility location problem with unsplittable demands. Yahyaei and Bozorgi-Amiri [13] studied the reliable network design problem for humanitarian relief, and they proposed a robust linear programming model to deal with the uncertainty in this problem. Afify et al. [14] proposed an evolutionary learning technique to solve the reliable p-median problem and the reliable uncapacitated facility location problem under the assumption that facilities have heterogeneous failure probabilities.Regardless of whether the failure probabilities of the facilities are the same or not, the abovementioned studies held the assumption on independent facility disruptions, which may not always be realistic. Therefore, some studies have been made to address correlated facility disruptions. For example, Li et al. [15] proposed a virtual station model for a reliable facility location problem where facilities are positively correlated. Gueye and Menezes [16] proposed a two-stage stochastic model for a median facility location problem under correlated facility disruptions. They presented some asymptotic results using a scenario-based method. Xie et al. [17] proposed a methodological framework for decomposing general correlated facility disruptions. Any type of correlation can be transformed into an augmented network problem by this methodology. To balance the reliability and the cost-efficiency of the system, Xie et al. [18] further developed a mixed-integer optimization model for reliable location-allocation problem based on their framework.


### 2.2. Link Failure Uncertainty

The literature on reliable facility location problems only considers the failure possibility of facilities, but this is not enough in reality. Failures occur on network links often make facilities/demand points unreachable or significantly reduce system efficiency, which is unacceptable for time-critical postdisaster relief efforts in the postdisaster response stage. Under the assumption that disruptions occur on the network links, the literature usually focuses on developing measures to assess network vulnerability/robustness/resilience but few on facility location problems. For example, to organize the last mile delivery tasks after an earthquake, Ahmadi et al. [19] proposed a multidepot location-routing model to determine the locations of local depots by considering the possibility of road destruction. Salman and Yücel [20] formulated a stochastic model for emergency response facilities location problems. The spatial impact of disasters on the failure of network links is considered in the model, and the uncertainty of the demand network links is dealt with a scenario-based approach. A tabu search algorithm is proposed to determine the location of the emergency response facilities for earthquake disaster preparation in Istanbul. Hassin et al. [21] studied the facility location problem by considering a special type of failure correction that occurs on network links. They presented a link dependency model to determine the failure situation of network links. Poudel et al. [22] presented a predisaster planning model to determine the location of the emergency facilities. The goal is to optimize the connectivity and cost in the postdisaster response stage, where the failure probabilities of the links are estimated by a spatial statistic model. Yücel et al. [23] first proposed a dependency model for random link failures after a disaster. Then, they established a two-stage stochastic framework to measure and decide the set of links that should be strengthened.


### 2.3.Q-Coverage Location Models

When the primary facility is unable to service the point of demand due to failure or other reasons, a common approach is to use available backup facilities to meet the demand. The concept of backup coverage location problem was first introduced by Hogan and ReVelle [24]. Then, this concept was developed into Q-coverage location models, which allow the demand to be covered by multiple facilities.Karatas et al. [25] considered the p-median location model and the maximal coverage location model to compare the performance of five decision criteria under Q-coverage requirements. Farahani et al. [26] defined the backup service as a situation where facilities other than the primary one can be use to serve a demand when needed. Soltani-Sobh et al. [27] presented a facility location model to determine recovery centers by considering the failure possibilities of network links and facilities. The primary and backup recovery centers are determined based on the reliable path instead of the shortest path. Gábrisová and Jezek [28] developed a capacitated p-median location model to determine the location of medical system services by using a backup coverage strategy. The aim of the model is to seek a fair workload distribution scheme among ambulances. Kordjazi and Kazemi [29] applied the interval full-ranking method to the maximal location problem under Q-coverage requirement to address the availability, certainty, and efficiency of the problem simultaneously. Zhen et al. [30] studied how ex-ante business interruption insurance can affect ex-post transportation recovery and compared business interruption insurance and backup transportation together with two other strategies. To assure the effectiveness and efficiency of the emergency medical service (EMS), Mohamadi and Yaghoubi [31] developed a biobjective stochastic optimization model to locate transfer points and medical supplies distribution centers (MSDCs). Backup MSDCs are utilized in the model to reduce the impact of the failure of MSDCs. Rahmani et al. [32] proposed a reliable and robust humanitarian relief supply chain model that can identify backup suppliers for affected population centers to improve the reliability of the model. Karatas and Yakici [33] investigated the effects of backup service level and demand assignment policy and other issues on the solution performance of the classic p-median location model.


## 2.1. Facility Failure Uncertainty

Plenty of literature studied the facility location problem under the assumption of disruptions occur at facilities, the reliable facility location problem. Drezner’s research [7] may be the first study on the reliable facility location problem, where the p-median and p-center problems are studied by considering the possibility of failure of one or more facilities. Under the assumption that different facilities have an identical failure probability, Snyder and Daskin [8] presented stochastic location models to locate these unreliable facilities. Berman et al. [9] further studied the reliable facility location problem on the network and presented an efficient heuristic algorithm. Their study reveals that the optimal location of facilities is closely related to the failure probability of the facilities. Cui et al. [10] proposed discrete and continuous reliable facility location models by relaxing the assumption of identical failure probability. Lu and Sheu [11] proposed a robust vertex p-center model to locate urgent relief distribution centers. In their paper, fixed intervals instead of probability distributions are used to represent uncertain travel times. Albareda-Sambola et al. [12] introduced the facility capacity into a reliable facility location problem with unsplittable demands. Yahyaei and Bozorgi-Amiri [13] studied the reliable network design problem for humanitarian relief, and they proposed a robust linear programming model to deal with the uncertainty in this problem. Afify et al. [14] proposed an evolutionary learning technique to solve the reliable p-median problem and the reliable uncapacitated facility location problem under the assumption that facilities have heterogeneous failure probabilities.Regardless of whether the failure probabilities of the facilities are the same or not, the abovementioned studies held the assumption on independent facility disruptions, which may not always be realistic. Therefore, some studies have been made to address correlated facility disruptions. For example, Li et al. [15] proposed a virtual station model for a reliable facility location problem where facilities are positively correlated. Gueye and Menezes [16] proposed a two-stage stochastic model for a median facility location problem under correlated facility disruptions. They presented some asymptotic results using a scenario-based method. Xie et al. [17] proposed a methodological framework for decomposing general correlated facility disruptions. Any type of correlation can be transformed into an augmented network problem by this methodology. To balance the reliability and the cost-efficiency of the system, Xie et al. [18] further developed a mixed-integer optimization model for reliable location-allocation problem based on their framework.


## 2.2. Link Failure Uncertainty

The literature on reliable facility location problems only considers the failure possibility of facilities, but this is not enough in reality. Failures occur on network links often make facilities/demand points unreachable or significantly reduce system efficiency, which is unacceptable for time-critical postdisaster relief efforts in the postdisaster response stage. Under the assumption that disruptions occur on the network links, the literature usually focuses on developing measures to assess network vulnerability/robustness/resilience but few on facility location problems. For example, to organize the last mile delivery tasks after an earthquake, Ahmadi et al. [19] proposed a multidepot location-routing model to determine the locations of local depots by considering the possibility of road destruction. Salman and Yücel [20] formulated a stochastic model for emergency response facilities location problems. The spatial impact of disasters on the failure of network links is considered in the model, and the uncertainty of the demand network links is dealt with a scenario-based approach. A tabu search algorithm is proposed to determine the location of the emergency response facilities for earthquake disaster preparation in Istanbul. Hassin et al. [21] studied the facility location problem by considering a special type of failure correction that occurs on network links. They presented a link dependency model to determine the failure situation of network links. Poudel et al. [22] presented a predisaster planning model to determine the location of the emergency facilities. The goal is to optimize the connectivity and cost in the postdisaster response stage, where the failure probabilities of the links are estimated by a spatial statistic model. Yücel et al. [23] first proposed a dependency model for random link failures after a disaster. Then, they established a two-stage stochastic framework to measure and decide the set of links that should be strengthened.


## 2.3.Q-Coverage Location Models

When the primary facility is unable to service the point of demand due to failure or other reasons, a common approach is to use available backup facilities to meet the demand. The concept of backup coverage location problem was first introduced by Hogan and ReVelle [24]. Then, this concept was developed into Q-coverage location models, which allow the demand to be covered by multiple facilities.Karatas et al. [25] considered the p-median location model and the maximal coverage location model to compare the performance of five decision criteria under Q-coverage requirements. Farahani et al. [26] defined the backup service as a situation where facilities other than the primary one can be use to serve a demand when needed. Soltani-Sobh et al. [27] presented a facility location model to determine recovery centers by considering the failure possibilities of network links and facilities. The primary and backup recovery centers are determined based on the reliable path instead of the shortest path. Gábrisová and Jezek [28] developed a capacitated p-median location model to determine the location of medical system services by using a backup coverage strategy. The aim of the model is to seek a fair workload distribution scheme among ambulances. Kordjazi and Kazemi [29] applied the interval full-ranking method to the maximal location problem under Q-coverage requirement to address the availability, certainty, and efficiency of the problem simultaneously. Zhen et al. [30] studied how ex-ante business interruption insurance can affect ex-post transportation recovery and compared business interruption insurance and backup transportation together with two other strategies. To assure the effectiveness and efficiency of the emergency medical service (EMS), Mohamadi and Yaghoubi [31] developed a biobjective stochastic optimization model to locate transfer points and medical supplies distribution centers (MSDCs). Backup MSDCs are utilized in the model to reduce the impact of the failure of MSDCs. Rahmani et al. [32] proposed a reliable and robust humanitarian relief supply chain model that can identify backup suppliers for affected population centers to improve the reliability of the model. Karatas and Yakici [33] investigated the effects of backup service level and demand assignment policy and other issues on the solution performance of the classic p-median location model.


## 3. Methodology

The problem is defined on an undirected input graphG(N, A), consisting of the node set N and the edge set A. The set of demand points and potential locations of emergency facilities are all subsets of N.


### 3.1. Reachability Guarantee

Assume that each undirected linka ∈ A has a damage tolerance ra ∈ [0, 1], which represents the maximum degree of disaster damage it can withstand. The road a will only be interrupted if the damage to the road by the disaster exceeds ra. The value of ra can be estimated by experts based on the actual situation of the road. The larger the ra, the stronger the link a can resist damage. The damage tolerance of the link can be extended to the damage tolerance of the path as follows: given the damage tolerance ra for all links in a path p, the damage tolerance of the path p (denoted as r|p) is rp≔mina∈pra. From the definition of the damage tolerance of the path, when the most fragile link in path p is damaged more than r∣p, the path p will be broken. This is actually the worst scenario when considering the same level of damage on different links of this path.In graph theory, pointj is reachable from point i if there exists a path from i to j and there are no broken links in this path. Because the impact of most disasters on network links is highly uncertain, it makes sense to consider the reachability based on the damage tolerance of the path. The concept of reachability guarantee between nodes i and j was first introduced by Yu [34]. It can be defined as the minimum cut separating i and j as follows:(1)Ri,j≔mini∈S,t∈N\S∑a∈AS,N\Sra,where S is any subset of node set N that can separate i and j. Figure 1 shows a simple example, the number near the link indicates the damage tolerance of link. There are two subsets S1 = {1} and S2 = {1, 2} which can separate nodes 1 and 3. Therefore, the reachability guarantee between nodes 1 to 3 is R1,3 = min{0.2 + 0.4, 0.2 + 0.3} = 0.5.Figure 1
Example of the reachability guarantee.The reachability guarantee between pointsi and j reflects the ability of all paths that connect these two points to resist disaster damage. In other words, when the total damage on the network links is less than Ri,j, at least one path between i and j will not be interrupted. Therefore, this value can be viewed as a guarantee of reachability between points i and j. For the example in Figure 1, if the total damage on links is less than 0.5, regardless of the level of damage on different links, there is at least one path between points 1 and 3 that will not be interrupted. That is, points 1 and 3 are reachable to each other.Suppose that the set of demand points isJ. For each demand point j ∈ J, the facility i(j) is allocated to j, then the reachability guarantee of J can be defined as follows:(2)RJ≔∑j∈JRij,j.Note that a facility can be allocated to multiple demand points, but a demand point can only served by one facility. Obviously, we can determine the facilityi(j) of j from the perspective of the reachability guarantee to prepare for postdisaster relief efforts. Therefore, the facility i(j) can be regarded as the backup facility of the demand point j.


### 3.2. Operating Cost

Under normal circumstances, the links of the transportation network will not be damaged, so the operating cost should be considered. In these cases, the service relationship between emergency facilities and demand points is usually established according to the shortest path. Therefore, the shortest distance between a demand point and its corresponding facility can be used to represent the operating cost.Denote the shortest distance between the potential location of facilityi and the demand point j as dij, the facility that is allocated to the demand point j as i(j). Then, the shortest distance between points j and i(j) is dij,j. From the perspective of the demand point set J, the total shortest distance can be defined as follows:(3)DJ≔∑j∈Jdij,j.Obviously, we can determine the facilityi(j) of j from the perspective of the operating cost for normal circumstances. Therefore, the facility i(j) can be regarded as the primary facility of the demand point j.


### 3.3. Reinforce Link

In general, some reinforcements can be taken to increase the value of the damage tolerancera of the link a ∈ A. Suppose that for each link a ∈ A, the damage tolerance ra can be increased by Δa through reinforcement, that is, the damage tolerance after reinforcement becomes ra + Δa. Obviously, reinforcing measures can improve the reachability guarantee between the demand point and its backup facility. To ensure the maximum degree of reachability guarantee, we need to determine links to be reinforced given a limited budget. For example, in Figure 2, to maximize the reachability guarantee between points 1 and 3, if only one link can be reinforced due to the limited budget, which link should be selected? Let R1,3i−j denote the reachability guarantee between points 1 and 3 after reinforce link (i − j), then after simple calculation, we can get R1,31−2=min0.2+0.6,0.2+0.3=0.5, R1,31−3=min0.6+0.4,0.6+0.3=0.9, RG1,32−3=min0.2+0.4,0.2+0.6=0.6, so the suitable link is (1–3) in this case.Figure 2
Example of reinforce link.


## 3.1. Reachability Guarantee

Assume that each undirected linka ∈ A has a damage tolerance ra ∈ [0, 1], which represents the maximum degree of disaster damage it can withstand. The road a will only be interrupted if the damage to the road by the disaster exceeds ra. The value of ra can be estimated by experts based on the actual situation of the road. The larger the ra, the stronger the link a can resist damage. The damage tolerance of the link can be extended to the damage tolerance of the path as follows: given the damage tolerance ra for all links in a path p, the damage tolerance of the path p (denoted as r|p) is rp≔mina∈pra. From the definition of the damage tolerance of the path, when the most fragile link in path p is damaged more than r∣p, the path p will be broken. This is actually the worst scenario when considering the same level of damage on different links of this path.In graph theory, pointj is reachable from point i if there exists a path from i to j and there are no broken links in this path. Because the impact of most disasters on network links is highly uncertain, it makes sense to consider the reachability based on the damage tolerance of the path. The concept of reachability guarantee between nodes i and j was first introduced by Yu [34]. It can be defined as the minimum cut separating i and j as follows:(1)Ri,j≔mini∈S,t∈N\S∑a∈AS,N\Sra,where S is any subset of node set N that can separate i and j. Figure 1 shows a simple example, the number near the link indicates the damage tolerance of link. There are two subsets S1 = {1} and S2 = {1, 2} which can separate nodes 1 and 3. Therefore, the reachability guarantee between nodes 1 to 3 is R1,3 = min{0.2 + 0.4, 0.2 + 0.3} = 0.5.Figure 1
Example of the reachability guarantee.The reachability guarantee between pointsi and j reflects the ability of all paths that connect these two points to resist disaster damage. In other words, when the total damage on the network links is less than Ri,j, at least one path between i and j will not be interrupted. Therefore, this value can be viewed as a guarantee of reachability between points i and j. For the example in Figure 1, if the total damage on links is less than 0.5, regardless of the level of damage on different links, there is at least one path between points 1 and 3 that will not be interrupted. That is, points 1 and 3 are reachable to each other.Suppose that the set of demand points isJ. For each demand point j ∈ J, the facility i(j) is allocated to j, then the reachability guarantee of J can be defined as follows:(2)RJ≔∑j∈JRij,j.Note that a facility can be allocated to multiple demand points, but a demand point can only served by one facility. Obviously, we can determine the facilityi(j) of j from the perspective of the reachability guarantee to prepare for postdisaster relief efforts. Therefore, the facility i(j) can be regarded as the backup facility of the demand point j.


## 3.2. Operating Cost

Under normal circumstances, the links of the transportation network will not be damaged, so the operating cost should be considered. In these cases, the service relationship between emergency facilities and demand points is usually established according to the shortest path. Therefore, the shortest distance between a demand point and its corresponding facility can be used to represent the operating cost.Denote the shortest distance between the potential location of facilityi and the demand point j as dij, the facility that is allocated to the demand point j as i(j). Then, the shortest distance between points j and i(j) is dij,j. From the perspective of the demand point set J, the total shortest distance can be defined as follows:(3)DJ≔∑j∈Jdij,j.Obviously, we can determine the facilityi(j) of j from the perspective of the operating cost for normal circumstances. Therefore, the facility i(j) can be regarded as the primary facility of the demand point j.


## 3.3. Reinforce Link

In general, some reinforcements can be taken to increase the value of the damage tolerancera of the link a ∈ A. Suppose that for each link a ∈ A, the damage tolerance ra can be increased by Δa through reinforcement, that is, the damage tolerance after reinforcement becomes ra + Δa. Obviously, reinforcing measures can improve the reachability guarantee between the demand point and its backup facility. To ensure the maximum degree of reachability guarantee, we need to determine links to be reinforced given a limited budget. For example, in Figure 2, to maximize the reachability guarantee between points 1 and 3, if only one link can be reinforced due to the limited budget, which link should be selected? Let R1,3i−j denote the reachability guarantee between points 1 and 3 after reinforce link (i − j), then after simple calculation, we can get R1,31−2=min0.2+0.6,0.2+0.3=0.5, R1,31−3=min0.6+0.4,0.6+0.3=0.9, RG1,32−3=min0.2+0.4,0.2+0.6=0.6, so the suitable link is (1–3) in this case.Figure 2
Example of reinforce link.


## 4. Model Formulation

The main assumptions of the problem are summarized as follows:(1)
The set of candidate facility locationsI and the set of demand points J are known(2)
The damage tolerancera is known, a ∈ A(3)
The potential increment of the damage tolerance Δa and reinforcement cost ca are known, a ∈ A(4)
The facility opening cost of each candidate locationi ∈ I is known as fi(5)
The budget for opening facilities and reinforcing links is known asG(6)
Each demand point is allocated a primary facility and a backup facility


### 4.1. Reachability Guarantee Calculating

From the definition ofRi,j, this is a minimum cut problem of source point i and sink point j. According to the maximum flow minimum cut theorem, this problem is equivalent to the corresponding maximum flow problem. In order to calculate R(J), we must calculate Rij,j for each demand point j ∈ J. If the set of facility locations is determined to be I, then for any j ∈ J, the calculating process of Rij,j is as follows:(1)
Add a link between the virtual source pointS and each point i in I(2)
Let the damage tolerant of link (S, i) be M · y″(i,j), ∀i ∈ I, where M is a large enough positive number(3)
Let the damage tolerant of link (i, j) be r(i,j) + Δ(i,j) · z(i,j)(4)
Add the condition that∑i∈IyS,i2=1 in the maximal flow problemThen, we can getRij1,j1 by solving the maximum flow problem with source point S and sink point j1, as shown in Figure 3.Figure 3
Example for reachability guarantee calculating.


### 4.2. Model Representation

To solve the problem proposed in Section1, we need to find the primary facility and the backup facility for each demand point j ∈ J and to determine the set of links to be reinforced. One goal is to maximize the reachability guarantee R(J), and another goal is to minimize the total shortest distance D(J). This problem can be easily modeled as a bilevel programming. In the upper-level model, different subsets I ⊆ I1 and A1 ⊆ A that satisfy ∑i∈I1fi+∑a∈A1ca≤G can be chosen by some methods. In the low-level model, R(J) and D(J) can be calculated by solving the maximum flow problem and the shortest path problem, respectively. The values of R(J) and D(J) return to the upper level to evaluate subsets I1 and A1. But, this structure is difficult to design effective algorithms. In this paper, the maximum flow model is directly embedded in the location model to replace the bilevel programming structure. The advantage of our method is that it can be easily solved by many commercial optimization software. In our problem, there are two types of variables: one is to determine the primary and backup facilities, and the other is to determine the set of links to be reinforced. Since the variables on the reinforcement links do not affect the shortest distance dij between the candidate point i and the demand point j, the shortest distance dij can be obtained through data preprocessing.The parameters and variables are listed as follows:I: the set of candidate locations for emergency facilitiesJ: the set of demand pointsdij: the shortest distance between i and jG: the budget to open facilities and reinforce linksM: a positive number that is large enoughr(i,k): the damage tolerance of link (i, k) ∈ AΔ(i,k): the damage tolerance increment of the link (i, k) after reinforcementc(i,k): the fixed-charge cost to reinforce the link (i, k)fi: the fixed-charge cost to establish a facility at i ∈ Iyi: facility location decision variable, 1 if a facility is open at location i ∈ I and 0 otherwisexikj: decision variable of flow from source point i through k to sink point jyi,j′: primary facility allocation variable, 1 if i is the primary facility of demand point j and 0 otherwiseyi,j″: backup facility allocation variable, 1 if i is the backup facility of demand point j and 0 otherwisez(i,j): reinforce link decision variable, 1 if link (i, j) is selected to reinforce and 0 otherwiseThe concrete emergency facility location problem is formulated as follows:(4)ming1=∑i∈I∑j∈Jdijyi,j′,(5)maxg2=∑i∈I∑j∈JxSij,(6)subject to:∑i∈Ifiyi+∑i,j∈Aci,jzi,j≤G;(7)xikj≤ri,k+Δi,kzi,k,∀i,k∈A,∀j∈J;(8)∑i∈IxiSj=0,∀j∈J;(9)∑k∈Jxjkj=0,∀j∈J;(10)xSij≤M⋅yi,j″,∀i∈I,j∈J;(11)∑k∈Nxijk−∑k∈Nxkij=0,∀i∈I,j∈J;(12)∑i∈Iyi,j″=1,∀j∈J;(13)∑i∈Iyi,j′=1,∀j∈J;(14)yi,j′+yi,j″≤1,∀i∈I,j∈J;(15)xijk≥0,∀i∈I,k∈N,j∈J;(16)yi,yi,j′,yi,j″,zi,j∈0,1,∀i∈I,j∈J.The first objective function (4) represents the total operating cost between all demand points and their primary facilities. The second objective function (5) means the total reachability guarantee between all demand points and their backup facilities. Constraint (6) restricts the total cost is less than the budget. (7)–(11) are the classical constraints for the maximal flow problem. Constraints (12) and (13) confirm that each demand point is allocated only one backup and one primary facility. Constraint (14) confirms that the primary facility and the backup facility must be different. Constraint (15) defines nonnegative variables in the maximum flow problem, and constraint (16) defines the remaining binary variables.The first goal of this model is the operating cost when there is no link interruption under normal circumstances. The second goal represents the reachability guarantee between facilities and demand points in the worst case. To solve this biobjective model, a weighted objective function is defined asωg1+1−ωg2 where 0 ≤ ω ≤ 1. Solving the model for different values of ω yields a trade-off curve between g1andg2. Since the two goals are different in size, the goals should first be normalized as follows:(17)g˜1=g1maxg1,g˜2=1−g2maxg2,where the maximum value of g1andg2 can be estimated by solving the corresponding single objective problems. Note that our normalization method is slightly different from the method given in Grodzevich and Romanko [35]. Since there is min{gi(x) : x ∈Ω} = 0, both normalization methods can be expressed as gi˜=gi−ziU/ziN−ziU, where ziU=gixi, x[j] = argmin{gi(x) : x ∈Ω}. The difference is that ziN=max1≤j≤kgixj in their method and ziN=maxgix:x∈Ω in our method.


## 4.1. Reachability Guarantee Calculating

From the definition ofRi,j, this is a minimum cut problem of source point i and sink point j. According to the maximum flow minimum cut theorem, this problem is equivalent to the corresponding maximum flow problem. In order to calculate R(J), we must calculate Rij,j for each demand point j ∈ J. If the set of facility locations is determined to be I, then for any j ∈ J, the calculating process of Rij,j is as follows:(1)
Add a link between the virtual source pointS and each point i in I(2)
Let the damage tolerant of link (S, i) be M · y″(i,j), ∀i ∈ I, where M is a large enough positive number(3)
Let the damage tolerant of link (i, j) be r(i,j) + Δ(i,j) · z(i,j)(4)
Add the condition that∑i∈IyS,i2=1 in the maximal flow problemThen, we can getRij1,j1 by solving the maximum flow problem with source point S and sink point j1, as shown in Figure 3.Figure 3
Example for reachability guarantee calculating.


## 4.2. Model Representation

To solve the problem proposed in Section1, we need to find the primary facility and the backup facility for each demand point j ∈ J and to determine the set of links to be reinforced. One goal is to maximize the reachability guarantee R(J), and another goal is to minimize the total shortest distance D(J). This problem can be easily modeled as a bilevel programming. In the upper-level model, different subsets I ⊆ I1 and A1 ⊆ A that satisfy ∑i∈I1fi+∑a∈A1ca≤G can be chosen by some methods. In the low-level model, R(J) and D(J) can be calculated by solving the maximum flow problem and the shortest path problem, respectively. The values of R(J) and D(J) return to the upper level to evaluate subsets I1 and A1. But, this structure is difficult to design effective algorithms. In this paper, the maximum flow model is directly embedded in the location model to replace the bilevel programming structure. The advantage of our method is that it can be easily solved by many commercial optimization software. In our problem, there are two types of variables: one is to determine the primary and backup facilities, and the other is to determine the set of links to be reinforced. Since the variables on the reinforcement links do not affect the shortest distance dij between the candidate point i and the demand point j, the shortest distance dij can be obtained through data preprocessing.The parameters and variables are listed as follows:I: the set of candidate locations for emergency facilitiesJ: the set of demand pointsdij: the shortest distance between i and jG: the budget to open facilities and reinforce linksM: a positive number that is large enoughr(i,k): the damage tolerance of link (i, k) ∈ AΔ(i,k): the damage tolerance increment of the link (i, k) after reinforcementc(i,k): the fixed-charge cost to reinforce the link (i, k)fi: the fixed-charge cost to establish a facility at i ∈ Iyi: facility location decision variable, 1 if a facility is open at location i ∈ I and 0 otherwisexikj: decision variable of flow from source point i through k to sink point jyi,j′: primary facility allocation variable, 1 if i is the primary facility of demand point j and 0 otherwiseyi,j″: backup facility allocation variable, 1 if i is the backup facility of demand point j and 0 otherwisez(i,j): reinforce link decision variable, 1 if link (i, j) is selected to reinforce and 0 otherwiseThe concrete emergency facility location problem is formulated as follows:(4)ming1=∑i∈I∑j∈Jdijyi,j′,(5)maxg2=∑i∈I∑j∈JxSij,(6)subject to:∑i∈Ifiyi+∑i,j∈Aci,jzi,j≤G;(7)xikj≤ri,k+Δi,kzi,k,∀i,k∈A,∀j∈J;(8)∑i∈IxiSj=0,∀j∈J;(9)∑k∈Jxjkj=0,∀j∈J;(10)xSij≤M⋅yi,j″,∀i∈I,j∈J;(11)∑k∈Nxijk−∑k∈Nxkij=0,∀i∈I,j∈J;(12)∑i∈Iyi,j″=1,∀j∈J;(13)∑i∈Iyi,j′=1,∀j∈J;(14)yi,j′+yi,j″≤1,∀i∈I,j∈J;(15)xijk≥0,∀i∈I,k∈N,j∈J;(16)yi,yi,j′,yi,j″,zi,j∈0,1,∀i∈I,j∈J.The first objective function (4) represents the total operating cost between all demand points and their primary facilities. The second objective function (5) means the total reachability guarantee between all demand points and their backup facilities. Constraint (6) restricts the total cost is less than the budget. (7)–(11) are the classical constraints for the maximal flow problem. Constraints (12) and (13) confirm that each demand point is allocated only one backup and one primary facility. Constraint (14) confirms that the primary facility and the backup facility must be different. Constraint (15) defines nonnegative variables in the maximum flow problem, and constraint (16) defines the remaining binary variables.The first goal of this model is the operating cost when there is no link interruption under normal circumstances. The second goal represents the reachability guarantee between facilities and demand points in the worst case. To solve this biobjective model, a weighted objective function is defined asωg1+1−ωg2 where 0 ≤ ω ≤ 1. Solving the model for different values of ω yields a trade-off curve between g1andg2. Since the two goals are different in size, the goals should first be normalized as follows:(17)g˜1=g1maxg1,g˜2=1−g2maxg2,where the maximum value of g1andg2 can be estimated by solving the corresponding single objective problems. Note that our normalization method is slightly different from the method given in Grodzevich and Romanko [35]. Since there is min{gi(x) : x ∈Ω} = 0, both normalization methods can be expressed as gi˜=gi−ziU/ziN−ziU, where ziU=gixi, x[j] = argmin{gi(x) : x ∈Ω}. The difference is that ziN=max1≤j≤kgixj in their method and ziN=maxgix:x∈Ω in our method.


## 5. Illustrative Example

The Sioux Falls Network is a well-known transportation network that has been used in many studies to test models and methods. In this article, we use a simplified Sioux Falls network to test the proposed model. There are 24 nodes and 38 links (undirected) in this simplified network. Of these 24 nodes, 7 of them are considered as demand points (J = {3, 8, 10, 13, 14, 18, 22}), and the remaining 17 nodes are considered as candidate locations of emergency facilities. The structure and link distances of this simplified network together with the demand points are presented in Figure 4.Figure 4
Case study network.Table1 lists the damage tolerance ra, the potential damage tolerance increment Δa, and the corresponding reinforcement cost ca. Note that some links may not be reinforced due to the environment and/or geology reasons. In Table 1, the symbol “—” is used to denote these links that cannot be reinforced. Table 2 lists the cost to open an emergency facility at each candidate point.Table 1
r
a, Δa, and ca for link a.
Link
r
a
Δa
c
a
(1-2)
0.42
0.32
34
(1–3)
0.60
0.28
27
(2–6)
0.92
—
—
(3-4)
0.43
0.53
49
(3–12)
0.56
0.15
17
(4-5)
0.60
0.14
12
(4–11)
0.38
—
—
(5-6)
0.03
0.80
91
(5–9)
0.04
0.49
39
(6–8)
0.03
0.45
60
(7-8)
0.84
—
—
(7–18)
0.64
0.26
28
(8-9)
0.38
0.49
40
(8–16)
0.22
0.76
91
(9-10)
0.84
0.14
17
(10-11)
0.01
0.46
42
(10–15)
0.59
0.17
18
(10–16)
0.62
0.32
37
(10–17)
0.56
0.11
12
(11-12)
0.93
—
—
(11–14)
0.05
0.79
76
(12-13)
0.75
0.12
12
(13–24)
0.72
0.22
23
(14-15)
0.27
0.72
70
(14–23)
0.4
—
—
(15–19)
0.46
0.36
30
(15–22)
0.88
—
—
(16-17)
0.97
—
—
(16–18)
0.41
0.16
16
(17–19)
0.55
0.27
27
(18–20)
0.53
0.14
15
(19-20)
0.83
—
—
(20-21)
0.28
0.44
40
(20–22)
0.02
0.75
77
(21-22)
0.08
0.58
48
(21–24)
0.90
—
—
(22-23)
0.01
0.36
36
(23-24)
0.39
0.27
29Table 2
f
i for candidate location i.
Locationi
1
2
4
5
6
7
9
11
12
15
16
17
19
20
21
23
24
Open costfi
119
64
71
78
79
72
56
70
71
70
61
50
89
111
52
59
109The problem is programmed in MATLAB R2015b platform and run on a 64-bit Intel i5-7200U portable computer with 2.50 GHz CPU and 8 GB RAM. The commercial solver GUROBI 8.1.1 is used to solve the mixed-integer program.


### 5.1. Trade-off Solutions

The given data needs to be preprocessed, and here the Floyd algorithm is used to find the shortest distancedij between any node pair (i, j). For a given budget G, the weights ω are valued at 0.1, 0.2, …, 0.9 to find trade-off solutions between the operating cost and the reachability guarantee. In this article, budget G takes five different values {300, 350, 400, 450, 500} to illustrate its impact on trade-off solutions. All these solutions are presented in Table 3.Table 3
Solutions for differentG and ω (P: primary facility, B: backup facility).
G
ω
g
1
g
2
C
F
C
L
Set of reinforced linksRL
J
3
8
10
13
14
18
22
300
[0.1, 0.2]
507
10.54
106
193
(1-2), (4-5), (6–8), (10-11), (3–12), (7–18)
P
9
9
9
9
17
9
17
B
17
17
17
17
9
17
9
[0.3, 0.5]
357
9.10
108
191
(1-2), (4-5), (6–8), (3–12), (7–18), (20-21)
P
9
9
9
21
21
9
21
B
21
21
21
9
9
21
9
[0.6, 0.9]
304
6.89
115
180
(1-2), (4-5), (6–8), (3–12), (7–18), (23-24)
P
9
9
9
23
23
9
23
B
23
23
23
9
9
23
9
350
0.1
396
10.85
131
215
(1-2), (4-5), (6–8), (3–12), (7–18), (16–18), (21-22)
P
16
16
15
15
15
16
15
B
15
15
16
16
16
15
16
0.2
304
10.13
165
182
(1-2), (4-5), (6–8), (3–12), (7–18), (16–18), (18–20)
P
9
9
9
23
23
9
23
B
17
17
17
17
9
17
9
[0.3, 0.5]
260
9.57
176
168
(1-2), (4-5), (6–8), (9-10), (3–12), (7–18)
P
9
9
9
23
23
16
23
B
16
16
16
9
16
9
9
[0.6, 0.9]
219
6.69
191
151
(1-2), (4-5), (6–8), (3–12), (7–18)
P
4
16
16
23
23
16
23
B
16
4
4
16
16
4
16
400
0.1
396
11.73
131
269
(1-2), (4-5), (6–8), (10-11), (3–12), (12-13), (7–18), (16–18), (21-22)
P
16
16
15
15
15
16
15
B
15
15
16
16
16
15
16
[0.2, 0.3]
260
10.82
176
222
(1-2), (3-4), (6–8), (5–9), (12-13), (7–18)
P
9
9
9
23
23
16
23
B
16
16
16
16
16
9
9
0.4
219
9.83
241
151
(1-2), (4-5), (6–8), (3–12), (7–18)
P
4
16
16
23
23
16
23
B
17
17
17
16
16
17
17
[0.5, 0.9]
209
9.43
247
151
(1-2), (4-5), (6–8), (3–12), (7–18)
P
4
9
9
23
23
16
23
B
16
16
16
16
16
21
16
450
0.1
313
12.03
169
275
(1-2), (4-5), (6–8), (3–12), (11–14), (7–18), (21-22)
P
9
9
9
21
21
16
21
B
15
15
16
16
16
15
16
0.2
260
11.60
176
274
(1-2), (3-4), (6–8), (5–9), (7–18), (16–18), (21-22)
P
9
9
9
23
23
16
23
B
16
16
16
9
16
9
16
[0.3, 0.5]
219
10.91
191
258
(1-2), (3-4), (6–8), (5–9), (7–18), (21-22)
P
4
16
16
23
23
16
23
B
16
4
4
4
16
4
16
0.6
209
10.27
247
199
(1-2), (4-5), (6–8), (3–12), (7–18), (21-22)
P
4
9
9
23
23
16
23
B
16
16
16
16
4
9
16
[0.7, 0.9]
200
9.46
258
187
(1-2), (4-5), (6–8), (3–12), (7–18), (22-23)
P
4
9
9
23
23
7
23
B
7
7
7
7
4
9
7
500
[0.1, 0.2]
260
12.47
176
324
(1-2), (4-5), (6–8), (8-9), (10-11), (3–12), (8–16), (7-18)
P
9
9
9
23
23
16
23
B
16
16
16
9
16
9
9
[0.3, 0.4]
219
11.74
191
308
(1-2), (3-4), (6–8), (5–9), (12-13), (7-18), (18–20), (21-22), (13-24)
P
4
16
16
23
23
16
23
B
16
4
4
16
16
4
16
0.5
209
11.3
247
246
(1-2), (3-4), (6–8), (5–9), (7–18), (22-23)
P
4
9
9
23
23
16
23
B
16
16
16
16
4
4
16
0.6
202
10.76
299
199
(1-2), (4-5), (6–8), (3–12), (7–18), (21-22)
P
4
9
9
23
23
16
21
B
21
16
16
16
4
21
16
[0.7, 0.9]
193
9.46
310
187
(1-2), (4-5), (6–8), (3–12), (7–18), (22-23)
P
4
9
9
23
23
7
21
B
7
7
7
7
21
21
7The first two columns of Table3 show the values of G and ω. Columns 3 to 6 indicate operating cost (g1), reachability guarantee (g2), facility opening cost (CF), and link reinforcing cost (CL), respectively. Column 7 shows the links to be reinforced. The last column shows the allocation between demand points and opened facilities, where the symbols P and B denote the primary facilities and backup facilities, respectively. Note that for simplicity, the collection of open facilities is not shown directly in Table 3, but can be easily obtained by summarizing all primary and backup facilities. For example, when G = 300 and ω = 0.1, the set of open facilities is {9, 17}.Where CF is the total opening cost of facilities and CL is the total cost of the links to be reinforced.From Table3, it is clear that for a given budget G, the operating cost g1 and the reachability guarantee g2 both decrease as the weight ω increases. At the same time, the opening cost of the facility (CF) increases as the weight ω increases, while the cost of reinforcement (CL) decreases. This phenomenon is due to the fact that more facility opening costs can achieve lower operating costs, while more link reinforcement costs can achieve higher reachability guarantee.


### 5.2. Budget Efficiency Analysis

For the optimization problem of target conflicts, the Pareto front (trade-off) curve can help the decision-makers to choose the proper solution. Since the method of determining Pareto boundary weights is not the focus of this article, we can simply obtain the Pareto front curve by changing the weightω from 0.05 in steps of 0.05 to 0.95. Figure 5 shows five Pareto front curves, each of which corresponds to a different value of G.Figure 5
Pareto front (trade-off) curves.From Figure5, it is clear that the larger the value of G, the higher the corresponding Pareto front curve. This is consistent with intuition because more budgets can open more facilities and reinforce more links, which can reduce the operating cost and improve the reachability guarantee. Of course, for a given budget G, the operating cost and the reachability guarantee are two conflicting goals. There is a positive correlation between the reachability guarantee and the operating cost.For a givenω, we know that more budget means lower operating cost and higher reachability guarantee. But, the same rate of budget increase may result in different rates of change for the two goals. Therefore, it is necessary to use the target improvement percentage to evaluate the efficiency of the budget increase. Let ω be 0.1, 0.5, 0.7, the percentage decrease of g1 and the percentage increase of g2 are listed in Table 4. Here, let G1 < G2, and the percentage decrease of g1 is defined as ∇G1,G2=g1G1−g1G2/g1G1 and the percentage increase of g2 is defined as ΔG1,G2=g2G2−g2G1/g2G1.Table 4
Budget efficiency of two objectives.
ω
G
300
350
400
450
500
0.2
∇(G1, G2)
—
40.04%
14.47%
0%
0%
Δ(G1, G2)
—
−3.89%
6.81%
7.21%
7.50%
0.5
∇(G1, G2)
—
27.17%
19.62%
−4.78%
4.57%
Δ(G1, G2)
—
5.16%
−1.46%
15.69%
3.57%
0.7
∇(G1, G2)
—
27.96%
4.57%
4.31%
3.50%
Δ(G1, G2)
—
−2.90%
40.96%
0.32%
0%It can be seen from Table4 that when the budget increases, the operating cost and the reachability guarantee may not necessarily be improved at the same time. For example, let ω = 0.5, and when the budget G changes from 350 to 400, the percentage decrease of g1 is 19.62%, and the percentage increase of g2 is − 1.46%. However, when the budget G increases from 400 to 450, the percentage decrease of g1 is − 4.78%, and the percentage increase of g2 is 15.69%. Therefore, if we can determine the value of ω, we can derive a suitable G from these two indicators of ∇(G1, G2), Δ(G1, G2). For example, if the weight ω = 0.5, the values of ∇(G1, G2) and Δ(G1, G2) indicate that the increment of G from 300 to 350 is appropriate. Similar conclusion can be drawn when G is increasing from 450 to 500. Therefore, a budget with a high input-output rate can be determined based on a given weight.


### 5.3. Effects of Reinforced Links

To investigate the impact of the links to be reinforced, we delved into the solutions forG = 500. For a given ω, let us keep the primary facility and the backup facility that is allocated to each demand point unchanged and then compare the reachability guarantee before and after reinforcing a link. Table 5 lists these comparisons of the reachability guarantee when ω = 0.1, 0.5, 0.7.Table 5
Reachability improvement forG = 500.
J
ω = 0.1
ω = 0.5
ω = 0.7
BF
AF
BF
AF
BF
AF
3
0.72
1.61
0.72
1.79
0.72
1.30
8
1.27
2.98
1.27
1.92
1.47
1.74
10
2.20
2.98
2.20
2.22
1.27
1.74
13
0.72
1.44
0.72
1.47
0.72
1.30
14
0.72
0.72
0.72
0.77
0.72
0.77
18
1.26
1.75
0.72
1.78
0.72
1.26
22
0.99
0.99
0.99
1.35
0.99
1.35
Total
7.88
12.47
7.34
11.3
6.61
9.46
BF: before reinforcing, AF: after reinforcing.Table5 shows that for each demand point, the reachability guarantee of the link after reinforcement is not lower than the reachability guarantee before reinforcement, and the total reachability guarantee increases significantly after reinforcement. Another conclusion that can be drawn from Table 5 is that after link reinforcement, the percentage increase of total reachability guarantee is negatively correlated with ω. For ω = 0.1, 0.5, 0.7, the corresponding percentage increase in reachability guarantee are 58.25%, 53.95%, and 43.12%. Therefore, we can conclude that by reinforcing appropriate links, the reachability guarantee between the demand point and its backup facility can be greatly improved.ForG = 500 and ω = 0.5, the primary facility and the backup facility that is allocated to each demand point and the entire reinforcement links are shown in Figure 6. Here, the black arrow line indicates the primary facility of the demand point, the blue dotted arrow line indicates the backup facility of the demand point, and the red line along the link indicates the link to be reinforced.Figure 6
Location-allocation scheme forG = 500 and ω = 0.5.From Figure6, we know that the primary facility is relatively close to the demand point, but the backup facility depends on the reachability guarantee. To find the impact of each reinforced link, after removing the links one by one from the set of links to be reinforced (RL), we calculate the reachability guarantee for each demand point. These results are shown in Table 6.Table 6
Reachability effect of each link forG = 500 and ω = 0.5
J
Removed link from RL
(1-2)
(3-4)
(6–8)
(5–9)
(7–18)
(22-23)
3
1.76
1.50
1.34
1.30
1.79
1.66
8
1.89
1.92
1.47
1.92
1.72
1.92
10
2.22
2.22
2.22
2.20
2.22
2.22
13
1.47
1.47
1.34
1.30
1.47
1.44
14
0.77
0.77
0.77
0.77
0.77
0.72
18
1.76
1.37
1.34
1.30
1.58
1.66
22
1.35
1.35
1.35
1.35
1.35
0.99
Total
11.22
10.60
9.83
10.14
10.90
10.61From Table6, we can conclude that the most important link need to be reinforced is (6–8), because if this link is removed from the set of links to be reinforced, the total reachability guarantee decreases from 11.3 to 9.83. Obviously, removing this link has the greatest impact on the reachability guarantee among all links. Therefore, we can conclude that the links that need to be reinforced have different impacts on the reachability guarantee of demand points. For links with large effect on the reachability guarantee, we should pay more attention to their reinforcement.


## 5.1. Trade-off Solutions

The given data needs to be preprocessed, and here the Floyd algorithm is used to find the shortest distancedij between any node pair (i, j). For a given budget G, the weights ω are valued at 0.1, 0.2, …, 0.9 to find trade-off solutions between the operating cost and the reachability guarantee. In this article, budget G takes five different values {300, 350, 400, 450, 500} to illustrate its impact on trade-off solutions. All these solutions are presented in Table 3.Table 3
Solutions for differentG and ω (P: primary facility, B: backup facility).
G
ω
g
1
g
2
C
F
C
L
Set of reinforced linksRL
J
3
8
10
13
14
18
22
300
[0.1, 0.2]
507
10.54
106
193
(1-2), (4-5), (6–8), (10-11), (3–12), (7–18)
P
9
9
9
9
17
9
17
B
17
17
17
17
9
17
9
[0.3, 0.5]
357
9.10
108
191
(1-2), (4-5), (6–8), (3–12), (7–18), (20-21)
P
9
9
9
21
21
9
21
B
21
21
21
9
9
21
9
[0.6, 0.9]
304
6.89
115
180
(1-2), (4-5), (6–8), (3–12), (7–18), (23-24)
P
9
9
9
23
23
9
23
B
23
23
23
9
9
23
9
350
0.1
396
10.85
131
215
(1-2), (4-5), (6–8), (3–12), (7–18), (16–18), (21-22)
P
16
16
15
15
15
16
15
B
15
15
16
16
16
15
16
0.2
304
10.13
165
182
(1-2), (4-5), (6–8), (3–12), (7–18), (16–18), (18–20)
P
9
9
9
23
23
9
23
B
17
17
17
17
9
17
9
[0.3, 0.5]
260
9.57
176
168
(1-2), (4-5), (6–8), (9-10), (3–12), (7–18)
P
9
9
9
23
23
16
23
B
16
16
16
9
16
9
9
[0.6, 0.9]
219
6.69
191
151
(1-2), (4-5), (6–8), (3–12), (7–18)
P
4
16
16
23
23
16
23
B
16
4
4
16
16
4
16
400
0.1
396
11.73
131
269
(1-2), (4-5), (6–8), (10-11), (3–12), (12-13), (7–18), (16–18), (21-22)
P
16
16
15
15
15
16
15
B
15
15
16
16
16
15
16
[0.2, 0.3]
260
10.82
176
222
(1-2), (3-4), (6–8), (5–9), (12-13), (7–18)
P
9
9
9
23
23
16
23
B
16
16
16
16
16
9
9
0.4
219
9.83
241
151
(1-2), (4-5), (6–8), (3–12), (7–18)
P
4
16
16
23
23
16
23
B
17
17
17
16
16
17
17
[0.5, 0.9]
209
9.43
247
151
(1-2), (4-5), (6–8), (3–12), (7–18)
P
4
9
9
23
23
16
23
B
16
16
16
16
16
21
16
450
0.1
313
12.03
169
275
(1-2), (4-5), (6–8), (3–12), (11–14), (7–18), (21-22)
P
9
9
9
21
21
16
21
B
15
15
16
16
16
15
16
0.2
260
11.60
176
274
(1-2), (3-4), (6–8), (5–9), (7–18), (16–18), (21-22)
P
9
9
9
23
23
16
23
B
16
16
16
9
16
9
16
[0.3, 0.5]
219
10.91
191
258
(1-2), (3-4), (6–8), (5–9), (7–18), (21-22)
P
4
16
16
23
23
16
23
B
16
4
4
4
16
4
16
0.6
209
10.27
247
199
(1-2), (4-5), (6–8), (3–12), (7–18), (21-22)
P
4
9
9
23
23
16
23
B
16
16
16
16
4
9
16
[0.7, 0.9]
200
9.46
258
187
(1-2), (4-5), (6–8), (3–12), (7–18), (22-23)
P
4
9
9
23
23
7
23
B
7
7
7
7
4
9
7
500
[0.1, 0.2]
260
12.47
176
324
(1-2), (4-5), (6–8), (8-9), (10-11), (3–12), (8–16), (7-18)
P
9
9
9
23
23
16
23
B
16
16
16
9
16
9
9
[0.3, 0.4]
219
11.74
191
308
(1-2), (3-4), (6–8), (5–9), (12-13), (7-18), (18–20), (21-22), (13-24)
P
4
16
16
23
23
16
23
B
16
4
4
16
16
4
16
0.5
209
11.3
247
246
(1-2), (3-4), (6–8), (5–9), (7–18), (22-23)
P
4
9
9
23
23
16
23
B
16
16
16
16
4
4
16
0.6
202
10.76
299
199
(1-2), (4-5), (6–8), (3–12), (7–18), (21-22)
P
4
9
9
23
23
16
21
B
21
16
16
16
4
21
16
[0.7, 0.9]
193
9.46
310
187
(1-2), (4-5), (6–8), (3–12), (7–18), (22-23)
P
4
9
9
23
23
7
21
B
7
7
7
7
21
21
7The first two columns of Table3 show the values of G and ω. Columns 3 to 6 indicate operating cost (g1), reachability guarantee (g2), facility opening cost (CF), and link reinforcing cost (CL), respectively. Column 7 shows the links to be reinforced. The last column shows the allocation between demand points and opened facilities, where the symbols P and B denote the primary facilities and backup facilities, respectively. Note that for simplicity, the collection of open facilities is not shown directly in Table 3, but can be easily obtained by summarizing all primary and backup facilities. For example, when G = 300 and ω = 0.1, the set of open facilities is {9, 17}.Where CF is the total opening cost of facilities and CL is the total cost of the links to be reinforced.From Table3, it is clear that for a given budget G, the operating cost g1 and the reachability guarantee g2 both decrease as the weight ω increases. At the same time, the opening cost of the facility (CF) increases as the weight ω increases, while the cost of reinforcement (CL) decreases. This phenomenon is due to the fact that more facility opening costs can achieve lower operating costs, while more link reinforcement costs can achieve higher reachability guarantee.


## 5.2. Budget Efficiency Analysis

For the optimization problem of target conflicts, the Pareto front (trade-off) curve can help the decision-makers to choose the proper solution. Since the method of determining Pareto boundary weights is not the focus of this article, we can simply obtain the Pareto front curve by changing the weightω from 0.05 in steps of 0.05 to 0.95. Figure 5 shows five Pareto front curves, each of which corresponds to a different value of G.Figure 5
Pareto front (trade-off) curves.From Figure5, it is clear that the larger the value of G, the higher the corresponding Pareto front curve. This is consistent with intuition because more budgets can open more facilities and reinforce more links, which can reduce the operating cost and improve the reachability guarantee. Of course, for a given budget G, the operating cost and the reachability guarantee are two conflicting goals. There is a positive correlation between the reachability guarantee and the operating cost.For a givenω, we know that more budget means lower operating cost and higher reachability guarantee. But, the same rate of budget increase may result in different rates of change for the two goals. Therefore, it is necessary to use the target improvement percentage to evaluate the efficiency of the budget increase. Let ω be 0.1, 0.5, 0.7, the percentage decrease of g1 and the percentage increase of g2 are listed in Table 4. Here, let G1 < G2, and the percentage decrease of g1 is defined as ∇G1,G2=g1G1−g1G2/g1G1 and the percentage increase of g2 is defined as ΔG1,G2=g2G2−g2G1/g2G1.Table 4
Budget efficiency of two objectives.
ω
G
300
350
400
450
500
0.2
∇(G1, G2)
—
40.04%
14.47%
0%
0%
Δ(G1, G2)
—
−3.89%
6.81%
7.21%
7.50%
0.5
∇(G1, G2)
—
27.17%
19.62%
−4.78%
4.57%
Δ(G1, G2)
—
5.16%
−1.46%
15.69%
3.57%
0.7
∇(G1, G2)
—
27.96%
4.57%
4.31%
3.50%
Δ(G1, G2)
—
−2.90%
40.96%
0.32%
0%It can be seen from Table4 that when the budget increases, the operating cost and the reachability guarantee may not necessarily be improved at the same time. For example, let ω = 0.5, and when the budget G changes from 350 to 400, the percentage decrease of g1 is 19.62%, and the percentage increase of g2 is − 1.46%. However, when the budget G increases from 400 to 450, the percentage decrease of g1 is − 4.78%, and the percentage increase of g2 is 15.69%. Therefore, if we can determine the value of ω, we can derive a suitable G from these two indicators of ∇(G1, G2), Δ(G1, G2). For example, if the weight ω = 0.5, the values of ∇(G1, G2) and Δ(G1, G2) indicate that the increment of G from 300 to 350 is appropriate. Similar conclusion can be drawn when G is increasing from 450 to 500. Therefore, a budget with a high input-output rate can be determined based on a given weight.


## 5.3. Effects of Reinforced Links

To investigate the impact of the links to be reinforced, we delved into the solutions forG = 500. For a given ω, let us keep the primary facility and the backup facility that is allocated to each demand point unchanged and then compare the reachability guarantee before and after reinforcing a link. Table 5 lists these comparisons of the reachability guarantee when ω = 0.1, 0.5, 0.7.Table 5
Reachability improvement forG = 500.
J
ω = 0.1
ω = 0.5
ω = 0.7
BF
AF
BF
AF
BF
AF
3
0.72
1.61
0.72
1.79
0.72
1.30
8
1.27
2.98
1.27
1.92
1.47
1.74
10
2.20
2.98
2.20
2.22
1.27
1.74
13
0.72
1.44
0.72
1.47
0.72
1.30
14
0.72
0.72
0.72
0.77
0.72
0.77
18
1.26
1.75
0.72
1.78
0.72
1.26
22
0.99
0.99
0.99
1.35
0.99
1.35
Total
7.88
12.47
7.34
11.3
6.61
9.46
BF: before reinforcing, AF: after reinforcing.Table5 shows that for each demand point, the reachability guarantee of the link after reinforcement is not lower than the reachability guarantee before reinforcement, and the total reachability guarantee increases significantly after reinforcement. Another conclusion that can be drawn from Table 5 is that after link reinforcement, the percentage increase of total reachability guarantee is negatively correlated with ω. For ω = 0.1, 0.5, 0.7, the corresponding percentage increase in reachability guarantee are 58.25%, 53.95%, and 43.12%. Therefore, we can conclude that by reinforcing appropriate links, the reachability guarantee between the demand point and its backup facility can be greatly improved.ForG = 500 and ω = 0.5, the primary facility and the backup facility that is allocated to each demand point and the entire reinforcement links are shown in Figure 6. Here, the black arrow line indicates the primary facility of the demand point, the blue dotted arrow line indicates the backup facility of the demand point, and the red line along the link indicates the link to be reinforced.Figure 6
Location-allocation scheme forG = 500 and ω = 0.5.From Figure6, we know that the primary facility is relatively close to the demand point, but the backup facility depends on the reachability guarantee. To find the impact of each reinforced link, after removing the links one by one from the set of links to be reinforced (RL), we calculate the reachability guarantee for each demand point. These results are shown in Table 6.Table 6
Reachability effect of each link forG = 500 and ω = 0.5
J
Removed link from RL
(1-2)
(3-4)
(6–8)
(5–9)
(7–18)
(22-23)
3
1.76
1.50
1.34
1.30
1.79
1.66
8
1.89
1.92
1.47
1.92
1.72
1.92
10
2.22
2.22
2.22
2.20
2.22
2.22
13
1.47
1.47
1.34
1.30
1.47
1.44
14
0.77
0.77
0.77
0.77
0.77
0.72
18
1.76
1.37
1.34
1.30
1.58
1.66
22
1.35
1.35
1.35
1.35
1.35
0.99
Total
11.22
10.60
9.83
10.14
10.90
10.61From Table6, we can conclude that the most important link need to be reinforced is (6–8), because if this link is removed from the set of links to be reinforced, the total reachability guarantee decreases from 11.3 to 9.83. Obviously, removing this link has the greatest impact on the reachability guarantee among all links. Therefore, we can conclude that the links that need to be reinforced have different impacts on the reachability guarantee of demand points. For links with large effect on the reachability guarantee, we should pay more attention to their reinforcement.


## 6. Conclusion

The ground transportation network is vulnerable to natural and manmade disasters; hence, the locations of emergency facilities and the reinforcement of fragile links are critical in reducing the impact of these disasters. To determine the location of emergency facilities and the links to be reinforced, we presented a biobjective optimization model by defining the reachability guarantee. The reachability guarantee is derived from the worst case of path disruption caused by a disaster. In the proposed model, each demand point is allocated a primary facility and a backup facility. The primary facility provides service in the normal situation, and the backup facility is prepared for disaster situation. So, the objective to locate the primary facility is minimizing the operating cost while the objective to locate the backup facility is maximizing the reachability guarantee.Given the location of emergency facilities and the set of links to be reinforced, the operating cost and the reachability guarantee can be obtained by solving the shortest path problem and the max-flow problem, respectively. In this paper, these two submodels are embedded in the location-allocation model directly. The advantage of our method is that our model can be easily solved by many commercial optimization software. The biobjective framework provides greater flexibility that allows the decision-maker to choose a suitable nondominated solution given a limited budget. The illustrative example shows that the model presented in this paper can help us to determine the location of emergency facilities and the links to be reinforced at the same time.This paper only considers the possibility of link interruption and does not consider other factors such as the possibility failure of facility and the demand quantity. How to incorporate these factors into some decision-making issues in the preparation stage of disaster management will be the direction of our future research.



---

*Source: 4648908-2020-03-10.xml*