El estudio de problemas de ubicación de instalaciones (FLP, por sus siglas en inglés) , 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 al tiempo que considera factores como evitar colocar materiales peligrosos cerca de viviendas y competidores. instalaciones. Las técnicas también se aplican al análisis de conglomerados .
Un problema de ubicación de instalaciones simple es el problema de Weber , en el que se debe colocar una sola instalación, con el único criterio de optimización que es la minimización de la suma ponderada de distancias desde un conjunto dado de sitios de puntos. Los problemas más complejos considerados en esta disciplina incluyen la ubicación de múltiples instalaciones, restricciones en las ubicaciones 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 consta de un conjunto de sitios de instalación potenciales 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 instalaciones en gráficos generales es NP-difícil de resolver de manera óptima, mediante la reducción (por ejemplo) del problema de cobertura establecida . 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 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 ajustado, a través de una reducción que preserva 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 logra una relación de aproximación de 1,488. [3]