1 Introduction

Planar facility location problems were investigated by mathematicians for hundreds of years [32, 54]. In the last 50 years, with the advent of computers, operations research and logistics practitioners recognized the importance of such models in providing efficient and cost-effective solutions to logistics problems. There are many applications to facility location models. For example:

  • Desirable Facilities: warehouses, schools, post offices, public swimming pools, product positioning, cell phone transmission towers.

  • Competitive Facilities: stores, shopping malls, restaurants, gas stations, bank branches.

  • Emergency Facilities: hospitals, fire stations, ambulance depots, police stations.

  • Obnoxious Facilities: airports, jails, nuclear power plants, dump sites, polluting factories.

  • Miscellaneous Models: satellite orbits, roads, networks.

Common to these models is that (a) a set of demand points is given, and (b) the objective function is a function of the distances between demand points and the unknown locations of the facilities. The first proposed location problem is the Weber problem which seeks the location of a facility minimizing the weighted sum of distances to the demand points [32, 54]. This model is in the category of desirable facilities because shorter distances are preferable. The objective of competitive facility location models is to locate facilities that attract the most buying power associated with demand points in the presence of competing facilities. A typical objective function in emergency facilities models is the minimization of the maximum distance to all demand points. A typical objective function in obnoxious facility models is the maximization of the minimum distance to demand points.

We first present the ordered median formulation that provides a unified scheme to model many of the location problems discussed above. We then review various global optimization techniques to solve planar location problems that are based on a non-convex objective.

When the objective function is convex, finding the optimal solution is relatively easy. There is only one local optimum which must be the global one. A simple gradient search results in the optimum. However, when the objective function is not convex, and thus there may be many local optima, finding the optimal solution may not be that easy. Many heuristic algorithms terminate with a local optimum. The value of the objective function at a local optimum may be unacceptably higher than the optimal value of the objective function. For example, the planar p-median problem is known to possess many local optima. If the heuristic algorithm is fast enough, then a multi-start approach may be implemented and the solution with the best value of the objective function selected.

For some problems a finite set of dominating set of candidate locations can be found, and algorithms scanning such dominating points can be constructed. However, the set of dominating points may be very large and lead to intractable algorithms even for a moderate number of demand points. For many years, researchers and practitioners applied heuristic approaches to obtain reasonably good solutions to single facility location problems. Even the more recent metaheuristic approaches such as tabu search, genetic algorithms and variable neighborhood search can only guarantee finding a local optimum. Recently, various efficient approaches that find the optimal solution were proposed. Such approaches, some not published yet, are briefly discussed and examples for their implementation given. Topics discussed include in the following:

  • The Ordered Median formulation.

  • Big Square Small Square (BSSS).

  • Big Cube Small Cube (BCSC).

  • Big Triangle Small Triangle (BTST).

  • Big Segment Small Segment.

  • The principle of DC Optimization.

  • A general algorithm using DC optimization.

  • General algorithms using the Ordered Median formulation.

Many of these approaches can be implemented to solving optimization problems that are based on two variables and may even apply to any small number of variables. Therefore, some of the methods described here have general implications to solving many other optimization problems.

2 The Ordered Median formulation

The Ordered Median formulation is a unified approach for many location problems [36, 46]. Suppose there is a set of distances d i (X) for i = 1, …, n. The distances are sorted, and the sorted vector is defined as d(1) ≤ d(2) ≤ … ≤ d(n). The Ordered Median formulation is based on an objective function of the type \( \sum\nolimits_{i = 1}^{n} {\lambda_{i} d_{(i)} (X)} \) for a fixed set of λs. For a comprehensive discussion of the Ordered Median formulation, the reader is referred to [46].

2.1 Simple examples for the vector λ

  • Sum: (1, 1, …, 1).

  • Min: (1, 0, 0, …, 0).

  • Max: (0, 0, …, 0, 1).

  • Truncated mean: (0, …, 0, 1, …, 1, 0, …, 0).

  • Median (even): (0, …, 0, 1/2, 1/2, 0, …, 0).

  • Range; (−1, 0, …, 0, 1).

  • Average of k largest: (0, …, 0, 1/k, …, 1/k).

