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, teniendo en cuenta factores como evitar colocar materiales peligrosos cerca de viviendas e instalaciones de la competencia. Las técnicas también se aplican al análisis de conglomerados .

Ubicación mínima de las instalaciones

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

En una formulación básica, el problema de la ubicación de las instalaciones consiste en un conjunto de posibles emplazamientos L donde se puede abrir una instalación y un conjunto de puntos de demanda D que deben recibir 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 la 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 grafos generales es NP-difícil de resolver de manera óptima, mediante reducción a partir (por ejemplo) del 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 suponer que las distancias satisfacen la desigualdad triangular ), el problema se conoce como ubicación de instalaciones no métricas y se puede aproximar 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 del conjunto.

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

Ubicación de las instalaciones de 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 desde un punto a los sitios es la distancia desde el punto a su sitio más cercano. Una definición formal es la siguiente:

Dado un conjunto de puntos P ⊂ ${\displaystyle \mathbb {R} ^{d}}$ , encuentre un conjunto de puntos S ⊂ , | S | = k , ${\displaystyle \mathbb {R} ^{d}}$ de modo que max _{p ∈ P} (min _{q ∈ S} (d( p , q )) ) se minimice.

En el caso de la métrica euclidiana para k = 1 , se la conoce como el problema de la esfera envolvente más pequeña o problema de 1 centro . Su estudio se remonta al menos al año 1860.

Dureza NP

Se ha demostrado que la solución exacta del problema de k -centros 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 de k -centros 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 tiempo . ^{[8] [9]} ${\displaystyle n^{O({\sqrt {k}})}}$

Aproximación 1 + ε

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 arbitrario. Se propone un enfoque basado en el concepto de coreset con una complejidad de ejecución de . ^[10] Como alternativa, está disponible otro algoritmo también basado en coresets. Se ejecuta en . ^[11] El autor afirma que el tiempo de ejecución es mucho menor que el del peor caso 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})}$

Agrupamiento de puntos más lejanos

Debido a la dificultad del problema, no es práctico obtener una solución exacta o una aproximación precisa. En cambio, se utiliza ampliamente una aproximación con factor = 2 para casos de k grandes . La aproximación se conoce como algoritmo de agrupamiento de puntos más lejanos (FPC) o recorrido del más lejano primero . ^[6] El algoritmo es bastante simple: elija cualquier punto del conjunto como un centro; busque el punto más lejano del conjunto restante como otro centro; repita el proceso hasta que se encuentren 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 menor que 2 es NP difícil, se consideró que FPC era la mejor aproximación que se podía encontrar.

En cuanto al rendimiento de la ejecución, la complejidad temporal 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 la ubicación de instalaciones maxmin o de la ubicación de instalaciones molestas busca una ubicación que maximice la distancia mínima a los sitios. En el caso de la métrica euclidiana, se conoce como el problema de la esfera vacía más grande . El caso planar ( problema del círculo vacío más grande ) se puede resolver en un tiempo óptimo Θ( n  log n). ^{[12] [13]}

Formulaciones de programación entera

Los problemas de localización de instalaciones suelen resolverse como programas enteros . En este contexto, los problemas de localización de instalaciones suelen plantearse de la siguiente manera: supongamos que hay instalaciones y clientes. Queremos elegir (1) cuál de las instalaciones abrir, y (2) qué instalaciones (abiertas) utilizar para abastecer a los clientes, con el fin de satisfacer una demanda fija a un coste mínimo. Introducimos la siguiente notación: sea el coste (fijo) de apertura de la instalación , para . Sea el coste de enviar un producto desde la instalación al cliente para y . Sea la demanda del cliente para . Supongamos además que cada instalación tiene una producción máxima. Sea la cantidad máxima de producto que puede producir la instalación , es decir, sea 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 la instalación capacitada

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 la instalación . El llamado problema de ubicación de la instalación capacitada se da entonces 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}}}$$

Obsérvese que el segundo conjunto de restricciones garantiza que si , es decir, la instalación no está abierta, entonces para todos , es decir, no se puede 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 instalación no capacitada

Un caso común del problema de ubicación de instalaciones capacitadas mencionado anteriormente es el caso en el que 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 de arriba con las variables binarias , donde si el cliente es abastecido por la instalación , y en caso contrario. El problema de ubicación de instalaciones no capacitadas se da entonces 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 es una constante elegida para que sea lo suficientemente 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 la ubicación de instalaciones no capacitadas es desagregar las restricciones de capacidad (las restricciones de big- ). Es decir, reemplazar las restricciones con las restricciones En la práctica, esta nueva formulación funciona significativamente mejor, en el sentido de que tiene una relajación de programación lineal más estricta que la primera formulación. ^[14] Nótese que al sumar las nuevas restricciones juntas se obtienen las restricciones de big- originales . En el caso de instalaciones capacitadas, estas formulaciones no son equivalentes. Puede encontrar más información sobre el problema de la ubicación de instalaciones no capacitadas en el Capítulo 3 de "Teoría de la ubicación discreta". ^[15] ${\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}$$ ${\displaystyle M}$

