Compact Model for the Obnoxious p-Median Problem

Yen-I Chiang, Chang-Chun Lin

Department of Information Management, Chang Gung University, Taoyuan City.

DOI: 10.4236/ajor.2017.76026                

Abstract

Obnoxious facilities are those crucial to human living, yet antagonistic to the public or environment. However, the interactions between obnoxious facilities and their clients have been less frequently investigated. A state-of-the-art model for this problem involves numerous 0 - 1 variables, rendering it difficult to solve. This study aims at removing most of these 0 - 1 variables to enhanced model efficiency. A compact model is presented in this study, with the equivalence between the new and original models proved. Additionally, numerical tests were conducted to show that the proposed compact model is more efficient than the original one.

Keywords

Facility Location, Obnoxious Facility, 0 - 1 Programming, Facility Dispersion

1. Introduction

The urbanization of human populations and rapid technological advancements have driven the development of service facilities, such as nuclear power plants, waste dumpsites, incinerators, oil refineries, and airports. The location of public facilities is not only crucial to the overall operation costs and service quality, but also to the impact of these facilities on the surrounding environment. Most studies on location analysis have investigated desirable facilities that are acceptable to all communities, where the objective is usually to minimize a metric of distance or transportation cost. Typically, the facility number is confined by p in these problems. The most investigated p-facility problem might be the p-median problem [1] and the p-hub location problem [2] . The p-median problem entails minimizing the sum of distances from clients to facilities, whereas the p-hub location problem minimizes the transmission costs from clients to clients with the aids of hubs.

However, some facilities are associated with undesirable side effects antagonistic to people or the environment. The term “obnoxious facility” refers to a facility that is required by the society but unpleasant for communities near it. Therefore, the objective of locating obnoxious facilities is typically to maximize their distances from population centers or from each other. Early studies have investigated locating one facility in a continuous plane, discrete space, or network, with respect to existing facilities. According to Erkut and Neuman [2] , existing facilities can refer to clients, population centers, cities, or facilities that interact with new facilities. One survey was conducted by Cappanera [3] . More recently, studies have focused on multiple obnoxious facility problems. Obnoxious p-facility location problems can be regarded as anti-p-facility location problems.

Most research on locating obnoxious facilities has focused on dispersing the facilities, without considering the interactions between facilities and clients (or other existing facilities or population centers). Research has increasingly suggested that models might be impractical if they ignore the effects of obnoxious facilities on population centers or clients. Such studies include those of Cappanera et al. [4] , Alumur and Kara [5] , and Batta et al. [6] . A variant identified by Labbé et al. [7] as the obnoxious p-median problem (OpMP) has attracted the attention of researchers. Subsequently, Belotti et al. [8] proposed a branch-and-cut method for solving the OpMP. Recently, Colmenar et al. [9] attempted to solve the problem by using a greedy randomized adaptive search procedure (GRASP) algorithm. The algorithm was fast in solving large problems; however, the optimality of the obtained solutions remains undetermined.

For those not aware of coding or not frequently dealing with the facility location problem, an efficient programming model is irreplaceable. When implementing heuristics is both time-consuming and tricky, an easy-to-implement model that can provide the optimal solution appears to be more appealing than heuristic approaches, especially for medium-size problems. However, the model adopted by Labbé et al. [7] involves a high number of 0 - 1 variables, rendering it difficult to solve. Actually, most of the 0 - 1 variables are redundant; therefore, this study devised an equivalent model with the least 0 - 1 variables to more efficiently solve the OpMP.

2. Current Models

Facilities are required to disperse for several reasons such as the consideration of service-providing costs or security. Sometimes, the facilities are simply undesirable or semi-desirable to the communities surrounding them. Analytical models have been used for dispersing facilities. Most studies on obnoxious facility problems have focused on dispersing the facilities, without considering their interactions with other clients (or existing facilities in some studies). Moon and Chaudhry [10] briefly investigated the relationship between clients and facilities, and suggested that the two parts can be managed separately. Additionally, studies, such as [4] [5] [6] , have suggested that models might be impractical if they ignore the effects of obnoxious facilities on population centers or clients.