2.2 More contrived examples that may not “look like” ordered median

  1. 1.

    Fitting a concentric circle [26]

    The minimum absolute deviation of distances is \( \mathop {\hbox{Min} }\limits_{X,R} \left\{ {F(X,R) = \sum\nolimits_{i = 1}^{n} {\left| {d_{i} (X) - R} \right|} } \right\} \). It can be shown that R is the median of distances. Suppose that n is even. The absolute value of distances below the median is R-d i (X), and above the median it is d i (X)-R. There is an equal number of distances bellow the median and above the median and therefore the R’s cancel out in the sum. Therefore, for the median R: \( F(X) = \sum\nolimits_{i > n/2}^{{}} {d_{(i)} (X) - \sum\limits_{i \le n/2} {d_{(i)} (X)} } \) and λ = (−1, … −1,1, …, 1).

  2. 2.

    Minimizing the numerator of the Gini coefficient of the Lorenz curve [18]:

    $$ F(X) = \sum\limits_{i,j = 1}^{n} {\left| {d_{i} (X) - d_{j} (X)} \right|} $$

    In this sum, when the absolute values are expressed explicitly, the smallest distance is negative n − 1 times and positive 0 times. The second smallest is negative n − 2 times and positive once, and so on, yielding λ = (−(n − 1), −(n − 3), −(n − 5), …, + (n − 1)).

3 Geometric branch and bound techniques

Global optimization is defined as finding the global optimum to a non-convex objective function with possibly many local optima. Usually the solution methods are based on a branch and bound approach. For a successful application of such techniques, an efficient lower bound (for minimization) or upper bound (for maximization) is required. There are four branch and bound approaches to locating a single facility. We describe in more detail the original Sect. 3.1 [37]. The other three algorithms are based on this basic method.

3.1 Big Square Small Square (BSSS)

The Big Square Small Square was suggested by Hansen, Peeters and Thisse [37] and generalized by Plastria [47].

Consider a minimization problem in a feasible area. The following is the branch and bound procedure. We implicitly assume that the value of the objective function at infeasible points is higher than the optimum, which can be achieved by a penalty added to non-feasible solutions or requires checking feasibility during the process. A relative accuracy ε is given.

  • Start with a big square that includes an optimal solution. The set of squares consists of the big square.

  • The value of the objective function at the center of the square (another point can be selected when it is advantageous) is used to generate the best-known solution (BK).

  • Split the square into four small squares by lines through its center parallel to its sides as is shown in Fig. 1.

    Fig. 1
    figure 1

    Splitting a big square into four small squares

    Full size image

  • Calculate the value of the objective function at the center of each of the four small squares. Update BK if necessary.

  • Calculate a lower bound on the value of the objective function for each of the small squares.

  • Discard all small squares for which LB ≥ (1 − ε)BK.

  • Add the remaining small squares to the set of squares, and remove the big square and all other squares for which LB ≥ (1 − ε)BK.

  • Select the square in the set of squares with the lowest LB as the next “big square.” Other selection rules are possible.

  • Split the big square into four small squares, and repeat until there are no squares left in the set.

  • The BK is within ε of the optimal solution.

The efficiency of the procedure depends mainly on the quality of the lower bound in a square.

3.2 Big Triangle Small Triangle (BTST)

The procedure Big Triangle Small Triangle (BTST) by Drezner and Suzuki [22] is based on the same idea as BSSS but using triangles rather than squares. The feasible area (usually the convex hull of demand points) is triangulated by the Delaunay triangulation [43] using demand points as vertices. The initial set of triangles is the result of the triangulation rather than a “Big Square.” During the process big triangles are split into four small triangles as depicted in Fig. 2. Note that the small four triangles have the exact same shape as the big triangle.

Fig. 2
figure 2

Splitting a big triangle into four small triangles

Full size image

