Ubicación óptima de las instalaciones

El estudio de los problemas de ubicación de instalaciones (FLP) , también conocido como análisis de ubicación , es una rama de la investigación de operaciones y la geometría computacional que se ocupa de la ubicación óptima de las instalaciones para minimizar los costos de transporte, considerando factores como evitar colocar materiales peligrosos cerca de las viviendas y las ubicaciones de los competidores. instalaciones. Las técnicas también se aplican al análisis de conglomerados .

Ubicación mínima de las instalaciones

Un problema simple de ubicación de instalaciones es el problema de Weber , en el que se debe ubicar una sola instalación, siendo el único criterio de optimización la minimización de la suma ponderada de distancias desde un conjunto dado de sitios puntuales. Los problemas más complejos considerados en esta disciplina incluyen la ubicación de múltiples instalaciones, restricciones en la ubicación de las instalaciones y criterios de optimización más complejos.

En una formulación básica, el problema de ubicación de una instalación consiste en un conjunto de sitios potenciales L donde se puede abrir una instalación y un conjunto de puntos de demanda D a los que se debe dar servicio. El objetivo es elegir un subconjunto F de instalaciones para abrir, para minimizar la suma de las distancias desde cada punto de demanda hasta su instalación más cercana, más la suma de los costos de apertura de las instalaciones.

El problema de ubicación de instalaciones en gráficos generales es NP-difícil de resolver de manera óptima, mediante la reducción de (por ejemplo) el problema de cobertura de conjuntos . Se han desarrollado varios algoritmos de aproximación para el problema de ubicación de instalaciones y muchas de sus variantes.

Sin suposiciones sobre el conjunto de distancias entre clientes y sitios (en particular, sin asumir que las distancias satisfacen la desigualdad del triángulo ), el problema se conoce como ubicación de instalación no métrica y puede aproximarse dentro de un factor O(log  n ). ^[1] Este factor es estricto, a través de una reducción que preserva la aproximación del problema de cobertura establecida.

Si asumimos que las distancias entre clientes y sitios no están dirigidas y satisfacen la desigualdad del triángulo, estamos hablando de un problema de ubicación métrica de instalaciones (MFL) . El MFL sigue siendo NP-duro y difícil de aproximar dentro de un factor mejor que 1,463. ^[2] El algoritmo de aproximación más conocido actualmente alcanza una relación de aproximación de 1,488. ^[3]

Ubicación de las instalaciones Minimax

El problema de ubicación de instalaciones minimax busca una ubicación que minimice la distancia máxima a los sitios, donde la distancia de un punto a los sitios es la distancia del punto a su sitio más cercano. Una definición formal es la siguiente: Dado un conjunto de puntos P  ⊂ ℝ ^d , encuentre un conjunto de puntos S  ⊂ ℝ ^d , | S | =  k , de modo que max _{p  ∈  P} (min _{q  ∈  S} (d( p ,  q )) ) se minimiza.

En el caso de la métrica euclidiana para k  = 1, se la conoce como problema de la esfera envolvente más pequeña o problema de 1 centro . Su estudio se remonta al menos al año 1860. Consulte el círculo circundante más pequeño y la esfera delimitadora para obtener más detalles.

Dureza NP

Se ha demostrado que la solución exacta del problema del centro k es NP difícil. ^{[4] [5] [6]} Se encontró que la aproximación al problema también es NP difícil cuando el error es pequeño. El nivel de error en el algoritmo de aproximación se mide como un factor de aproximación, que se define como la relación entre la aproximación y el óptimo. Se ha demostrado que la aproximación del problema del centro k es NP difícil cuando el factor de aproximación es menor que 1,822 (dimensión = 2) ^[7] o 2 (dimensión > 2). ^[6]

Algoritmos

solucionador exacto

Existen algoritmos para producir soluciones exactas a este problema. Un solucionador exacto se ejecuta en el tiempo . ^{[8] [9]} ${\displaystyle n^{O({\sqrt {k}})}}$

1 + ε aproximación

