El estudio de 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 la colocación de materiales peligrosos cerca de las viviendas y de la competencia instalaciones. Las técnicas también se aplican al análisis de conglomerados .
Ubicación mínima de la instalación
Un problema simple de ubicación de instalaciones es el problema de Weber , en el que se debe colocar una única 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 la instalación consiste en un conjunto de sitios potenciales de instalaciones L donde se puede abrir una instalación, y un conjunto de puntos de demanda D que deben ser atendidos. 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 la instalación en los gráficos generales es NP-difícil de resolver de manera óptima, reduciendo (por ejemplo) el problema de cobertura del conjunto . Se han desarrollado varios algoritmos de aproximación para el problema de ubicación de las instalaciones y muchas de sus variantes.
Sin supuestos 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 instalaciones no métricas y se puede aproximar dentro de un factor O (log n ). [1] Este factor es estrecho, a través de una reducción que conserva la aproximación del problema de la cobertura del conjunto.
Si asumimos que las distancias entre los clientes y los sitios no están dirigidas y satisfacen la desigualdad del triángulo, estamos hablando de un problema de ubicación de instalaciones métricas (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 la instalación de Minimax
El problema de ubicación de la instalación 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 al 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 conoce como el problema de la esfera envolvente más pequeña o el problema de un centro . Su estudio se remonta al menos al año de 1860. ver el círculo circundante más pequeño y la esfera delimitadora para más detalles.
Dureza NP
Se ha demostrado que la solución exacta de k -center problema es NP duro. [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. Está 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 a tiempo. [8] [9]
Aproximación 1 + ε
La aproximación 1 + ε es 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 coreset con una complejidad de ejecución de. [10] Como alternativa, se encuentra disponible otro algoritmo también basado en conjuntos básicos. Corre 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).
Agrupación en el punto más lejano
Por 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 el algoritmo de agrupación en clústeres del punto más lejano (FPC) o el recorrido más lejano primero . [6] El algoritmo es bastante simple: elija cualquier punto del conjunto como un centro; buscar el punto más alejado del resto establecido como otro centro; 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, FPC se consideró como la mejor aproximación que se puede 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 la instalación maxmin o la ubicación desagradable de la instalación 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 mayor problema de esferas vacías . El caso plano ( problema de círculo vacío más grande ) puede resolverse en el tiempo óptimo Θ ( n log n). [12] [13]
Formulaciones de programación de enteros
Los problemas de ubicación de instalaciones a menudo se resuelven como programas de números enteros . En este contexto, los problemas de ubicación de las instalaciones a menudo se plantean de la siguiente manera: supongamos que hay instalaciones y clientes. Deseamos elegir (1) cuál de las instalaciones para abrir, y (2) qué instalaciones (abiertas) utilizar para suministrar el clientes, con el fin de satisfacer una demanda fija a un costo mínimo. Introducimos la siguiente notación: deje denotar el costo (fijo) de apertura de la instalación , por . Dejardenotar el costo de enviar un producto desde la instalación al cliente por y . Dejar denotar la demanda del cliente por . Además, suponga que cada instalación tiene un rendimiento máximo. Dejar denotar la cantidad máxima de producto que se puede producir por instalación , es decir, deja denotar la capacidad de la instalación. El resto de esta sección sigue [14]
Ubicación de la instalación capacitada
En nuestra formulación inicial, introduzca una variable binaria por , dónde si facilidad está abierto, y de lo contrario. Introduzca más la variable por y que representa la fracción de la demanda llenado por la instalación . El llamado problema de ubicación de instalaciones capacitadas viene dado por
Tenga en cuenta que el segundo conjunto de restricciones asegura que si , es decir, facilidad no está abierto, entonces para todos , es decir, no se puede cubrir la demanda de ningún cliente desde la instalación .
Ubicación de la instalación no capacitada
Un caso común del problema de ubicación de instalaciones capacitadas anterior es el caso cuando para todos . En este caso, siempre es óptimo satisfacer toda la demanda del cliente.de la instalación abierta más cercana. Debido a esto, podemos reemplazar las variables continuas desde arriba con las variables binarias , dónde si cliente es suministrado por la instalación , y de lo contrario. El problema de ubicación de la instalación no capacitada viene dado por
dónde es una constante elegida para que sea adecuadamente grande. La elección de puede afectar los resultados de los cálculos; la mejor opción en este caso es obvia: tome . Entonces sí, cualquier elección del satisfará el segundo conjunto de restricciones.
Otra posibilidad de formulación para el problema de ubicación de instalaciones no capacitadas es desagregar las limitaciones de capacidad (las grandeslimitaciones). Es decir, reemplace las restricciones
Aplicaciones
Cuidado de la salud
En el cuidado de la salud, las decisiones incorrectas sobre la ubicación de las instalaciones tienen un impacto serio en la comunidad más allá de las simples métricas de costos y servicios; por ejemplo, es probable que las instalaciones sanitarias de difícil acceso se relacionen con un aumento de la morbilidad y la 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 al aumento de la producción de residuos y los altos costos asociados con la gestión de residuos. Mediante la formulación y resolución exacta de un problema de ubicación de una instalación, es posible optimizar la ubicación de los vertederos para la eliminación de desechos. [17]
Agrupación
Un subconjunto particular de problemas de análisis de conglomerados puede verse como problemas de ubicación de instalaciones. En un problema de agrupamiento basado en centroides, el objetivo es particionarpuntos 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]
Para ver cómo se puede ver (leer "transformar" o "reducir") un problema de agrupamiento basado en centroides como un problema de ubicación de instalaciones (métricas), vea cada punto de datos en el primero como un punto de demanda en el segundo. Suponga que los datos que se agrupan son elementos de un espacio métrico (por ejemplo, deja ser -espacio euclidiano dimensional para algunos fijos). En el problema de ubicación de las 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 costospara ser las distancias por pares entre los pares de puntos de demanda de ubicación (por ejemplo, consulte la métrica k-centro ). En un problema de agrupamiento basado en centroides, uno divide los datos enclases 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 construidas 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 decentroides en nuestro problema de agrupamiento basado en centroides. Ahora, asigne cada punto de demanda a la ubicación que minimiza su costo de servicio; es decir, asignar el punto de datos al centroide (romper lazos arbitrariamente). Esto logra la partición siempre que los costos del problema de ubicación de la instalación se definen de manera que son las imágenes de la función de distancia del problema de agrupamiento basado en centroides.
El popular libro de texto sobre 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 agrupación en clústeres basado en centroides o la métrica-problema del centro ) como el problema de selección del centro , aumentando así la lista de sinónimos.
Además, vea que en nuestra definición anterior del problema de ubicación de la instalación que la función objetivo es general. Opciones específicas deproducen diferentes variantes del problema de ubicación de las instalaciones y, por lo 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 ).
Ver también
- Centro gráfico
- Problema de asignación cuadrática
- Ubicación-asignación
- Algoritmo de Dijkstra
- Lista de software de análisis espacial
- Juego competitivo de ubicación de instalaciones
- Problema del vértice del centro k
Referencias
- ^ Hochbaum, DS (1982). "Heurística para el problema de la mediana de costo fijo". Programación matemática . 22 : 148-162. doi : 10.1007 / BF01581035 .
- ^ 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 .
- ^ Li, S. (2011). "Un algoritmo de aproximación 1.488 para el problema de ubicación de instalaciones sin capacidad". Autómatas, lenguajes y programación . LNCS . 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.
- ^ Fowler, RJ; Paterson, MS; Tanimoto, SL (1981), "El embalaje y el recubrimiento óptimos en el avión son NP-completos", Information Processing Letters , 12 (3): 133-137, doi : 10.1016 / 0020-0190 (81) 90111-3.
- ^ Meguido, Nimrod ; Tamir, Arie (1982), "Sobre la complejidad de ubicar instalaciones lineales en el plano" (PDF) , Cartas de investigación de operaciones , 1 (5): 194-197, doi : 10.1016 / 0167-6377 (82) 90039-6.
- ^ a b c González, Teófilo (1985), "Agrupación para minimizar la distancia máxima entre grupos" (PDF) , Theoretical Computer Science , 38 : 293–306, doi : 10.1016 / 0304-3975 (85) 90224-5 , archivado desde el original (PDF ) el 2013-01-24.
- ^ a b Feder, Tomás; Greene, Daniel (1988), "Algoritmos óptimos para agrupamiento aproximado" , Actas del vigésimo simposio anual de ACM sobre teoría de la computación : 434–444, doi : 10.1145 / 62212.62255 , ISBN 0897912640
- ^ 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
- ^ HWang, RZ; Chang, RC; Lee, RCT (1993), "La búsqueda generalizada sobre la estrategia de separadores para resolver algunos problemas NP-Hard en tiempo subexponencial", Algorithmica , 9 (4): 398–423, doi : 10.1007 / bf01228511
- ^ Bādoiu, Mihai; Har-Peled, Sariel ; Indyk, Piotr (2002), " Agrupación aproximada a través de conjuntos básicos" (PDF) , Actas del 34º Simposio Anual de ACM sobre Teoría de la Computación : 250–257, doi : 10.1145 / 509907.509947 , ISBN 1581134959
- ^ Kumar, Pankaj; Kumar, Piyush (2010), "Soluciones casi óptimas para problemas de agrupación k" (PDF) , International Journal of Computational Geometry & Applications , 20 (4): 431–447, doi : 10.1142 / S0218195910003372
- ^ 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 rusa, 1989., p. 256
- ^ GT Toussaint, "Computación 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.
- ^ a b Conforti, Michele; Cornuéjols, Gérard; Zambelli, Giacomo (2014). Programación de enteros | SpringerLink . Textos de Posgrado en Matemáticas. 271 . doi : 10.1007 / 978-3-319-11008-0 . ISBN 978-3-319-11007-3.
- ^ Teoría de la ubicación discreta . Mirchandani, Pitu B., Francis, RL Nueva York: Wiley. 1990. ISBN 9780471892335. OCLC 19810449 .CS1 maint: otros ( enlace )
- ^ Ahmadi-Javid, A .; Seyedi, P .; Syam, S. (2017). "Una encuesta sobre la ubicación de las instalaciones sanitarias". Investigación de Computación y Operaciones . 79 : 223-263. doi : 10.1016 / j.cor.2016.05.018 .
- ^ Franco, DGB; Steiner, MTA; Assef, FM (2020). "Optimización en la partición de vertederos de residuos en el estado de Paraná, Brasil". Revista de producción más limpia . 283 . doi : 10.1016 / j.jclepro.2020.125353 .
- ^ Hastie, Trevor; Tibshirani, Robert; Friedman, Jerome (2009). Los elementos del aprendizaje estadístico (Segunda ed.). Saltador.
- ^ Kleinberg, Jon; Tardos, Éva (2006). Diseño de algoritmos . Pearson.
enlaces externos
- Grupo de trabajo EWGLA EURO sobre análisis de ubicación .
- INFORMA la sección sobre análisis de ubicación , una sociedad profesional preocupada por la ubicación de las 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 ubicación
- Utilidad de ubicació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.