There are two main advantages of BTST over BSSS: (1) If there is a feasible region that can be expressed as a union of polygons such as the convex hull of the demand points which is one polygon, no feasibility check is required for BTST because all the points in a triangle are “automatically” feasible. However, when BSSS is used, points need to be checked for feasibility unless infeasible points are known to be inferior. A clear example is obnoxious facility location when being farther from demand points leads to better value of the objective function, and if the problem is unconstrained, the optimal solution is at infinity. Suppose that we wish to find a solution in the convex hull of demand points (or any union of convex polygons). The optimal solution inside a “big square” is likely to be at one of the vertices of the square outside the convex hull. A special care is needed to make sure that the points considered are feasible. When upper bound (for minimization) and lower bound (for maximization) are sought, the value of the objective function at a point in the square, such as the center of the square, is calculated. What if the center of the square is infeasible? Also, an efficient bound may be more difficult to construct because the bound should be based only on points in the feasible part of the square. (2) There are no demand points in the interior of a triangle (true for both the Dealunay triangles and all subsequent ones) which may help in constructing an efficient lower bound. There are two main disadvantages to BTST: (1) The initial set of triangles has close to 2n triangles which may be a waste. (2) The idea cannot be generalized to more than two dimensions as is done in BCSC [49]. There is no clear way to split a k-dimensional polyhedron into smaller polyhedra.

Convergence of the BTST algorithm is discussed in [31] where a bound on the number of generated triangles is established.

Examples (all can be solved by BSSS or BTST):

  • Mixed weights Weber problem [25, 53].

  • Obnoxious facility [5, 22, 37].

  • Huff competitive location models [1, 11, 34, 52].

  • Competitive Model with a threshold objective [19].

  • The Weber problem with a threshold objective [15].

  • Inventory-Location Problem [30].

  • Minimize the variance of distances [12, 33].

  • Minimize the range of distances [12, 33].

  • Location with acceleration-deceleration [17].

  • Maximize cover with gradual cover objective [31].

  • Location with limited distances [29].

  • Locating objects in the plane such as segments, arcs of circumferences, arbitrary convex sets, their complements or their boundaries [7].

  • Lost demand in a competitive environment [13].

  • Location of a Facility Minimizing Nuisance to or from a Planar Network [16].

  • Solving Scheduling and Location Problems in the Plane Simultaneously [42].

  • A Stochastic Gradual Cover Location Problem [20].

  • Location of a production firm [23].

  • Equity across groups [14].

  • Locating a service facility with some unserviced demand [24].

  • The planar k-centrum problem [48].

3.3 Big Cube Small Cube (BCSC)

The Big Cube Small Cube by Schöbel and Scholz [49] is a generalization of the BSSS based on cubes in k dimensions. For example, solving a two-facilities problem is formulated in four dimensions. Every “Big Cube” is split into 2k “Small Cubes.” For k ≥4 Schöbel and Scholz [49] suggested, based on Toth et al. [52], to split a hypercube to two cuboids along the longest side of the cube so following many splits 2k smaller cubes of equal size are obtained. However, many of these small cubes may be eliminated in the process because a bigger cuboid containing several small cubes is discarded when its lower bound exceeds the best-known solution.

Convergence of the BCSC algorithm is discussed in [51]. Their discussion also applies to BSSS which is a special case of BCSC in two dimensions.

Examples demonstrated in Schöbel and Scholz [49] include the following:

  • The three-dimensional Weber problem with positive and negative weights.

  • The weighted median circle.

  • 2-median and 3-median planar problems. (see Daskin [10] for a discussion of p-median problems). This model was solved by D.C. optimization (see Sect. 4) by [9].

3.4 Big Segment Small Segment

The method Big Segment Small Segment by Berman, Drezner and Krass [3] is suitable for facility location problems anywhere on a network. Segments (links or parts of links) replace squares. The initial set consists of all the links of the network. Each big segment is split into two small segments.

Examples solved in [3]:

  • Weber problem with positive and negative weights [25, 53].

  • Obnoxious facility. Disturbance declines by the square of the distance. Locate the facility on a link such that total disturbance is minimized. The problem in the plane is analyzed in [22, 37].

  • Competitive facility location on the network [40, 41].

  • Minimum covering problem [5].

  • Minimum covering problem with two facilities [2].

4 DC optimization for location analysis

DC (difference of two convex functions) optimization [6, 38, 39, 45, 53] is a general efficient approach for constructing effective lower bounds. Implementing the four optimization techniques described in Sect. 3 requires effective lower (or upper) bounds. DC optimization provides effective bounds for many location problems. Other bounds such as interval extension [34, 35, 52] or others specific to particular location problems are also used. For a review see [50].

