An Enhanced Large Neighborhood Search Approach for the Capacitated Facility Location Problem with Incompatible Customers

Resumen Técnico: Un Enfoque Mejorado de Búsqueda en Vecindario Grande para el Problema de Localización de Instalaciones Capacitadas con Clientes Incompatibles

Definición del Problema
Este artículo aborda el Problema de Localización de Instalaciones Capacitadas con Múltiples Fuentes e Incompatibilidades de Clientes (MS-CFLP-CI). Esta variante extiende el clásico MS-CFLP introduciendo un conjunto de pares de clientes incompatibles ($I$) que no pueden ser atendidos por la misma instalación. El problema consiste en determinar qué instalaciones abrir (incurriendo en costos de apertura $f_j$) y cómo distribuir la demanda de los clientes ($d_i$) entre las instalaciones abiertas (incurriendo en costos de envío $c_{ij}$) para minimizar el costo total. La solución debe satisfacer las restricciones de capacidad de las instalaciones ($s_j$), cubrir completamente la demanda de los clientes y garantizar que ningún par de clientes incompatibles comparta una instalación. La presencia de restricciones de incompatibilidad hace que el subproblema de encontrar el suministro óptimo desde las instalaciones abiertas sea NP-duro, incluso cuando el conjunto de instalaciones abiertas está fijo.

Metodología
Los autores proponen un marco de Búsqueda en Vecindario Grande (LNS) para resolver el MS-CFLP-CI. El núcleo del enfoque implica destruir iterativamente una porción de la solución actual y repararla utilizando un solucionador exacto de Programación Entera Mixta (MIP) (Gurobi).

• Representación de la Solución: Las soluciones se representan como matrices de cantidades enviadas, respaldadas por estructuras de datos auxiliares que rastrean las instalaciones abiertas/cerradas y los clientes asignados.
• Solución Inicial: Una heurística construye una solución inicial ordenando las instalaciones por costo de apertura, seleccionando suficientes para satisfacer la demanda total y añadiendo un número específico de instalaciones adicionales ($k=5$) para manejar las restricciones de incompatibilidad. Los clientes se asignan basándose en una estrategia uniforme.
• Operadores de Destrucción: El artículo introduce tres operadores de destrucción novedosos diseñados específicamente para las restricciones de incompatibilidad:
  1. Instalaciones Más Baratas (CF): Selecciona una instalación aleatoria y sus clientes, luego identifica otras instalaciones abiertas que ofrecen el costo promedio de envío más bajo para ese grupo específico de clientes.
  2. Clientes Híbridos (HC): Una recombinación de dos estrategias. Selecciona una instalación aleatoria y sus clientes, luego identifica "clientes baratos" (aquellos con costos de envío bajos hacia la instalación) y "clientes caros" (aquellos con costos de envío altos). Luego selecciona instalaciones adicionales que ofrecen el mejor servicio para estos subconjuntos específicos de clientes.
  3. Instalaciones Cerradas: Tanto las instalaciones cerradas aleatorias como aquellas con la medida de costo mínima ($Q_g$) se incluyen en el subproblema para explorar la apertura de nuevas instalaciones.
• Operador de Reparación: El subproblema definido por los elementos destruidos se resuelve exactamente utilizando Gurobi. Para gestionar el tiempo computacional, la fase de reparación incluye una restricción que limita el número de instalaciones recién abiertas a un máximo de dos más que las actualmente involucradas en el subproblema. Se proporciona un valor de corte (el costo actual del subproblema) al solucionador para acelerar la convergencia.
• Configuración y Ajuste: Los autores emplean la herramienta irace para el ajuste de parámetros basado en características, ajustando parámetros como el tamaño del subproblema ($\nu$) según la escala de la instancia (específicamente distinguiendo entre instancias con $\le 700$ y $> 700$ instalaciones). El algoritmo final, denominado $LNS_{init,accept}$, combina los operadores de destrucción propuestos con una heurística de solución inicial mejorada y un criterio de aceptación que permite aceptar soluciones con costo igual, facilitando la salida de óptimos locales.

Contribuciones Clave

• Marco Algorítmico Novel: Esta es la primera aplicación de Búsqueda en Vecindario Grande al problema MS-CFLP-CI.
• Operadores Especializados: El diseño de operadores de destrucción (CF y HC) que tienen en cuenta explícitamente las restricciones de incompatibilidad, superando las heurísticas estándar de localización de instalaciones.
• Reparación Híbrida Exacta/Heurística: La integración de un solucionador exacto de MIP dentro de la fase de reparación, optimizado con restricciones específicas para equilibrar la calidad de la solución y el tiempo de ejecución.
• Análisis Riguroso: Un estudio de ablación exhaustivo y análisis estadístico (utilizando pruebas de Friedman y Nemenyi) para evaluar el impacto de los componentes individuales (inicialización, criterios de aceptación, pesos adaptativos).
• Evaluación Exhaustiva: Evaluación en dos conjuntos de datos a gran escala (wlp y cflp-ci) que contienen hasta 3.000 instalaciones y 8.000 clientes.

Resultados Experimentales
El método propuesto $LNS_{init,accept}$ fue probado contra metaheurísticas de última generación, incluyendo Búsqueda Local Iterada Multi-Inicio basada en MineReduce (MR-MS-ILS), GRASP, Algoritmo Evolutivo codificado por Permutaciones (PcEA), Múltiples Inicios Greedy (MG) y Recocido Simulado (SA).

• Rendimiento: El método propuesto superó significativamente a todos los métodos existentes en ambos conjuntos de datos bajo dos límites de tiempo diferentes ($10\sqrt{m}$ y $m$ segundos).
• Nuevas Mejores Soluciones: El enfoque encontró nuevas mejores soluciones para todas las 80 instancias en ambos conjuntos de datos.
• Significancia Estadística: Las pruebas estadísticas confirmaron que las mejoras sobre el método anterior mejor (SA) son estadísticamente significativas.
• Escalabilidad: Mientras que los solucionadores exactos (Gurobi/CPLEX) solo pudieron resolver instancias de hasta 150 instalaciones hasta la optimalidad en un tiempo razonable, el enfoque LNS manejó efectivamente instancias de hasta 3.000 instalaciones.
• Reducción de Brecha: Para el conjunto de datos wlp, el método logró mejoras de brecha que oscilaron entre -0.68% y -1.84% sobre las soluciones de mejor conocimiento. Para el conjunto de datos cflp-ci, las mejoras oscilaron entre -0.46% y -2.09%.

Significancia y Afirmaciones
Los autores afirman que su método representa el estado actual del arte para el problema MS-CFLP-CI. La significancia del trabajo radica en su capacidad para manejar la complejidad computacional introducida por las incompatibilidades de los clientes, que las metaheurísticas anteriores lucharon por optimizar completamente, particularmente para instancias más grandes. El artículo afirma que la combinación de operadores de destrucción novedosos, una fase de reparación exacta y un ajuste algorítmico específico permite al método explorar vecindarios de tamaño mediano de manera efectiva, encontrando soluciones superiores donde SA y otros métodos se estancan. Los autores notan modestamente que, aunque su método es actualmente el mejor, el trabajo futuro podría involucrar Análisis del Espacio de Instancias para comprender mejor la dificultad de las instancias y extender el enfoque a otras variantes de localización de instalaciones.