¿Qué es el CVRP?
El CVRP decide qué clientes atiende cada vehículo de una flota con capacidad limitada y en qué orden los visita, minimizando la distancia total recorrida.
Definición formal
Dado un depósito, un conjunto de clientes con una demanda cada uno, una matriz de distancias entre todos los puntos y una flota de vehículos con capacidad Q, el CVRP busca un conjunto de rutas que:
- empiecen y terminen en el depósito;
- visiten cada cliente exactamente una vez;
- no excedan la capacidad Q en ninguna ruta;
- minimicen la distancia total (o el costo total).
Es una generalización del problema del agente viajero (TSP): si hay un solo vehículo con capacidad infinita, el CVRP es un TSP.
Por qué es difícil
El CVRP es NP-difícil. En términos prácticos: el número de soluciones posibles crece de forma factorial con el número de clientes, así que no existe un método conocido que garantice la solución óptima en tiempo razonable para instancias grandes.
Esto explica algo que se ve en toda operación logística: la planeación manual no es "mejorable con más experiencia", es estructuralmente incapaz de explorar el espacio de soluciones. Un buen despachador encuentra una solución razonable; un algoritmo explora millones.
Cómo se resuelve en la práctica
Métodos exactos
Ramificación y acotamiento, ramificación y corte, generación de columnas. Garantizan el óptimo pero solo son viables en instancias pequeñas —decenas de clientes— o con mucho tiempo de cómputo. Sirven para investigación y para certificar cotas.
Heurísticas constructivas
Construyen una solución razonable rápido: vecino más cercano, ahorros de Clarke-Wright, barrido angular, primero-mejor-ajuste. Son el punto de partida, no el destino: suelen quedar entre 10% y 20% por encima del óptimo.
Búsqueda local
Mejoran una solución existente con movimientos pequeños: mover un cliente a otra posición (relocate), intercambiar dos clientes (swap), invertir un tramo (2-opt), reconectar dos rutas (2-opt*). Para que sea rápida se usan listas de vecinos cercanos y evaluación incremental del costo en tiempo constante.
Metaheurísticas
Coordinan la búsqueda para escapar de óptimos locales: recocido simulado, búsqueda tabú, algoritmos genéticos y, sobre todo en VRP moderno, búsqueda de vecindarios grandes adaptativa (ALNS), que destruye parte de la solución y la reconstruye guiada por el aprendizaje de qué operadores funcionan mejor.
Cómo se mide una solución: BKS y benchmarks
La comunidad científica evalúa los algoritmos sobre conjuntos de instancias estándar —Christofides, Golden, Uchoa (conjunto X), entre otros— y compara contra el BKS (Best Known Solution), la mejor solución encontrada por cualquier método hasta la fecha. Un algoritmo serio reporta su brecha porcentual promedio contra esos BKS, con semillas y tiempos declarados; sin ese contexto, cualquier afirmación de calidad es marketing.
Variantes que aparecen en la operación real
| Variante | Qué añade |
|---|---|
| VRPTW | Ventanas de tiempo de entrega por cliente. |
| HFVRP | Flota heterogénea: vehículos con capacidades y costos distintos. |
| PDP | Recolección y entrega emparejadas. |
| MDVRP | Varios depósitos. |
| 3L-CVRP | La carga debe caber físicamente en tres dimensiones. |
Del modelo a la calle
Un detalle que separa los ejercicios académicos de los sistemas que se usan: en los bancos de prueba las distancias suelen ser euclidianas, mientras que en una ciudad real hay sentidos únicos, ríos y avenidas sin retorno. Un optimizador aplicable necesita trabajar sobre la clausura métrica de la red vial: la matriz de caminos mínimos reales entre todos los puntos. Es la diferencia entre una ruta bonita y una ruta que el chofer puede manejar.
Pruebe LATTIMEX con sus propias entregas
Cuenta demo gratuita: planifique rutas reales sobre el mapa de su ciudad.
