A Metaheuristic Solution for the Capacitated Vehicle Routing Problem: Empirical Evaluation of Flexible Capacity Constraints via Ant Colony Optimisation

Resumen Técnico: Una Solución Metaheurística para el Problema de Enrutamiento de Vehículos con Capacidad Limitada

1. Definición y Contexto del Problema
El estudio aborda un Problema de Enrutamiento de Vehículos con Capacidad Limitada (CVRP, por sus siglas en inglés) del mundo real, derivado de una operación de recolección de materia prima entrante en Colombia. La red logística consiste en un depósito central en Guadalajara de Buga (Valle del Cauca) que sirve a treinta centros de distribución ubicados en diversas regiones colombianas (costas, regiones andinas y zonas industriales). La operación enfrenta ciclos de demanda variables (de 643 a 1,192 paquetes por ciclo) y utiliza una flota homogénea de diez camiones Foton FRR Cummins.

Una restricción operativa crítica es la política de capacidad flexible: si bien la capacidad nominal del vehículo es $Q = 150$ paquetes, la política corporativa autoriza una sobrecarga controlada del 5%, estableciendo una capacidad de planificación efectiva de $Q_{eff} = 157.5$ paquetes. El enrutamiento debe realizarse sobre redes viales no euclidianas derivadas de OpenStreetMap (vía OSMnx), donde las complejidades topológicas (corredores montañosos, calles de un solo sentido) crean una asimetría significativa entre las distancias euclidianas y los costos de viaje reales.

El sistema de planificación actual, "Rout Now", emplea una arquitectura de "agrupar primero, enrutar después": particiona los nodos en 10 grupos geográficos utilizando k-means (basado en coordenadas planas) y luego secuencia cada grupo de forma independiente mediante Simulated Annealing (SA). Este enfoque resulta en una utilización heterogénea de la flota (35%–90%) y despliega sistemáticamente los 10 vehículos, incluso cuando los límites inferiores teóricos sugieren que 6–8 vehículos serían suficientes.

2. Metodología
La investigación propone y evalúa una metaheurística de Optimización de Colonia de Hormigas (ACO) diseñada para operar sobre el grafo completo de nodos activos sin una partición geográfica previa.

• Formulación Matemática: El problema se modela como un Programa Lineal Entero Mixto (MILP) utilizando la formulación de Miller–Tucker–Zemlin (MTZ) para la eliminación de subtours. La restricción de capacidad se relaja explícitamente a $Q_{eff} = 157.5$ para modelar la política de sobrecarga dentro de la lógica de optimización.
• Arquitectura ACO:
  • Construcción: Las hormigas construyen rutas de múltiples vehículos de forma iterativa. Un diferenciador clave es el mecanismo de enmascaramiento dinámico: el conjunto de nodos siguientes factibles ($F_k$) se filtra en tiempo real para asegurar que la carga acumulada no exceda $Q_{eff}$. Esto permite al algoritmo "empaquetar" los nodos de manera eficiente, explotando el margen del 5% solo cuando es necesario para evitar la apertura de una nueva ruta.
  • Probabilidad de Transición: La probabilidad de seleccionar un nodo depende de los rastros de feromonas ($\tau$) y la visibilidad heurística ($\eta = 1/C_{ij}$). Dada la alta varianza en los costos viales colombianos (desviación estándar del 47% respecto a la media), el peso heurístico ($\beta = 2.0$) se calibró para dominar el peso de la feromona ($\alpha = 1.0$), priorizando la eficiencia de costo inmediato.
  • Mecanismo de Actualización: Se aplican las reglas estándar de evaporación y depósito, reforzando los arcos que contribuyen a soluciones de bajo costo y alta consolidación.
