Continuous Facility Location Problems

Abstract

In this chapter we review continuous location models. Location models involve locating one or more facilities among a given set of demand points to achieve a certain objective. For example, locating a warehouse that serves a set of stores each requires a given delivery volume. The objective is minimizing the total delivery cost which is the sum of distances, weighted by the volume. In discrete location models, a finite set of potential locations for facilities is given. In continuous location models, facilities can be located anywhere in the plane, or in a limited region with an infinite number of potential locations.

1 Introduction

Facility location models investigate the location of one or more facilities, among a set of demand points, to achieve a certain objective. Discrete location models assume that there is a set of potential locations for the facilities, and a partial subset of locations is selected for locating them. Continuous location problems assume that facilities can be located anywhere (usually in the plane) or in a given area, and thus the set of candidate locations is “infinite”. In this chapter we review continuous location models.

One of the earliest objectives investigated in the literature is minimizing the weighted sum of distances between the demand points and their closest facility. For example, locating warehouses to serve a given set of outlets. The cost of service is proportional to the distance and if there are two or more facilities, service to a demand point is provided by the closest facility.

Another objective is minimizing the maximum distance to the closest facility so that the customer who gets the worst service is getting the service as quickly as possible. For example, location of emergency facilities, such as ambulances or fire trucks, so that the farthest customer is as close as possible to a facility. Some types of facilities such as polluting or noisy factories, landfills, airports, have a negative impact on neighborhoods and thus should be located as far as possible from communities. Such facilities are termed “obnoxious” facilities. Another objective is to locate facilities to provide equitable service to all demand points. Covering models attempt to cover as many demand points as possible within a given distance from the closest facility. Competitive location models, discussed in Chapter [52] in this book, involve the location of facilities, such as retail outlets, to attract as much demand as possible from competing facilities.

Commonly used distance measures between points (x, y) and (u, v) include:

• Euclidean distance (also termed $\ell _2$): $\sqrt{(x-u)^2+(y-v)^2}$. This is a straight line distance.

• Rectilinear (also termed Manhattan, or $\ell _1$) distance: $|x-u|+|y-v|$. This is a distance on a grid where roads are either in a North-South or East-West directions and there are no diagonal roads.

• General $\ell _p$ distance: $\left\{ |x-u|^p+|y-v|^p\right\} ^{\frac{1}{p}}$. $p=2$ is the Euclidean distance, and $p=1$ is the rectilinear distance.

There are extensions to the basic location models. For example, some models are formulated on the surface of a sphere. Distances on the globe are not “straight” lines but great circle distances used by airplanes flying between origin and destination. Spherical models are discussed in Sect. 9.2.5.

2 Single Facility Location Problems

In this section we review single facility location models. The location of multiple facilities is discussed in Sect. 9.3.

2.1 The Weber (One-Median) Location Problem

The first and most basic location problem is the Weber problem [202]. A set of demand points with associated weights exist in the area. The problem is to find a location for a facility that minimizes the weighted sum of distances to the set of demand points. The formulation and solution methods are detailed in Sect. 9.4.2.4. The simple form of the problem dates back to the French mathematician Pierre de Fermat who lived in 1601–1665. For historical reviews the reader is referred to [207, 39, 97]. As detailed in [39, 147], Pierre de Fermat asked the question of finding the point in a triangle that minimizes the sum of the distances to the vertices of the triangle. The problem was solved by Torricelli (1608–1647). Torricelli showed (see Fig. 9.1), that the optimal location (Fermat point) is at a point forming three angles of $120^\circ$ each with the sides of the triangle (and on a vertex if an angle at a vertex is 120$^\circ$ or greater).

Fig. 9.1

Solution to the minimum sum of distances in a triangle

This is the solution to connecting three cities by the shortest possible railroad. Suppose that we need to connect four cities on the vertices of a square with a side of 1. Connecting three sides, or forming an H shape, has a total length of 3. The two diagonals have a total length of $2\sqrt{2}=2.828$. The optimal solution to this problem is depicted in Fig. 9.2. The two points in the interior of the square are Fermat’s points in the triangles formed by two vertices and the square’s center C. Therefore, all the angles are 120$^\circ$. The total distance is $1+\sqrt{3}=2.732$. The general problem of connecting n points by the shortest tree is called the Steiner tree problem [180].

Fig. 9.2

Solution to the minimum sum of distances in a square

2.1.1 Extensions to the Basic Weber Problem

Drezner et al. [90] investigated a model where travel time is not necessarily proportional to the distance. Every trip starts at a speed of zero, then the vehicle accelerates to a cruising speed, stays at the cruising speed for a portion of the trip, and then decelerates back to a speed of zero. A time equivalent distance which is equal to the travel time multiplied by the cruising speed is defined. It is proved that every demand point is a local minimum for the Weber problem defined by travel time rather than distance. Accurate estimate of travel time is especially important when evaluating hub location [187, 176, 30, 46, 1]. When a flight has one or more stopovers, the underestimation of flight time is increased, in addition to the waiting time at the stopover, because there are more acceleration and deceleration periods. Therefore, when using distances rather than flight times, hub location models may underestimate the decline in quality of service due to stopovers at hubs.

Drezner and Wesolowsky [110] and Drezner and Drezner [61] considered the Weber problem when the distance from point A to point B is not the same as the distance from B to A. This is common in rush hour traffic or for flights that in one direction have tail winds and in the opposite direction have head winds.

Drezner et al. [101] considered the Weber problem on a network where demand points can be on nodes of the network or anywhere in the plane off the network. Distances to demand points located on the network can be either network distances or Euclidean distances, while distances to points off-the network are Euclidean. Travel time on the network is slower by a given factor but is cheaper than using Euclidean distances. Applications include building a hospital providing emergency services either by an ambulance using network roads, or by a helicopter flying directly to the patient, especially when the patient is off the network. The facility can be located anywhere on the network and the optimal solution is not necessarily on a node. The problem is optimally solved by the “Big Segment Small Segment” global optimization algorithm (see also Sect. 9.4.2.3 and Berman et al. [9]). Locating a transfer point where service is switched from one vehicle to another on the way to a demand point or on the way back is investigated in [13, 14, 15].