An OpMP variant, identified and proved to be NP hard by Labbé et al. [7] , has attracted the attention of researchers. Belotti et al. [8] subsequently devised a branch-and-cut method for solving the OpMP. The OpMP is formulated as follows. Let I denote the set of clients. Each client and facility pair is associated with a distance $d_{ij},\left(i,j\right)\in I\times J$ . The 0 - 1 variable $x_{ij}=1$ indicates client i is served by facility j; otherwise, $x_{ij}=0$ . Client i is assumed to be served by its nearest facility, and therefore a set $S_{ij}$ can be defined to record the sites that cannot serve client i when site j is selected. The following equation defines the set:

$S_{ij}=\left\{k\in J|\left(d_{ik}>d_{ij}\right)\text{or}\left(\left(d_{ik}=d_{ij}\right)\text{and}\left(k>j\right)\right)\right\}$ (1)

Accordingly, the model can be formulated as follows.

Model OpMP.

max ${\displaystyle {\sum }_{i\in I}{\displaystyle {\sum }_{j\in J}{d}_{ij}{x}_{ij}}}$ (2)

s.t. ${\displaystyle {\sum }_{j\in J}{y}_j}=p$ (3)

$x_{ij}\le y_j,\forall i\in I,\forall j\in J$ (4)

$y_j+{\displaystyle {\sum }_{k\in S_{ij}}{x}_{ik}\le 1},\forall i\in I,\forall j\in J$ (5)

$y_j,x_{ij}\in \left\{0,1\right\},\forall i\in I,j\in J$

The set J comprises all potential sites. The 0 - 1 variable $y_j=1$ indicates that site j is selected; otherwise, $y_j=0$ . The term $d_{jk}$ denotes the distance between sites j and k, and M is a large enough positive number.

Constraint (4) ensures that client i can be served only by an open facility j. When $y_j=1$ , Constraint (5) stipulates that client i cannot be served by any facility located at the sites of $S_{ij}$ . Consequently, each client can be served only by its nearest facility. In this regard, Model OpMP can be formulated to be more compact to enhance efficiency. Specifically, the 0 - 1 variable $x_{ij}$ is redundant. The following section demonstrates how the $x_{ij}$ variables can be eliminated from the model to improve efficiency.

3. Proposed Model

The OpMP model signifies the assignment of client i to facility j through variable $x_{ij}$ , such that $\left|I\right|\times \left|J\right|$ of these variables are required. However, knowing the distance from each client to the nearest open facility obviates the necessity of stipulating which facility is assigned. Therefore, $Z_i$ can be used to denote the shortest distance from client i to the nearest open facility. An alternative model for the OpMP can be formulated as follows:

Proposed model.

max ${\displaystyle {\sum }_{i\in I}{Z}_i}$ (6)

s.t. ${\displaystyle {\sum }_{j\in J}{y}_j}=p$ (3)

$Z_i\le d_{ij}+M\left(1-y_j\right),\forall i\in I,\forall j\in J$ (7)

$y_j\in \left\{0,1\right\},\forall j\in J$

Constraint (7) determines the supremum for $Z_i$ . If $y_j=0$ , then $Z_i$ is unbounded; otherwise, $Z_i\le d_{ij}$ . The equivalence between the proposed model and the OpMP model is demonstrated as follows.

Lemma 1: Let $F=\left\{j\in J|y_j=1\right\}$ , $\left|F\right|=p$ be a feasible solution to the OpMP model. Then, for all $k\in S_{ij}$ , $x_{ik}=0$ if $j\in F$ .

Proof: Constraint (5) stipulates that ${\displaystyle {\sum }_{k\in S_{ij}}{x}_{ik}}=0$ when $y_j=1$ . Namely, $x_{ik}=0$ if $k\in S_{ij}$ . QED.

Lemma 2: For each client $i\in I$ , there must be ${\displaystyle {\sum }_{j\in F}{x}_{ij}}\le 1$ .

Proof: Assuming that $x_{ij}=1$ and $x_{ik}=1$ , both $j,k\in F$ , and $k\ne j$ . If $d_{ik}\ge d_{ij}$ then $k\in S_{ij}$ , according to the definition of $S_{ij}$ . As indicated by Lemma 1, $x_{ik}$ must be 0. Otherwise, if $d_{ik}<d_{ij}$ , then $j\in S_{ik}$ according to the definition of $S_{ij}$ . Lemma 1 stipulates that $x_{ij}=0$ . Because either result contradicts the assumption, $x_{ij}$ and $x_{ik}$ cannot be simultaneously equal to 1. Therefore, the only possible result is ${\displaystyle {\sum }_{j\in F}{x}_{ij}}\le 1$ . QED.

