Fuzzy interdiction/fortification location problems on p-median systems

Abstract

An interdiction/fortification location problem deals with finding the locations of resources and customer-facility assignments. Due to the special characteristics of the problem, the overall performance of the system depends on interdiction/fortification operations and the demand of customers. Therefore, the design of efficient systems is a remarkable issue to be considered. In this paper, a new point of view in the field of mathematical modeling of p-median systems in terms of fuzzy theory has been allocated and a bi-level programming is applied. It is assumed that the demand of customers and fortification/interdiction resources are imprecise. For solving this model, the bi-level problem is converted to a single level problem on using the Karush-Kuhn-Tucker (KKT) conditions. The single level model can be solved to optimality using CPLEX. Finally, a test problem is presented and the results are analyzed.

Keywords

Fuzzy sets location problems interdiction/fortification models Karush-Kuhn-Tucker conditions

1 Introduction

A decision-making problem is regarded as the process or situation resulting in the selection and identification of some decisions among several possibilities. These problems create in the operation of some system known as the system related to the problem. The person(s) responsible for decision making is (are) called the decision maker(s) for the problem. The most reasonable models for decision making are based on quantitative analysis which includes of the following models [16].

Deterministic: all relevant data and information on the problem can be controlled by the decision makers and set at desired values;

Stochastic or probabilistic: in this problem, factors such as environmental factors which are random variables not under the control of the decision makers.

In complex institutional and logistic systems, the decision making process is more difficult and crucial, which plays a key role in the management of organizations and analyzing variables concerning technological costs, environmental protection, risk level, investment effects on plants and behavior of people, etc. [9]. Rosenhead et al. [19] divide decision making environments into three classes: certainty, risk, and uncertainty. In certainty status, all parameters are deterministic and definite, whereas risk and uncertainty situations both include randomness. In risk case, uncertain parameters are determined by probability distributions that are known by the decision maker. In uncertainty case, parameters are uncertain and no information about probabilities is known. Problems in risk case are known as stochastic optimization problems; and problems under uncertainty are known as robust optimizationproblems.

Facility location decisions are costly and difficult, and their impact spreads in a long time and the parameters of these problems such as costs, demands, distances may change widely. Thus, authors have developed models for facility location problems under uncertainty for several decades. Since our model belongs to the class of p-median problem, a short review of related models in deterministic, stochastic and fuzzy version is the following. The p-median problem, is proposed by Hakimi [10], include to locate p facilities in a network for covering given demands and minimizing transport costs. This problem be formulated as a linear programming model with 0–1 variables specifying the location,and with continuous variables specifying the demand to be covered from each facility [18]. Serra and Marianov [22] presented the p-median problem in a changing network. They stated uncertainty in:

The demand or population at the vertices of the network. That was, the demand or population to be served was not a known quantity but assumed different values depending on community growth or the community’s economic vitality, among other factors;

The different values that travel times had depending on the time of the day, or day of the week.

Berman and Drezner [5] formulated the p-median problem under uncertainty when the number of facilities in the future is uncertain. They consider the situation to locate p facilities at the present time and to locate up to q additional facilities in the future. The probability that r facilities will be located in the future was given for every 0 ≤ r ≤ q.

Although stochastic models prepared for a variety of cases, they are not adequate to characterize many other cases. For example, the probability distribution of customer’s demands may be unknown. Suppose that we will institute some factories in new areas to service some new demands in which they can not be obtained from history data and given precisely. But these demands can be represented by the natural language such as large, little or general, etc. In these situations, fuzzy set theory is better in dealing with ambiguous data. Fuzzy set theory was introduced by Zadeh [23] and has been numerous used in real-world problems. There has been a vast interest for fuzzy sets to be applied for the facility location problem in the recent years. For example, in Canos et al. [6], a fuzzy set of constraints is considered for the classical p-median problem, in which it obtained lower costs than the crisp p-median model by leaving a part of the demand unserviced. Mayoya and Verdegay [15] also formulated the p-median problem in a fuzzy environment. In this model, data related to the node demands and the edge distances are imprecise and uncertain. Numerical results presented solutions better than deterministic model.