Drezner [74] considered the Weber problem when there is uncertainty in the location of demand points. Each demand point can be located anywhere in a circle. The set of all possible optimal locations is found.

Farahani et al. [120] investigated the Weber problem with multiple relocation opportunities. The weight associated with each demand point is a known function of time. Relocations can take place at pre-determined times. The objective function is the minimization of the total location and relocation costs.

Drezner and Scott [100] considered the location of a facility that sells goods to a set of demand points. The cost for producing an item and the transportation cost per unit distance are given. The total cost is the sum of the price charged at the source (mill price) and the transportation cost paid by the customers. Demand by customers is elastic and assumed to decline linearly in the total cost to customers.

Drezner [79] found the sensitivity of the optimal location of the Weber problem to changes in the locations and weights of the demand points. An approximate formula for the set of all optimal sites is found when demand points are restricted to given areas and weights are within given ranges.

Drezner and Goldman [94] found the smallest set of points that may include at least one optimal solution to the Weber problem for a given set of demand points and any unknown set of weights.

Drezner and Simchi-Levi [103] proved that when n points with random weights are randomly generated in a unit circle, the probability that the Weber solution point with Euclidean distances is on a demand point is approximately $\frac{1}{n}$. One would expect that when the number of demand points increases to infinity, the probability that a solution is on a demand point converges to 1 because there is no “empty space” left in the circle. This counter-intuitive result was verified by simulation.

The possibility that some of the weights in the Weber problem are negative is proposed in [111, 160, 33, 178]. This problem is also termed “the Weber problem with attraction and repulsion”. Schöbel and Scholz [184] generalized it to multiple facilities.

Drezner et al. [72] proposed the Weber obnoxious facility location problem. The facility location is required to be at least a given distance from demand points because it is “obnoxious” to them. For example, locating an airport that generates noise and pollution and thus should not be too close to communities. However, it serves travelers and thus their total travel distance to the airport should be minimized. Kalczynski and Drezner [140] extended this model to multiple facilities.

2.2 The Minimax (One-Center) Location Problem

The minimax facility location problem (also termed the one-center problem) is to locate a facility so that the maximum distance to a set of demand points is minimized. For planar Euclidean distances, this problem is equivalent to finding the center of the smallest circle enclosing all points hence the term “center” is used for this problem. When other metrics are used, the one-center problem is equivalent to covering all points with a shape similar to the unit ball of the metric. For example, when rectilinear distances are used, the problem is to cover all points with the smallest possible rhombus (a square rotated by $45^\circ$). This objective can be viewed as locating a facility that will provide the best possible service to the farthest community.

The smallest circle problem was first suggested and solved by the renowned English mathematician James Joseph Sylvester [195, 196]. An almost identical algorithm is provided by Chrystal [38]. Chrystal [38] starts with a “large” circle that encloses all the points and reduces the radius of the circle iteratively until the smallest circle is obtained. Drezner [86] reviewed planar center problems and their history. Solution methods are discussed in Sect. 9.4.2.5.

A variation on the weighted one-center problem is proposed in [75]. The objective is to maximize the total weight of n demand points within a given distance from the facility. An optimal procedure of complexity $O(n^2\log n)$ is proposed. This problem is a single facility covering problem. For its multiple facility version see Sect. 9.3.4.

2.3 The Obnoxious Facility Location Problem

In most location problems, the closer is a facility to demand points the better. However, there are facilities that have a negative impact on communities (being “obnoxious”) and being farther from communities is better. For example, noisy or polluting factories, garbage dumps, airports, should not be located close to communities. The maximin location problem is to find the point that maximizes the minimum (weighted) distance to all demand points. If no restrictions on the location of the facility are imposed, the best location is at infinity. Therefore, the location is restricted to a finite region, such as the convex hull of the demand points.

Melachrinoudis and Xanthopulos [167] proposed a model of locating a new facility that serves certain demand points. Two objectives are considered: (1) minimize the undesirable effects introduced by the new facility by maximizing its minimum Euclidean distance with respect to all demand points, and (2) minimize the total transportation cost from the new facility to the demand points.

Drezner and Wesolowsky [112] and Drezner et al. [73] found the best location of a facility inside a planar network. Drezner and Wesolowsky [112] found a point that maximizes the minimum weighted distance to the links and nodes of the network. Drezner et al. [73] investigated two equivalent problems. In one problem it is assumed that the links of the network generate a negative impact and the objective is to locate a facility, such as a school or a hospital, where the total impact is minimized. An equivalent problem is locating an obnoxious facility where the total negative impact generated by the facility and inflicted on the links of the network is minimized.

Berman et al. [12] considered the location of an obnoxious facility by a developer that has a given expropriation budget. Each demand point can be bought by the developer at a given price. Demand points closest to the facility are expropriated (bought and eliminated) with the given budget. The objective is to maximize the distance to the closest point not expropriated. This model is similar to minimizing the population that is exposed to the negative impact [40].

Melachrinoudis and Cullinane [165] considered the location of an obnoxious facility when some obnoxious facilities already exist in the area. The facility must be located outside circles centered at the existing facilities.

A review of obnoxious facilities models is [41]. A review of single obnoxious facility location models is [164]. Solution approaches are discussed in Sect. 9.4.2.4

2.4 Equity Models

The purpose of equity models is to provide equitable service to demand points. Eiselt and Laporte [115] list nineteen equity objectives. Below are some single facility location models with equity objectives. Models involving location of multiple facilities are discussed in Sect. 9.3.6.

• 1. Minimizing the range of the distances to all demand points [55, 105].

• 2. Minimizing the variance of the distances to the facility [55, 159, 31, 5, 54].

• 3. Minimizing the quintile share ratio [119]. The quintile share ratio is the ratio of total weight of the 20% of the demand points with the largest distance (top quintile) to the weight of the 20% of the demand points with the lowest distance (lowest quintile) [64].

2.5 Location on a Sphere

In this section we review several location models on the surface of a sphere. For solution approaches see Sect. 9.4.2.7.

2.5.1 Calculating Spherical Distances

