Optimal facility location (OFL), also called location analysis, is a class of optimization problems. In all these problems, the goal is to decide where to locate some facility (e.g. a school, a gas station, a factory, etc.), in a way that optimizes some pre-specified criteria. Some examples are:
"Decide where to locate a new school, given the locations of the students, such that the sum of daily transportation costs of all students to the school will be as small as possible." "Decide where to locate a new factory, given the locations of citizens, such that the minimum distance between the factory and a citizen house is as large as possible".
OFL is studied in operations research, computational geometry (a branch of computer science), and location theory (a branch of economics). Some techniques used for OFL also apply to cluster analysis.
There are various kinds of OFL problems. They differ in their objective function (e.g. sum of distances or minimum distance), in the optimization direction (maximization vs. minimization), in the number of facilities (one vs. many), and more.
Utilitarian location: minimizing the sum of distances
A minisum facility location problem is an OFL in which the input is a set of points in space, and the goal is to find a location for a facility, such that the sum of distances between the facility to the points is as small as possible. If the points correspond to people, and the distances correspond to their dis-utility (the cost they incur from traveling to a faraway facility), then minisum OFL is an instantiation of the utilitarian rule. Some special cases are:
If there are only 3 input points, the solution is their Fermat point of the triangle. If there are n points, the solution is their geometric median. The Weber problem is a generalization in which each input point has a weight, and the goal is to minimize the weighted sum of distances.
In the most general form, there can be multiple facilities, but each facility has a construction cost. The goal is to pick a subset of facilities to open, to minimize the sum of distances from each demand point to its nearest facility, plus the sum of construction costs of the facilities. A different common formulation limits the number of facilities to a fixed integer k instead of giving them a cost.
The minisum facility location problem on general graphs is NP-hard to solve optimally, by reduction from (for example) the set cover problem. A number of approximation algorithms have been developed for the facility location problem and many of its variants.
Without assumptions on the set of distances between clients and sites (in particular, without assuming that the distances satisfy the triangle inequality), the problem is known as non-metric facility location and can be approximated to within a factor O(log n). This factor is tight, via an approximation-preserving reduction from the set cover problem.
If we assume distances between clients and sites are undirected and satisfy the triangle inequality, we are talking about a metric facility location (MFL) problem. The MFL is still NP-hard and hard to approximate within factor better than 1.463. The currently best known approximation algorithm achieves approximation ratio of 1.488.
Egalitarian location: Minimizing the maximum distance A minimax facility location problem is an OFL in which the input is a set of points in space, and the goal is to find a location for a facility, such that the largest distance between the facility and any of the points is as small as possible. If the points correspond to people, and the distances correspond to their dis-utility, then minimax OFL is an instantiation of the egalitarian rule. Some special cases are:
In the case of the Euclidean metric for (one facility) on the plane, it is known as the smallest enclosing circle problem. For one facility in three dimensional space, it is known as the smallest enclosing sphere problem or 1-center problem. Its study is traced at least to the year of 1860. The general problem with k facilities, in a general metric space, is called Metric k-center.
The multi-facility variant can be formally defined as follows:Given a point set ,
find a point set
so that
is minimized.
NP hardness Exact solution of k-center problem is NP hard.. . . Approximation to the problem was found to be also NP hard when the error is small. The error level in the approximation algorithm is measured as an approximation factor, which is defined as the ratio between the approximation and the optimum. It's proved that the k-center problem approximation is NP hard when approximation factor is less than 1.822 (dimension = 2) or 2 (dimension > 2).
Algorithms Exact solver
There exist algorithms to produce exact solutions to this problem. One exact solver runs in time .
1 + ε approximation
1 + ε approximation is to find a solution with approximation factor no greater than 1 + ε. This approximation is NP hard as ε is arbitrary. One approach based on the coreset concept is proposed with execution complexity of . As an alternative, another algorithm also based on core sets is available. It runs in . The author claims that the running time is much less than the worst case and thus it's possible to solve some problems when k is small (say k < 5).
Farthest-point clustering
For the hardness of the problem, it's impractical to get an exact solution or precise approximation. Instead, an approximation with factor = 2 is widely used for large k cases. The approximation is referred to as the farthest-point clustering (FPC) algorithm, or farthest-first traversal. The algorithm is quite simple: pick any point from the set as one center; search for the farthest point from remaining set as another center; repeat the process until k centers are found.
It is easy to see that this algorithm runs in linear time. As approximation with factor less than 2 is proved to be NP hard, FPC was regarded as the best approximation one can find.
As per the performance of execution, the time complexity is later improved to O(n log k) with box decomposition technique.
Maximizing the minimum distance A maximin facility location, also called obnoxious facility location problem, seeks a location which maximizes the smallest distance to the input points. It is another instantiation of the egalitarian rule, assuming that the utility of each agent is an increasing function of the distance from the obnoxious facility.
In the case of the Euclidean metric, it is known as the largest empty sphere problem. The planar single-facility case (largest empty circle problem) may be solved in optimal time Θ(n log n)., p. 256G. T. Toussaint, "Computing largest empty circles with location constraints," International Journal of Computer and Information Sciences, vol. 12, No. 5, October, 1983, pp. 347–358.
Integer programming formulations OFL problems are often solved as integer programs, posed as follows: suppose there are facilities and customers. We wish to choose (1) which of the facilities to open, and (2) which (open) facilities to use to supply the customers, in order to satisfy some fixed demand at minimum cost. We introduce the following notation: let denote the (fixed) cost of opening facility , for . Let denote the cost to ship a product from facility to customer for and . Let denote the demand of customer for . Further suppose that each facility has a maximum output. Let denote the maximum amount of product that can be produced by facility , that is, let denote the capacity of facility . The remainder of this section follows.
Capacitated facility location In our initial formulation, introduce a binary variable for , where if facility is open, and otherwise. Further introduce the variable for and which represents the fraction of the demand filled by facility . The so-called capacitated facility location problem is then given by
Note that the second set of constraints ensures that if , that is, facility isn't open, then for all , that is, no demand for any customer can be filled from facility .
Uncapacitated facility location A common case of the capacitated facility location problem above is the case when for all . In this case, it is always optimal to satisfy all of the demand from customer from the nearest open facility. Because of this, we may replace the continuous variables from above with the binary variables , where if customer is supplied by facility , and otherwise. The uncapacitated facility location problem is then given by
where is a constant chosen to be suitably large. The choice of can affect computation results—the best choice in this instance is obvious: take . Then, if , any choice of the will satisfy the second set of constraints.
Another formulation possibility for the uncapacitated facility location problem is to disaggregate the capacity constraints (the big- constraints). That is, replace the constraintswith the constraintsIn practice, this new formulation performs significantly better, in the sense that it has a tighter linear programming relaxation than the first formulation. Notice that summing the new constraints together yields the original big- constraints. In the capacitated case, these formulations are not equivalent. More information about the uncapacitated facility location problem can be found in Chapter 3 of "Discrete location theory".
Pareto-efficient locations Rather than finding a location that optimizes a single objective, one may be interested in finding all locations that can possibly be optimal for some objective. This is defined formally as follows. Let X be a normed space with norm |.|. Let A be a non-empty subset of X. A point x in X is called ---
Strictly efficient w.r.t. A if for all y≠x there exists a in A that is nearer to x than to y (|a-x| < |a-y|). Equivalently: the intersection (for all a in A) of Ball(a,|x-a|) is the singleton {x}. Efficient w.r.t. A if for all y≠x either there exists a in A that is nearer to x than to y (|a-x| < |a-y|), or all a in A are at least as near to x than to y (|a-x| ≤ |a-y|). Equivalently: the intersection (for all a in A) of Ball(a,|x-a|), intersect the union (for all a in A) of interior(Ball(a,|x-a|)), is empty. Weakly efficient w.r.t A if for all y≠x there exists a in A that is at least as near to x as to y (|a-x| ≤ |a-y|). Equivalently: the intersection (for all a in A) of interior(Ball(a,|x-a|)) is empty.
These concepts are motivated by considering each point in A as representing the location of an agent, and the points x and y are potential locations for a facility. Each agent prefers the facility to be as near as possible to his own location. With this interpretation, efficiency and weak-efficiency correspond to the economic notions of Pareto-efficiency and weak Pareto-efficiency respectively.
Every location minimizing the sum of distances, or the weighted sum of distances, is efficient w.r.t. the input points. Every location minimizing the maximum distance is weakly-efficient w.r.t. the input points.
These efficiency concepts satisfy the following properties for every norm:
If A is bounded, then the sets of strictly-efficient, efficient and weakly-efficient points are all bounded. If A is a subset of B, then the same containment holds between the sets of strictly-efficient points and the set of weakly-efficient points, but not between the sets of efficient points. The sets of strictly-efficient and efficient points are closed under closure, but the set of weakly-efficient points is not.
With some assumptions on the norm, additional properties are satisfied:
If X is a strictly convex normed space, then all three efficiency concepts are equivalent. If X is a Hilbert space (for example, when the norm is the L2 norm), then for all three efficiency concepts, the set of points satisfying them is the closed convex hull of A.