Lemma 3: For each client $i\in I$ , ${\displaystyle {\sum }_{j\in J}{d}_{ij}{x}_{ij}}\le \min \left\{d_{ik}|k\in F\right\}$ .

Proof: Constraint (4) stipulates that $x_{ij}=0$ if $y_j=0$ , implying that ${\displaystyle {\sum }_{j\in J}{d}_{ij}{x}_{ij}}={\displaystyle {\sum }_{j\in F}{d}_{ij}{x}_{ij}}$ . According to Lemma 2, ${\displaystyle {\sum }_{j\in J}{x}_{ij}}\le 1$ for every i.

When ${\displaystyle {\sum }_{j\in F}{x}_{ij}}=0$ , there must be $x_{ij}=0$ for all $j\in J$ . The inequality ${\displaystyle {\sum }_{j\in J}{d}_{ij}{x}_{ij}}\le \min \left\{d_{ik}|k\in F\right\}$ is trivially true. When ${\displaystyle {\sum }_{j\in F}{x}_{ij}}=1$ , let ${\displaystyle {\sum }_{j\in J}{x}_{ij}}=x_{ij*}=1,j*\in J$ ; then ${\displaystyle {\sum }_{j\in J}{d}_{ij}{x}_{ij}}=d_{ij*}$ .

Without loss of generality, let $d_{ia}=\min \left\{d_{ik}|k\in F\right\}$ , where $a\in F$ . If $d_{ij*}>d_{ia}$ , then $j*\in S_{ia}$ , and $x_{ij*}=0$ according to Lemma 1; this contradicts the preposition $x_{ij*}=1$ . Because $d_{ia}=\min \left\{d_{ik}|k\in F_p\right\}$ , $d_{ij*}<d_{ia}$ cannot be true. The only possible result is $d_{ij*}=d_{ia}$ ; that is, the predicate ${\displaystyle {\sum }_{j\in J}{d}_{ij}{x}_{ij}}\le \min \left\{d_{ik}|k\in F\right\}$ is true. QED.

Lemma 4: For each client $i\in I$ , $Z_i\le \min \left\{d_{ik}|k\in F\right\}$ .

Proof: Constraint (7) implies that $Z_i\le d_{ij}$ for all $j\in F$ , including $a\in F$ , of which $d_{ia}=\min \left\{d_{ik}|k\in F\right\}$ . Namely, $Z_i\le d_{ia}=\min \left\{d_{ik}|k\in F\right\}$ . QED.

Proposition 1: The proposed model and the OpMP model are equivalent.

Proof: In the OpMP model, the constraints for node i and those for node $i^{\prime }$ are mutually independent. Therefore, given a feasible set $F$ , the objective func-

tion (2) is separable such that $\underset{F}{\text{sup}}{\displaystyle {\sum }_{i\in I}{\displaystyle {\sum }_{j\in J}{d}_{ij}{x}_{ij}}}={\displaystyle {\sum }_{i\in I}\left(\underset{F}{\text{sup}}{\displaystyle {\sum }_{j\in J}{d}_{ij}{x}_{ij}}\right)}$ . Although Lemma 3 stipulates that ${\displaystyle {\sum }_{j\in J}{d}_{ij}{x}_{ij}}\le \min \left\{d_{ik}|k\in F\right\}$ , there must be

$\underset{F}{\text{sup}}{\displaystyle {\sum }_{j\in J}{d}_{ij}{x}_{ij}}=\min \left\{d_{ik}|k\in F\right\}$ . Thus, the optimal value of the objective function (2) must be ${\displaystyle {\sum }_{i\in I}\left(\min \left\{d_{ik}|k\in F\right\}\right)}$ .

Similarly, the constraints for node $i$ and those for node $i^{\prime }$ are mutually independent in the proposed model. The objective function (6) equals

${\displaystyle {\sum }_{i\in I}\left(\underset{F}{\sup }{Z}_i\right)}$ . Because $\underset{F}{\sup }{Z}_i=\min \left\{d_{ik}|k\in F\right\}$ according to Lemma 4, the

