Glossario · approach
Clarke-Wright Savings
Euristica classica del 1964 per il Capacitated Vehicle Routing Problem: ogni cliente parte sulla propria rotta e le coppie di rotte vengono fuse iterativamente per il maggior 'risparmio' finché la capacità non blocca ulteriori fusioni.
Algoritmo di Clarke-WrightAlgoritmo dei RisparmiSavings AlgorithmClarke e Wright 1964
L'algoritmo Clarke-Wright Savings, introdotto da Clarke e Wright nel 1964 in *Operations Research*, è l'euristica costruttiva classica e più semplice per CVRP. Inizialmente ogni cliente è sulla propria rotta andata-ritorno (deposito → cliente → deposito). Per ogni coppia di clienti (i, j) si calcola il 'risparmio' s(i, j) = d(deposito, i) + d(deposito, j) − d(i, j) — la riduzione di distanza che si ottiene fondendo le due rotte mono-cliente in deposito → i → j → deposito. Le coppie sono ordinate per risparmio decrescente; l'algoritmo scorre la lista e fonde due rotte ogni volta che la capacità lo consente. Gira in pochi secondi per 100-200 clienti e si attesta tipicamente entro il 5-10 % dall'ottimo. Pur avendo oltre sessant'anni e precedendo l'ottimizzazione digitale, Clarke-Wright resta un benchmark pratico per CVRP di taglia media e un warm-start standard per metaeuristiche più sofisticate come 2-opt, Or-opt e ALNS.
Örnek
Due rotte mono-cliente (deposito → A → deposito e deposito → B → deposito) producono un risparmio di 8 km se fuse in deposito → A → B → deposito. Se la capacità lo permette, la fusione viene eseguita; la lista dei risparmi è scorsa dall'alto in basso finché non restano fusioni compatibili con la capacità.