La aproximación 1 +  ε consiste en encontrar una solución con un factor de aproximación no mayor que 1 +  ε . Esta aproximación es NP difícil ya que ε es arbitraria. Se propone un enfoque basado en el concepto de conjunto de núcleos con una complejidad de ejecución de . ^[10] Como alternativa, está disponible otro algoritmo también basado en conjuntos básicos. Se ejecuta en . ^[11] El autor afirma que el tiempo de ejecución es mucho menor que en el peor de los casos y, por lo tanto, es posible resolver algunos problemas cuando k es pequeño (digamos  k  < 5). ${\displaystyle O(2^{O(k\log k/\varepsilon ^{2})}dn)}$ ${\displaystyle O(k^{n})}$

Agrupación del punto más lejano

Dada la dureza del problema, no es práctico obtener una solución exacta o una aproximación precisa. En cambio, una aproximación con factor = 2 se usa ampliamente para k casos grandes. La aproximación se conoce como algoritmo de agrupamiento de puntos más lejanos (FPC), o recorrido primero más lejano . ^[6] El algoritmo es bastante simple: elija cualquier punto del conjunto como centro; buscar el punto más alejado de quedar fijado como un centro más; repita el proceso hasta encontrar k centros.

Es fácil ver que este algoritmo se ejecuta en tiempo lineal. Como se ha demostrado que la aproximación con un factor inferior a 2 es NP difícil, se consideró que FPC era la mejor aproximación que se podía encontrar.

Según el rendimiento de la ejecución, la complejidad del tiempo se mejora posteriormente a O ( n  log  k ) con la técnica de descomposición de cajas. ^[7]

Ubicación de las instalaciones de Maxmin

El problema de ubicación de instalación maxmin o ubicación de instalación desagradable busca una ubicación que maximice la distancia mínima a los sitios. En el caso de la métrica euclidiana, se le conoce como el problema de la esfera vacía más grande . El caso plano ( problema del círculo vacío más grande ) se puede resolver en el tiempo óptimo Θ ( n  log n). ^{[12] [13]}

Formulaciones de programación entera

Los problemas de ubicación de instalaciones a menudo se resuelven como programas enteros . En este contexto, los problemas de ubicación de las instalaciones suelen plantearse de la siguiente manera: supongamos que hay instalaciones y clientes. Deseamos elegir (1) cuál de las instalaciones abrir y (2) qué instalaciones (abiertas) utilizar para abastecer a los clientes, a fin de satisfacer cierta demanda fija al mínimo costo. Introducimos la siguiente notación: denotemos el costo (fijo) de abrir la instalación , para . Denotemos el costo de enviar un producto desde las instalaciones al cliente para y . Denotemos la demanda del cliente por . Supongamos además que cada instalación tiene una producción máxima. Denotemos la cantidad máxima de producto que puede producir una instalación , es decir, denotemos la capacidad de la instalación . El resto de esta sección sigue ^[14] ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle f_{i}}$ ${\displaystyle i}$ ${\displaystyle i=1,\dots ,n}$ ${\displaystyle c_{ij}}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle i=1,\dots ,n}$ ${\displaystyle j=1,\dots ,m}$ ${\displaystyle d_{j}}$ ${\displaystyle j}$ ${\displaystyle j=1,\dots ,m}$ ${\displaystyle u_{i}}$ ${\displaystyle i}$ ${\displaystyle u_{i}}$ ${\displaystyle i}$

Ubicación de las instalaciones capacitadas

En nuestra formulación inicial, introduzca una variable binaria para , donde si la instalación está abierta y en caso contrario. Introduzca además la variable para y que representa la fracción de la demanda cubierta por instalación . El llamado problema de ubicación de instalaciones capacitadas viene dado por ${\displaystyle x_{i}}$ ${\displaystyle i=1,\dots ,n}$ ${\displaystyle x_{i}=1}$ ${\displaystyle i}$ ${\displaystyle x_{i}=0}$ ${\displaystyle y_{ij}}$ ${\displaystyle i=1,\dots ,n}$ ${\displaystyle j=1,\dots ,m}$ ${\displaystyle d_{j}}$ ${\displaystyle i}$

$${\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=1\dots ,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 ,n\end{array}}}$$

