Sözlük · approach
Clarke-Wright Savings
Kapasiteli Araç Rotalama Problemi için 1964 tarihli klasik sezgisel: her müşteri kendi turunda başlar, iki tur birleştirildiğinde elde edilen en büyük 'tasarruf'lu çiftler kapasite müsait olduğu sürece adım adım birleştirilir.
Clarke-Wright AlgoritmasiTasarruf AlgoritmasiSavings AlgorithmClarke ve Wright 1964
Clarke ve Wright'ın 1964'te *Operations Research* dergisinde tanıttığı Savings algoritması, CVRP için klasik ve en basit yapıcı sezgiseldir. Her müşteri başlangıçta kendi gidiş-dönüş turundadır (depo → müşteri → depo). Her (i, j) müşteri çifti için 'tasarruf' s(i, j) = d(depo, i) + d(depo, j) − d(i, j) — iki tek-müşterili turun depo → i → j → depo şeklinde birleştirilmesinden kaynaklanan mesafe azalması — hesaplanır. Çiftler azalan tasarruf sırasına göre dizilir; algoritma listeyi yürür ve araç kapasitesini ihlal etmediği sürece iki turu birleştirir. 100-200 müşteri ölçeğinde saniyeler içinde çalışır, optimuma genellikle %5-10 uzaklıkta sonuç verir. 60 yılı aşkın yaşına ve dijital optimizasyon öncesi geliştirilmiş olmasına rağmen, Clarke-Wright orta ölçekli CVRP için pratik bir benchmark ve daha gelişmiş metaheuristiklerin (2-opt, Or-opt, ALNS) standart sıcak başlangıcı olarak hâlâ kullanılır.
Örnek
İki tek-müşterili tur (depo → A → depo ve depo → B → depo) birleştirildiğinde depo → A → B → depo şeklinde 8 km tasarruf sağlar. Kapasite uygunsa birleşme yapılır; tasarruf listesi yukarıdan aşağı yürünür, kapasiteye uygun başka birleşme kalmayana dek devam edilir.