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 y al mismo tiempo considerar 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 .
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]