The distance between any two points on the sphere can be calculated by the “great circle” formula, which is the shortest distance between two points on the surface of a sphere, utilized by airplanes [106]. The distance $\widehat{d}$ along the great circle between two points whose latitudes are $\varphi _1, \varphi _2$ and longitudes $\theta _1, \theta _2$ is:

$$\begin{aligned} {\widehat{d}}=R\arccos \left\{ \cos \varphi _1\cos \varphi _2\cos (\theta _1-\theta _2)+\sin \varphi _1\sin \varphi _2\right\} \end{aligned}$$

(9.1)

where R is the sphere’s radius (3959 miles, or 6371 kilometers, for the earth).

This formula can be re-written to avoid large round-off errors for small distances when $\cos \frac{\widehat{d}}{R}\approx 1$ [93]. The identity $\cos \alpha =1-2\sin ^2\frac{\alpha }{2}$ is used:

$$\begin{aligned}&\cos \varphi _1\cos \varphi _2\cos (\theta _1-\theta _2)+\sin \varphi _1\sin \varphi _2=\cos \varphi _1\cos \varphi _2+\sin \varphi _1\sin \varphi_2 \\ & -(1-\cos (\theta _1-\theta _2)) \cos \varphi _1\cos \varphi _2= \cos (\varphi _1-\varphi _2) \\ & -2\sin ^2\frac{\theta _1-\theta _2}{2}\cos \varphi _1\cos \varphi _2\end{aligned}$$

yielding

$$\begin{aligned} \cos \frac{\widehat{d}}{R}= & {} 1-2\sin ^2\frac{\widehat{d}}{2R}= \cos (\varphi _1-\varphi _2)-2\sin ^2\frac{\theta _1-\theta _2}{2}\cos \varphi _1\cos \varphi _2\nonumber \\\rightarrow & {} 2\sin ^2\frac{\widehat{d}}{2R}=2\sin ^2\frac{\varphi _1-\varphi _2}{2}+2\sin ^2\frac{\theta _1-\theta _2}{2}\cos \varphi _1\cos \varphi _2\nonumber \\\rightarrow & {} \widehat{d}=2R\arcsin \sqrt{\sin ^2\frac{\varphi _1-\varphi _2}{2}+\sin ^2\frac{\theta _1-\theta _2}{2}\cos \varphi _1\cos \varphi _2} \end{aligned}$$

(9.2)

Another way to calculate the great circle distance [146] is to convert the points on the surface of the sphere to three-dimensional coordinates (x, y, z) so that $x^2 + y^2 + z^2 = R^2$. A point $(\varphi , \theta )$ is transformed to: $x = R \cos \varphi \sin \theta ; y = R \cos \varphi \cos \theta ; z=R\sin \varphi .$ The distance d between the points $(x_1,y_1,z_1),(x_2,y_2,z_2)$ in a three-dimensional space is

$$\begin{aligned} d=\sqrt{(x_1-x_2)^2+(y_1-y_2)^2+(z_1-z_2)^2}.\end{aligned}$$

(9.3)

The angle of the segment connecting the two points seen from the sphere’s center is $\alpha = 2 \arcsin \frac{d}{2R}$. Therefore, the great circle distance $\widehat{d}$ is:

$$\begin{aligned} \widehat{d}=R\alpha = 2R \arcsin \frac{d}{2R} \end{aligned}$$

(9.4)

because the great circle is on the plane connecting the two points and the center of the sphere. $\widehat{d}>d$ for $d>0$ because $\arcsin \alpha >\alpha$ for $\alpha >0$. For very small values of $\frac{d}{R}$, $\arcsin \alpha \approx \alpha$ and thus $\widehat{d}\approx d$.

Drezner and Wesolowsky [106] showed that the spherical distance is convex up to a distance of $\frac{\pi R}{2}$ and not convex for greater distances. Therefore, if all demand points are within a circle of radius $\frac{\pi R}{4}$ (about 5000 kilometers or 3100 miles on earth), the Weber problem on the sphere is convex and has one local minimum which is the global one. They also constructed an example of a problem with all demand points in a circle of radius $\frac{\pi R}{4}+\varepsilon$ for any $\varepsilon >0$ that has two local optima with different values of the objective function. Drezner et al. [93] analyzed small multiple facility location problems on the surface of a sphere.

2.5.2 Various Location Models on the Sphere

The antipode of a point on a sphere is a point on the line connecting the point with the center of the sphere “on the other side”. For example, the antipode of Hong Kong is near Rio de Janeiro. The antipode of a point $(\varphi ,\theta )$ is $(-\varphi ,\theta \pm \pi )$. Every circle, centered at the sphere’s center, passing through these two points is a “great circle”, and the distance between the point and its antipode is $\pi R$ which is the largest possible distance between any two points on the sphere. This distance is obtained by the three formulas above.

• By Eq. (9.1), $\widehat{d}= R\arccos \left\{ -\cos ^2\varphi -\sin ^2\varphi \right\} =R\arccos \{-1\}=\pi R$.

• By Eq. (9.2), $\widehat{d}= 2R\arcsin \left\{ \sin ^2\varphi +\cos ^2\varphi \right\} =2R\arcsin \{1\}=\pi R$.

• By Eq. (9.3), $d=2R$. Then, by Eq. (9.4), $\widehat{d}= 2R\arcsin \{1\}=\pi R$.

The concept of the antipode can be useful for analyzing spherical problems. The distance between any point X and point Y plus the distance between X and the antipode of Y is equal to $\pi R$. Therefore, if there are negative weights in a location problem, a point with a negative weight can be replaced by its antipode with a positive weight. The maximin problem based on a set of points, is equivalent to the minimax problem based on the antipodes of these points. This property was utilized in [109] for solving the maximin and minimax problems on the sphere, and in [76] for solving constrained maximin and minimax problems on the sphere.

Drezner [81] investigated the Weber objective on a surface of a sphere when the demand points and weights are randomly generated. It is proven that when the number of demand points increases to infinity: (i) the ratio between the maximum value of the objective function and the minimum value converges to one, and (ii) the expected number of points that are a local minimum converges to one.

3 Multiple Facilities Location Problems