Tenga en cuenta que el segundo conjunto de restricciones garantiza que si , es decir, la instalación no está abierta, entonces para todos , es decir, no se podrá satisfacer ninguna demanda de ningún cliente desde la instalación . ${\displaystyle x_{i}=0}$ ${\displaystyle i}$ ${\displaystyle y_{ij}=0}$ ${\displaystyle j}$ ${\displaystyle i}$

Ubicación de instalaciones no capacitadas

Un caso común del problema de ubicación de instalaciones capacitadas mencionado anteriormente es el caso cuando para todos . En este caso, siempre es óptimo satisfacer toda la demanda del cliente desde la instalación abierta más cercana. Debido a esto, podemos reemplazar las variables continuas anteriores con variables binarias , donde si el cliente recibe el suministro por instalación , y en caso contrario. El problema de ubicación de la instalación no capacitada viene dado por ${\displaystyle u_{i}=+\infty }$ ${\displaystyle i=1,\dots ,n}$ ${\displaystyle j}$ ${\displaystyle y_{ij}}$ ${\displaystyle z_{ij}}$ ${\displaystyle z_{ij}=1}$ ${\displaystyle j}$ ${\displaystyle i}$ ${\displaystyle z_{ij}=0}$

$${\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=1\dots ,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 ,n\end{array}}}$$

donde se elige una constante que sea adecuadamente grande. La elección de puede afectar los resultados del cálculo; la mejor opción en este caso es obvia: tomar . Entonces, si , cualquier elección de satisfará el segundo conjunto de restricciones. ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle M=m}$ ${\displaystyle x_{i}=1}$ ${\displaystyle z_{ij}}$

Otra posibilidad de formulación para el problema de ubicación de instalaciones no capacitadas es desagregar las restricciones de capacidad (las grandes restricciones). Es decir, reemplazar las restricciones. ${\displaystyle M}$

$${\displaystyle \sum _{j=1}^{m}z_{ij}\leqslant Mx_{i}{\text{ for all }}i=1,\dots ,n}$$

$${\displaystyle z_{ij}\leqslant x_{i}{\text{ for all }}i=1,\dots ,n{\text{ and }}j=1,\dots ,m}$$

de programación lineal^[14][15] ${\displaystyle M}$

Aplicaciones

Cuidado de la salud

En el sector de la salud, las decisiones incorrectas sobre la ubicación de las instalaciones tienen un impacto grave en la comunidad más allá de las simples métricas de costos y servicios; por ejemplo, es probable que los centros de salud de difícil acceso se asocien con una mayor morbilidad y mortalidad. Desde esta perspectiva, el modelado de la ubicación de las instalaciones para el cuidado de la salud es más crítico que el modelado similar para otras áreas. ^[dieciséis]

Manejo de residuos sólidos

La gestión de residuos sólidos municipales sigue siendo un desafío para los países en desarrollo debido a la creciente producción de residuos y los altos costos asociados con la gestión de residuos. A través de la formulación y resolución exacta de un problema de ubicación de instalaciones es posible optimizar la ubicación de los vertederos para la disposición de residuos. ^[17]

Agrupación

Un subconjunto particular de problemas de análisis de conglomerados puede considerarse como problemas de ubicación de instalaciones. En un problema de agrupamiento basado en centroides, el objetivo es dividir puntos de datos (elementos de un espacio métrico común) en clases de equivalencia, a menudo llamadas colores , de modo que los puntos del mismo color estén cerca unos de otros (de manera equivalente, de modo que los puntos de diferentes colores están lejos unos de otros). ^[18] ${\displaystyle n}$

