Resumen Técnico: Una Metaheurística Híbrida para el Problema de Rutas de Vehículos con Capacidad Familiar

Definición del Problema

El artículo aborda el Problema de Rutas de Vehículos con Capacidad Familiar (F-CVRP), una generalización del Problema del Viajante con Familias (FTSP) y del clásico Problema de Rutas de Vehículos con Capacidad (CVRP). En el F-CVRP, una flota homogénea de $K$ vehículos con capacidad $Q$ parte de un único depósito para dar servicio a un conjunto de clientes divididos en familias. A diferencia del CVRP estándar donde cada cliente debe ser visitado, el F-CVF requiere que se visite un número específico de miembros ($v_l$) de cada familia $l$, mientras que los miembros restantes de esa familia pueden quedar sin visitar. El objetivo es minimizar el costo total de las rutas respetando las restricciones de capacidad de los vehículos y cumpliendo con los requisitos exactos de visitas por familia.

A medida que las instancias del problema escalan, los métodos exactos se vuelven computacionalmente prohibitivos. En consecuencia, el artículo se centra en desarrollar una heurística rápida y de alta calidad capaz de entregar soluciones dentro de presupuestos de tiempo estrictos, sirviendo tanto como un resolvedor independiente como un proveedor de cotas primas para marcos de trabajo exactos.

Metodología: La Metaheurística Híbrida ILS+SP

Los autores proponen ILS+SP, una metaheurística híbrida que combina un marco de Búsqueda Local Iterada (ILS) con una fase de post-optimización de Partición de Conjuntos (SP). El algoritmo opera de la siguiente manera:

1. Núcleo de Búsqueda Local Iterada (ILS)

La búsqueda es impulsada por un marco ILS que mantiene un conjunto de rutas ($P$) y rastrea la mejor solución factible encontrada ($s^*$).

• Solución Inicial: Generada mediante una heurística de Inserción Paralela de Mejor Tipo (BPI), construyendo $K$ rutas mediante la inserción iterativa de clientes para minimizar los incrementos de costo, asegurando que se cumplan los conteos de visitas por familia.
• Búsqueda Local (RVND): La búsqueda local emplea una estrategia de Descenso de Vecindad de Variable Aleatoria (RVND). Explora un portafolio de nueve vecindades:
  • Inter-ruta (5): Swap(1,1), Swap(2,1), Swap(2,2), Shift(1,0), Shift(2,0).
  • Intra-ruta (3): Exchange, Reinsertion, Or-opt2.
  • Especializada (1): MemberRelocate, un operador específico del problema que elimina un cliente visitado e inserta un miembro no visitado de la misma familia en la mejor posición a través de todas las rutas.
  • Todas las vecindades preservan las restricciones estructurales de los conteos de visitas de las familias y el número de rutas activas ($K$).
• Criterio de Aceptación: A diferencia de la búsqueda local estándar, el algoritmo acepta movimientos que empeoran la solución basándose en un criterio de Recocido Simulado (SA) con un esquema de enfriamiento basado en el tiempo. Esto permite que la búsqueda escape de los mínimos locales.
• Perturbación: Para diversificar la búsqueda, el algoritmo aplica una de tres perturbaciones aleatorias (RandomSwap, RandomShift o RandomMemberRelocate) a la solución actual antes de reingresar a la búsqueda local.
• Manejo de Penalizaciones: Las violaciones de capacidad se gestionan mediante un coeficiente de penalización dinámica ($\theta$) en la función objetivo, el cual se ajusta según la factibilidad de la solución actual para guiar la búsqueda hacia regiones factibles.

2. Post-Optimización por Partición de Conjuntos (SP)

Tras agotar el presupuesto de tiempo, el algoritmo realiza un paso de optimización final. Formula un problema de Partición de Conjuntos (SP) sobre el conjunto de rutas factibles en capacidad ($P$) recolectadas durante todo el proceso de búsqueda.

• El modelo SP selecciona un subconjunto de rutas para minimizar el costo total mientras satisface los requisitos de visita de las familias y utiliza exactamente $K$ rutas.
• Dado que el conjunto $P$ contiene las rutas que componen la mejor solución encontrada hasta el momento ($s^*$), la solución óptima del SP está garantizada para ser al menos tan buena como $s^*$.

Contribuciones Clave

El artículo destaca cuatro contribuciones primarias que distinguen este trabajo del estado del arte (específicamente el ILS de Bernardino y Paias, 2024):

1. Hibridación con Partición de Conjuntos: La introducción de una fase de post-optimización SP para re-optimizar el conjunto de rutas, un componente de matheurística ausente en enfoques previos.
2. Búsqueda Local Mejorada: La implementación de la vecindad MemberRelocate, que inserta de manera óptima a los miembros de la familia no visitados en la mejor posición a través de todas las rutas, en lugar de simplemente intercambiarlos en su lugar.
3. Exploración de Vecindades Aleatorizadas: El uso de RVND para aleatorizar el orden de exploración de las vecindades, contrastando con el orden fijo utilizado en la literatura previa.
4. Aceptación por Recocido Simulado: La adopción de un criterio de SA para aceptar soluciones que empeoran, reemplazando la estricta aceptación de solo mejoras de métodos anteriores, mejorando así el equilibrio entre intensificación y diversificación.

Resultados Computacionales

Los autores evaluaron el ILS+SP en dos conjuntos de referencia:

1. Benchmark Estándar (144 instancias): Derivado del conjunto de Augerat et al. (1995), que contiene instancias con más de 50 clientes.
   • Desempeño: El método ganó o empató en cada una de las instancias contra la heurística del estado del arte de Bernardino y Paias (2024).
   • Reducción de la Brecha (Gap): La brecha promedio respecto a la Mejor Solución Conocida (BKS) se redujo de 1.84% (el mejor anterior) a 0.01%.
2. Benchmark de Escalabilidad (120 instancias): Un nuevo conjunto de instancias más grandes (hasta 142 clientes) derivado del CVRP Set X (Uchoa et al., 2017).
   • Desempeño: El algoritmo logró una brecha promedio de 0.47% con un tiempo de ejecución promedio de 37 segundos, demostrando escalabilidad hacia tamaños de problema más grandes.

Significancia y Reivindicaciones

El artículo posiciona al ILS+SP como una solución robusta y escalable para el F-CVRP. Los autores afirman que, al integrar una post-optimización de tipo matheurística (SP) con un marco ILS sofisticado que cuenta con vecindades específicas del problema y aceptación por SA, el método supera significativamente a las heurísticas existentes. Los resultados sugieren que el enfoque no solo es capaz de igualar o mejorar las mejores soluciones conocidas para los benchmarks establecidos, sino que también escala efectivamente a instancias más grandes y complejas, convirtiéndolo en una herramienta valiosa tanto para aplicaciones independientes como para la integración en marcos de solución exactos.