Problema de ubicación de la instalación - Facility location problem

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 mientras se consideran factores como evitar la colocación de materiales peligrosos cerca de las viviendas y de los competidores. 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 ). 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. El algoritmo de aproximación más conocido actualmente alcanza una relación de aproximación de 1,488.

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. 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) o 2 (dimensión> 2).

Algoritmos

Solucionador exacto

Existen algoritmos para producir soluciones exactas a este problema. Un solucionador exacto se ejecuta a tiempo . ${\ Displaystyle n ^ {O ({\ sqrt {k}})}}$

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 . Como alternativa, se encuentra disponible otro algoritmo también basado en conjuntos básicos. Entra corriendo . 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 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 . 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.

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).

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 abrir, y (2) qué instalaciones (abiertas) utilizar para abastecer a los clientes, con el fin de satisfacer una demanda fija a un costo mínimo. Introducimos la siguiente notación: denotemos el costo (fijo) de apertura de la instalación , por . Dejar que denotan el costo del envío de un producto desde las instalaciones de los clientes de e . Dejar que denotan la demanda del cliente para . Además, suponga que cada instalación tiene un rendimiento máximo. Dejar que denotan la cantidad máxima de producto que puede ser producida por la instalación , es decir, dejar que denotan la capacidad de las instalaciones . El resto de esta sección sigue ${\ 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 de lo contrario. Introduzca aún más la variable para y que representa la fracción de la demanda satisfecha por la 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 {st}} & \ displaystyle \ sum _ {i = 1} ^ {n} y_ { ij} = 1 {\ text {para todos}} j = 1, \ dots, m \\ & \ displaystyle \ sum _ {j = 1} ^ {m} d_ {j} y_ {ij} \ leqslant u_ {i } x_ {i} {\ text {para todos}} i = 1 \ dots, n \\ & y_ {ij} \ geqslant 0 {\ text {para todos}} i = 1, \ dots, n {\ text {y }} j = 1, \ dots, m \\ & x_ {i} \ in \ {0,1 \} {\ text {para todos}} i = 1, \ dots, n \ end {array}}}

Tenga en cuenta que el segundo conjunto de restricciones asegura que si , es decir, la instalación no está abierta, entonces para todos , es decir, no se puede satisfacer la 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 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 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 de otra manera. 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 {st}} & \ displaystyle \ sum _ {i = 1} ^ {n} z_ { ij} = 1 {\ text {para todos}} j = 1, \ dots, m \\ & \ displaystyle \ sum _ {j = 1} ^ {m} z_ {ij} \ leqslant Mx_ {i} {\ text {para todos}} i = 1 \ dots, n \\ & z_ {ij} \ in \ {0,1 \} {\ text {para todos}} i = 1, \ dots, n {\ text {y}} j = 1, \ dots, m \\ & x_ {i} \ in \ {0,1 \} {\ text {para todos}} i = 1, \ dots, n \ end {array}}}

donde es una constante elegida para 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 satisfacerá 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 sin capacidad es desagregar las limitaciones de capacidad (las grandes limitaciones). Es decir, reemplace las restricciones ${\ Displaystyle M}$

{\ Displaystyle \ sum _ {j = 1} ^ {m} z_ {ij} \ leqslant Mx_ {i} {\ text {para todos}} i = 1, \ dots, n}

con las limitaciones

{\ Displaystyle z_ {ij} \ leqslant x_ {i} {\ text {para todos}} i = 1, \ dots, n {\ text {y}} j = 1, \ dots, m}

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. Observe que la suma de las nuevas restricciones da como resultado las restricciones grandes originales . En el caso capacitado, estas formulaciones no son equivalentes. Se puede encontrar más información sobre el problema de ubicación de instalaciones sin capacidad en el Capítulo 3 de "Teoría de ubicación discreta".

{\ Displaystyle M}

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.

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.

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 dividir puntos de datos (elementos de un espacio métrico común) en clases de equivalencia, a menudo llamadas colores , de manera que los puntos del mismo color estén cerca unos de otros (de manera equivalente, de manera que los puntos de diferentes colores están lejos unos de otros). ${\ Displaystyle n}$

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. Supongamos que los datos que se van a agrupar son elementos de un espacio métrico (por ejemplo, sea -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 costos como las distancias por pares entre los pares de puntos de demanda de ubicación (p. Ej., Consulte la métrica k-centro ). En un problema de agrupamiento basado en centroides, uno divide 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 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 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 (rompa los lazos arbitrariamente). Esto logra la partición siempre que los costos del problema de ubicación de la instalación 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 sobre algoritmos Algorithm Design 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 del centro métrico ) como el problema de selección del centro , 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 las instalaciones y, por lo tanto, diferentes variantes del problema de agrupamiento basado en centroides. Por ejemplo, se puede 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 puede optar por minimizar el máximo de todas esas distancias (al estilo del problema de 1 ). ${\ Displaystyle f}$ ${\ Displaystyle f}$

Ver también

Referencias

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.

Languages

In other projects