The obnoxious facilities planar p-median problem

Abstract

In this paper, we propose the planar obnoxious facilities p-median problem. In the p-median problem the objective is to find p locations for facilities that minimize the weighted sum of distances between communities and their closest facility. In the obnoxious version, we add constraints that each facility must be located at least a certain distance from a partial set of communities because they generate nuisance affecting these communities. The resulting problem is extremely non-convex and traditional nonlinear solvers such as SNOPT are not efficient. An efficient solution method based on Voronoi diagrams is proposed and tested. We also constructed the efficient frontiers of the test problems, showing the trade-off between the required distance and the p-median objective, to assist the planers in making location decisions.

1 Introduction

Drezner et al. (2018) proposed the single facility median problem, (the Weber problem, Weber 1909; Drezner et al. 2002; Wesolowsky 1993; Love et al. 1988), with a minimum distance D requirement between the facility and communities. This is a practical and useful model when the facility is “obnoxious” to the communities (e.g., landfills, noisy and polluting factories, airports), and should not be located near them. However, we are interested in minimizing the operating cost of such facilities which is modeled as the weighted sum of distances. For example, operating cost of landfills depends on the total distance traveled by the disposal trucks. In this paper, we investigate the multiple facility model. The unrestricted model in the network or discrete space is termed the p-median model (for example, Daskin and Maass 2015), and in the plane, it is also called the multi-source Weber problem (Brimberg et al. 2000; Kuenne and Soland 1972). In this paper, we propose to add to the p-median model a requirement of a minimum distance D between some communities and facilities.

Fig. 1

Configuration of 100 communities for various values of D

The problem is non-convex and may have many local optima depending on the value of D; see Fig. 1. The feasible area for $D=0$ is convex, and the feasible region is non-convex and shrinks as D increases. If D is quite small the feasible region is well connected and solving the unconstrained p-median problem may constitute a good starting solution for a follow-up phase incorporating the obnoxious constraints. When D is large, the whole convex hull of the communities becomes infeasible and the solution is to locate the facilities at the periphery of the infeasible region.

The most challenging problem seems to be moderate values of D. For a moderate value of D, the feasible region is a union of disconnected areas. If a starting solution includes a facility in one of these disconnected feasible areas, standard nonlinear procedures will not move such a facility to another feasible area. To get a “good” solution, the feasible areas for the facilities need to be properly selected.