Recently, Scaparra and Church [20] introduced an extension of the p-median problem with a bilevel formulation, called the r-interdiction median problem with fortification (RIMF), in which the upper level problem included the fortifier’s decision about fortification operations of q facilities to minimize the worst-case efficiency reduction due to the loss of r unprotected facilities and the lower-level problem included the interdictor’s decision about interdiction operations of r facilities to maximize the efficiency reduction of a public service system. In traditional RIMF models, minimizing the weighted distance between facilities and customers after interdiction operations of facilities is the considerable objective. In fact, the success of any fortifier depends entirely on fortifying facilities and the quality of service of customers after interdiction operations. Some examples are given in [7] as a interdiction median problem with fortification (IMF). The defender’s objective was to determine q facilities, in which, when protected in a network with p existing facilities, to minimize the demand-weighted distance between non-interdicted facilities and customers after the attacks and the attacker’s objective was to damage r facilities to maximize the total demand-weighted distance, Scaparra and Church [21] developed another formulation referred to as the maximal covering problem with precedence constraints (MCPC), a novel interdiction/fortification model for an uncapacitated p-median system that was subject to the human or natural occurrence when taking into account facility recovery time and frequent disruptions [14], a capacitated median system with a limited protection budget such that the type of disruptive operations are considered in [11], a fixed charge location model in the context of RIMF [1] and partial interdiction decisions in a median system with capacitated facilities and outsourcing option [2].

In the real service system, decision making can occur in an environment where the objectives, constraints or parameters are not specified precisely. Therefore, the problem parameters are described hardly due to the complexity of social and economic environment as well as some unpredictable factors such as bad weather and facility breakdowns. These augments increased the importance of stochastic and fuzzy programming for solving these problems where data are not known precisely. Many researchers have been presented stochastic RIMF models that are closer to real situations. They have modeled the uncertainty by using probability distribution. Some authors have recently studied some aspects of the RIMF from a probability point of view in which the result of an attack is uncertain [13], the stochastic r-interdiction median problem with fortification (S-RIMF) (a random number of losses) [12] and the probabilistic protection problem in service networks with respect to intentional attacks and a model with multiple interdictors [24].

In addition, reviewing the literature of RIMF, we came to notify that the fuzzy version of RIMF has attracted little attention. As an example, in a p-median system, many parameters such as the demand of customers and interdiction/fortification resources are not deterministic. Also, it is sometimes difficult to describe these parameters as random variables, due to the servicing distance or time and financial resources and cost values that is considered for them. Considering a constant value for each of these parameters will cause that the problem can not be a realistic model. The situations are vague and changeable, so the fuzzy approach are presented to overcome this deficiency or weakness. Therefore, one may resort to using fuzzy theory. Consequently, the main aim of this study is to explain how the RIMF could be modeled in a fuzzy environment. As for a probabilistic method, we can befit probability distributions based on the stochastic experiments and the historical data. Thus, the model’s parameters are estimated and eventually the structure of the model. As for a fuzzy model, In cases where there are no reliable historical data for estimating parameters, we can estimate the parameters based on our perceptions. Thus, in lieu of collecting data for estimation procedure and passing time and cost, the model is analyzed based on the imprecise data. Therefore, the RIMF is formulated as a bi-level programming problem with fuzzy parameters. On the other hand, since fuzzy RIMF be formulated as a bi-level programming problem, the Karush-Kuhn-Tucker (KKT) conditions are used for converting the bi-level fuzzy RIMF into single level problem. Then by utilizing the CPLEX, the single level problem is solved.

The content of this paper is outlined as follows: Section 2 describes the r-interdiction median problem with fortification (RIMF) and the fuzzy formulation which has been proposed. We provide the methodology to solve fuzzy RIMF in Section 3. computational results are exhibited and analyzed in Section 4. Finally, Section 5 states the conclusions of the paper.

2 A bi-level formulation of the fuzzy RIMF

The RIMF involved identifying the optimal allocation of the protective resources among the facilities of an existing system so that the impact of the most disruptive attack on unprotected facilities is minimized. In the bi-level formulation, the top level problem involved the decisions about which facilities to fortify in order to minimize the worst-case efficiency reduction due to the loss of unprotected facilities. Worst-case scenario losses are modeled in the lower-level problem. Indeed, this problem was modeled as a static Stackelberg game between a defender (leader) and an attacker (follower). The defender’s decisions were related to finding optimal allocations of protective resources as well as customer-facility assignments so that the total demand-weighted distance is minimized. Following this action, the attacker seeks facilities to interdict that resulting reduction of the system efficiency with a limited offensive resource. It is well known that the crisp RIMF can be modeled by a mixed integer 0-1 and bi-level problem. In the formulation of RIMF, the inputs are applied followed by [20]:

Index sets

I =

Set of customers, I = {1, …, n};

J =

Set of operating facility locations, J = {1, …, m};

T_ij =

Set of available sites that are farther than j is from demand i, T_ij = {k ∈ J |k ≠ j and d_ik > d_ij}.

Parameters

d_ij =

unit traveling cost (shortest distance cost) between customer i and facility location j;

a_i =

demand of customer i;

q =

