Glosario · approach
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.
Algoritmo de Clarke-WrightAlgoritmo de AhorrosSavings AlgorithmClarke y Wright 1964
El algoritmo Clarke-Wright Savings, introducido por Clarke y Wright en 1964 en *Operations Research*, es la heurística constructiva clásica y más simple para CVRP. Inicialmente cada cliente está en su propia ruta de ida y vuelta (almacén → cliente → almacén). Para cada par de clientes (i, j) se calcula el 'ahorro' s(i, j) = d(almacén, i) + d(almacén, j) − d(i, j) — la reducción de distancia al fusionar las dos rutas de un solo cliente en una ruta almacén → i → j → almacén. Los pares se ordenan por ahorro decreciente; el algoritmo recorre la lista y fusiona dos rutas siempre que la capacidad lo permita. Corre en segundos para 100-200 clientes y suele quedar a 5-10 % del óptimo. A pesar de tener más de sesenta años y de haber sido desarrollado antes de la optimización digital, Clarke-Wright sigue siendo un benchmark práctico para CVRP de tamaño moderado y un arranque cálido estándar para metaheurísticas más sofisticadas como 2-opt, Or-opt y ALNS.
Örnek
Dos rutas de un solo cliente (almacén → A → almacén y almacén → B → almacén) producen un ahorro de 8 km cuando se fusionan en almacén → A → B → almacén. Si la capacidad lo permite, se realiza la fusión; la lista de ahorros se recorre de arriba abajo hasta que no quedan fusiones viables en capacidad.