optimal value of the objective function (6) is also ${\displaystyle {\sum }_{i\in I}\left(\min \left\{d_{ik}|k\in F\right\}\right)}$ . The objective functions (2) and (6) possess the same optimal value, and the models are thus equivalent. QED.

The proposed model has been proved to be equivalent to the OpMP model. Therefore, the proposed model in the present study is NP-hard because the OpMP model is NP-hard. Nevertheless, the proposed model is expected to be more efficient than the OpMP model. Still, both models suffer from a drawback that can compromise their applicability. Unlike the objective functions for locating desirable facilities, which tends to disperse the facilities, the objective function of an obnoxious facility problem distances the facilities from the clients and can cause the facilities to congregate. Belotti et al. [8] have observed that the OpMP model cannot achieve facility dispersion, and therefore suggested that facility dispersion can be obtained by imposing a minimum inter-facility distance. However, they did not implement and test such a model.

Let D be the required minimum distance between any two facilities; the constraint to impose D to the model can have various formulations. Constraint (8) stipulates that the distance between facility j and k be larger than D when both facilities are selected.

$D\le d_{jk}+M\left(2-y_j-y_k\right),\forall j,k\in J,j\ne k$ (8)

Because both D and $d_{jk}$ are constants, their relation need not be determined in the solving process. The critical condition is that there must be $2-y_j-y_k\ge 1$ when $d_{jk}<D$ . Otherwise, $y_j$ and $y_k$ are free to be either 0 or 1. This condition leads to the following formulation without D and $d_{jk}$ .

$y_k\le 1-y_j,\forall j,k\in J,d_{jk}<D$ (9)

Constraint (9) requires that facility j and k cannot be selected simultaneously when $d_{jk}<D$ . Further, constraints regarding $y_j$ can be aggregated to form another equivalent constraints. Let $N_j=\left\{y_k|k\in J,d_{jk}<D\right\}$ denotes the set of sites located in the neighborhood of facility j. Constraint (10) specifies that the facilities located in its neighborhood $N_j$ cannot be selected when facility j is selected.

${\displaystyle {\sum }_{k\in N_j}{y}_k}\le M\left(1-y_j\right),\forall j\in J$ (10)

Although these constraints have equivalent effects, their efficiencies might be different. The impacts of the distance constraint to the objective, as well as the efficiencies of these alternative formulations, are demonstrated in the next section.

4. Numerical Tests

This section presents a comparison of the proposed model with the OpMP model. Because most of the data sets used by Belotti et al. [8] are no longer available, this study adopted a simple way to randomly generate test problems. The coordinates of both client and facilities were randomly selected from the Euclidean square between (0, 0) and (100, 100). However, only problems with more than 100 clients and 100 sites were generated because small problems appeared to be too easy to differentiate between the models. The test problems were solved using Gurobi 6.0.4 on a personal computer with a Intel Core i7 CPU and 32-GB RAM. The allowable computation time was set to 12 h.

Belotti et al. [8] set the maximal p value to be $\lfloor \left|J\right|/2\rfloor$ , which is followed by Colmenar et al. [9] . The notation $\lfloor \left|J\right|/2\rfloor$ means the largest integer below $\left|J\right|/2$ , lacking practical significance, such a large p value is only meaningful for testing the model capability. This large p value means in practice that every facility is averagely responsible for only two clients, which might mean a large amount of redundant investment and operation costs. Therefore, the maximal p value was set to $\lfloor \left|J\right|/5\rfloor$ in this study.

Table 1 shows the computational results obtained by using the proposed model and the OpMP model, respectively. As expected, the proposed model is more efficient than was the OpMP model. When the problem difficulty increased with p, the optimal objective value decreased because a client is closer to a facility when the number of facilities increases. The results suggest that eliminating the redundant x variables yields a model more compact and efficient than the original OpMP model.

Table 2 shows the results obtained by using the proposed model with alternative distance constraints. The value of D was set to be $\lfloor \bar{D}\rfloor$ and $\lfloor \text{0}\text{.9}\bar{D}\rfloor$ , respectively. The parameter $\bar{D}$ for each of the test problem is the maximal distance between facilities, which can be easily obtained by using a simple model.

The objective values were largely compromised, which means that the facilities were located close to the client when the distance constraint was imposed. While Constraint (14) appeared to be less efficient than the other two, no significant difference between Constraints (12) and (13) can be identified. When

