Facility location

Facility location

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.


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 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)).[1] 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 [2].

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. Its study traced a least to the year of 1860. The planar case (smallest enclosing circle problem) may be solved in optimal time \Theta(n\, \log\, n).[3]

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 sphere problem. The planar case (largest empty circle problem) may be solved in optimal time \Theta(n\, \log\, n)\,. [3][4]

See also


  1. ^ D. S. Hochbaum. Heuristics for the fixed cost median problem. Math. Programming, 22:148-162, 1982.
  2. ^ Shi Li. A 1.488-approximation algorithm for the uncapacitated facility location problem. International Colloquium on Automata, Languages and Programming (ICALP), pages 77-88, 2011 [1]
  3. ^ a b Franco P. Preparata and Michael Ian Shamos (1985). Computational Geometry - An Introduction. Springer-Verlag. 1st edition: ISBN 0-387-96131-3; 2nd printing, corrected and expanded, 1988: ISBN 3-540-96131-3; Russian translation, 1989: ISBN 5-03-001041-6. , p. 256
  4. ^ G. 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.

External links

Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Facility Location — Bei einem Facility Location Problem (FL) handelt es sich um ein Optimierungsproblem, in dem es darum geht aus einer Menge an Standorten eine Teilmenge als Versorgungsstandorte auszusuchen, dass diese unter den gegebenen Bedingungen optimal… …   Deutsch Wikipedia

  • Location based advertising — (LBA) Location based advertising (LBA) is a new form of marketing communication that uses location tracking technology in mobile networks to target consumers with location specific advertising on their mobile devices. As Bruner Kumar (2007)… …   Wikipedia

  • Location-allocation — is the process of finding the best locations for one or more facilities that will service a given set of points and then assigning those points to the facilities, taking into account factors such as the number of facilities available, their cost …   Wikipedia

  • Facility registry system — The Facility Registry System The Facility Registry System (FRS) is a centrally managed Environmental Protection Agency database that identifies facilities, sites or places of environmental interest. FRS creates high quality, accurate, and… …   Wikipedia

  • Facility —   A location where electric energy is generated from energy sources.   ***   An existing or planned location or site at which prime movers, electric generators, and/or equipment for converting mechanical, chemical, and/or nuclear energy into… …   Energy terms

  • Location identifier — A location identifier is a symbolic representation for the name and the location of an airport, navigation aid, or weather station, and is used for manned air traffic control facilities in air traffic control, telecommunications, computer… …   Wikipedia

  • facility — noun 1) parking facilities Syn: provision, space, means, potential, equipment 2) the facilities consisted of an old wooden outhouse Syn: washroom, toilet, restroom, bathroom 3) a wealth of l …   Thesaurus of popular words

  • facility — noun 1) car parking facilities Syn: provision, space, means, equipment 2) the camera has a zoom facility Syn: feature, setting, mode, option 3) a wealth of local facilities …   Synonyms and antonyms dictionary

  • Coxsackie Correctional Facility — Location Coxsackie, New York, USA Status Operational Security class Maximum Managed by New York State Department of Correctional Services Coxsackie Correctional Facility is a maximum security prison in New York in the USA. The prison is in the …   Wikipedia

  • Westville Correctional Facility — The Westville Correctional Facility, located in Westville, Indiana, is a state operated prison for adult males. The facility contains sections of three levels of security.cite web url = http://indianafind.com/Government/Correctional… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”