Para ver cómo se podría ver (léase "transformar" o "reducir") un problema de agrupamiento basado en centroides como un problema de ubicación de instalaciones (métrico), vea cada punto de datos en el primero como un punto de demanda en el segundo. Supongamos que los datos que se van a agrupar son elementos de un espacio métrico (por ejemplo, sea un espacio euclidiano -dimensional para algunos fijos ). En el problema de ubicación de instalaciones que estamos construyendo, permitimos que las instalaciones se coloquen en cualquier punto dentro de este espacio métrico ; esto define el conjunto de ubicaciones de instalaciones permitidas . Definimos los costos como las distancias por pares entre los pares ubicación-punto de demanda (por ejemplo, ver métrica k-centro ). En un problema de agrupamiento basado en centroides, se dividen los datos en clases de equivalencia (es decir, colores), cada una de las cuales tiene un centroide. Veamos cómo una solución al problema de ubicación de nuestras instalaciones construidas también logra dicha partición. Una solución factible es un subconjunto de ubicaciones no vacío . Estas ubicaciones en nuestro problema de ubicación de instalaciones comprenden un conjunto de centroides en nuestro problema de agrupamiento basado en centroides. Ahora, asigne cada punto de demanda a la ubicación que minimice su costo de servicio; es decir, asignar el punto de datos al centroide (romper los vínculos arbitrariamente). Esto logra la partición siempre que los costos del problema de ubicación de las instalaciones se definan de manera que sean imágenes de la función de distancia del problema de agrupamiento basado en centroides. ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle M}$ ${\displaystyle L}$ ${\displaystyle c_{\ell ,d}}$ ${\displaystyle k}$ ${\displaystyle L'\subseteq L}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle d}$ ${\displaystyle \ell ^{*}}$ ${\displaystyle d}$ ${\displaystyle \ell ^{*}:=\mathrm {arg\,min} _{\ell \in L}\{c_{\ell ,d}\}}$ ${\displaystyle c_{\ell ,d}}$

El popular libro de texto de algoritmos Algorithm Design ^[19] proporciona una descripción del problema relacionado y un algoritmo de aproximación. Los autores se refieren al problema de ubicación de instalaciones métricas (es decir, el problema de agrupamiento basado en centroides o el problema de centros métricos) como el problema de selección de centros , aumentando así la lista de sinónimos. ${\displaystyle k}$

Además, vea que en nuestra definición anterior del problema de ubicación de instalaciones la función objetivo es general. Las elecciones específicas de producen diferentes variantes del problema de ubicación de instalaciones y, por tanto, diferentes variantes del problema de agrupamiento basado en centroides. Por ejemplo, se podría optar por minimizar la suma de distancias desde cada ubicación a cada uno de sus puntos de demanda asignados (al estilo del problema de Weber ), o se podría optar por minimizar el máximo de todas esas distancias (al estilo del problema de 1 centro). ). ${\displaystyle f}$ ${\displaystyle f}$

Ver también

• Centro de gráficos
• problema de asignación cuadrática
• Asignación de ubicación
• algoritmo de dijkstra
• Lista de software de análisis espacial
• Juego competitivo de ubicación de instalaciones.
• Problema del centro k del vértice
• mediana geométrica

Referencias

