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 .
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]
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.
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]
solucionador exacto
Existen algoritmos para producir soluciones exactas a este problema. Un solucionador exacto se ejecuta en el tiempo . [8] [9]
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).
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]
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]
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]
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
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 .
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
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.
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.
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]
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]
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]
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.
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.
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). ).
{{cite book}}
: CS1 maint: others (link)