[{"@context":"http:\/\/schema.org\/","@type":"BlogPosting","@id":"https:\/\/wiki.edu.vn\/en\/wiki14\/facility-location-problem-wikipedia\/#BlogPosting","mainEntityOfPage":"https:\/\/wiki.edu.vn\/en\/wiki14\/facility-location-problem-wikipedia\/","headline":"Facility location problem – Wikipedia","name":"Facility location problem – Wikipedia","description":"before-content-x4 The study of facility location problems (FLP), also known as location analysis, is a branch of operations research and","datePublished":"2018-03-23","dateModified":"2018-03-23","author":{"@type":"Person","@id":"https:\/\/wiki.edu.vn\/en\/wiki14\/author\/lordneo\/#Person","name":"lordneo","url":"https:\/\/wiki.edu.vn\/en\/wiki14\/author\/lordneo\/","image":{"@type":"ImageObject","@id":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","height":96,"width":96}},"publisher":{"@type":"Organization","name":"Enzyklop\u00e4die","logo":{"@type":"ImageObject","@id":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","url":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","width":600,"height":60}},"image":{"@type":"ImageObject","@id":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/f34bc331a34c0035eb426a0cd38b4019f852df54","url":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/f34bc331a34c0035eb426a0cd38b4019f852df54","height":"","width":""},"url":"https:\/\/wiki.edu.vn\/en\/wiki14\/facility-location-problem-wikipedia\/","wordCount":14548,"articleBody":"     (adsbygoogle = window.adsbygoogle || []).push({});before-content-x4The study of facility location problems (FLP), also known as location analysis, is a branch of operations research and computational geometry concerned with the optimal placement of facilities to minimize transportation costs while considering factors like avoiding placing hazardous materials near housing, and competitors’ facilities. The techniques also apply to cluster analysis.       (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4Table of ContentsMinimum facility location[edit]Minimax facility location[edit]NP hardness[edit]Algorithms[edit]Maxmin facility location[edit]Integer programming formulations[edit]Capacitated facility location[edit]Uncapacitated facility location[edit]Applications[edit]Healthcare[edit]Solid waste management[edit]Clustering[edit]See also[edit]References[edit]External links[edit]Minimum facility location[edit]A simple facility location problem is the Weber problem, in which a single facility is to be placed, with the only optimization criterion being the minimization of the weighted 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.       (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4In 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 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\u00a0n).[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 (MFL) problem. The MFL is still NP-hard and hard to approximate within factor better than 1.463.[2] The currently best known approximation algorithm achieves approximation ratio of 1.488.[3]       (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4Minimax facility location[edit]The minimax facility location problem seeks a location which minimizes the maximum distance to the sites, where the distance from one point to the sites is the distance from the point to its nearest site. A formal definition is as follows:Given a point set P\u00a0\u2282\u00a0\u211dd, find a point set S\u00a0\u2282\u00a0\u211dd, |S|\u00a0=\u00a0k, so that maxp\u00a0\u2208\u00a0P(minq\u00a0\u2208\u00a0S(d(p,\u00a0q)) ) is minimized.In the case of the Euclidean metric for k\u00a0=\u00a01, it is known as the smallest enclosing sphere problem or 1-center problem. Its study traced at least to the year of 1860. see smallest enclosing circle and bounding sphere for more details.NP hardness[edit]It has been proven that exact solution of k-center problem is NP hard.[4][5][6]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\u00a0=\u00a02)[7] or 2 (dimension\u00a0>\u00a02).[6]Algorithms[edit]Exact solverThere exist algorithms to produce exact solutions to this problem. One exact solver runs in time nO(k){displaystyle n^{O({sqrt {k}})}}.[8][9]1 + \u03b5 approximation1\u00a0+\u00a0\u03b5 approximation is to find a solution with approximation factor no greater than\u00a01\u00a0+\u00a0\u03b5. This approximation is NP hard as \u03b5 is arbitrary. One approach based on the coreset concept is proposed with execution complexity of  O(2O(klog\u2061k\/\u03b52)dn){displaystyle O(2^{O(klog k\/varepsilon ^{2})}dn)}.[10]As an alternative, another algorithm also based on core sets is available. It runs in O(kn){displaystyle O(k^{n})}.[11] 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\u00a0k\u00a0,n{displaystyle i=1,dots ,n} and j=1,\u2026,m{displaystyle j=1,dots ,m}. Let dj{displaystyle d_{j}} denote the demand of customer j{displaystyle j} for j=1,\u2026,m{displaystyle j=1,dots ,m}. Further suppose that each facility has a maximum output. Let ui{displaystyle u_{i}} denote the maximum amount of product that can be produced by facility i{displaystyle i}, that is, let ui{displaystyle u_{i}} denote the capacity of facility i{displaystyle i}. The remainder of this section follows[14]Capacitated facility location[edit]In our initial formulation, introduce a binary variable xi{displaystyle x_{i}} for i=1,\u2026,n{displaystyle i=1,dots ,n}, where xi=1{displaystyle x_{i}=1} if facility i{displaystyle i} is open, and xi=0{displaystyle x_{i}=0} otherwise. Further introduce the variable yij{displaystyle y_{ij}} for i=1,\u2026,n{displaystyle i=1,dots ,n} and j=1,\u2026,m{displaystyle j=1,dots ,m} which represents the fraction of the demand dj{displaystyle d_{j}} filled by facility i{displaystyle i}. The so-called capacitated facility location problem is then given bymin\u2211i=1n\u2211j=1mcijdjyij+\u2211i=1nfixis.t.\u2211i=1nyij=1\u00a0for all\u00a0j=1,\u2026,m\u2211j=1mdjyij\u2a7duixi\u00a0for all\u00a0i=1\u2026,nyij\u2a7e0\u00a0for all\u00a0i=1,\u2026,n\u00a0and\u00a0j=1,\u2026,mxi\u2208{0,1}\u00a0for all\u00a0i=1,\u2026,n{displaystyle {begin{array}{rl}min &displaystyle sum _{i=1}^{n}sum _{j=1}^{m}c_{ij}d_{j}y_{ij}+sum _{i=1}^{n}f_{i}x_{i}\\{text{s.t.}}&displaystyle sum _{i=1}^{n}y_{ij}=1{text{ for all }}j=1,dots ,m\\&displaystyle sum _{j=1}^{m}d_{j}y_{ij}leqslant u_{i}x_{i}{text{ for all }}i=1dots ,n\\&y_{ij}geqslant 0{text{ for all }}i=1,dots ,n{text{ and }}j=1,dots ,m\\&x_{i}in {0,1}{text{ for all }}i=1,dots ,nend{array}}}Note that the second set of constraints ensure that if xi=0{displaystyle x_{i}=0}, that is, facility i{displaystyle i} isn’t open, then yij=0{displaystyle y_{ij}=0} for all j{displaystyle j}, that is, no demand for any customer can be filled from facility i{displaystyle i}.Uncapacitated facility location[edit]A common case of the capacitated facility location problem above is the case when ui=+\u221e{displaystyle u_{i}=+infty } for all i=1,\u2026,n{displaystyle i=1,dots ,n}. In this case, it is always optimal to satisfy all of the demand from customer j{displaystyle j} from the nearest open facility. Because of this, we may replace the continuous variables yij{displaystyle y_{ij}} from above with the binary variables zij{displaystyle z_{ij}}, where zij=1{displaystyle z_{ij}=1} if customer j{displaystyle j} is supplied by facility i{displaystyle i}, and zij=0{displaystyle z_{ij}=0} otherwise. The uncapacitated facility location problem is then given bymin\u2211i=1n\u2211j=1mcijdjzij+\u2211i=1nfixis.t.\u2211i=1nzij=1\u00a0for all\u00a0j=1,\u2026,m\u2211j=1mzij\u2a7dMxi\u00a0for all\u00a0i=1\u2026,nzij\u2208{0,1}\u00a0for all\u00a0i=1,\u2026,n\u00a0and\u00a0j=1,\u2026,mxi\u2208{0,1}\u00a0for all\u00a0i=1,\u2026,n{displaystyle {begin{array}{rl}min &displaystyle sum _{i=1}^{n}sum _{j=1}^{m}c_{ij}d_{j}z_{ij}+sum _{i=1}^{n}f_{i}x_{i}\\{text{s.t.}}&displaystyle sum _{i=1}^{n}z_{ij}=1{text{ for all }}j=1,dots ,m\\&displaystyle sum _{j=1}^{m}z_{ij}leqslant Mx_{i}{text{ for all }}i=1dots ,n\\&z_{ij}in {0,1}{text{ for all }}i=1,dots ,n{text{ and }}j=1,dots ,m\\&x_{i}in {0,1}{text{ for all }}i=1,dots ,nend{array}}}where M{displaystyle M} is a constant chosen to be suitably large. The choice of M{displaystyle M} can affect computation results\u2014the best choice in this instance is obvious: take M=m{displaystyle M=m}. Then, if xi=1{displaystyle x_{i}=1}, any choice of the zij{displaystyle z_{ij}} will satisfy the second set of constraints.Another formulation possibility for the uncapacitated facility location problem is to disaggregate the capacity constraints (the big-M{displaystyle M} constraints). That is, replace the constraints\u2211j=1mzij\u2a7dMxi\u00a0for all\u00a0i=1,\u2026,n{displaystyle sum _{j=1}^{m}z_{ij}leqslant Mx_{i}{text{ for all }}i=1,dots ,n}with the constraintszij\u2a7dxi\u00a0for all\u00a0i=1,\u2026,n\u00a0and\u00a0j=1,\u2026,m{displaystyle z_{ij}leqslant x_{i}{text{ for all }}i=1,dots ,n{text{ and }}j=1,dots ,m}In practice, this new formulation performs significantly better, in the sense that it has a tighter Linear programming relaxation than the first formulation.[14] Notice that summing the new constraints together yields the original big-M{displaystyle M} 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”.[15]Applications[edit]Healthcare[edit]In healthcare, incorrect facility location decisions have a serious impact on the community beyond simple cost and service metrics; for instance, hard-to-access healthcare facilities are likely to be associated with increased morbidity and mortality. From this perspective, facility location modeling for healthcare is more critical than similar modeling for other areas.[16]Solid waste management[edit]Municipal solid waste management still remains a challenge for developing countries because of increasing waste production and high costs associated with waste management. Through the formulation and exact resolution of a facility location problem it is possible to optimize the location of landfills for waste disposal.[17]Clustering[edit]A particular subset of cluster analysis problems can be viewed as facility location problems. In a centroid-based clustering problem, the objective is to partition n{displaystyle n} data points (elements of a common metric space) into equivalence classes\u2014often called colors\u2014such that points of the same color are close to one another (equivalently, such that points of different colors are far from one another).[18]To see how one might view (read “transform” or “reduce”) a centroid-based clustering problem as a (metric) facility location problem, view each data point in the former as a demand point in the latter. Suppose that the data to be clustered are elements of a metric space M{displaystyle M} (e.g. let M{displaystyle M} be p{displaystyle p}-dimensional Euclidean space for some fixed p{displaystyle p}). In the facility location problem that we are constructing, we permit facilities to be placed at any point within this metric space M{displaystyle M}; this defines the set of allowed facility locations L{displaystyle L}. We define the costs c\u2113,d{displaystyle c_{ell ,d}} to be the pairwise distances between location-demand point pairs (e.g., see metric k-center). In a centroid-based clustering problem, one partitions the data into k{displaystyle k} equivalence classes (i.e. colors) each of which has a centroid. Let us see how a solution to our constructed facility location problem also achieves such a partition. A feasible solution is a non-empty subset L\u2032\u2286L{displaystyle L’subseteq L} of k{displaystyle k} locations. These locations in our facility location problem comprise a set of k{displaystyle k} centroids in our centroid-based clustering problem. Now, assign each demand point d{displaystyle d} to the location \u2113\u2217{displaystyle ell ^{*}} that minimizes its servicing-cost; that is, assign the data point d{displaystyle d} to the centroid \u2113\u2217:=argmin\u2113\u2208L{c\u2113,d}{displaystyle ell ^{*}:=mathrm {arg,min} _{ell in L}{c_{ell ,d}}} (break ties arbitrarily). This achieves the partitioning provided that the facility location problem’s costs c\u2113,d{displaystyle c_{ell ,d}} are defined such that they are the images of the centroid-based clustering problem’s distance function.The popular algorithms textbook Algorithm Design [19] provides a related problem-description and an approximation algorithm. The authors refer to the metric facility location problem (i.e. the centroid-based clustering problem or the metric k{displaystyle k}-center problem) as the center selection problem, thereby growing the list of synonyms.Furthermore, see that in our above definition of the facility location problem that the objective function f{displaystyle f} is general. Specific choices of f{displaystyle f} yield different variants of the facility location problem, and hence different variants of the centroid-based clustering problem. For example, one might choose to minimize the sum of distances from each location to each of its assigned demand points (\u00e0 la the Weber problem), or one might elect to minimize the maximum of all such distances (\u00e0 la the 1-center problem).See also[edit]References[edit]^ Hochbaum, D. S. (1982). “Heuristics for the fixed cost median problem”. Mathematical Programming. 22: 148\u2013162. doi:10.1007\/BF01581035. S2CID\u00a03451944.^ Guha, S.; Khuller, S. (1999). “Greedy Strikes Back: Improved Facility Location Algorithms”. Journal of Algorithms. 31: 228\u2013248. CiteSeerX\u00a010.1.1.47.2033. doi:10.1006\/jagm.1998.0993. S2CID\u00a05363214.^ Li, S. (2011). “A 1.488 Approximation Algorithm for the Uncapacitated Facility Location Problem”. Automata, Languages and Programming. LNCS. Vol.\u00a06756. pp.\u00a077\u201388. CiteSeerX\u00a010.1.1.225.6387. doi:10.1007\/978-3-642-22012-8_5. ISBN\u00a0978-3-642-22011-1.^ Fowler, R. J.; Paterson, M. S.; Tanimoto, S. L. (1981), “Optimal packing and covering in the plane are NP-complete”, Information Processing Letters, 12 (3): 133\u2013137, doi:10.1016\/0020-0190(81)90111-3.^ Megiddo, Nimrod; Tamir, Arie (1982), “On the complexity of locating linear facilities in the plane” (PDF), Operations Research Letters, 1 (5): 194\u2013197, doi:10.1016\/0167-6377(82)90039-6.^ a b c Gonzalez, Teofilo (1985), “Clustering to minimize the maximum intercluster distance”, Theoretical Computer Science, 38: 293\u2013306, doi:10.1016\/0304-3975(85)90224-5.^ a b Feder, Tom\u00e1s; Greene, Daniel (1988), “Optimal algorithms for approximate clustering”, Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing: 434\u2013444, doi:10.1145\/62212.62255, ISBN\u00a00897912640, S2CID\u00a0658151^ HWang, R. Z.; Lee, R. C. T.; Chang, R. C. (1993), “The slab dividing approach to solve the Euclidean p-center problem”, Algorithmica, 9 (1): 1\u201322, doi:10.1007\/BF01185335, S2CID\u00a05680676^ HWang, R. Z.; Chang, R. C.; Lee, R. C. T. (1993), “The generalized searching over separators strategy to solve some NP-Hard problems in subexponential time”, Algorithmica, 9 (4): 398\u2013423, doi:10.1007\/bf01228511, S2CID\u00a02722869^ B\u0101doiu, Mihai; Har-Peled, Sariel; Indyk, Piotr (2002), “Approximate clustering via core-sets” (PDF), Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing: 250\u2013257, doi:10.1145\/509907.509947, ISBN\u00a01581134959, S2CID\u00a05409535^ Kumar, Pankaj; Kumar, Piyush (2010), “Almost optimal solutions to k-clustering problems” (PDF), International Journal of Computational Geometry & Applications, 20 (4): 431\u2013447, doi:10.1142\/S0218195910003372^ Franco P. Preparata and Michael Ian Shamos (1985). Computational Geometry \u2013 An Introduction. Springer-Verlag. ISBN\u00a0978-0-387-96131-6. 1st edition; 2nd printing, corrected and expanded, 1988; Russian translation, 1989., p.\u00a0256^ 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\u2013358.^ a b Conforti, Michele; Cornu\u00e9jols, G\u00e9rard; Zambelli, Giacomo (2014). Integer Programming | SpringerLink. Graduate Texts in Mathematics. Vol.\u00a0271. doi:10.1007\/978-3-319-11008-0. ISBN\u00a0978-3-319-11007-3.^ Discrete location theory. Mirchandani, Pitu B., Francis, R. L. New York: Wiley. 1990. ISBN\u00a09780471892335. OCLC\u00a019810449.{{cite book}}:  CS1 maint: others (link)^ Ahmadi-Javid, A.; Seyedi, P.; Syam, S. (2017). “A Survey of Healthcare Facility Location”. Computers & Operations Research. 79: 223\u2013263. doi:10.1016\/j.cor.2016.05.018.^ Franco, D. G. B.; Steiner, M. T. A.; Assef, F. M. (2020). “Optimization in waste landfilling partitioning in Paran\u00e1 State, Brazil”. Journal of Cleaner Production. 283: 125353. doi:10.1016\/j.jclepro.2020.125353. S2CID\u00a0229429742.^ Hastie, Trevor; Tibshirani, Robert; Friedman, Jerome (2009). The elements of statistical learning (Second\u00a0ed.). Springer.^ Kleinberg, Jon; Tardos, \u00c9va (2006). Algorithm Design. Pearson.External links[edit]     (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4"},{"@context":"http:\/\/schema.org\/","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"item":{"@id":"https:\/\/wiki.edu.vn\/en\/wiki14\/#breadcrumbitem","name":"Enzyklop\u00e4die"}},{"@type":"ListItem","position":2,"item":{"@id":"https:\/\/wiki.edu.vn\/en\/wiki14\/facility-location-problem-wikipedia\/#breadcrumbitem","name":"Facility location problem – Wikipedia"}}]}]