VRP multi-vehículo: Clarke-Wright Savings explicado

Ha leído el TSP (ordenar paradas) y el VRPTW (respetar las franjas horarias). Queda un caso práctico muy común: tiene varios vehículos. 2 repartidores por la mañana, 5 auxiliares de cuidado en el campo, 3 caterings que salen a la vez. ¿Cómo repartir los clientes entre ellos para minimizar el tiempo total?

Es el VRP (Vehicle Routing Problem) y el método más usado en la práctica data de 1964: el algoritmo de Clarke y Wright, llamado Savings algorithm. Es lo que OptiRoad usa en su plan Business para gestionar de 2 a 10 vehículos.

El problema en una frase

Tiene 1 almacén y N clientes que entregar. Tiene M vehículos disponibles. ¿Cómo repartir los N clientes entre los M vehículos para que el tiempo total sea mínimo?

Parece simple. No lo es.

Por qué es difícil

Con 20 clientes y 3 vehículos, el número de particiones posibles supera los 3,5 millones. Y para cada partición, hay que resolver un TSP (o VRPTW si hay franjas) en cada vehículo. La fuerza bruta es imposible más allá de 10 a 15 clientes.

El VRP, como el TSP, es NP-difícil: ningún algoritmo garantiza la solución óptima en tiempo razonable. Así que usamos heurísticas. La que domina desde hace 60 años en el mundo real es Clarke-Wright Savings.

La idea genial de Clarke-Wright (1964)

George Clarke y John Wright publicaron su artículo "Scheduling of vehicles from a central depot to a number of delivery points" en 1964. La idea es de una elegancia desconcertante.

Paso 1: la solución ingenua

Se empieza con una solución degenerada: cada cliente tiene su propio vehículo. 20 clientes = 20 mini-rutas almacén → cliente → almacén. Derrochador, pero es nuestro punto de partida.

Coste total: para cada cliente i, el vehículo hace d(almacén, i) + d(i, almacén) = 2 × d(almacén, i).

Paso 2: el concepto de "saving"

Imaginemos que fusionamos las rutas de dos clientes i y j en una sola. En lugar de:

almacén → i → almacén   +   almacén → j → almacén

Hacemos:

almacén → i → j → almacén

El ahorro (el saving) es:

s(i,j) = d(almacén, i) + d(j, almacén) - d(i, j)

Cuanto más cerca estén i y j entre sí y más lejos estén del almacén, mayor es el saving. Es intuitivo: vale la pena agruparlos.

Paso 3: la fusión voraz

1. Calcula s(i,j) para todas las parejas de clientes
2. Ordena estos savings en orden descendente
3. Para cada par (i,j), en orden:
   • Si i y j están en rutas diferentes
   • Y están en los extremos de sus rutas respectivas
   • Y aún hay vehículos disponibles (≤ M)
   • Fusiona las dos rutas
4. Continúa hasta agotar los pares útiles

Al final, obtienes M rutas (o menos) que cubren todos los clientes, con una distancia total muy mejor que la solución ingenua, y típicamente a 5 a 10 % del óptimo teórico.

¿Savings, barrido o metaheurística?

Clarke-Wright no es la única familia de algoritmos para el VRP. Coexisten tres grandes enfoques.

El algoritmo de barrido (Gillett y Miller, 1974) agrupa a los clientes por su ángulo alrededor del almacén, como una aguja de reloj que barre el plano. Es extremadamente sencillo de programar, pero la calidad de las rutas es inferior: sigues la geometría, no el coste real.

Las metaheurísticas (búsqueda tabú, algoritmos genéticos) exploran el espacio de soluciones de forma más fina y alcanzan resultados ligeramente mejores. La contrapartida es que son más lentas y más delicadas de ajustar: hay que calibrar numerosos parámetros, lo que las hace pesadas de llevar a producción.

Clarke-Wright Savings se sitúa en el punto de equilibrio ideal: resultados cercanos al óptimo, ejecución rápida, una robustez a toda prueba y una gran facilidad para ampliarlo con capacidades o franjas horarias. Es exactamente por eso que domina la optimización de flotas en condiciones reales desde hace 60 años.

Un ejemplo concreto

Imaginemos 6 clientes a entregar desde un almacén en Madrid-Centro, con 2 vehículos disponibles:

Solución ingenua (1 vehículo por cliente, 6 vehículos):

• Coste total: 2 × (4 + 5 + 8 + 6 + 9 + 7) = 78 km

Con Clarke-Wright Savings y 2 vehículos:

1. Cálculo de los savings para las 15 parejas posibles
2. Orden descendente
3. Fusiones sucesivas respetando el límite de 2 vehículos
4. Resultado posible: Vehículo 1 = almacén → A → B → D → almacén (~22 km), Vehículo 2 = almacén → C → F → E → almacén (~28 km)

• Coste total: ~50 km (-36% vs ingenua)

En casos reales, se observan habitualmente ahorros del 30 al 40% frente a una partición manual "a ojo".

Variantes y extensiones

El algoritmo original es para el VRP básico. En la práctica, se enriquece:

