Facility location
Encyclopedia
Facility location, also known as location analysis, is a branch of operations research
and computational geometry
concerning itself with mathematical modeling and solution of problems concerning optimal placement of facilities in order to minimize transportation costs, avoid placing hazardous materials near housing, outperform competitors' facilities, etc.
In a basic formulation, the Facility Location problem consists of a set of potential facility sites L where a facility can be opened, and a set of demand points D that must be serviced. The goal is to pick a subset F of facilities to open, to minimize the sum of distances from each demand point to its nearest facility, plus the sum of opening costs of the facilities.
The 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 (FP) 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 is approximable 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 problem (MFL). The MFL is still NP-hard and hard to approximate within factor better than 1.46. The currently best known approximation algorithm achieves approximation ratio of 1.488 .
In the case of the Euclidean metric, it is known as the smallest enclosing sphere problem or 1-center problem
. Its study traced a least to the year of 1860. The planar case (smallest enclosing circle problem) may be solved in optimal time
.
problem. The planar case (largest empty circle problem) may be solved in optimal time
Operations research
Operations research is an interdisciplinary mathematical science that focuses on the effective use of technology by organizations...
and computational geometry
Computational geometry
Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems are also considered to be part of computational...
concerning itself with mathematical modeling and solution of problems concerning optimal placement of facilities in order to minimize transportation costs, avoid placing hazardous materials near housing, outperform competitors' facilities, etc.
Minsum facility location
A simple facility location problem is the Fermat-Weber problem, in which a single facility is to be placed, with the only optimization criterion being the minimization of the sum of distances from a given set of point sites. More complex problems considered in this discipline include the placement of multiple facilities, constraints on the locations of facilities, and more complex optimization criteria.In a basic formulation, the Facility Location problem consists of a set of potential facility sites L where a facility can be opened, and a set of demand points D that must be serviced. The goal is to pick a subset F of facilities to open, to minimize the sum of distances from each demand point to its nearest facility, plus the sum of opening costs of the facilities.
The Facility Location problem on general graphs is NP-hard
NP-hard
NP-hard , in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H...
to solve optimally, by reduction from (for example) the Set Cover problem. A number of approximation algorithms have been developed for the facility location (FP) 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
Triangle inequality
In mathematics, the triangle inequality states that for any triangle, the sum of the lengths of any two sides must be greater than or equal to the length of the remaining side ....
), the problem is known as Non-Metric Facility Location and is approximable 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 problem (MFL). The MFL is still NP-hard and hard to approximate within factor better than 1.46. The currently best known approximation algorithm achieves approximation ratio of 1.488 .
Minimax facility location
The minimax facility location problem seeks a location which minimizes the maximum distance to the sites.In the case of the Euclidean metric, it is known as the smallest enclosing sphere problem or 1-center problem
1-center problem
The 1-center problem or minimax or minmax location problem is a classical combinatorial optimization problem in operations research of facilities location type...
. Its study traced a least to the year of 1860. The planar case (smallest enclosing circle problem) may be solved in optimal time
Time complexity
In computer science, the time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the size of the input to the problem. The time complexity of an algorithm is commonly expressed using big O notation, which suppresses multiplicative constants and...
.Maxmin facility location
The maxmin facility location or obnoxious facility location problem seeks a location which maximizes the minimum distance to the sites. In the case of the Euclidean metric, it is known as the largest empty sphereLargest empty sphere
In computational geometry, the largest empty sphere problem is the problem of finding a hypersphere of largest radius in d-dimensional space whose interior does not overlap with any given obstacles.-Two dimensions:...
problem. The planar case (largest empty circle problem) may be solved in optimal time
Time complexity
In computer science, the time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the size of the input to the problem. The time complexity of an algorithm is commonly expressed using big O notation, which suppresses multiplicative constants and...
External links
- INFORMS section on location analysis, a professional society concerned with facility location.
- Bibliography on facility location collected by Trevor Hale, containing over 3400 articles.
- Library of location algorithms
- Web-based facility location utility (single facility)