4.1 A general description of DC optimization

Suppose that an objective function F(X) can be expressed as a difference between two convex functions: F(X) = G(X) − H(X). A lower bound LB is generated in a polyhedron such that LB ≤ F(X) for any X in the polyhedron.

  • Select a point X 0 in the polyhedron.

  • Construct a tangent plane T(X) to G(X) at X 0 .

  • T(X) ≤ G(X) by the convexity of G(X).

  • F(X) = G(X) − H(X) ≥ T(X) − H(X) = U(X).

  • T(X) is linear and thus concave.

  • U(X) is concave and obtains its minimum at one of the vertices of the polyhedron.

  • The minimum value of U(X) at the vertices of the polyhedron is a lower bound in the polyhedron.

4.1.1 A “Classic” example:

Consider the Weber problem: \( F(X) = \sum\nolimits_{i = 1}^{n} {w_{i} d_{i} (X)} \) when the weights can be positive or negative [25]. This problem is not convex. The sum is partitioned into two sums: One includes all positive weights, and one includes all negative weights (with reverse signs). Since a weighted sum of distances using positive weights is convex, these two sums are a representation of F(X) as a difference between two convex functions.

4.2 Application of DC optimization to location problems

Drezner [21] designed a general algorithm for solving single facility location problems that have a special structure. The algorithm is based on BTST but can be used as well using BSSS. Consider a minimization of a function of the type \( F(X) = \sum\nolimits_{i = 1}^{n} {\phi_{i} (d_{i} (X)} ) \) for functions φ(d), which can be expressed as a difference between two convex functions in d. This condition is not the customary condition in DC optimization when the assumption is that φ(d(X)) is a difference between convex functions in the location X. The distance function d(X) is a convex function in X. However, a convex function of a convex function is not necessarily convex.

For every demand point there are minimum and maximum distances to all the points in the triangle (or a square for applying BSSS) dmin and dmax. Therefore, we just need to bound φ(d) in the range dmin ≤ d ≤ dmax. The tangent plane is a tangent line in d and not a tangent plane in X.

Suppose that the function φ(d) can be expressed as a difference between two convex functions φ 1 (d) − φ 2 (d). It is usually not difficult to express a function of one variable as a difference between two convex functions. For example, if the second derivative of φ(d) exists for dmin ≤ d ≤ dmax and is bounded such that ∂2φ/∂d2 ≥ − M, then φ(d) = [φ(d) + Md2/2] − Md2/2 is a difference between two convex functions in d. It is recommended, if possible, to express φ(d) as a difference between two convex functions which have no artificially large values [8]. Sometimes it is tractable to find the second derivative of φ(d) by d, separate it to a difference between two positive expressions and double integrate each of these functions obtaining a difference between two convex functions. It suffices to double integrate one of the functions, and the second one can be obtained as a difference between φ(d) and that function. For example, consider the function φ(d) = 1/(a + ed) with a > 0 which is common in competitive Huff-like location models [11, 40, 41, 52] with exponential decay. The second derivative of this function is \( \frac{{e^{2d} - ae^{d} }}{{(a + e^{d} )^{3} }} \) which clearly indicates that the function is neither convex nor concave. This expression is a difference between two positive numbers. Double integration of the negative term yields \( \varphi_{2} \left( d \right) = \frac{1}{2a}{ \ln }(1 + ae^{ - d} ) - \frac{0.5}{{a + e^{d} }} \) leading to \( \varphi_{1} \left( d \right) = \frac{1}{2a}{ \ln }(1 + ae^{ - d} ) + \frac{0.5}{{a + e^{d} }} \) which are two small-valued convex functions. It can be proven that these two functions are bounded between 0 and e−d.

We construct a general lower bound in a triangle. The minimum and maximum possible distance between a demand point and a facility located anywhere in the triangle (or square for BSSS) is found [21]. See Fig. 3. Note that by design of the Delaunay triangulation, the demand point cannot be in the interior of the triangle (it can be one of its vertices). However, in BSSS the demand point can be in the interior of the square in which case the minimum distance is zero. A convex function for d between dmin and dmax is bounded between the line connecting the end points dmin and dmax and their value of the objective function and the tangent line at the middle of the segment. See Fig. 4.

