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 k = 1 (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 P ⊂ R d {\displaystyle \mathbb {R} ^{d}} , find a point set S ⊂ R d {\displaystyle \mathbb {R} ^{d}} , |S| = k, so that
maxp ∈ P(minq ∈ S(d(p, q)) ) 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).
… excerpt ends here. Continue reading the full article.