Most multiple facilities location models assume that customers are getting their services from, or are affected by, the closest facility. If only one facility is located, all customers are served by that facility. However, if several facilities are located, the set of demand points is partitioned into subsets so that all demand points in each subset are closest to the facility located in that subset. When Euclidean distances are used, the plane is partitioned into polygons based on the perpendicular bisectors between all pairs of facilities which is a Voronoi diagram (see Sect. 9.4.2.2). Such problems are not convex and may have several (may be many) local optima. Most of the solution methods proposed for such problems are heuristics. For solution methods see Sect. 9.4.3. Models that do not assume that services are provided by the closest facility are discussed in Sect. 9.3.7.

3.1 Conditional Models

Conditional location models investigate locating one or more facilities when some facilities already exist in the area. Customers select the closest existing or new facility. Many of the models listed in the rest of this section can also be formulated as conditional problems. The first to suggest such models was Minieka [168]. Some papers investigating conditional models are [174, 135, 7, 83, 80, 36, 35, 18].

3.2 The p-Median Location Problem

The continuous p-median problem [89, 99], also known as the multi-source Weber problem [22, 150, 132], or continuous location-allocation problem [158, 23] is an extension of the single facility Weber problem [202] discussed in Sect. 9.2.1. The problem is to find p sites for facilities that minimize a weighted sum of distances from a set of demand points to their closest facility.

Let $X_i= (x_i, y_i)$ denote the location of facility $i \in \{1,\ldots , p\}$, and $A_j=(a_j, b_j); w_j>0$ the known location of demand point j and its associated weight for $j \in N=\{1,\ldots , n\}$. For distances measured by the Euclidean norm: $d (X_i, A_j) = \sqrt{(x_i - a_j)^2 + (y_i - b_j)^2}.$

The planar p-median problem is: $\min \limits _{\mathbf {X}\subset \mathbb {R}^2}\left\{ f (\mathbf {X}) = \sum \limits _{j = 1}^n w_j \min \limits _{1\le i\le p}\{ d (X_i, A_j)\}\right\} ,$ where $\mathbf {X} = \{X_1,\ldots , X_p\}$.

This model was originally proposed by Cooper [47, 48], who also observed that the objective function $f(\mathbf {X})$ is not convex, and may contain several local optima. The problem was later shown to be NP-hard [163]. For a recent review of the planar p-median problem see Brimberg and Hodgson [24]. In the discrete version of this problem (reviewed in Daskin and Maass[51, 50]), there is a list of potential locations for the facilities, rather than locating facilities anywhere in the plane.

It can be easily shown that in the optimal solution for Euclidean distances, the facilities must be located in the convex hull of the demand points. The proof is based on the theorem in Wendell and Hurter [206]: if a point is located outside the convex hull of the demand points, then there exists a point in the convex hull that is closer to all demand points. Therefore, if a facility is located outside the convex hull, there is a better location for it in the convex hull.

An extension to the p-median problem was proposed in Brimberg and Drezner [20] based on the procedure proposed in Drezner et al. [67]. Suppose that the set of demand points can be separated into k disconnected subsets, such as a subset in New-York, a subset in Tokyo, etc., so that demand points get their services from a facility assigned to a subset and not a facility assigned to another subset. $p>k$ facilities are to be built in these subsets. The problem is finding how many facilities to assign to each subset so that the sum of the individual p-median objectives, which is the p-median objective for the whole set, is minimized.

3.3 The p-Center Location Problem

The p-center location problem is an extension of the 1-center problem discussed in Sect. 9.2.2. The objective is to minimize the maximum (weighted) distance of demand points to their closest facility. The problem was proposed in a network environment [145]. Solution approaches are discussed in Sect. 9.4.3.2.

3.4 Cover Models

Facilities need to be located in an area to provide as much cover as possible. A demand point is covered by a facility within a certain distance [44, 183]. Such models are used for cover provided by emergency facilities such as ambulances, police cars, or fire trucks. They are also used to model cover by transmission towers such as cell-phone towers, TV or radio transmission towers, and radar coverage. For a review see [179, 124, 188, 43]. Drezner et al. [65, 66] applied the cover concept to competing facilities. Each competing facility has a “sphere of influence” [151, 121, 157, 37, 182], and customers patronize a facility up to a certain distance.

3.4.1 Gradual Cover Models

In the gradual cover models, up to a certain distance $R_1$ the demand point is fully covered and beyond a greater distance $R_2$ it is not covered at all. Between these two extreme distances the demand point is partially covered. Suppose that the cover distance in traditional cover models is 3 miles. At a distance of 2.99 miles the demand point is fully covered, while at a distance of 3.01 miles it is not covered at all. This assumption may be convenient for analyzing and solving covering problems. However, in reality cover does not drop abruptly but the decline in cover is gradual.

Church and Roberts [45] were the first to propose the gradual cover model (also referred to as partial cover). The facilities must be located within a finite set of potential locations. The network version with a step-wise cover function is discussed in [16]. The network and discrete models with a general non-increasing cover function were analyzed in [17]. The single facility planar model with a linearly decreasing cover function between $R_1$ and $R_2$ was optimally solved in [114], and its stochastic version (randomly distributed $R_1$ and $R_2$) analyzed and optimally solved in [62]. Additional references include [143, 116, 60, 10].

Drezner et al. [68] proposed the directional gradual cover. Communities are usually areas and not points. Not all residents are at the same distance from a facility and in many instances only some of the residents, that are closer to the facility, are covered. Suppose that customers residing at a demand “point” reside in a disc (centered at the demand point) of radius r, and the facility is located at a point. The facility covers customers within a given distance D. All the points in the disc centered at the facility with a radius D are covered. The intersection area between this disc and the disc centered at the demand point of radius r is covered. Therefore, the partial cover by one facility is the ratio between this intersection area and the area of the demand disc. A facility within a distance $D-r$ from the demand point covers the whole disc, and at a distance exceeding $D+r$ it covers none. Follow-up papers extending the concept of the directional cover are [69, 71].