Fig. 3
figure 3

Finding the minimum and maximum distance

Full size image
Fig. 4
figure 4

Bounds on a convex function

Full size image

That means that for demand point i we calculate \( \alpha_{i} ,\beta_{i} ,\gamma_{i} ,\delta_{i} \) which define the relevant line for these functions:

$$ \varphi_{1} \left( {d\left( X \right)} \right) \ge \alpha_{i} d_{i} \left( X \right) + \beta_{i} ; \varphi_{2} \left( {d\left( X \right)} \right) \le \gamma_{i} d_{i} \left( X \right) + \delta_{i} $$

Therefore,

$$ F\left( X \right) = \mathop \sum \limits_{i = 1}^{n} \varphi_{i} \left( {d_{i} \left( X \right)} \right) \ge \mathop \sum \limits_{i = 1}^{n} (\alpha_{i} - \gamma_{i} )d_{i} \left( X \right) + \mathop \sum \limits_{i = 1}^{n} \left( {\beta_{i} - \delta_{i} } \right) $$

The second sum is constant. The first sum is the classic Weber problem with positive and negative weights that can be expressed as a difference between two convex functions and bounded from below leading to an effective lower bound.

It is proved in [21] that if the second derivative of φ(d) by d is bounded, then the difference between the lower bound and the minimum value of the objective function in the triangle (error) is approximately proportional to the square of the side of the triangle. Therefore, when a triangle is split into four triangles, the error in the lower bound for each of the four smaller triangles is reduced by about fourfold. Five splits of triangles reduce the error by about one thousand times.

4.3 Solving general ordered median problems

Drezner and Nickel [27, 28] suggested two different approaches for solving general ordered median problems. In one approach three lower bounds are suggested [27]. The Lipschitz lower bound is based on the radius r of the circle circumscribing the triangle. The minimum value of the objective function at the three vertices of the triangle is calculated. The extra possible reduction in the value of the objective function at up to distance r from the vertex is bounded. The lower bound based on individual distances is derived by replacing the vector of distances by the shortest distances to the triangle for positive λs and the largest distance for negative λs. A third heuristic lower bound is based on estimating the Lipschitz constant by evaluating the value of the objective function on a grid of points in the triangle.

The second approach is based on DC optimization [28]. An important theorem [46]: The order median function is convex if and only if 0 ≤ λ1 ≤ λ2 ≤ , …, ≤ λn.

For a given vector λ we express it as λ = λ’ − λ” such that both λ’ and λ” satisfy the theorem and thus represent convex functions. This is done sequentially from left to right guaranteeing that the first λ is nonnegative and that each λ is greater than or equal to the previous one. The objective function is represented as a difference between two convex functions. The DC optimization approach is implemented. The first convex function is replaced by a tangent plane. The DC lower bound yields a very effective one.

4.4 Examples for ordered median applications

  • Minimize the median of distances [28].

  • Minimize the truncated mean of distances [28].

  • Minimize the range of distances [12].

  • Minimize the inter-quartile range [28].

  • Minimize the sum of k largest distances [48].

  • Maximize the sum of k smallest distances [44].

  • Minimize the Gini coefficient of the Lorenz curve [18].

  • Minimize absolute deviation of distances [26].

  • The expropriation problem [4].

5 Comments on solving multiple facilities problems

Solving multiple facilities to optimality may be done by the Big Cube Small Cube for a small number of facilities. It can also be done by nested BTST or BSSS, Big Segment Small Segment or other methods, but it may not be efficient. Heuristically, it can be done by fixing p − 1 facilities and optimizing the free facility by BTST or another technique. Some specific problems can be solved by exploiting special structures of the particular problem. In some cases a set of dominating points can be identified, thus reducing the infinite number of possible solutions to a manageable number. Using metaheuristic approaches such as tabu search, simulated annealing, evolutionary methods, variable neighborhood search and others probably remain the best approach to heuristically solve most multiple facilities problems.