Table 1. Computational results by Model OpMP and the proposed model.

Table 2. Computation time by the proposed model with alternative distance constraints.

$D=\lfloor \bar{D}\rfloor$ , the computation time was shorter than the time without the distance constraints because the solution space was highly confined. When the solution space was enlarged by lowering D, the computation time increased rapidly. The experimental results reveal that the problem difficulty increased dramatically even though D was only slightly shorter than $\bar{D}$ .

5. Concluding Remarks

This study focuses on locating obnoxious facilities; specifically, the focus is on the problem that considers the interaction between clients and facilities. One state-of-the-art model for this regard involves a high number of 0 - 1 variables. The current study sought to provide an efficient model for the obnoxious p-median problem. The proposed model was determined to be equivalent to, but more efficient than, the OpMP model formulated by Labbé et al. [7] .

A common drawback of current models is that some of the selected facilities tend to congregate, which might be undesirable in certain decision-making scenarios. Adding a simple facility distance constraint can prevent congregation. This study has presented three different yet equivalent formulations for the distance constraint. Numerical experiments have demonstrated that the distance constraint was effective; however, the problem can become much more difficult to solve.

The proposed model is currently the most efficient formulation and can solve a medium-size problem. Users who confront such a problem can easily obtain the solution without having to implementing complicated heuristics. Nevertheless, when the problem becomes complicated due to increased problem size or unfavorable facility distance constraints, a heuristic approach is still unavoidable. Although the GRASP of Colmenar et al. [6] appeared to be fast for problems without the distance constraint, its performance on problems with the distance constraint remains undetermined. Therefore, a robust heuristic approach for the OpMP remains to be investigated.

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Mladenovic, M., Brimberg, J., Hansen, P. and Moreno-Pérez, J.A. (2007) The p-Median Problem: A Survey of Metaheuristic Approaches. European Journal of Operational Research, 179, 927-939. https://doi.org/10.1016/j.ejor.2005.05.034
[2]	Erkut, E. and Neuman, S. (1989) Analytical Models for Locating Undesirable Facilities. European Journal of Operational Research, 40, 275-291. https://doi.org/10.1016/0377-2217(89)90420-7
[3]	Cappanera, P. (1999) A Survey on Obnoxious Facility Location Problems. Technical Report TR-99-11, Department of Information, University of Pisa. http://compass2.di.unipi.it/TR/files/TR-99-11.ps.gz
[4]	Cappanera, P., Gallo, G. and Maffioli, F. (2003) Discrete Facility Location and Routing of Obnoxious Activities. Discrete Applied Mathematics, 133, 3-28. https://doi.org/10.1016/S0166-218X(03)00431-1
[5]	Alumur, S. and Kara, B.Y. (2007) A New Model for the Hazardous Waste Location-Routing Problem. Computers & Operations Research, 34, 1406-1423. https://doi.org/10.1016/j.cor.2005.06.012
[6]	Batta, R., Lejeune, M. and Prasad, S. (2014) Public Facility Location Using Dispersion, Population, and Equity Criteria. European Journal of Operational Research, 234, 819-829. https://doi.org/10.1016/j.ejor.2013.10.032
[7]	Labbé, M., Maffioli, F., Ndiaye, M. and Belotti, P. (2001) Obnoxious p-Median Problems: Valid Inequalities and a Branch-and-Cut Approach. The OR Peripatetic Post-Graduate Programme, Paris, 26-29. https://pdfs.semanticscholar.org/2b02/b79302fd8003cb838999a7df73b8a7b5d73a.pdf
[8]	Belotti, P., Labbé, M., Maffioli, F. and Ndiaye, M.M. (2007) A Branch-and-Cut Method for the Obnoxious p-Median Problem. 4OR, 5, 299-314. https://doi.org/10.1007/s10288-006-0023-3
[9]	Colmenar, J.M., Greistorfer, P., Martí, R. and Duarte, A. (2016) Advanced Greedy Randomized Adaptive Search Procedure for the Obnoxious p-Median Problem. European Journal of Operational Research, 252, 432-442. https://doi.org/10.1016/j.ejor.2016.01.047
[10]	Moon, I.D. and Chaudhry, S.S. (1984) An Analysis of Network Location Problems with Distance Constraints. Management Science, 30, 290-307. https://doi.org/10.1287/mnsc.30.3.290