A different gradual covering model where facilities “cooperate” in providing cover was proposed in [8]. Each facility emits a signal (such as light posts in a parking lot) whose strength declines according to a distance decay function. A point is covered if the combined signal from all facilities exceeds a certain threshold. Recent papers on the cooperative cover are [170, 144, 201, 3].

It is not obvious how to estimate the total partial cover of a demand point when it is partially covered by several facilities. This issue is discussed in [10]. Let $c_j$ be the partial cover of a demand point by facility j for $j=1,\ldots ,p$. Eiselt and Marianov [116] proposed a total partial cover of $\min \left\{ \sum \limits _{j=1}^p c_{j}, 1 \right\}$. Partial cover can be interpreted as the probability of cover. Assuming that the partial covers are not correlated, the total partial cover is: $1-\prod \limits _{j=1}^p\left( 1-c_{j}\right)$ [12, 113, 57]. In the directional gradual cover [68], if a demand point is partially covered by two or more facilities, the total cover (area) depends on the distances between the facilities and the demand point, and on the directions of the facilities from the demand point. For example, if two facilities are located North of the demand point, the cover areas overlap and the total cover is equal to the larger cover area. If one facility is to the North and one to the South, total cover is greater than the larger cover area unless the demand point is fully covered by one of the facilities. Total cover is at least the largest cover by one of the facilities and cannot exceed the sum of the covers by individual facilities. When $r=0$, the demand point is either fully covered or not covered at all. The cover is identical to the cover applied in the standard non-gradual cover models.

3.5 The Multiple Obnoxious Facilities Location Problem

In all models of locating obnoxious facilities, all facilities must be located in a finite feasible area. Otherwise, facilities will be located “at infinity”. For a review of obnoxious facilities models see [41].

Fig. 9.3

Surface of the distance to the closest demand point in a square

One of the models for the multiple obnoxious facilities location problem is to locate p facilities, that are at least a distance D from one another, with the objective of maximizing the shortest distance between facilities and demand points [205, 96]. The problem is “extremely” non-convex. The surface of the shortest distance to the communities is depicted in Fig. 9.3. The hilltops are Voronoi points discussed in Sect. 9.4.2.2. There are 202 hilltops in the figure. Drezner et al. [96] proposed to find locations on hilltops for p facilities that are at least a given distance D from one another with the objective of maximizing the shortest distance between demand points and facilities. Kalczynski and Drezner [139] improved this procedure. Kalczynski et al. [141] generalized this problem to include weights associated with demand points. Rather than maximizing the minimum distance, the objective is maximizing the minimum weighted distance. Solution methods are described in Sect. 9.4.3.3

Eiselt and Marianov [117] modeled the locations of landfills and transfer stations. The model is formulated as a bi-objective problem. One objective is cost-minimization, while the other is minimizing pollution. Melachrinoudis et al. [166] proposed a multi-objective model for the location of landfills. Teran-Somohano and Smith [199] present a model for the obnoxious, multiple capacitated facility location problem on a Euclidean plane. The problem is solved using a bi-objective evolutionary strategy algorithm that seeks to minimize social and non-social costs. The effects of under and over capacitating the facility are included in the cost functions.

Kalczynski and Drezner [138] proposed solving two variants of obnoxious multi-facilities problems with the objective of maximizing the sum of the shortest distances rather than the minimum, which can be termed p-maxian following the terminology of [42]. Since there is no advantage to locating facilities close to one another, there is no need to require a minimum distance between facilities. One problem’s objective is maximizing the sum of weighted distances between each demand point and its closest obnoxious facility. The second objective is maximizing the sum of weighted distances between each facility and its closest obnoxious demand point. They first solved the problems using three general purpose nonlinear software packages from many randomly generated starting solutions: Matlab’s [129] interior point, SNOPT [125], and MSLP (Multi-start Sequential Linear Programming [95] which performed the best of the three). However, as in [96], the best quality solutions and shortest run times were obtained by selecting p starting locations among the Voronoi points.

Drezner et al. [70] defined a different objective function. The negative impact emitted by the facilities declines by the square of the distance and is additive. The facilities “cooperate” in inflicting the disturbance. The objective is to minimize the disturbance inflicted on the most affected community. Since locating two facilities at the same location doubles the disturbance generated at that location, there is no need to require a minimum distance between facilities. The model is a generalization of the single facility location model proposed by Hansen et al. [133].

The p-dispersion problem, originally described by Shier [186] on a tree network, deals with facility to facility interactions as no demand points are included in the model. The objective is maximizing the minimum distance between facilities. Kuby [149] designed an integer programming formulation for the discrete case. It was approached in the continuous space by [92, 161]. For the continuous case, there is a bounded area with no demand points. An equivalent problem is circle packing in a convex area (finding p non-intersecting circles inside a convex area with the greatest possible radius [154, 161, 173, 197]). Common convex areas investigated in the literature include a square, a rectangle, a disk, and an equilateral triangle [197, 155].

3.6 Equity Models

Equity models aim to provide similar service to the demand points rather than minimizing or maximizing some objective. Single facility models are discussed in Sect. 9.2.4. Examples of multiple facilities models include:

• 1. Minimizing the Gini coefficient of the Lorenz curve [156, 126] calculated by service distances to the closest facility [63].

• 2. Equalizing the load serviced by the facilities [193, 4, 11].

• 3. The set of demand points is partitioned into groups. These groups are not necessarily divided by their locations but by characteristics such as neighborhoods’ wealth. The objective is to provide equitable service to the groups by locating one or more facilities. For example, poor neighborhoods should get comparable service level to rich neighborhoods [59].

3.7 Not Necessarily Patronizing the Closest Facility

Most multiple facility location problems assume that customers get their services from the closest facility. There are a few papers that do not assume that. Brimberg et al. [26] assumed that there is a sequence of probabilities $p_1,p_2,\ldots$. A customer is served by the closest facility with probability $p_1$, by the second closest with probability $p_2$, and so on. In competitive location, discussed in Chapter [52] in this book, one approach termed the gravity or Huff model [181, 136, 137] assumes that customers split their patronage among several competing facilities rather than patronize the closest one. The probability of patronizing a facility declines by a distance decay function.

