La decisión clásica del distribuidor que entrega a diario desde un único almacén a 5-30 clientes: cuántos vehículos salen, qué vehículo atiende a qué clientes y en qué orden — sin superar la capacidad y con kilometraje total mínimo. Nombre académico: Capacitated Vehicle Routing Problem (CVRP); ancestro canónico de la familia VRP, abierto por Dantzig y Ramser en 1959.
En pocas palabras
¿Te suena?
- Repartimos a diario desde nuestro almacén a 30-100 clientes — distribución a distribuidores, recambios B2B, distribución de alimentación-bebidas, operación de un solo almacén.
- El pedido de cada cliente se conoce en kg o m³; el planificador agrupa clientes por intuición para no superar la capacidad de 2-5 toneladas.
- Los clientes no tienen ventanas o las tienen muy amplias (aceptan entre 08:00 y 18:00) — reciben a cualquier hora.
- Dos clientes vecinos a veces caen en dos vehículos distintos — la decisión 'qué vehículo en qué zona esta semana' sigue el plan anterior.
- Cuántos vehículos salen por la mañana lo decide el planificador — unos días bastan 3, otros salen 5, sin regla clara.
- El combustible y los salarios de los conductores son el 30-50 % del gasto operativo, pero no sabemos cuántos km ahorraría un cambio de ruta.
- Al añadir un cliente nuevo, 'a qué vehículo encaja' se responde a ojo, no con un cálculo.
Por qué importa
Cómo se resuelve
Profundidad técnica
Cómo se resuelve
Profundidad técnicaEn una frase: En lugar de hacer un viaje almacén-cliente por separado para cada uno, calcula cuántos km ahorras al meter dos clientes en el mismo camión, fusiona los pares con mayor ahorro mientras la capacidad lo permita — corre en segundos; añade búsqueda local por encima para más calidad.
CVRP es el miembro canónico y más antiguo de la familia VRP en la literatura de Investigación de Operaciones (disciplina que usa matemáticas e informática para resolver decisiones de negocio). El artículo de 1959 (“The Truck Dispatching Problem”) abrió el campo. Un único almacén, varios vehículos, restricción de capacidad, demanda del cliente; sin ventanas horarias. Solución en tres etapas:
1. Modelización. Datos de entrada: localización del almacén (una coordenada), localización de los clientes y demandas (kg, m³, paquetes — sea la unidad que sea, la suma no debe superar la capacidad), flota de vehículos (homogénea — todos con la misma capacidad; heterogénea — capacidades distintas), matriz de distancias almacén–cliente y cliente–cliente (simétrica — A→B = B→A; asimétrica — calles de un solo sentido). Restricciones: cada cliente se visita exactamente una vez, cada ruta empieza y termina en el almacén, la demanda total de una ruta no supera la capacidad. Opcionales: longitud máxima de ruta (turno del conductor), nº máximo de clientes por ruta, open VRP (el vehículo acaba en el último cliente y no vuelve — escenarios de alquiler), multi-depósito. La función objetivo suele ser distancia total mínima (o combustible); se puede añadir el número de vehículos como objetivo secundario.
2. Decisión por solver. Tres enfoques principales:
- Heurística clásica — Clarke-Wright Savings (1964): Cada cliente empieza en su propia ruta (almacén → cliente → almacén). Se calcula el “ahorro” al fusionar dos rutas: si A y B están en rutas separadas y se fusionan, cuánta distancia se ahorra. Se fusiona el par con mayor ahorro siempre que la capacidad lo permita. Se puede calcular sin ordenador; corre en segundos para 100-200 clientes; suele quedar a 5-10 % del óptimo. Sesenta años después sigue siendo un punto de partida práctico para operaciones medianas.
- MIP exacto — branch-and-cut-and-price (ramificación-corte-precio — búsqueda en árbol reforzada con generación de columnas): da el óptimo en 50-200 clientes, pero la solución tarda de minutos a horas. Útil para planificación semanal o estacional — pesado para planificación dinámica diaria. MIP = Mixed-Integer Linear Programming (optimización con algunas variables 0/1 y otras continuas).
- Metaheurísticas — 2-opt, Or-opt, ALNS (Adaptive Large Neighborhood Search — búsqueda adaptativa de gran vecindario, método inteligente que arranca y reinserta trozos): operadores de mejora local (“intercambiar dos aristas”) aplicados sobre la salida de Clarke-Wright suben la solución paso a paso. Prácticas para 200-1000 clientes; quedan a 2-5 % del óptimo en minutos.
Preferencia práctica: menos de 50 clientes — MIP exacto (óptimo garantizado); 50-200 clientes — Clarke-Wright + mejora 2-opt; 200+ clientes — ALNS u otra metaheurística.
3. Despliegue en campo. La salida es una lista ordenada que llega al tablet del conductor o a la impresión: “Vehículo 1 — 08:30 sale del almacén → cliente A (1,2 t) → cliente C (0,8 t) → cliente F (1,5 t) → vuelve al almacén.” El sistema de gestión de pedidos (ERP o software de despacho independiente) alimenta el solver CVRP: lista de pedidos, demandas, estado de flota, stock en almacén. Se calcula por la tarde o temprano por la mañana; si entran pedidos durante el día, replanificación con horizonte deslizante (5-15 minutos). Reunión mensual de operaciones: km reales vs plan, número de vehículos real vs plan, informe de ahorro."
Alternativas
Manual + hoja de cálculo + criterio del planificador
GratisSin licencia
Para quién: 1-3 vehículos, 15-30 clientes/día, territorio fijo
- + Coste de software cero
- + Experiencia del planificador al frente
- + Ajustes rápidos por teléfono
- − La calidad cae por encima de 30-50 clientes
- − Sin garantía de uso óptimo de capacidad
- − Curva de aprendizaje larga para nuevos planificadores
- − Sin histórico de km/vehículo
Software local de rutas (mercado pyme)
Empresarial300-1.500 EUR de implantación + 100-400 EUR/mes
Para quién: 5-15 vehículos, 50-200 clientes/día, almacén único
- + Datos de mapa y direcciones locales integrados
- + Interfaz en español, soporte local
- + App móvil del conductor incluida
- − Motor típico: un método 'savings' o nearest-neighbor simple; débil con restricciones complejas
- − Multi-depósito o flota con capacidades mixtas poco soportados
- − Transparencia algorítmica limitada — 'por qué esta ruta' es difícil de responder
Software internacional especializado en rutas
Empresarial100-500 EUR/vehículo/mes o 50.000-250.000 EUR/año de licencia
Para quién: 20-100 vehículos, multi-depósito, flota heterogénea, restricciones complejas
- + Maduro: planificación capacitada y extensiones (flota con capacidades mixtas, rutas sin retorno a depósito, multi-depósito) totalmente soportadas
- + Motores de búsqueda avanzados para gran escala
- + Comparación de escenarios fuerte
- − Licencia alta + 3-6 meses de implantación
- − Soporte en español puede ser limitado
- − Programa de formación amplio
Solver de código abierto + desarrollo interno
Código abiertoLicencia gratuita; desarrollo interno 8-16 semanas o 30.000-100.000 EUR de consultoría
Para quién: Distribuidor con equipo técnico, integración con ERP deseada
- + Sin coste de licencia
- + Planificación capacitada bien soportada en solvers de código abierto
- + Implementaciones de referencia 'savings' + mejora local extensas
- − Requiere experiencia interna en optimización y software
- − 6-12 meses hasta nivel productivo
- − Mantenimiento a cargo del operador
Recomendación
Pregunta en la reunión
- ¿Cuál es el motor — método 'savings', solver con garantía de óptimo, motor de búsqueda avanzado o nearest-neighbor simple? En una demo con 50 clientes, ¿qué método produce el resultado?
- ¿Solo flota con la misma capacidad o también flota con capacidades mixtas? En una flota con capacidades mixtas, ¿la elección de vehículo-cliente la hace el motor?
- ¿Se soportan rutas sin retorno a depósito (vehículos de alquiler, el vehículo acaba en el último cliente) y rutas multi-depósito?
- ¿Cómo se calcula la matriz de distancias — línea recta, distancia real por carretera o tiempo con tráfico? ¿Cómo se validó la precisión regional?
- Si llega un pedido nuevo durante el día, ¿se re-resuelve el plan? ¿En cuántos segundos llega la ruta actualizada al conductor?
- ¿Los límites de longitud de ruta (p. ej., máx. 6 h o 300 km) y las restricciones de turno del conductor se aplican a nivel de motor o como filtro posterior?
- En un piloto de 8-12 semanas con datos reales, ¿qué informe de ahorro se puede presentar frente a la planificación manual previa?
- Si terminamos el contrato, ¿en qué formato abierto (CSV, GeoJSON o similar) podemos exportar localizaciones de clientes, histórico de pedidos, histórico de rutas y matriz de distancias?
Detalles técnicos
Nota de la redacción
En el lenguaje cotidiano este problema se llama “planificación de rutas”, “plan de reparto” o “secuencia de entregas”. En la literatura académica su nombre es Capacitated Vehicle Routing Problem (CVRP) — el miembro más antiguo y canónico de la familia VRP. Dantzig y Ramser abrieron el campo en 1959. La pregunta que usted se hace cada mañana — “cuántos vehículos, qué vehículo a qué clientes, en qué orden, sin superar la capacidad” — es la pregunta sobre la que la investigación lleva más de 60 años trabajando.
Esta página no debe confundirse con VRPTW (#002): VRPTW añade una ventana horaria por cliente (“la tienda solo abre 09:00-12:00”). CVRP no tiene ventanas — el cliente está disponible todo el día. Es la diferencia entre el horario de reparto vegano y la entrega B2B con tiempo flexible. CVRP es más fácil (más blando); VRPTW es más realista pero matemáticamente más difícil. Si sus clientes tienen realmente horarios flexibles de recepción — distribución a distribuidores, recambios B2B, distribución de agua-bebidas — esta es su página. Si hay ventanas horarias estrechas (entrega a domicilio de e-commerce, cadena de frío), véase #002.
Punto más omitido del sector: la fuerza práctica del algoritmo Clarke-Wright Savings. Desarrollado en 1964 para ser calculado con papel y lápiz antes de que hubiera ordenadores, esta heurística sigue llegando a 5-10 % del óptimo sesenta años después en operaciones medianas, en minutos. Cuando un proveedor publicita un “motor heurístico propietario” o “motor de optimización patentado”, pídale un benchmark sobre 50 clientes frente a Clarke-Wright + 2-opt. Si la diferencia es menor del 2 %, no compensa el coste de licencia. Segundo punto omitido: calidad de la matriz de distancias. Muchas herramientas usan distancia Euclídea (línea recta); la distancia real urbana es 1,3-1,8 veces mayor. Distancia equivocada implica ruta equivocada — hay que probar la matriz vial real durante el piloto.
Camino paso a paso para una pyme
Fase 1 — Primero medir, luego planificar. Mantener al menos 4 semanas una tabla: km diarios por vehículo, número de clientes, utilización de capacidad (carga/máximo), duración de la ruta almacén-almacén, horas de conductor. Sin esta base no se puede evaluar ningún software.
Fase 2 — Construir la tabla cliente-demanda. Por cada cliente: cantidad típica del pedido (kg o m³), dirección, coordenadas, restricciones (límite de tamaño de vehículo — “el camión grande no entra”, tiempo de descarga manual). En la mayoría de pymes esta información vive solo en la cabeza del planificador; escribirla ya aporta 5-10 % de eficiencia.
Fase 3 — Piloto. 6-10 semanas. 1-3 vehículos. Criterio de éxito por escrito antes de empezar: “en 60 días, km totales -10 %, utilización de capacidad +5 %, número diario de vehículos -1.” Si no se cumple, el piloto termina — asegurar el derecho de salida en el contrato.
Fase 4 — Despliegue. 2-4 meses a toda la flota. Formación de conductores 1-2 semanas. Un conductor “campeón” por zona. Reunión mensual de operaciones: km real vs plan, utilización de capacidad, coste por cliente.
Riesgos — qué puede fallar
- Desviación de la previsión de demanda. Si la cantidad diaria pedida está 20-50 % fuera del plan, la capacidad queda medio vacía o se supera. Cut-off de pedidos y cálculo de rutas tan próximos como sea posible; replanificación con horizonte deslizante imprescindible.
- Avería de vehículo en pleno día. Si un vehículo se avería en ruta, la reasignación intuitiva de los clientes restantes a otros vehículos sobrepasa la capacidad o se salta a alguien. El software debe soportar re-resolver en el día y producir un plan en 30 minutos.
- Demanda de ventanas horarias emergente. Si un cliente dice “en realidad solo recibo por la mañana”, el modelo CVRP se rompe — el problema se convierte en VRPTW. Cuando el número de ventanas en la cartera supere 10-20, hay que migrar a un solver VRPTW.
- Dependencia de un solo proveedor (TMS). Sin cláusula contractual de exportación anual en formato estándar (CSV o GeoJSON) de localizaciones, histórico de pedidos y rutas, abandonar el sistema significa perder la memoria operativa del distribuidor.
Vista técnica del método de solución
Principales enfoques en la literatura CVRP:
| Enfoque | Tamaño típico | Tiempo | ¿Óptimo garantizado? |
|---|---|---|---|
| Heurística (planificador + regla) | 1-3 vehículos, 15-30 clientes | inmediato | No, 50-80 % óptimo |
| Clarke-Wright Savings (1964) | 50-200 clientes | seg-min | No, 5-10 % del óptimo |
| Clarke-Wright + 2-opt / Or-opt | 50-300 clientes | minutos | No, 3-7 % del óptimo |
| MIP exacto — branch-and-cut-and-price | 50-200 clientes | min-h | Sí (a escala limitada) |
| Metaheurística ALNS | 200-1000 clientes | minutos | No, 2-5 % del óptimo |
| Generación de columnas | 100-500 clientes, multi-tour | horas | Prácticamente cerca del óptimo |
Elección de formulación:
- Formulación 2-índice: Una variable por arista (i, j). Fácil de entender, pero pesada a gran escala por restricciones de eliminación de subrutas (SEC).
- Formulación 3-índice: Una variable por (i, j, vehículo k). Más flexible para flota heterogénea u open VRP; el número de variables se multiplica.
Función objetivo:
- Distancia total mínima: la más habitual; enfoque combustible + mantenimiento.
- Tiempo total mínimo: cuando el coste del conductor supera al del combustible.
- Número de vehículos + distancia (jerárquico): primero vehículos, luego distancia — decisión de flota reducida.
- Combustible + salario combinados: coste operativo directo como objetivo.
Extensiones — parientes prácticos del CVRP:
- VRP de flota heterogénea: vehículos de capacidades distintas — se combina con “vehículo grande no entra en el casco urbano”.
- Open VRP: el vehículo acaba en el último cliente, no vuelve.
- VRP multi-depósito: varios almacenes; cada cliente se asigna al más conveniente.
- VRP con restricción de distancia: longitud de ruta limitada por el turno del conductor.
- CVRP asimétrico: A→B distinto de B→A por calles de un solo sentido.
VRPTW (#002), PDPTW (#046), DARP (#047) y TSP (#068) son parientes cercanos. CVRP es el miembro más simple y más antiguo; entenderlo es el primer paso hacia los demás.
Fuentes académicas
Listadas en el bloque sources del frontmatter.
Fuentes
- Dantzig, G. B. y Ramser, J. H. (1959). The truck dispatching problem. Management Science, 6(1), 80-91. Artículo fundacional de la familia VRP — primera definición como ‘TSP con capacidad’.
- Clarke, G. y Wright, J. W. (1964). Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, 12(4), 568-581. Algoritmo clásico de ahorros — todavía benchmark práctico.
- Toth, P. y Vigo, D. (2014). Vehicle Routing: Problems, Methods, and Applications (2.ª ed.). SIAM-MOS. Libro canónico del campo VRP.
- Laporte, G. (1992). The vehicle routing problem: An overview of exact and approximate algorithms. European Journal of Operational Research, 59(3), 345-358. Panorámica histórica y de métodos.
- Fukasawa, R., Longo, H., Lysgaard, J., Aragão, M. P., Reis, M., Uchoa, E. y Werneck, R. F. (2006). Robust branch-and-cut-and-price for the capacitated vehicle routing problem. Mathematical Programming, 106(3), 491-511. Algoritmo exacto moderno para CVRP.
- Centro de Tesis YÖK — palabra clave: ‘kapasiteli araç rotalama’ o ‘CVRP’ — más de 30 tesis de la academia turca. tez.yok.gov.tr
Glosario
- Ruteo de vehículos con capacidad
- Diseño de rutas de vehículos de coste mínimo que empiezan y terminan en un único almacén, visitan a cada cliente exactamente una vez, sin que la demanda total por ruta supere la capacidad del vehículo.
- Clarke-Wright Savings
- Heurística clásica de 1964 para el Capacitated Vehicle Routing Problem: cada cliente empieza en su propia ruta y los pares de rutas se fusionan iterativamente por el mayor 'ahorro' hasta que la capacidad bloquea nuevas fusiones.
- VRP
- La decisión de qué vehículos, partiendo de uno o varios almacenes, visitan a qué clientes y en qué orden.
- MIP
- Modelo de optimización donde parte de las variables de decisión deben ser números enteros (p. ej. número de camiones o de turnos).
Problemas relacionados
¿Dónde Abro el Nuevo Almacén?
Un distribuidor, un operador de comercio electrónico o un fabricante pyme prevé abrir 1–5 nuevos almacenes, sucursales o centros de distribución en los próximos 2–5 años. La decisión: en qué ciudad o región, cuántas instalaciones, de qué tamaño y qué almacenes existentes transfieren qué volumen de pedido o cliente a la nueva instalación. Una mala localización implica 5–10 años de alto coste de transporte, entregas tardías y pérdida de clientes; una buena localización supone 300.000–1,5 M EUR de ahorro anual en el mismo periodo. Cuando la decisión se toma por intuición (por ejemplo 'al lado de la fábrica, los empleados viven cerca') rara vez se acierta — porque coste de transporte, alquiler, impuestos, mano de obra y tiempo de servicio son restricciones que deben equilibrarse a la vez.
¿Qué cabe en un camión o contenedor, y en qué orden se carga?
Dado un camión, contenedor o vehículo de carga de dimensiones fijas, ¿qué disposición de cajas (o pallets) con tamaños, pesos y reglas de apilado distintos da la mayor tasa de utilización? El nombre matemático de esta pregunta es Three-Dimensional Bin Packing Problem (3D-BPP) o Container Loading Problem (CLP). Métodos que resuelven al mismo tiempo volumen, límites de peso, reglas de apilado, distribución del peso (balance) y orden de entrega (multi-drop) se estudian desde los 1990. Incluso un 5% de mejora en utilización aumenta entregas por vehículo de forma material para una pyme.
¿Qué Furgoneta a Qué Cliente, a Qué Hora?
Una flota local de reparto de 5–30 furgonetas planifica sus rutas diarias. Cada cliente tiene una ventana horaria (una tienda recibe entre 09:00 y 12:00; un restaurante solo antes de las 14:00). La decisión: a qué furgoneta asignar cada cliente, en qué orden visitarlos, de modo que todas las ventanas se cumplan, las horas de combustible y conductor sean mínimas, y ninguna furgoneta supere su capacidad. Un repartidor puede planificar a mano 30–50 paradas; por encima, la calidad cae — kilómetros vacíos, entregas tardías, segundas rutas y horas extra del conductor.