المسرد · approach
خوارزمية Clarke-Wright للوفورات
خوارزمية تجريبية كلاسيكية من عام 1964 لمسألة Capacitated VRP: كلّ عميل يبدأ على جولته الخاصّة، ثمّ تُدمج أزواج الجولات تدريجيًا بحسب أكبر 'وفر' في المسافة، إلى أن تمنع السعة مزيدًا من الدمج.
خوارزمية Clarke-Wrightخوارزمية الوفوراتSavings AlgorithmClarke and Wright 1964
خوارزمية Clarke-Wright Savings، التي قدّمها Clarke وWright عام 1964 في *Operations Research*، هي الخوارزمية البنّاءة الكلاسيكية والأبسط لـCVRP. في البدء كلّ عميل على جولته الخاصة ذهابًا وإيابًا (مستودع → عميل → مستودع). لكلّ زوج من العملاء (i, j) تُحسب 'الوفر' s(i, j) = d(مستودع, i) + d(مستودع, j) − d(i, j) — وهي تخفيض المسافة الناتج عن دمج الجولتين الفرديتين في جولة مستودع → i → j → مستودع. تُرتَّب الأزواج تنازليًا بحسب الوفر؛ تمشي الخوارزمية في القائمة وتدمج جولتين كلّما سمحت سعة المركبة. تعمل في ثوانٍ على 100-200 عميل، وتنتج عادةً نتيجة تبعد 5-10% عن الأمثل. رغم أنّ عمرها يفوق الستين عامًا، وأنّها سبقت عصر التحسين الرقمي، لا تزال Clarke-Wright benchmark عمليًا لـCVRP بحجم متوسّط، وبدايةً ساخنة قياسية لميتاهيرستيك أكثر تعقيدًا مثل 2-opt وOr-opt وALNS.
Örnek
جولتان من عميل واحد (مستودع → A → مستودع، ومستودع → B → مستودع) تنتجان وفرًا قدره 8 كم عند دمجهما في مستودع → A → B → مستودع. إذا سمحت السعة، يُجرى الدمج؛ تُقرأ قائمة الوفورات من الأعلى إلى الأسفل، ويستمرّ الدمج إلى أن تنتهي عمليات الدمج المتوافقة مع السعة.