Some models propose that customers obtain their services according to the gravity rule. Drezner and Drezner [56, 54] proposed the gravity p-median model. It is assumed that users choose from among the facilities providing services according to the gravity rule rather than getting them from the closest facility.

Drezner and Drezner [53] applied the gravity rule to the hub location problem. A traveler needs to fly from one airport to another. Several potential hub airports are available. If the origin or the destination is a hub airport, the traveler chooses a non-stop flight. Otherwise, the probability that a certain hub is selected is governed by the gravity rule.

Drezner and Drezner [58] considered the gravity rule version of the multiple server location problem [6]. Total service time consists of travel time to the facility, waiting time in line, and service time. There is a given number of servers to be distributed among the facilities. Each facility acts as an M/M/k queuing system [162]. Customers select a server with a probability proportional to its attractiveness and to a decay function of the distance, not necessarily selecting the closest one.

4 Solution Methods

4.1 Generating Replicable Test Problems

In order to compare computational results of test problems in future research, access to the parameters of the test problems is required. Drezner et al. [96] suggested a simple method, that was used in many follow-up papers, to generate a pseudo-random sequence of numbers distributed uniformly in the open range between 0 and 1 based on the idea of Law and Kelton [152]. Such test problems can be easily replicated without a need for an access to a data base.

A starting seed $r_1$ and a multiplier $\lambda$, which are odd numbers not divisible by 5, are selected. Note that $r_1$ can be an even number not ending with a zero. Drezner et al. [96] used $\lambda =12,219$. The sequence is generated by the following rule for $k\ge 1$:

$$r_{k+1}=\lambda r_k-\lfloor \frac{\lambda r_k}{100,000}\rfloor \times 100,000$$

The number $r_k$ is an integer between 1 and 99,999, so $\frac{r_k}{100,000}$ is a number in the open range between 0 and 1. If a random number between a and b is sought, we can use $a+(b-a)\frac{r_k}{100,000}$. It turns out that $r_{5001}=r_1$ and if a sequence of more than 5,000 points is needed, the 100,000 can be replaced by 1,000,000 and sequences of up to 50,000 numbers can be generated [142]. Drezner et al. [96] used $r_1=97$ to generate the x coordinates, and $r_1=367$ to generate the y coordinates of their test problem. The surface plot for $n=100$ for the obnoxious facility problem depicted in Fig. 9.3 is based on the points generated this way.

4.2 Solving Single Facility Problems

4.2.1 Solving with the Solver in Excel

Convex single facility location problems can be solved with the Solver in Excel, mainly for instruction purposes. Expression (9.5) is easy to program. There are only two variables (x, y). For the one-center problem, it is better to formulate it as minimize $\{ L\}$ subject to the constraints that each distance $\le L$. The distances (9.1) for problems on the sphere are somewhat more complicated to program, but spherical problems can serve as a good example for a global FedEx idea of planes flying to a central airport, exchange packages and fly back. If the company serves 20 cities all over the world, flying directly between all pairs of cities will require 380 airplanes to fly daily, while this scheme requires only 20 airplanes.

If a problem is not convex, it can be heuristically solved by Solver using VBA (Visual Basic for Applications) in a multi-start approach (for example repeating the process 100 times). Each starting solution is randomly generated, and the problem is solved by calling Solver in the VBA code, and the best solution is selected.

4.2.2 Voronoi Diagram and Delaunay Triangulation

A Voronoi diagram [200] is constructed by a set of generator points. The plane is partitioned into polygons so that all the points inside a polygon are closest to one generator point. The sides of the polygons are equidistant from two generator points (and closest to them), and the vertices of the polygons (termed Voronoi points) are equidistant from three generator points. So, for example, if the generator points are facilities, the plane is partitioned into polygons so that the points inside a polygon are closest to the same facility. If a demand point gets its services from the closest facility, each facility provides service to the set of demand points in its polygon.

Fig. 9.4

Delaunay triangulation of the convex hull

The Delaunay triangulation [153] is based on the Voronoi diagram. A polygon whose interior is the feasible set, has demand points in its interior (and boundary). The polygon is partitioned into non-overlapping triangles so that the vertices of the triangles are demand points, and the union of the triangles covers the whole feasible polygon. Figure 9.4 depicts an example of a Delaunay triangulation of the convex hull of a set of points. The Delaunay triangulation can be generated by Mathematica [208]. For a review of Voronoi Diagrams and Delaunay triangulation see [2, 194, 175].

4.2.3 General Global Optimization Algorithms

The first global optimization procedure suitable for the location of a single facility is the “Big-Square-Small-Square” (BSSS) proposed by Hansen et al. [133]. It is a branch and bound algorithm. A relative accuracy $\varepsilon >0$ is given. A square that covers the feasible region is defined, and a formula (or procedure) for finding lower and upper bounds in a square is needed. The following steps are executed for a minimization problem. A procedure for maximization is very similar.

• 1. Find the lower bound $LB_1$ and the upper bound $UB_1$ in the square. The upper bound is at a feasible point. The list of squares has one member. The best upper bound (best solution found so far) in the list is $UB=UB_1$.

• 2. Select the square i in the list with the minimum $LB_i$. If $LB_i>UB(1-\varepsilon )$, stop with UB as the solution.

• 3. Remove square i (the “big” square) from the list and create four “small” squares by perpendicular lines, parallel to its sides, through the big square’s center.

• 4. For each of the four small squares:

  • a. Calculate the lower bound $\overline{LB}$ and the feasible upper bound $\overline{UB}$ in the square.

  • b. Update UB if $\overline{UB}<UB$.

  • c. If $\overline{LB}\le UB(1-\varepsilon )$, add the small square to the list.

• 5. If UB was updated in Step 4b, check all the squares in the list and remove squares for which $LB_i>UB(1-\varepsilon )$.

• 6. If the list of squares is empty, stop with UB as the solution within a relative accuracy $\varepsilon$. Otherwise, go to Step 2.