• Diseño Experimental:
  • Escenarios: Se extrajeron diez escenarios operativos distintos (S-1 a S-10) que representan un mes completo de ciclos de planificación a partir de datos reales de la empresa.
  • Repetición: Cada escenario se ejecutó 20 veces de forma independiente con diferentes semillas aleatorias para aislar la varianza estocástica.
  • Comparación con la Línea Base: Los resultados de ACO se compararon contra la línea base "Rout Now" (k-means + SA) utilizando matrices de distancia de OSMnx idénticas para asegurar la validez interna.
  • Validación Estadística: Se aplicó la prueba de rango con signo de Wilcoxon no paramétrica a las distancias totales medias de las 20 ejecuciones por escenario para probar la significancia estadística.

3. Resultados Clave
El enfoque ACO demostró mejoras sistemáticas y estadísticamente significativas sobre la línea base en los diez escenarios:

• Reducción de Flota: En el escenario de mayor demanda (S-3; 1,192 paquetes), el ACO redujo la flota activa de 10 vehículos (línea base) a 8 vehículos, igualando el límite inferior teórico ($\lceil 1192/157.5 \rceil = 8$). En todos los escenarios, la flota activa se redujo aproximadamente un 20%.
• Distancia y Costo:
  • Distancia Total: Se redujo en un promedio del 20.05% (con un rango de 19.97% a 20.25%). En S-3, la distancia cayó de 11,023 km a 8,790.5 km.
  • Costo de Combustible: Ahorros estimados del 16.05% en el escenario crítico (aprox. 941,340 COP por ciclo).
  • Tiempo Operativo: Reducido en un 20.02%.
• Utilización de Capacidad: El ACO logró una consolidación casi perfecta, elevando la utilización promedio de capacidad de ~79.47% (línea base) al 99.50% en S-3. Las rutas en la solución ACO operaron entre el 96% y el 101% de la capacidad nominal, con rutas específicas explotando el margen de sobrecarga del 5% para evitar la necesidad de un noveno vehículo.
• Significancia Estadística: La prueba de rango con signo de Wilcoxon arrojó un estadístico de $W=0$ (todas las diferencias favorecieron al ACO) con un p-valor $< 0.01$, rechazando la hipótesis nula de igualdad de medianas y confirmando la robustez de las mejoras.

4. Significancia y Contribuciones
El artículo reclama tres contribuciones científicas primarias:

1. Evaluación Empírica de Restricciones Flexibles: Documenta cómo el modelado explícito de una restricción de capacidad flexible ($Q_{eff}$) dentro de una metaheurística constructiva permite una consolidación de carga coordinada que es estructuralmente imposible para las arquitecturas de partición previa. El estudio demuestra que la tolerancia del 5% no es simplemente un margen de seguridad, sino una palanca estratégica para la reducción de la flota cuando se gestiona dinámicamente.
2. Robustez en Topologías del Mundo Real: El trabajo proporciona evidencia de que las metaheurísticas bio-inspiradas (específicamente ACO) superan a las heurísticas clásicas de "agrupar primero, enrutar después" en redes viales complejas y no euclidianas. El estudio destaca que la partición geográfica previa (k-means) no logra considerar las asimetrías de la red vial, mientras que ACO opera en el espacio de costo real.
3. Identificación del Mecanismo Causal: El artículo identifica el "enmascaramiento dinámico" de los nodos no factibles durante la construcción de la ruta como el mecanismo causal del éxito. Esto permite al algoritmo realizar un "empaquetado eficiente" de la demanda, explotando orgánicamente el margen de sobrecarga para minimizar el número de rutas, una capacidad ausente en la arquitectura de la línea base.

5. Limitaciones y Trabajo Futuro
Los autores señalan que el estudio está limitado a un contexto industrial específico sin ventanas de tiempo (VRPTW) o restricciones de horas de conducción. Las direcciones de investigación futura propuestas incluyen:

• Extender el modelo a VRPTW para incorporar horarios de recepción.
• Abordar la incertidumbre de la demanda mediante VRP Estocástico (SVRP).
• Desarrollar formulaciones multiobjetivo (por ejemplo, minimización de emisiones de CO₂) utilizando algoritmos evolutivos.
• Integrar el núcleo de ACO como un microservicio para pruebas A/B controladas dentro de los sistemas logísticos existentes.