Aplicaciones

Cuidado de la salud

En el ámbito de la atención sanitaria, las decisiones incorrectas sobre la ubicación de los centros sanitarios tienen un grave impacto en la comunidad, más allá de los simples parámetros de costo y servicio; por ejemplo, es probable que los centros sanitarios de difícil acceso estén asociados con un aumento de la morbilidad y la mortalidad. Desde esta perspectiva, la modelización de la ubicación de los centros sanitarios es más crítica que la modelización similar para otras áreas. ^[16]

Gestión de residuos sólidos

La gestión de los residuos sólidos urbanos sigue siendo un reto para los países en desarrollo debido a la creciente producción de residuos y a los altos costos asociados a su gestión. Mediante 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 eliminación de residuos. ^[17]

Agrupamiento

Un subconjunto particular de los 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 los puntos de datos (elementos de un espacio métrico común) en clases de equivalencia (a menudo denominadas colores ) de modo que los puntos del mismo color estén cerca unos de otros (de modo equivalente, de modo que los puntos de diferentes colores estén lejos unos de otros). ^[18] ${\displaystyle n}$

Para ver cómo se puede ver (léase "transformar" o "reducir") un problema de agrupamiento basado en centroides como un problema de ubicación de instalaciones (métricas), veamos 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 de dimensión 1 para algún fijo ). 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 pares de puntos de demanda y ubicación (por ejemplo, consulte 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 a nuestro problema de ubicación de instalaciones construido también logra dicha partición. Una solución factible es un subconjunto no vacío de ubicaciones. 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, asigne el punto de datos al centroide (elimine los empates arbitrariamente). Esto logra la partición siempre que los costos del problema de ubicación de las instalaciones se definan de manera que sean las imágenes de la función de distancia del problema de agrupamiento basado en el centroide. ${\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 y un algoritmo de aproximación relacionados. 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 del centro métrico) como el problema de selección del centro , aumentando así la lista de sinónimos. ${\displaystyle k}$

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

Véase también

• Centro del gráfico
• Problema de asignación cuadrática
• Ubicación-asignación
• Algoritmo de Dijkstra
• Lista de software de análisis espacial
• Juego de localización de instalaciones competitivo
• Problema del vértice k-centro
• mediana geométrica

Referencias

1. Hochbaum, DS (1982). "Heurísticas para el problema de la mediana de los costos fijos". Programación matemática . 22 : 148–162. doi :10.1007/BF01581035. S2CID  3451944.
2. Guha, S.; Khuller, S. (1999). "Greedy Strikes Back: algoritmos mejorados de ubicación de instalaciones". Journal of Algorithms . 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 de 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 empaquetamiento y el recubrimiento óptimos en el plano son NP-completos", Information Processing Letters , 12 (3): 133–137, doi :10.1016/0020-0190(81)90111-3.
5. Megiddo, Nimrod ; Tamir, Arie (1982), "Sobre la complejidad de la localización de instalaciones lineales en el plano" (PDF) , Operations Research Letters , 1 (5): 194–197, doi :10.1016/0167-6377(82)90039-6.
6. Gonzalez, Teofilo (1985), "Agrupamiento para minimizar la distancia máxima entre clústeres", Theoretical Computer Science , 38 : 293–306, doi : 10.1016/0304-3975(85)90224-5.
7. Feder, Tomás; Greene, Daniel (1988), "Algoritmos óptimos para agrupamiento aproximado", Actas del vigésimo simposio anual de la ACM sobre teoría de la computación - STOC '88, págs. 434–444, doi :10.1145/62212.62255, ISBN 0897912640, S2CID658151 ​
8. HWang, RZ; Lee, RCT; Chang, RC (1993), "El enfoque de división de losas para resolver el problema del p-centro 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-Hard en tiempo subexponencial", Algorithmica , 9 (4): 398–423, doi :10.1007/bf01228511, S2CID  2722869
10. Bādoiu, Mihai; Har-Peled, Sariel ; Indyk, Piotr (2002), "Agrupamiento aproximado mediante conjuntos básicos", Actas del trigésimo cuarto simposio anual de la ACM sobre teoría de la computación (PDF) , págs. 250–257, doi :10.1145/509907.509947, ISBN 1581134959, Número de identificación del sujeto  5409535
11. Kumar, Pankaj; Kumar, Piyush (2010), "Soluciones casi óptimas para problemas de agrupamiento k" (PDF) , Revista internacional de geometría computacional y aplicaciones , 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ª impresión, corregida y ampliada, 1988; traducción rusa, 1989., pág. 256
13. GT Toussaint, "Cálculo de los círculos vacíos más grandes con restricciones de ubicación", International Journal of Computer and Information Sciences , 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 de atención médica". Computers & Operations Research . 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 residuos en vertederos del 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 edición). Springer.
19. Kleinberg, Jon; Tardos, Éva (2006). Diseño de algoritmos . Pearson.

Enlaces externos

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