• Capacidades: cada vehículo tiene una carga máxima. Se verifica en cada fusión que no se supera la capacidad.
• Multi-almacén: varios almacenes. Heurística: asignar cada cliente al almacén más cercano, luego Clarke-Wright en cada subproblema.
• Franjas horarias: combinar con VRPTW. Solo fusionar dos rutas si el orden resultante respeta todas las franjas.
• Cota en el número de vehículos: si quiere exactamente M vehículos, se detiene la fusión antes.
• Asimetría: la distancia A→B puede diferir de B→A (sentido único, etc.). El cálculo de los savings sigue siendo válido.

Cómo implementa OptiRoad el VRP multi-vehículo

En plan Business, puede optimizar hasta 10 vehículos en paralelo. Esto es lo que hace OptiRoad cuando activa el modo multi-vehículo:

1. Configuración: indica el número de vehículos, su almacén (común o propio de cada uno), y opcionalmente su punto de llegada.
2. Clarke-Wright Savings: cálculo de los savings sobre todas las parejas, orden descendente, fusiones voraces respetando el límite de vehículos.
3. Multi-almacén: si cada vehículo tiene un almacén diferente (sharedDepot: false), pre-asignación de paradas por proximidad antes de ejecutar Clarke-Wright en cada cluster.
4. TSP local por vehículo: una vez encontrada la partición, cada ruta se re-optimiza individualmente con vecino más cercano + 2-opt para minimizar su distancia interna.
5. Si VRPTW activo: EDF (Earliest Deadline First) en cada ruta, respetando las franjas de cada cliente.
6. Colores distintos: cada vehículo recibe un color en el mapa (#3B82F6, #EF4444, #10B981, etc.) para visualizar fácilmente las rutas.

Timeouts adaptativos: 15 segundos para 2 a 4 vehículos, 30 segundos para 5 a 10 vehículos. Si se supera, OptiRoad devuelve el mejor resultado encontrado con un flag partial: true.

Drag and drop para ajuste manual

Si el reparto automático no le conviene (un cliente debe ir absolutamente con un repartidor concreto por razones comerciales), puede arrastrar y soltar una parada de un vehículo a otro en la app. OptiRoad recalcula entonces el orden TSP para cada vehículo impactado respetando la nueva partición. Endpoint: POST /api/optimize/reorder (plan Business únicamente).

Equilibrar las rutas

En su versión bruta, Clarke-Wright persigue una sola cosa: minimizar la distancia total. Como resultado, puede producir rutas desequilibradas, un repartidor cargado con 25 paradas mientras otro tiene solo 8. Sobre el papel la distancia es óptima; en la vida real eso es ingestionable para la planificación.

En la práctica, por tanto, se limita el número de paradas o la capacidad por vehículo para forzar un reparto más homogéneo. Luego se reequilibra a mano cuando el terreno lo exige. OptiRoad le permite fijar el número de vehículos y mover paradas de uno a otro mediante drag and drop: cada ruta afectada se recalcula al instante, así que mantiene un orden optimizado sin perder el control de la carga de cada repartidor.

Cuándo usar el multi-vehículo

• 2 a 3 vehículos: útil en cuanto su día supera las 30 paradas, o si reparte en zonas geográficas distintas.
• 5 a 10 vehículos: para flotas estructuradas (servicios a la persona, catering con equipo, e-commerce que escala).
• Más de 10 vehículos: contáctenos, podemos activar un solver dedicado para flotas muy grandes.

En la práctica: lo que cambia para usted

Sobre un día típico de 60 entregas a repartir entre 3 repartidores:

• Sin optimización (reparto manual "al ojo"): ~280 km, 12 h acumuladas
• Con Clarke-Wright Savings de OptiRoad: ~190 km, 8 h acumuladas
• Ganancia: -32% de distancia, -33% de tiempo acumulado

Más allá de los kilómetros, la verdadera ganancia es organizativa: cada repartidor empieza con su hoja de ruta clara, su color en el mapa, sus ETAs precisas. Se acabó el "quién lleva a quién" por la mañana.

Para ir más lejos

El VRP multi-vehículo está disponible exclusivamente en plan Business (49 €/mes). El plan Pro sigue siendo mono-vehículo (con o sin franjas horarias).

Esta serie de 3 artículos (TSP → VRPTW → VRP multi-vehículo) cubre las bases conceptuales de OptiRoad. Los próximos artículos abordarán los temas prácticos: cuántos ahorros reales, cómo integrar la API a su tienda e-commerce, etc.

Preguntas frecuentes

¿Cuántos vehículos gestiona OptiRoad? De 2 a 10 vehículos en plan Business. Más allá, contáctenos: podemos activar un solver dedicado para flotas muy grandes.

¿Puede cada vehículo tener un almacén diferente? Sí, el modo multi-almacén está pensado para eso. Las paradas se pre-asignan al almacén más cercano antes de que Clarke-Wright se ejecute en cada cluster, lo que garantiza rutas coherentes por zona.

¿Puedo bloquear un cliente en un vehículo concreto? Sí, mediante drag and drop. Mueve la parada al vehículo deseado y OptiRoad recalcula al instante el orden TSP de los vehículos afectados para mantener cada ruta optimizada.

¿Qué plan se necesita? El plan Business únicamente. El plan Pro sigue siendo mono-vehículo, con o sin franjas horarias.