The BSSS branch and bound algorithm was modified in several ways. Drezner and Suzuki [104] constructed the “Big-Triangle-Small-Triangle” (BTST) procedure. The feasible set, such as the convex hull of the demand points, is triangulated by the Delaunay triangulation [153] described in Sect. 9.4.2.2. The initial list consists of the Delaunay triangles. In the first phase bounds are calculated for each triangle, and some triangles are removed from the list. The second phase is similar to BSSS. Four “small triangles” are created by connecting the centers of the sides of the selected “big triangle”. The BTST algorithm is more efficient, especially when the feasible area is not the whole square. In order to evaluate the bounds for BSSS, the feasibility of points in a square needs to be considered. In BTST all Delaunay triangles and consequently all small triangles are feasible by design and no feasibility check is required.

Drezner [85] constructed a general algorithm for solving by BTST any location problem whose objective is a sum of individual terms, one for each demand point. Specific bounds are constructed when each term can be expressed as a difference between two convex functions of the distance which are not necessarily convex in the coordinates x and y. For example, $-\ln (d)$ is convex for $d>0$ but it is not convex (or concave) in the coordinates. Drezner and Nickel [98] constructed general bounds for problems that can be formulated as an ordered median problem [172].

Drezner et al. [72] constructed the “Big-Arc-Small-Arc” (BASA) algorithm for solving location problems on peripheries of circles. Berman et al. [9] designed the “Big-Segment-Small-Segment” algorithm for solving problems on networks. Schöbel and Scholz [184] proposed the “Big-Cube-Small-Cube” (BCSC) algorithm for solving problems in k-dimensional space for $k\ge 3$.

4.2.4 Solving the Weber Problem

The first algorithm for solving the Weber [202] problem with Euclidean distances was designed by [203] (translated to English in [204]). It is an iterative procedure converging to the optimal solution because the problem is convex [177].

Let $(x_i,y_i)$ for $i=1,\ldots n$ with weights $w_i>0$ be a set of demand points in the plane. The objective function is:

$$\begin{aligned} \min \limits _{x,y}\left\{ \sum \limits _{i=1}^n w_i\sqrt{(x-x_i)^2+(y-y_i)^2}\right\} \end{aligned}$$

(9.5)

A starting solution $(\widehat{x},\widehat{y})$ is selected. The next iterate is obtained by equating the derivatives of Eq. (9.5) by x and y at $(\widehat{x},\widehat{y})$ to zero, and solving for (x, y). Define $\widehat{w}_i= \frac{w_i}{\sqrt{(\widehat{x}-x_i)^2+(\widehat{y}-y_i)^2}}$, then

$$\begin{aligned} \sum \limits _{i=1}^n\widehat{w}_i(x-x_i)=0;~\sum \limits _{i=1}^n\widehat{w}_i(y-y_i)=0~\rightarrow ~x=\frac{\sum \limits _{i=1}^n\widehat{w}_ix_i}{\sum \limits _{i=1}^n\widehat{w}_i};~y=\frac{\sum \limits _{i=1}^n\widehat{w}_iy_i}{\sum \limits _{i=1}^n\widehat{w}_i}. \end{aligned}$$

(9.6)

When the Euclidean distance is replaced by the squared Euclidean distance, the solution is at the center of gravity ($\widehat{w}_i=w_i$). When Manhattan ($\ell _1$) distances are used, the problem is separable into two unrelated one dimensional problems. The solution in one dimension (on a line) is at the median point, hence the name “the one-median problem”. For $\ell _p$ distances, a procedure similar to Weiszfeld [203] is designed by Brimberg and Love [25]. For details see [158, 122].

Several improvements of the Weiszfeld algorithm [203] were proposed. Drezner [82] proposed to multiply the change between two consecutive iterations by a factor of 1.8. An “ideal” multiplier that needs to be computed every iteration was also proposed. Drezner [84] proposed to accelerate the procedure by estimating the limit of a geometric series by the ratio of the changes of two consecutive iterations. Drezner [87] proposed the fortified algorithm based on the values of the objective function at 9 points (the present iteration and eight points around it on the vertices and sides’ centers of a square depicted in Fig. 9.5), and fitting a paraboloid to these nine values by a least squares quadratic regression. The next iterate is the minimum point of the paraboloid. For details see Drezner [87].

Fig. 9.5

The square configuration for the fortified algorithm

4.2.5 Solving the One-Center Problem

Elzinga and Hearn [118] proved that the smallest circle enclosing all points passes through two points (in which case the solution is in the middle between the points), or through three points. They proposed the following algorithm for solving optimally the unweighted 1-center problem:

• 1. Pick any two points. Construct a circle based on the segment connecting the two points as a diameter.

• 2. If the circle covers all points, a solution has been found, stop.

• 3. Otherwise, add a point outside the circle to the pair of points to form a set of three points.

• 4. If the triangle with the three points at its vertices has an angle of at least 90$^\circ$, drop the point on the obtuse angle and go to Step 3.

• 5. If the circle passing through the three points covers all points, a solution has been found, stop.

• 6. If there is a point outside the circle, choose such a point, and add it as a fourth point. One of the original three points needs to be discarded. Go to Step 4.

Once the solution based on three points is available [108], the following modification is faster and can be used for the weighted case as well.

• 1. Select a point such as the center of gravity of the demand points.

• 2. Select the three farthest points (weighted for the general case).

• 3. Find the solution point based on these three points.

• 4. This point is the next iterate. Note that the solution point may be based on only two of the points.

• 5. Find the largest weighted point from the next iterate. If it is within the (weighted) distance obtained in Step 4 stop.

• 6. Otherwise, replace each of the three points by the farthest point (actually solving the four point problem) and select the center of the best solution as the next iterate. Go to Step 4

Drezner and Shelah [102] constructed a special configuration that shows that the Elzinga and Hearn [118] algorithm can have a complexity of at least $o(n^2)$ even though in practice the complexity is linear for most tested problems.

4.2.6 Solving the Obnoxious Facility Problem

In Fig. 9.3 the surface of the shortest distance to a set of 100 randomly generated demand points is depicted. The solution is on the top of the tallest hill. There are 202 hilltops in the figure. It turns out that these hilltops are Voronoi points (see Sect. 9.4.2.2). The Voronoi points can be easily generated by Mathematica [208], or special FORTRAN programs such as Sugihara and Iri [190, 191]. Shamos and Hoey [185] observed this property. Their idea was to generate all the Voronoi points and select the one with the largest shortest distance. Dasarathy and White [49] solved the unweighted maximin problem directly without resorting to Voronoi diagrams. Drezner and Wesolowsky [107] solved the weighted version of the problem.