total fortification resources;

r =

total interdiction resources.

Decision variables

$\begin{matrix} z_{j} & = & {\begin{matrix} 1 & if a facility located at j is fortified, \\ 0 & otherwise . \end{matrix} \\ s_{j} & = & {\begin{matrix} 1 & if a facility located at j is interdicted, \\ 0 & otherwise . \end{matrix} \\ x_{ij} & = & the demand of customer i covered \\ by the facility at location j . \end{matrix}$

Mathematical model

RIMF can be formulated as follows: $min H (z)$ (1) $\begin{matrix} s . t . \\ \sum_{j \in J} z_{j} = q \end{matrix}$ (2) $z_{j} \in {0, 1}, \forall j \in J$ (3) $H (z) = max \sum_{i \in I} \sum_{j \in J} d_{ij} x_{ij}$ (4) $\begin{matrix} s . t . \\ \sum_{j \in J} x_{ij} = a_{i}, \forall i \in I \end{matrix}$ (5) $\sum_{j \in J} s_{j} = r$ (6) $\sum_{h \in T_{ij}} x_{ih} \leq a_{i} s_{j}, \forall i \in I, j \in J$ (7) $s_{j} \leq 1 - z_{j}, \forall j \in J$ (8) $s_{j} \in {0, 1}, \forall j \in J$ (9) $0 \leq x_{ij} \leq a_{i}, \forall i \in I, j \in J$ (10)

In the bi-level model (1–10), At first the leader allots q fortification resources (2) to minimize a function H (1) that it displays the highest level of weighted distance or costs which arisen from the loss of r of the p facilities. The follower problem objective consists maximizing the weighted distance or service cost after the removal of r facilities. The lower-level program (4–8) is the lower-level interdiction problem, with the extra constraints (8) which obstruct the interdiction of any site that chosen for fortifying in the upper level problem. Constraints (5) specify that each demand point must allocated to a facility after interdiction. Constraint (6) specify that r facilities be interdicted. Constraint (7) establishes that each demand point must be allocated to its closest open facility after interdiction. Moreover, these constraints specify that if a facility j is not interdicted (s_j = 0), a customer i cannot be served by a facility that is further than j from i. Constraints (8) state relation between the upper and lower-level problem. Constraints (3), (9) and (10) display the integrality requirements for the fortification, interdiction and assignment variables, respectively.

A fuzzy version of the RIMF makes if it is assumed that the demands a_i, fortification resources q and interdiction resources r are not fixed and the decision-maker has a degree of freedom in order to change them. We pursue the general framework given in [8, 25].

Definition 1. Assume that are given a fuzzy goal $\tilde{F}$ and three fuzzy constraint $\tilde{C_{1}}$ , $\tilde{C_{2}}$ and $\tilde{C_{3}}$ in a space of alternatives X. Then $\tilde{F}$ , $\tilde{C_{1}}$ , $\tilde{C_{2}}$ and $\tilde{C_{3}}$ combine to make a decision $\tilde{D}$ , which is a fuzzy set resulting from intersection of $\tilde{F}$ , $\tilde{C_{1}}$ , $\tilde{C_{2}}$ and $\tilde{C_{3}}$ , i.e. $\tilde{D} = \tilde{F} \cap \tilde{C_{1}} \cap \tilde{C_{2}} \cap \tilde{C_{3}}$ and also $μ_{\tilde{D}} = min {μ_{\tilde{F}}, μ_{\tilde{C_{1}}}, μ_{\tilde{C_{2}}}, μ_{\tilde{C_{3}}}} .$

Then, we search for a final crisp decision or solution where $μ_{\tilde{D}}$ is maximum.

Here, membership degrees are calculated to the fuzzy constraints $\tilde{C_{1}}$ , $\tilde{C_{2}}$ and $\tilde{C_{3}}$ depend on the actually served demand, fortification and interdiction resources which each solution provides, i.e., the degree of feasibility of each solution (x_ij, z_j, s_j) depend on the difference between the total demand that be served and the actual demand, total fortification and interdiction resources that be applied and the actual resources. i.e., they will be represented as functions of $\begin{matrix} \sum_{i \in I} a_{i} - \sum_{i \in I} \sum_{j \in J} x_{ij}, \\ q - \sum_{j \in J} z_{j}, \\ r - \sum_{j \in J} s_{j} . \end{matrix}$ Now, linear membership functions are selected and the degree of feasibility of each solution (x_ij, z_j, s_j) is calculated as $\begin{matrix} μ_{c_{1}} (x_{ij}, z_{j}, s_{j}) = h_{c_{1}} (\sum_{i \in I} a_{i} - \sum_{i \in I} \sum_{j \in J} x_{ij}), \\ μ_{c_{2}} (x_{ij}, z_{j}, s_{j}) = h_{c_{2}} (q - \sum_{j \in J} z_{j}), \\ μ_{c_{3}} (x_{ij}, z_{j}, s_{j}) = h_{c_{3}} (r - \sum_{j \in J} s_{j}) . \end{matrix}$ where h_{c
₁}, h_{c
₂} and h_{c
₃} are auxiliary functions given by $\begin{matrix} h_{c_{1}} & = & {\begin{matrix} 1 & if x < 0, \\ 1 - x / p_{c_{1}} & if 0 \leq x \leq p_{c_{1}}, \\ 0 & if x > p_{c_{1}} . \end{matrix} \\ h_{c_{2}} & = & {\begin{matrix} 1 & if x < 0, \\ 1 - x / p_{c_{2}} & if 0 \leq x \leq p_{c_{2}}, \\ 0 & if x > p_{c_{2}} . \end{matrix} \\ h_{c_{3}} & = & {\begin{matrix} 1 & if x < 0, \\ 1 - x / p_{c_{3}} & if 0 \leq x \leq p_{c_{3}}, \\ 0 & if x > p_{c_{3}} . \end{matrix} \end{matrix}$

Here, p_{c
₁}, p_{c
₂} and p_{c
₃} show the maximum tolerance level for a solution be considered feasible. Fuzzy goal $\tilde{F}$ is to increase the weighted distance. Degree of improvement of the goal (i.e., the membership degree to $\tilde{F}$ ) with respect to the crisp optimum cost H (z^∗) for each solution (x_ij, z_j, s_j) is calculated as $\begin{matrix} μ_{f} (x_{ij}, z_{j}, s_{j}) \\ = h_{f} (\sum_{i \in I} \sum_{j \in J} d_{ij} x_{ij} - H (z^{*})) . \end{matrix}$ where h_f is an auxiliary function given by $h_{f} = {\begin{matrix} 1 & if x < 0, \\ 1 - x / p_{f} & if 0 \leq x \leq p_{f}, \\ 0 & if x > p_{f} . \end{matrix}$ and p_f demonstrates how much the weighted distance should be increased in order for the improvement to be satisfactory. Let us assume λ the membership degree of the decision set $\tilde{D}$ . It will be called the global degree of satisfaction of a solution. Then, solutions with the greatest value of λ be searched. They can be found with an auxiliary crisp problem: $min H (λ)$ (11) $\begin{matrix} s . t . \\ λ \leq μ_{c_{2}} (x_{ij}, z_{j}, s_{j}) \end{matrix}$ (12) $\sum_{j \in J} z_{j} \leq q$ (13) $z_{j} \in {0, 1}, \forall j \in J$ (14) $H (λ) = max λ$ (15)

$\begin{matrix} s . t . \\ λ \leq μ_{f} (x_{ij}, z_{j}, s_{j}) \end{matrix}$ (16) $λ \leq μ_{c_{1}} (x_{ij}, z_{j}, s_{j})$ (17) $\sum_{j \in J} x_{ij} \leq a_{i}, \forall i \in I$ (18) $λ \leq μ_{c_{3}} (x_{ij}, z_{j}, s_{j})$ (19) $\sum_{j \in J} s_{j} \leq r$ (20) $\sum_{h \in T_{ij}} x_{ih} \leq a_{i} s_{j}, \forall i \in I, j \in J$ (21) $s_{j} \leq 1 - z_{j} \forall j \in J$ (22) $s_{j} \in {0, 1}, 0 \leq x_{ij} \leq a_{i}, \forall i \in I, j \in J,$ (23) $0 \leq λ \leq 1$ (24) where the variable λ is introduced which shows the global degree of satisfaction of a solution, i.e., its membership level with respect to the decision set. By replacing μ_{c
₁}, μ_{c
₂}, μ_{c
₃} and μ_f by their definitions, a linear programming problem is given: $min H (λ)$ (25) $\begin{matrix} s . t . \\ λ + \frac{\sum_{j \in J} z_{j}}{p_{c_{2}}} \leq 1 - \frac{q}{p_{c_{2}}} \end{matrix}$ (26) $\sum_{j \in J} z_{j} \leq q$ (27) $z_{j} \in {0, 1}, \forall j \in J$ (28) $H (λ) = max λ$ (29) $\begin{matrix} s . t . \\ λ + \frac{\sum_{i \in I} \sum_{j \in J} d_{ij} x_{ij}}{p_{f}} \leq 1 - \frac{H (z^{*})}{p_{f}} \end{matrix}$ (30) $λ + \frac{\sum_{i \in I} \sum_{j \in J} x_{ij}}{p_{c_{1}}} \leq 1 - \frac{\sum_{i \in I} a_{i}}{p_{c_{1}}}$ (31) $\sum_{j \in J} x_{ij} \leq a_{i}, \forall i \in I$ (32) $λ + \frac{\sum_{j \in J} s_{j}}{p_{c_{3}}} \leq 1 - \frac{r}{p_{c_{3}}}$ (33) $\sum_{j \in J} s_{j} \leq r$ (34) $\sum_{h \in T_{ij}} x_{ih} \leq a_{i} s_{j}, \forall i \in I, j \in J$ (35) $s_{j} \leq 1 - z_{j} \forall j \in J$ (36) $s_{j} \in {0, 1}, 0 \leq x_{ij} \leq a_{i}, \forall i \in I, j \in J,$ (37) $0 \leq λ \leq 1$ (38)

3 Solution methodology

The fuzzy RIMF is a bi-level programming problem. In order to solve this problem it is common to reformulate it into a single level programming problem [3, 17]. In the fuzzy RIMF, the lower level problem is convex (considering partial interdiction and fortification, i.e., 0 ≤ s_j, z_j ≤ 1), then the KKT conditions are not only necessary but also sufficient for the lower level problem. Therefore, we can consider the KKT optimality conditions instead of the lower level problem and this problem is solved by CPLEX 12.5.1. To this end, the Subsections 3.1 and 3.2 discuss about the single level problem is created by using Karush-Kuhn Tucker (KKT) conditions and the methodology for solving the fuzzy RIMF.

3.1 Using KKT conditions for fuzzy RIMF

In the fuzzy RIMF, KKT conditions for the lower level problem are necessary and sufficient, therefore, the lower level problem is replaced by its KKT conditions. Then new model becomes single level problem with quadratic constraints. Thus, by applying CPLEX with cplexqcp function, the single level problem is solved.

3.1.1 Replace the interdictor’s problem with its KKT conditions

Recall the interdictor’s problem: $max λ$ (39) $\begin{matrix} s . t . \\ λ + \frac{\sum_{i \in I} \sum_{j \in J} d_{ij} x_{ij}}{p_{f}} \leq 1 - \frac{H (z^{*})}{p_{f}} \end{matrix}$ (40) $λ + \frac{\sum_{i \in I} \sum_{j \in J} x_{ij}}{p_{c_{1}}} \leq 1 - \frac{\sum_{i \in I} a_{i}}{p_{c_{1}}}$ (41) $\sum_{j \in J} x_{ij} \leq a_{i}, \forall i \in I$ (42) $λ + \frac{\sum_{j \in J} s_{j}}{p_{c_{3}}} \leq 1 - \frac{r}{p_{c_{3}}}$ (43) $\sum_{j \in J} s_{j} \leq r$ (44) $\sum_{h \in T_{ij}} x_{ih} \leq a_{i} s_{j}, \forall i \in I, j \in J$ (45) $s_{j} \leq 1 - z_{j} \forall j \in J,$ (46) $0 \leq s_{j} \leq 1, 0 \leq x_{ij} \leq a_{i}, \forall i \in I, j \in J,$ (47) $0 \leq λ \leq 1$ (48)

3.1.2 KKT conditions

Let u₁, u₂, u₃, u₄, v_i, y_j and w_ij be the dual variables associated with the seven sets of constraints. $max λ$ (49) $\begin{matrix} s . t . \\ 1 - λ - \frac{\sum_{i \in I} \sum_{j \in J} d_{ij} x_{ij}}{p_{f}} - \frac{H (z^{*})}{p_{f}} \geq 0 (u_{1}) \end{matrix}$ (50) $1 - λ - \frac{\sum_{i \in I} \sum_{j \in J} x_{ij}}{p_{c_{1}}} - \frac{\sum_{i \in I} a_{i}}{p_{c_{1}}} \geq 0 (u_{2})$ (51) $a_{i} - \sum_{j \in J} x_{ij} \geq 0, \forall i \in I (v_{i})$ (52) $1 - λ - \frac{\sum_{j \in J} s_{j}}{p_{c_{3}}} - \frac{r}{p_{c_{3}}} \geq 0 (u_{3})$ (53) $r - \sum_{j \in J} s_{j} \geq 0, (u_{4})$ (54) $a_{i} s_{j} - \sum_{h \in T_{ij}} x_{ih} \geq 0, \forall i \in I, j \in J (w_{ij})$ (55) $1 - z_{j} - s_{j} \geq 0, \forall j \in J (y_{j})$ (56) $0 \leq s_{j} \leq 1, 0 \leq x_{ij} \leq a_{i}, \forall i \in I, j \in J,$ (57) $0 \leq λ \leq 1$ (58)

Applying the KKT conditions to the interdictor’s problem gives: $u_{1} + u_{2} + u_{3} = 0$ (59) $u_{1} \frac{d_{ij}}{p_{f}} + \frac{u_{2}}{p_{c_{1}}} + \sum_{i \in I} v_{i} = 0$ (60) $\frac{u_{3}}{p_{c_{3}}} + u_{4} - \sum_{i \in I} \sum_{j \in J} w_{ij} a_{i} + \sum_{j \in J} y_{j} = 0$ (61)

$u_{1} (1 - λ - \frac{\sum_{i \in I} \sum_{j \in J} d_{ij} x_{ij}}{p_{f}} - \frac{H (z^{*})}{p_{f}}) = 0$ (62) $u_{2} (1 - λ - \frac{\sum_{i \in I} \sum_{j \in J} x_{ij}}{p_{c_{1}}} - \frac{\sum_{i \in I} a_{i}}{p_{c_{1}}}) = 0$ (63) $v_{i} (a_{i} - \sum_{j \in J} x_{ij}) = 0$ (64) $u_{3} (1 - λ - \frac{\sum_{j \in J} s_{j}}{p_{c_{3}}} - \frac{r}{p_{c_{3}}}) = 0$ (65) $u_{4} (r - \sum_{j \in J} s_{j}) = 0$ (66) $w_{ij} (a_{i} s_{j} - \sum_{h \in T_{ij}} x_{ih}) = 0$ (67) $y_{j} (1 - z_{j} - s_{j}) = 0$ (68) $u_{1}, u_{2}, u_{3}, u_{4}, v_{i}, y_{j}, w_{ij} \leq 0, \forall i \in I, j \in J$ (69)

3.1.3 Reformulation

Solve for x_ij, s_j, λ, u₁, u₂, u₃, u₄, v_i, y_j, w_ij $min λ$ (70) $\begin{matrix} s . t . \\ λ + \frac{\sum_{j \in J} z_{j}}{p_{c_{2}}} \leq 1 - \frac{q}{p_{c_{2}}} \end{matrix}$ (71) $\sum_{j \in J} z_{j} \leq q$ (72) $λ + \frac{\sum_{i \in I} \sum_{j \in J} d_{ij} x_{ij}}{p_{f}} \leq 1 - \frac{H (z^{*})}{p_{f}}$ (73) $λ + \frac{\sum_{i \in I} \sum_{j \in J} x_{ij}}{p_{c_{1}}} \leq 1 - \frac{\sum_{i \in I} a_{i}}{p_{c_{1}}}$ (74) $\sum_{j \in J} x_{ij} \leq a_{i}, \forall i \in I$ (75) $λ + \frac{\sum_{j \in J} s_{j}}{p_{c_{3}}} \leq 1 - \frac{r}{p_{c_{3}}}$ (76) $\sum_{j \in J} s_{j} \leq r$ (77) $\sum_{h \in T_{ij}} x_{ih} \leq a_{i} s_{j}, \forall i \in I, j \in J$ (78) $s_{j} \leq 1 - z_{j}, \forall j \in J$ (79) $u_{1} + u_{2} + u_{3} = 0$ (80) $u_{1} \frac{d_{ij}}{p_{f}} + \frac{u_{2}}{p_{c_{1}}} + \sum_{i \in I} v_{i} = 0$ (81) $\frac{u_{3}}{p_{c_{3}}} + u_{4} - \sum_{i \in I} \sum_{j \in J} w_{ij} a_{i} + \sum_{j \in J} y_{j} = 0$ (82) $u_{1} (1 - λ - \frac{\sum_{i \in I} \sum_{j \in J} d_{ij} x_{ij}}{p_{f}} - \frac{H (z^{*})}{p_{f}}) = 0$ (83) $u_{2} (1 - λ - \frac{\sum_{i \in I} \sum_{j \in J} x_{ij}}{p_{c_{1}}} - \frac{\sum_{i \in I} a_{i}}{p_{c_{1}}}) = 0$ (84) $v_{i} (a_{i} - \sum_{j \in J} x_{ij}) = 0$ (85) $u_{3} (1 - λ - \frac{\sum_{j \in J} s_{j}}{p_{c_{3}}} - \frac{r}{p_{c_{3}}}) = 0$ (86) $u_{4} (r - \sum_{j \in J} s_{j}) = 0$ (87) $w_{ij} (a_{i} s_{j} - \sum_{h \in T_{ij}} x_{ih}) = 0$ (88) $y_{j} (1 - z_{j} - s_{j}) = 0$ (89) $0 \leq s_{j}, z_{j} \leq 1, 0 \leq x_{ij} \leq a_{i},$ (90) $u_{1}, u_{2}, u_{3}, u_{4}, v_{i}, y_{j}, w_{ij} \leq 0, \forall i \in I, j \in J,$ (91) $0 \leq λ \leq 1$ (92)

3.2 Solution algorithm for the crisp and fuzzy RIMF

We solve a random instance of crisp and fuzzy RIMF using CPLEX 12.5.1 Optimizer with cplexqcp function in MATLAB 7.6.0(R2008a). Indeed, a small instance of this problem is given and the single level problem is created by using Karush-Kuhn Tucker (KKT) conditions, then cplexqcp function is implemented for solving the single level problem in (70–90).

4 Computational results

In this section, we give some more details about the implementations as well as the experimental results of the CPLEX. In the first subsection, a random test instance is generated and then CPLEX is applied to solve it. Numerical results are reported in the subsequent subsection. The experiments have been conducted to compare the performance of the CPLEX for solving crisp and fuzzy RIMF on a standard DELL Vostro 1500 Laptop with 2.2 GHz processor, 2 GB RAM, and 160 GB of memory.

4.1 Generation of a random test instance

Our computational results are aimed at: (1) validating the fuzzy model through solving a small scale instance with exact algorithm; (2) comparing the novel model with the model described in Scaparra and Church [20]; (3) analyzing the impact of fuzziness the interdiction/fortification resources and demands at the level of service achieved. On the other hand, bi-level programming problems fall into the class of NP-hard problems. In order to solve the crisp and fuzzy RIMF, we converted the bi-level problem to a single level problem on using the KKT conditions and then utilized CPLEX solver. As a result, the authors can only solve instances of small size (the computing times sharply will increase as the size of instances become larger). Thus, a small instance of both models is considered. We conducted our experimental analysis on an instance of the fuzzy RIMF with 2 interdiction operation (r), 2 fortification operation (q), 10 existing facilities (m) and 100 customers (n) that their nodes are uniformly distributed on a circular area centered at the origin (0,0) with the radius R equal to 1000. Facilities location are uniformly dispersed on (m + 1) equidistant horizontal and vertical lines which hypothetically dice a square centered on the origin (0,0) with a side length of 1500. All coordinates (cx_i, cy_i) and (fx_j, fy_j) stand for the coordinates of customer node i and facility location j, respectively; dist (i, j) returns the Euclidean distance between these two; U (0, 1) stands for a uniform random number in the interval [0, 1); and finally U [lb, ub] symbolizes a random integer number between and inclusive of a lower bound lb and an upper bound ub.

Meanwhile, demand data of customers a_i have been taken from the interval [10, 100]. Demand data of customers and coordinates of customer and facility locations have been taken from the paper by Aras and Aksen [4]. Figure 1 visualize customer nodes and facility locations on the x-y plane for m = 10 and n = 100. Our instance characteristics are shown in Table 1.

4.2 Numerical results

The CPLEX is implemented on a test instance from the crisp and fuzzy RIMF. The crisp optimal solution allocates fortification and interdiction resources at vertices 3, 8 and 9, 10, respectively and an objective function 1.63e+06. In fuzzy model, we study the possibility of reducing this objective function at about 10000 units and the reduction of the demand and fortification/interdiction resources about 10, 1, 1 unit. Thus, we fix p_f = 20000 and p_{c
₁} = 20, p_{c
₂} = p_{c
₃} = 2 in such a way that a reduction of 10000 and 10,1,1 units have a degree of satisfaction 0.5. Then, the fuzzy solution allocates fortification and interdiction resources at vertices 3, 8 and 6, 10, respectively and with an objective function 1.61e+06 and a degree of satisfaction λ = 73.4%. So fuzzy model obtains a good solution. Table 2 compares solutions of both model: by reducing the demand at vertices 1, 17, 21, 26, 62, 65, 66 and 91, a objective function reduction of 1.97e + 004 units is achieved. More specifically, Table 2 shows the CPU times obtained for crisp and fuzzy instances. Both instances were solved to optimality using CPLEX solver. The difference in computing time between the two formulations was practically negligible.

5 Conclusions and future studies

In this paper, a mathematical model for ther-interdiction median problem with fortification (RIMF) with fuzzy demands and fortification/interdiction resources has been proposed. This fuzzy formulation give the degree of certainty of the uncertain solution obtained on uncertain data. For solving the fuzzy RIMF, we first convert it to a single level problem by using the KKT conditions. Next, we applied the CPLEX for a given test problem. Then, a random instance is obtained for illustration and cplexqcp function is utilized for solving the fuzzy RIMF that gets a satisfactory solution than crisp RIMF. The fuzzy RIMF is an NP-hard problem which is derived from the bi-level nature of the model. To apply the metaheuristic algorithms for this problem is an important future study.

Acknowledgments

We acknowledge the support of the research council of Shiraz University of Technology.

References

Aksen

and Aras

, A bilevel fixed charge location model for facilities under imminent attack, Computers & Operations Research 39 (2012), 1364–1381.

Aksen

, Akca

S.S.

and Aras

, A bilevel partial interdiction problem with capacitated facilities and demand outsourcing, Computers & Operations Research 41(1) (2014), 346–358.

Allende

G.B.

and Still

, Solving bilevel programs with the KKT-approach, Math Program Ser A 138 (2013), 309–332.

Aras

and Aksen

, Locating collection centers for distanceand incentive-dependent returns, Int J Prod Econ 111(2) (2008), 316–333.

Berman

and Drezner

, The p-median problem under uncertainty, European Journal of Operational Research 189 (2008), 19–30.

Canos

M.J.

, Ivorra

and Liern

, An exact algorithm for the fuzzy p-median problem, European Journal of Operational Research 116 (1999), 80–86.

Church

R.L.

and Scaparra

M.P.

, Protecting critical assets: The r-interdiction median problem with fortification, Geographical Analysis 39(2) (2007), 129–46.

Delgado

, Verdegay

J.L.

, Vila

M.A.

, Fuzzy linear programming: From Classical Methods to New Applications, Fuzzy Optimization: Recent Advances, Physica- Verlag, Heidelberg, 1994.

Donets

V.M.

, Decision Making and Programming, World Scientific Publishing Co. Pte. Ltd, 2003.

10.

Hakimi

S.L.

, Optimum locations of switching centers and the absolute centers and medians of a graph, Operations Research 12 (1964), 450–459.

11.

Liberatore

, Scaparra

M.P.

, Daskin

M.S.

, Hedging against disruptions with ripple effects in location analysis, Working Paper, No. 219, University of Kent, UK, 2010.

12.

Liberatore

, Scaparra

M.P.

and Daskin

M.S.

, Analysis of facility protection strategies against an uncertain number of attacks: The stochastic r-interdiction median problem with fortification, Computers & Operations Research 38(1) (2011), 357–366.

13.

Losada

, Scaparra

M.P.

, Church

R.L.

and Daskin

M.S.

, The multiple resource probabilistic interdiction median problem, Kent Business School Working Paper, No. 187, University of Kent, UK, 2010.

14.

Losada

, Scaparra

M.P.

and Church

R.L.

, On a bi-level formulation to protect uncapacitated p-median systems with facility recover time and frequent disruptions, Electronic Note in Discrete Mathematics 36 (2010), 591–598.

15.

Mayoya

D.K.

and Verdegay

J.L.

, P-median problems in a fuzzy environment, Mathware & Soft Computing 12 (2005), 97–106.

16.

Murty

K.G.

, Optimization Models For Decision Making, Junior Level Web-Book, 2003.

17.

Pilecka

, Combined reformulation of bilevel programming problems, Schedae Informaticae 21 (2012), 65–79.

18.

Revelle

C.S.

and Swain

R.W.

, Central facilities location, Geographical Analysis 2 (1972), 30–42.

19.

Rosenhead

, Elton

and Gupta

S.K.

, Robustness and optimality as criteria for strategic decisions, Operational Research Quarterly 23(4) (1972), 413–431.

20.

Scaparra

M.P.

and Church

R.L.

, A bilevel mixed-integer program for critical infrastructure protection planning, Computers & Operations Research 35 (2008), 1905–1923.

21.

Scaparra

M.P.

and Church

R.L.

, An exact solution approach for the interdiction median problem with fortification, European Journal of Operational Research 189(1) (2008), 76–92.

22.

Serra

and Marianov

, The p-median problem in a changing network: The case of Barcelona, Location Science 6 (1998), 383–394.

23.

Zadeh

L.A.

, Fuzzy sets, Information and Control l8 (1965), 338–353.

24.

Zhu

, Zheng

, Zhang

and Cai

, The r-interdiction median problem with probabilistic protection and its solution algorithm, Computers & Operations Research 40 (2013), 451–462.

25.

Zimmermann

H.J.

, Fuzzy mathematical programming, in: Gal

, Greenberg

H.J.

(Eds.) Advances in Sensitivity Analysis andarametric Programming, Kluwer Academic Publishers, Boston, 1997.