1. Hochbaum, DS (1982). "Heurística para el problema de la mediana del coste fijo". Programación Matemática . 22 : 148-162. doi :10.1007/BF01581035. S2CID  3451944.
2. Guha, S.; Khuller, S. (1999). "Greedy Strikes Back: algoritmos de ubicación de instalaciones mejorados". Revista de algoritmos . 31 : 228–248. CiteSeerX 10.1.1.47.2033 . doi :10.1006/jagm.1998.0993. S2CID  5363214. 
3. Li, S. (2011). "Un algoritmo de aproximación 1.488 para el problema de ubicación de instalaciones no capacitadas". Autómatas, Lenguajes y Programación . LNCS . vol. 6756, págs. 77–88. CiteSeerX 10.1.1.225.6387 . doi :10.1007/978-3-642-22012-8_5. ISBN  978-3-642-22011-1.
4. Fowler, RJ; Paterson, MS; Tanimoto, SL (1981), "El embalaje y la cobertura óptimos en el avión son NP-completos", Information Processing Letters , 12 (3): 133–137, doi :10.1016/0020-0190(81)90111-3.
5. Meguido, Nimrod ; Tamir, Arie (1982), "Sobre la complejidad de localizar instalaciones lineales en el avión" (PDF) , Operations Research Letters , 1 (5): 194–197, doi :10.1016/0167-6377(82)90039-6.
6. González, Teófilo (1985), "Agrupación para minimizar la distancia máxima entre grupos", Informática teórica , 38 : 293–306, doi : 10.1016/0304-3975(85)90224-5.
7. Feder, Tomás; Greene, Daniel (1988), "Algoritmos óptimos para la agrupación aproximada", Actas del vigésimo simposio anual de ACM sobre teoría de la informática - STOC '88, págs. 434–444, doi :10.1145/62212.62255, ISBN 0897912640, S2CID  658151
8. HWang, RZ; Lee, RCT; Chang, RC (1993), "El enfoque de división de losas para resolver el problema del centro p euclidiano", Algorithmica , 9 (1): 1–22, doi :10.1007/BF01185335, S2CID  5680676
9. HWang, RZ; Chang, RC; Lee, RCT (1993), "La estrategia de búsqueda generalizada sobre separadores para resolver algunos problemas NP-difíciles en tiempo subexponencial", Algorithmica , 9 (4): 398–423, doi :10.1007/bf01228511, S2CID  2722869
10. Badoiu, Mihai; Har-Peled, Sariel ; Indyk, Piotr (2002), "Agrupación aproximada mediante conjuntos de núcleos", Actas del trigésimo cuarto simposio anual de ACM sobre teoría de la informática (PDF) , págs. 250-257, doi :10.1145/509907.509947, ISBN 1581134959, S2CID  5409535
11. Kumar, Pankaj; Kumar, Piyush (2010), "Soluciones casi óptimas para problemas de agrupamiento k" (PDF) , Revista internacional de aplicaciones y geometría computacional , 20 (4): 431–447, doi :10.1142/S0218195910003372
12. Franco P. Preparata y Michael Ian Shamos (1985). Geometría computacional: una introducción . Springer-Verlag. ISBN 978-0-387-96131-6. 1ª edición; 2ª edición, corregida y ampliada, 1988; Traducción al ruso, 1989., pag. 256
13. GT Toussaint, "Cálculo de los círculos vacíos más grandes con restricciones de ubicación", Revista Internacional de Ciencias de la Información y la Computación , vol. 12, núm. 5, octubre de 1983, págs. 347–358.
14. Conforti, Michele; Cornuéjols, Gérard; Zambelli, Giacomo (2014). Programación entera . Textos de Posgrado en Matemáticas. vol. 271. doi : 10.1007/978-3-319-11008-0. ISBN 978-3-319-11007-3.
15. Teoría de la ubicación discreta . Mirchandani, Pitu B., Francis, RL Nueva York: Wiley. 1990.ISBN _ 9780471892335. OCLC  19810449.{{cite book}}: CS1 maint: others (link)
16. Ahmadi-Javid, A.; Seyedi, P.; Syam, S. (2017). "Una encuesta sobre la ubicación de los centros sanitarios". Investigación de operaciones y computadoras . 79 : 223–263. doi :10.1016/j.cor.2016.05.018.
17. Franco, DGB; Steiner, MTA; Assef, FM (2020). "Optimización en la compartimentación de vertederos de residuos en el estado de Paraná, Brasil". Revista de Producción Más Limpia . 283 : 125353. doi : 10.1016/j.jclepro.2020.125353. S2CID  229429742.
18. Hastie, Trevor; Tibshirani, Robert; Friedman, Jerome (2009). Los elementos del aprendizaje estadístico (Segunda ed.). Saltador.
19. Kleinberg, Jon; Tardos, Éva (2006). Diseño de algoritmos . Pearson.

enlaces externos

• Grupo de trabajo de EWGLA EURO sobre análisis de ubicación.
• INFORMA sección de análisis de localización, sociedad profesional que se ocupa de la localización de instalaciones.
• Bibliografía sobre la ubicación de las instalaciones recopilada por Trevor Hale y que contiene más de 3400 artículos.
• Biblioteca de algoritmos de localización
• Utilidad de ubicación de instalaciones basada en web (instalación única)
• Facility Location Optimizer, una herramienta basada en MATLAB para resolver problemas de ubicación de instalaciones.