The proposed model can be classified as an obnoxious facility model. Obnoxious location models involve locating one or more facilities as far as possible from a set of communities. The problem is investigated on: (i) the plane (Hansen et al. 1981; Goldman and Dearing 1975a, b; Shamos and Hoey 1975; Antunes et al. 2008; Eiselt and Marianov 2015; Drezner et al. 2019b; (ii) a network or discrete space (Church and Garfinkel 1978; Erkut and Neuman 1989; Church and Meadows 1979; Batta and Chiu 1988; (iii) location in the interior of a network (Drezner and Wesolowsky 1996; Drezner et al. 2009; (iv) location on the sphere (Drezner and Wesolowsky 1983). For recent reviews of obnoxious facility location models see Church and Drezner (2020) and Carrizosa and Toth (2019). In most applications, the nuisance propagates “by air” and not along network links and thus are best modeled using Euclidean distances. Many other objectives such as squared Euclidean distance, p-center, competitive facilities locations can yield useful models by adding the minimum distance requirement.

Drezner et al. (2019b) considered the location of p obnoxious facilities in the plane maximizing the minimum distance between facilities and demand points. No consideration of providing good service by the closest facility, which is the objective function in this paper, is included in the Drezner et al. (2019b) model.

A related field of research is location among forbidden regions. In forbidden regions models, a facility is not allowed to be located in some regions in the plane. Communities may be located there and travel is allowed through such regions. Therefore, the distance measure is not altered. Papers that consider forbidden regions solve problems with convex objectives (Hamacher and Schöbel 1997; Aneja and Parlar 1994; Batta et al. 1989; Butt and Cavalier 1996; Katz and Cooper 1981). The optimal solution without forbidden regions can be found. If it is not in a forbidden region, this is the optimal solution. For convex problems, it is shown that if the unconstrained solution is in a forbidden region, then the optimal solution is on the boundary of a forbidden region. This property does not necessarily hold for non-convex objectives. For example, the second-best local optimum for the unconstrained problem may be feasible and better than all solutions on the boundaries of the forbidden regions.

The paper is organized as follows. In the next section, the model is formulated. In Sect. 3, we show how to find the feasible area and in Sect. 4 we detail the proposed solution algorithm. In Sect. 5, we test the solution algorithm and compare it to standard nonlinear solvers on a set of test problems. In Sect. 6, we find and depict the efficient frontier. In Sect. 7, we investigate and solve the problem in the State of Colorado. We conclude the paper and propose ideas for future research in Sect. 8.

2 Model formulation

Two sets of points exist in the plane. The set $N_d$ includes points that generate demand $w_i>0$ for $i\in N_d$, and the set $N_o$ includes points that the facility is obnoxious to them. The set of all n points is $N=N_d\cup N_o$. It is possible that $N_d=N_o$, when all points generate demand and are also negatively affected by the facilities, or $N_d\cap N_o=\emptyset$, and all possibilities in between.

A set $N{=N_d\cup N_o}$ of n communities located in the plane with an associated weight $w_i\ge 0$ are given. The Euclidean distance between demand point i and location Y is $d_i(Y)$. The required minimum distance is a given D. The problem is to find p locations for facilities $X=\{X_j=(x_j,y_j), 1\le j\le p\}$ such that:

$$\begin{aligned} \begin{array}{ll} \displaystyle &{}\quad \min \limits _X \sum \limits _{i\in N_d}w_i\min \limits _{1\le j\le p}\left\{ d_i(X_j)\right\} \\ \\ \displaystyle \text{ Subject } \text{ to: }&{} \\ \\ \displaystyle &{} \quad d_i(X_j)\ge D \text{ for } i\in N_o;\,1\le j\le p \end{array} \end{aligned}$$

(1)

3 Finding the feasible areas

Drezner et al. (2018) proposed the “Big Arc Small Arc” algorithm for solving the single facility location problem which has a convex objective function. All feasible arcs on the periphery of circles are found and evaluated by a global optimization algorithm. Lower and upper bounds are found on each feasible arc. The upper bound is a feasible solution at a point on the arc. The arcs are scanned in the order of their lower bound. If the lower bound of an arc is smaller than the best found solution, the arc is divided into two arcs and the iterations continue. If the lower bound times $1+\epsilon >0$ is greater than the best known solution, the arc is discarded. The iterations are stopped when all arcs are eliminated. This approach is similar to many global optimization algorithms widely used to solve non-convex location problems: Big Square Small Square (Hansen et al. 1981), Big Region Small Region (Hansen et al. 1995), Big Triangle Small Triangle (Drezner and Suzuki 2004; Suzuki 2019), Big Cube Small Cube (Schöbel and Scholz 2010), Big Segment Small Segment (Berman et al. 2011).

Fig. 2

Infeasible areas for $n=100$, $D=0.95$, and 50 feasible Voronoi points

Fig. 3

Infeasible areas for $n=500$, $D=0.42$, and 245 feasible Voronoi points

Fig. 4

Infeasible areas for $n=1000$, $D=0.3$, and 473 feasible Voronoi points

Table 1 The first 50 Voronoi points ($n=100$)

For a convex objective, if the optimal location of the facility is not feasible (if it is feasible it is optimal for the constrained problem), then the optimal solution must be on a feasible arc of a circle. However, for multiple facilities, this property does not necessarily hold because the problem is not convex. Some facilities may be located on feasible arcs and some may be located in “open” feasible areas. We therefore propose a different approach for heuristically solving the multiple facility version of this problem.

In order to find the distinct feasible areas, we employ the concept of the Voronoi diagram (Suzuki and Okabe 1995; Okabe et al. 2000; Voronoï 1908; Aurenhammer et al. 2013) generated by the points in $N_o$. The plane is partitioned into triangles (termed Delaunay triangulation; Lee and Schachter 1980) so that the centers of the triangles are equidistant from the three vertices of the triangles (which belong to $N_o$) and are termed Voronoi points. These Voronoi points can be found by Mathematica (Wolfram 2020) and other available software (Ohya et al. 1984; Sugihara and Iri 1992). Each point (a vertex of a triangle) is closest to a Voronoi point located at that triangle. There are V Voronoi points. Voronoi point $V_j$ is at distance $D_j$ from the closest community in $N_o$ for $j=1,\ldots V$. The Voronoi points can be sorted from the largest minimum distance down creating a list of distances $D_1\ge D_2\ge \cdots \ge D_V$. Shamos and Hoey (1975) used this scheme to find the location for a facility which is farthest from all communities by choosing the Voronoi point with minimum distance $D_1$. Drezner et al. (2019b) used the list of Voronoi points to heuristically solve a multiple obnoxious facilities problem.

In Figs. 2, 3 and 4, the infeasible areas are depicted for the problems used in the computational experiments with $n=100$ communities; $D=0.95$, $n=500$; $D=0.42$, and $n=1000$ with $D=0.3$. The feasible Voronoi points (the Voronoi points for which $D_i\ge D$) are marked by black dots. One may have the impression that many feasible Voronoi points are inside the gray infeasible regions. However, they are located in very small feasible regions so that the white area is smaller than the black dot. It will be very difficult for conventional approaches to identify such small feasible areas without identifying the Voronoi points.

Fig. 5

The triangle example

To illustrate this phenomenon, consider an equilateral triangle, whose vertices are communities, depicted in Fig. 5 for which the distance to the Voronoi point $D_i$ is 1.05D. The radii of the circles (infeasible areas) are D. The feasible area is at the center of the triangle outside the circles. The bottom side of the long narrow triangle is $2D\sin \theta$. The distance to the center of the tiny triangle (the Voronoi point) is at distance $D_i$ from the top vertex. Therefore, $D(1-\cos \theta )+D_i-D=\frac{1}{\sqrt{3}}D\sin \theta$ leading to the relationship $\frac{1}{\sqrt{3}}\sin \theta +\cos \theta =\frac{D_i}{D}$. Multiplying by $\frac{\sqrt{3}}{2}$ and solving for $\theta$:

$$\begin{aligned} \frac{1}{2}\sin \theta +\frac{\sqrt{3}}{2}\cos \theta =\frac{\sqrt{3}D_i}{2D}\,\rightarrow \,\sin \left( \frac{\pi }{3}+\theta \right) =\frac{\sqrt{3}D_i}{2D}\,\rightarrow \,\theta =\arcsin \left\{ \frac{\sqrt{3} D_i}{2D}\right\} -\frac{\pi }{3}. \end{aligned}$$

Note that if $D_i>\frac{2}{\sqrt{3}} D$ the circles do not intersect.

The area of the small triangle is $\sqrt{3} D^2\sin ^2\theta$. The area of the part of the circle which is inside the triangle (non-feasible) is $D^2\theta -D^2\sin \theta \cos \theta$. The area A of the feasible region is therefore

$$\begin{aligned} A= & {} \sqrt{3} D^2\sin ^2\theta -3[D^2\theta -D^2\sin \theta \cos \theta ] =D^2\left\{ \sqrt{3} \sin ^2\theta -3[\theta -\sin \theta \cos \theta ]\right\} \nonumber \\= & {} 2\sqrt{3}D^2\sin \theta \left[ \frac{1}{2}\sin \theta +\frac{\sqrt{3}}{2}\cos \theta \right] -3\theta D^2=3D[D_i\sin \theta -D\theta ]\,. \end{aligned}$$

(2)

Assuming a small $\theta$, $\theta \approx \sin \theta \approx \sqrt{3}\frac{D_i-D}{D}$, and thus by approximating Eq. (2):

$$\begin{aligned} A\approx 3\sqrt{3} (D_i-D)^2. \end{aligned}$$

(3)

For example, for $D=1\ D_i=1.05$, the exact area is 0.013727 and the approximated area is 0.012990. For $D=1\ D_i=1.01$ the areas are 0.000525 and 0.000520. The exact results were confirmed by simulating randomly generated one billion points.

The largest distance $d_{\max }$ between the Voronoi point and the feasible area is

$$\begin{aligned} d_{\max }=\frac{D}{\sqrt{3}}\sin \theta \approx D_i-D. \end{aligned}$$

(4)

For $D=0.95$ and $n=100$ there are 10 Voronoi points satisfying $0.95<D_i< 0.95\times 1.05=0.9975$ (see Table 1). These points are at most at distance 0.05 from the boundary of their feasible area and clearly appear as black points surrounded by a gray area in Fig. 2. Recall that the square size is 10 by 10, and such a distance is $\frac{1}{200}$ of the square’s side. The side of the square in the figure is about 4 in. and thus this distance is 0.02 in. or 0.5 mm.

4 The proposed solution algorithm

We propose to find all the Voronoi points, identify which ones are feasible, find the p feasible Voronoi points that yield the best value of the objective function, and use these points as a starting solution for nonlinear solvers.

All the Voronoi points for which $D_i\ge D$ form a region of feasible area (if $D_i=D$ the region is one point). Actually, if $D> D_1$, the whole convex hull of points is infeasible. Suppose that the first $m\ge p$ sorted Voronoi points satisfy $D_i\ge D$. We propose to find the p-median solution for facilities located at p of these m Voronoi points and use it as a starting (feasible) solution for nonlinear optimization procedures. This is a discrete p-median problem that can be solved by the following Mixed Binary Linear Program (MBLP) or Binary Linear Program (BLP) (Daskin 1995; ReVelle and Swain 1970).

Let $d_{ij}$ be the distance between community i and potential location (Voronoi point) j. We minimize the value of the objective function by the best selection of the set P of the p out of the m potential locations. The standard formulation for the discrete p-median problem is:

$$\begin{aligned} \min \limits _{P}\left\{ \,\sum \limits _{i\in N_d}w_i\min \limits _{j\in P}\{d_{ij}\}\,\right\} \end{aligned}$$

(5)

Let $x_j\in \{0,1\}$ be a binary variable. $x_j=1$ if location j is selected and otherwise not selected. For MBLP $0\le y_{ij}\le 1$ are continuous variables for $i\in N_d$, $j=1,\ldots ,m$. For BLP $y_{ij}\in \{0,1\}$. The MBLP/BLP optimization problem is:

$$\begin{aligned} \begin{array}{rcl} &{}\min \left\{ \sum \limits _{i\in N_d}\sum \limits _{j=1}^m\left[ w_id_{ij}\right] y_{ij}\right\} &{}\\ \text{ subject } \text{ to: }&{}&{}\\ &{}\sum \limits _{j=1}^mx_j=p&{}\\ &{}y_{ij}\le x_j&{} \text{ for } i\in N_d;\,j=1,\ldots m\\ &{}\sum \limits _{j=1}^my_{ij}=1&{} \text{ for } i\in N_d\\ &{}x_j\in \{0,1\}&{}\\ \text{ For } \text{ MBLP: }&{}y_{ij}\ge 0&{}\\ \text{ For } \text{ BLP: }&{}y_{ij}\in \{0,1\}&{} \end{array} \end{aligned}$$

(6)

Note that this formulation can be used for any distance measure. In the solution $y_{ij}\in \{0,1\}$ because for each point $y_{ij}=1$ for the closest facility and all others are zeros. If there is a tie in the minimum distance, $y_{ij}$ can be non-integer but the objective function is the same as the integer solution. Therefore, an equivalent formulation is to require that $y_{ij}$ are binary variables yielding a BLP formulation. The MBLP and BLP formulations were solved by CPLEX (CPLEX, IBM ILOG 2019). The BLP performed faster and thus was used in the computational experiments.

4.1 The algorithm

• 1. Find all Voronoi points generated by the set of points the facility is obnoxious to, and for each one find its minimum distance to the generating points.

• 2. Remove from the list of Voronoi points those whose minimum distance is less than D getting a list of m potential feasible locations.

• 3. Solve the MBLP/BLP optimization (in future comparisons) for the list of potential locations getting a starting feasible solution.

• 4. Solve (1) by SNOPT from this starting solution.

We concentrate on medium values of D which are the most difficult to solve. We therefore ignore the possibility that a facility will be located outside the convex hull. It may be an issue if m is not much larger than p. It is, of course, an issue if $m<p$. It is possible to add all feasible intersection points which are outside the convex hull of points. However, this may increase the size of the BLP (6) so it may have to be solved heuristically rather than optimally.

5 Computational experiments

In all the computational experiments, it is assumed that $N_d=N_o=N$. The number of communities is denoted by n. CPLEX (CPLEX, IBM ILOG 2019) and SNOPT (Gill et al. 2005) were run on an Amazon EC2 instance with 32 CPUs and 70 GB of RAM. The BLP was implemented with the OPL and run on IBM’s CPLEX Optimization Studio 12.8 environment. We used the default CPLEX MIP solver settings. The unconstrained p-median problem algorithm was coded in FORTRAN using double precision arithmetic. The programs were compiled by an Intel 11.1 FORTRAN Compiler with no parallel processing. They were run on a desktop with the Intel i7-6700 3.4 GHz CPU processor and 16 GB RAM.

To allow for easy replication in future comparisons, we tested randomly generated instances by the method proposed in Drezner et al. (2019a, b). A sequence of integer numbers in the open range (0, 100,000) is generated. A starting seed $r_1$, which is the first number in the sequence, is selected. The sequence is generated by the following rule for $k\ge 1$:

• Set $\theta =12219 r_k$.

• Set $r_{k+1}=\theta -\lfloor \frac{\theta }{100000}\rfloor \times 100{,}000$, i.e., $r_{k+1}$ is the remainder of dividing $\theta$ by 100,000.

For the x coordinates, we used $r_1=97$ and for the y-coordinates we used $r_1=367$. To define the coordinates in a 10 by 10 square, $r_k$ is divided by 10,000.

The 50 Voronoi points (out of the $V=202$ Voronoi points) with the largest values of $D_i$ for the $n=100$ problem are depicted in Table 1. These are all the Voronoi points whose $D_i\ge 0.95$ miles (in a 10 by 10 square mile). Recall that all Voronoi points for which $D_i\ge D$ are feasible.

For the p-median problem we use all $w_i=1$. 1000 points are generated and the first n points selected. Three value of n were tested, $n=100,500,1000$ with corresponding values of $D=0.95,0.42,0.3$. These values of D yielded 50, 245, and 473 feasible Voronoi points, respectively. See Figs. 2, 3 and 4.

We first solved the unconstrained p-median for $p=2,3,4,5,10,15,20$, and $n=100,500,1000$ communities, by the best available heuristic solution method (Drezner and Drezner 2020). Each instance was solved 10 times from randomly generated starting solutions and the best solution was found in all 10 replications for every instance. Then we found by solving BLP (6) the optimal obnoxious p-median solutions when facilities are restricted to the set of feasible Voronoi points. These solutions where used as starting solutions for applying SNOPT (Gill et al. 2005) once. The SNOPT results using the BLP results as starting solutions serve as bench mark values for the obnoxious p-median solutions.

We then applied SNOPT from 1000 randomly generated starting solutions for each instance. This process took about 1000 times longer and yielded very poor results. These results of random starting solutions (feasible or not) are not reported. We therefore randomly generated 100,000 random points and selected a subset of these getting a set of feasible points for each n. We then solved the obnoxious p-median problem by SNOPT using randomly selected p points from the subset of feasible points as starting solutions. This approach produced significantly better results than those obtained by randomly generating 1000 starting solutions, whether feasible or not. However, run times are still 1000 longer than starting from Voronoi points.

Table 2 Objective function results

The results of these experiments are depicted in Table 2. Using the BLP (6) results as starting solutions performed best both in terms of run times and quality of results. Run times (not reported) are about 1000 times shorter. The random results matched the BLP starting solution results in only one instance out of 21 instances and are as much as 15% higher.

The reason for the underperformance of randomly selecting feasible points is that there are many very small feasible areas. The black dots in Figs. 2, 3 and 4 represent Voronoi points which are all feasible but many look like they are located in an infeasible gray area. When a Voronoi point distance to the closest community is $D_i$, see Fig. 5, the feasible area by Eq. (3) is approximately $5(D_i-D)^2$ . For $D=0.95$ and $D_i=0.96$ the area is about $5\times 10^{-4}$ which is about 1/200,000 of the area of the 10 by 10 square. There are three Voronoi points for which $D_i<0.96$; see Table 1. The feasible area has an area of about 5. Therefore, the probability that the generated feasible point is in that small area is about $10^{-4}$. Even when 1000 random feasible points are generated, the chance that even one point is in such a feasible area is very low (9.5%). Therefore, if a good solution has some facilities located in such small areas, it is likely to be missed even when 1000 random feasible starting solutions are used. Even if a particular small area is selected, it is unlikely that the additional required areas for locating other facilities will all be selected as well. When the Voronoi points are used, there is a candidate location in every feasible area and the BLP selects the best set of candidate locations. Note also that if the good solution has a point in a small area, the final location of this facility is very close to the Voronoi point, Eq. (4), and thus the value of the objective function changes very little and the “correct” feasible regions are likely to be selected by the BLP.

6 The efficient frontier

An interesting useful tool to support our model is the efficient frontier. For each D we find the best solution and the efficient frontier will give the planner a trade-off between the minimum distance D and the total cost. They may choose the best strategy by their own judgment. We constructed the efficient frontiers by applying SNOPT on the best Voronoi points. The efficient frontiers for $n=100, 500, 1000$ are depicted in Figs. 6, 7 and 8. As the number of facilities p increases, the deterioration of the value of the objective function is faster when D increases.

Fig. 6

The efficient frontiers for $n=100$

Fig. 7

The efficient frontiers for $n=500$

Fig. 8

The efficient frontiers for $n=1000$

For example, in Fig. 6 the efficient frontiers for $p=2,3,4,5,10,15,20$, $n=100$ are depicted. Suppose that the plan is to build $p=15$ facilities. When no minimum distance constraints are imposed ($D=0$, the black circle in the figure), the objective function is 74.47 (see Table 2). When a minimum distance of $D=0.2$ is required, the objective function increases a bit to 75.04 which can be easily justified. When the planner wishes not to exceed a cost of 80 (see Fig. 6), a minimum distance $D=0.43$ is possible yielding an objective of 79.81. $D=0.44$ has an objective of 80.03. If the planner is forced not to have facilities closer than $D=1$ mile from the communities, the objective function is almost doubled to 136.74, and for $D=1.1$ it increases to 173.46. The planner has to apply his best judgment and select the best trade-off option.

7 Case study: locating obnoxious facilities in the state of Colorado

There are 355 municipalities (cities) and 55 national and state parks in the state of Colorado for a total of 410 affected communities. We obtained the list and coordinates of cities and parks, and population counts, in Colorado from Wolfram Alpha Computational Knowledge Engine (Wolfram Alpha LLC, 2020. Wolfram|Alpha).

The map of the cities, the parks and the best found solution for locating 20 facilities at least 15 miles away from all 410 cities and parks is depicted in Fig. 9. The weights for the demand in the 355 cities are proportional to the populations. To get presentable values (not in the millions) we divided the weights by 663,862, the population of the largest city. The total Colorado population is 4,552,352. The demand at parks is zero so that in this case the set of points generating demand is different from the set of points affected by the negative impact of the facilities. The Voronoi points and the infeasible areas (shaded) are depicted in Fig. 10. The large concentration of urban areas in the middle north of the state is infeasible in its entirety so no facilities can be established there to service these communities. Six facilities are located around the large metropolitan area at feasible points closest to this population center.

In Table 3 we depict the results of the Voronoi approach as well as the best results by applying SNOPT from 1000 randomly generated feasible starting solutions. In one case, starting from 1000 random feasible solutions yielded a slightly better solution. However, the average above the best known solution is 0.03%, while the average of the best solution from 1000 feasible starting solutions is 4.13% above the best known solution and ran about 1000 times longer.

Fig. 9

Colorado cities, parks, and 20 facilities

Fig. 10

Feasible areas and Voronoi points

Table 3 Results starting with Voronoi points and best of 1000 random feasible points

8 Conclusions

In this paper, we proposed the obnoxious facilities p-median problem. A minimum given distance D between facilities and a partial set of communities is required. The objective is to find p locations for facilities that minimize the weighted sum of distances between communities and their closest facility subject to the minimum distance requirement. The resulting problem is extremely non-convex and traditional nonlinear solvers applied in a multi-start approach do not perform well. An efficient solution method based on Voronoi diagrams is proposed and tested. It significantly outperformed standard nonlinear solvers both in run times and quality of the solutions.

We also constructed the efficient frontiers of the test problems to assist planners in making location decisions. As expected, when the minimum required distance between facilities and communities increases, the objective function deteriorates. The planner can use the efficient frontier in order to select the best trade-off solution.

8.1 Suggestions for future research

The obnoxious p-median problem can be formulated for other distance measures such as Manhattan ($\ell _1$) distances, general $\ell _p$ distances or location on the sphere. The methodology developed in this paper can be applied to such problems as long as the Voronoi points for such metrics can be obtained.

In a network environment, we can replace the Voronoi points by two points on links connecting negatively affected communities that are at least 2D long. If such a link is less than 2D long, the whole link is infeasible. Links that are $B>2D$ long have a segment centered at the center of the link of length $B-2D$ and its endpoints are candidate locations for the facilities. The problem reduces to the discrete p median problem. Another variant is locating facilities on a planar network but distances to demand points, that may be off the network, are measured by the Euclidean norm. A single facility location model in this setting is proposed and solved in Drezner et al. (2016).

Locating obnoxious facilities minimizing other objectives can also apply the Voronoi points approach. For example, the obnoxious p-center problem is defined in a similar fashion. In the standard p-center problem (Kariv and Hakimi 1979; Chen and Chen 2009; Calik et al. 2015), rather than minimizing the sum of the weighted distances to the closest facility, the objective is minimizing the maximum weighted distance to the closest facility. The BLP formulation is changed to minimizing L and adding constraints $w_{i}d_{ij}y_{ij}\le L$. The MBLP formulation cannot be used because we must have $y_{ij}\in \{0,1\}$.

The conditional version of the problem (Minieka 1980; Berman and Simchi-Levi 1990; Ogryczak and Zawadzki 2002) can be useful in many circumstances. This means that several facilities already exist in the area and p additional facilities need to be located. Each community receives its services from the closest facility which may already exist or is a new one. The objective is to minimize total cost subject to distance constraints. The BLP formulation is modified so that the existing facilities are assigned $x_j=1$ and are no longer variables, and the new facilities are restricted to the Voronoi points. An interesting variant is that some of the existing facilities violate the distance constraints and should be considered for removal.