Hansen et al. [133] observed that the negative impact inflicted by an obnoxious facility usually declines by the square of the distance. Let a facility be located at location X, and the distance between community i for $i=1,\ldots ,n$ and location X is $d_i(X)$. There are $w_i$ residents in community i. The objective is to minimize the cumulative effect on the residents in the area by locating the facility in a pre-determined region S, with the objective:

$$\begin{aligned} \min \limits _{X\in S}\sum \limits _{i=1}^n \frac{w_i}{d_i^2(X)} \end{aligned}$$

(9.7)

They optimally solved this problem by the Big-Square-Small-Square (BSSS) global optimization method (described in Sect. 9.4.2.3) designed in that paper.

4.2.7 Solving Spherical Problems

Hansen et al. [130] and Suzuki [192] constructed global optimization algorithms for location on a sphere’s surface based on the algorithms described in Sect. 9.4.2.3. For spherical surfaces, Hansen et al. [130] generalized the BSSS algorithm [133], and Suzuki [192] generalized the BTST algorithm [104]. The spherical Delaunay triangles are found by the method in Sugihara [189].

4.3 Multiple Facilities Solution Methods

Most solution methods of continuous multiple facilities locations are heuristic. Only small instances can be optimally solved in reasonable computer time.

4.3.1 p-Median

The planar p-median problem is known to be NP-hard [163], and therefore many heuristics have been developed for its solution. Classical heuristics include the famous alternating procedure [47, 48], the projection method [19], and gradient-based methods [34, 171]. An algorithm that can optimally solve medium size problems is designed by Krau [148]. For recent reviews of solution approaches to the planar p-median problem the reader is referred to [88, 89, 27].

Cooper [47, 48] proposed the alternating (sometimes called location-allocation) method. Starting locations for p facilities are selected (randomly or otherwise). The set of demand points is partitioned into subsets, each served by one facility. The best location of the facility serving each subset (the Weber problem which is convex) is found, and possibly a different partition is found. The process is continued until the partition into subsets stabilizes

Genetic algorithms [134, 128] in combination of additional heuristics such as variable neighborhood search [169, 131], tabu search [127], were proposed in [198, 21, 123, 88, 99]. The best results were obtained in [91].

4.3.2 p-Center

Drezner [78] optimally solved the two-center and the two-median problems on the plane. It is proved that in the optimal solution there is a line separating the set of demand points into two subsets such that the single facility solution point for each subset yields the optimal solution to the two facilities problem. There are at most $\frac{1}{2}n(n-1)$ such lines. Once all separating lines are evaluated, the optimal solution is identified. A lower bound for each subset improves the efficiency of the algorithm.

Drezner [77] suggested two heuristics and one optimal algorithm for the solution of the weighted p-center problem. The two heuristic procedures are similar to the location-allocation algorithm [47, 48]. The optimal algorithm is based on the property that the solution to the one-center problem is based on two or three demand points [118]. There are $\frac{1}{6}n(n^2+5)$ possible maximal sets. Based on a proof in [75], the number of relevant maximal sets is bounded by $n(n-1)$. The proposed optimal algorithm is polynomial in n for a fixed p. The extension of the modified center problem [75] is also solved in polynomial time.

Callaghan et al. [28, 29] constructed the best optimal algorithm to solve the p-center problem. They optimally solved problems with up to 1,323 demand points. Earlier solution algorithms were proposed by [32, 34, 36, 35].

4.3.3 Multiple Obnoxious Facilities Solution Methods

The Voronoi points (hilltops in Fig. 9.3) are found. The heuristic algorithm proposed in Drezner et al. [96] is to select p hilltops so that the distance between any two hilltops is at least D, and the lowest hilltop is as high as possible. This is done by solving the following Binary Linear Program (BLP).

Let K be the number of hilltops, and $d_i$ be the shortest distance between hilltop i and all demand points (the height of the hilltop). The hilltops are sorted so that $d_1\ge d_2\ge \ldots d_K$. The distance between hilltops i and j is $D_{ij}$, and we select only hilltops that are at least a given distance D from one another. The proposed binary linear program is (For complete details see Drezner et al. [96]):

$$\begin{aligned}&\text{ Maximize } \left\{ L\right\} \nonumber \\ \text{ subject } \text{ to: } \\&\sum \limits _{i=1}^Kx_i=p \nonumber \\&x_i+x_j\le 1 \text{ when } D_{ij}<D \nonumber \\&L+x_i(d_1-d_i)\le d_1 \text{ for } i=1,\ldots ,K \nonumber \\&x_i\in \{0,1\}\nonumber \end{aligned}$$

(9.8)

5 Summary and Suggestions for Future Research

Location models involve locating one or more facilities among a given set of demand points to achieve a certain objective. For example: locating a warehouse that serves a set of stores; locating a landfill to serve communities but should not be close to them; locating cell-phone towers with a certain range to cover the population in an area. In discrete location models, a finite set of potential locations for facilities is given. In continuous location models, facilities can be located anywhere in the plane, or in a finite region with an infinite number of possible locations.

Such problems are modeled as optimization problems, such as nonlinear programming. Some models are convex and can be easily solved to optimality. Single facility location problems can be optimally solved by the algorithms detailed in Sect. 9.4.2.3. However, most multiple facility problems are non-convex and optimal algorithms are difficult to construct. Therefore, specially designed heuristic algorithms, meta-heuristic approaches such as genetic algorithms [134, 128], variable neighborhood search [169, 131], tabu search [127] and others, are applied for their solution.

There are many models that were proposed in discrete space but yet to be investigated in continuous space. In discrete space such problems are combinatorial in nature: selecting p locations for facilities out of the list of potential locations. Well-designed branch and bound algorithms may be able to solve them to optimality. In continuous space, optimal algorithms are difficult to construct, and heuristic algorithms are usually constructed for solving them.