القرار الكلاسيكي لموزّع يسلّم يوميًا من مستودع واحد إلى 5-30 عميلًا: كم مركبة تنطلق، أيّ مركبة تزور أيّ عملاء، وبأيّ ترتيب — دون تجاوز السعة وبأقلّ كيلومترات إجمالية. الاسم الأكاديمي: Capacitated Vehicle Routing Problem (CVRP)؛ الجدّ الكنسي لعائلة VRP، فتحه Dantzig وRamser عام 1959.
باختصار
هل يبدو مألوفاً؟
- نسلّم يوميًا من مستودعنا إلى 30-100 عميل — توزيع للوكلاء، قطع غيار B2B، توزيع أغذية-مشروبات، عملية بمستودع واحد.
- طلب كلّ عميل معروف بالكيلوغرام أو بالمتر المكعّب؛ المنسّق يجمّع العملاء حدسيًا لتجنّب تجاوز سعة المركبة من 2-5 طن.
- العملاء بلا نوافذ زمنية أو نوافذهم واسعة جدًا (يقبلون بين 08:00 و18:00) — يستلمون في أيّ ساعة.
- عميلان متجاوران ينتهيان أحيانًا على مركبتين مختلفتين — قرار 'أيّ مركبة في أيّ منطقة هذا الأسبوع' يتبع الخطة السابقة.
- كم مركبة تخرج من المستودع صباحًا يقرّره المنسّق — في بعض الأيام 3 تكفي، وفي أخرى تخرج 5، لا قاعدة واضحة.
- الوقود وأجور السائقين 30-50% من النفقات التشغيلية، لكن لا أحد يعرف كم كيلومترًا يوفّر تغيير المسار.
- عند إضافة عميل جديد، 'على أيّ مركبة يُوضع' يُجاب بالحدس لا بالحساب.
لماذا تهم
كيف تُحل
عمق تقني
كيف تُحل
عمق تقنيفي جملة واحدة: بدلاً من رحلة منفصلة من المستودع لكلّ عميل، احسب كم كم تُوفَّر إذا جمعتَ عميلَين في نفس الشاحنة، ادمج الأزواج الأعلى وفرًا طالما السعة تسمح — يعمل في ثوانٍ؛ أضف بحثًا محلّيًا فوقه لجودة أعلى.
CVRP هو العضو الكنسي والأقدم في عائلة VRP في أدبيات بحوث العمليات (التخصّص الذي يستخدم الرياضيات والحاسوب لحلّ قرارات الأعمال). ورقة عام 1959 (“The Truck Dispatching Problem”) افتتحت الحقل. مستودع واحد، عدّة مركبات، قيد السعة، طلب العملاء؛ لا نوافذ زمنية. الحلّ في ثلاث مراحل:
1. النمذجة. بيانات الإدخال: موقع المستودع (إحداثية واحدة)، مواقع العملاء وكميات الطلب (كغ، م³، طرود — أيًّا كانت الوحدة، المجموع لا يتجاوز السعة)، أسطول المركبات (متجانس — كلّها بنفس السعة؛ غير متجانس — سعات مختلفة)، مصفوفة المسافات مستودع-عميل وعميل-عميل (متماثلة — A→B = B→A؛ غير متماثلة — شوارع أحادية الاتجاه). القيود: كلّ عميل يُزار مرّةً واحدة بالضبط، كلّ جولة تبدأ وتنتهي في المستودع، مجموع الطلب على الجولة لا يتجاوز السعة. خياريّ: الحدّ الأقصى لطول الجولة (وردية السائق)، الحدّ الأقصى لعدد العملاء في الجولة، open VRP (المركبة تنتهي عند آخر عميل ولا تعود — سيناريوهات مركبات مستأجَرة)، VRP متعدّد المستودعات. دالّة الهدف عادةً المسافة الإجمالية الأدنى (أو الوقود)؛ يمكن إضافة عدد المركبات كهدف ثانوي.
2. القرار بالـsolver. ثلاثة مناهج رئيسية:
- خوارزمية كلاسيكية — Clarke-Wright Savings (1964): كلّ عميل يبدأ على جولته الخاصة (مستودع → عميل → مستودع). تُحسب “الوفورات” من دمج جولتين: إذا كان A وB على جولتين منفصلتين وتمّ دمجهما، كم مسافة تُوفَّر؟ يُدمج الزوج صاحب أكبر وفر طالما تسمح السعة. يمكن حسابها دون حاسوب؛ تعمل في ثوانٍ لـ100-200 عميل؛ تنتج عادةً نتيجة تبعد 5-10% عن الأمثل. بعد ستين عامًا لا تزال نقطة انطلاق عملية للعمليات المتوسطة.
- MIP دقيق — branch-and-cut-and-price (التشعيب-والقطع-والتسعير — بحث شجريّ مدعَّم بتوليد أعمدة): يقدّم الأمثل لـ50-200 عميل، لكن وقت الحلّ من دقائق إلى ساعات. مناسب للتخطيط الأسبوعي أو الموسمي — ثقيل للتخطيط الديناميكي اليومي. MIP = Mixed-Integer Linear Programming (تحسين ببعض المتغيّرات 0/1 وأخرى مستمرّة).
- خوارزميات تحسين عام — 2-opt، Or-opt، ALNS (Adaptive Large Neighborhood Search — بحث جوار كبير تكيّفيّ، طريقة ذكيّة تقتلع وتُعيد إدراج أجزاء من الحلّ): مشغّلات تحسين محلّي (“بدّل حافّتين”) تُطبَّق على ناتج Clarke-Wright لرفع الحلّ خطوة خطوة. عملية لـ200-1000 عميل؛ تصل إلى 2-5% من الأمثل في دقائق.
التفضيل العملي: أقلّ من 50 عميلًا — MIP دقيق (ضمان الأمثل)؛ 50-200 عميل — Clarke-Wright + تحسين 2-opt؛ 200+ عميل — ALNS أو ميتاهيرستيك مشابه.
3. التكامل الميداني. الناتج لائحة مرتّبة تذهب إلى لوحة السائق أو الطابعة: “المركبة 1 — 08:30 خروج من المستودع → العميل A (1,2 طن) → العميل C (0,8 طن) → العميل F (1,5 طن) → العودة إلى المستودع.” نظام إدارة الطلبات (ERP أو برنامج شحن مستقلّ) يغذّي solver CVRP: قائمة الطلبات، كميات الطلب، حال الأسطول، مخزون المستودع. يُحتسب مساءً أو فجر اليوم؛ إذا وردت طلبات أثناء النهار، إعادة تخطيط بأفق rolling (5-15 دقيقة). اجتماع تشغيلي شهري: كم فعلي مقابل خطة، عدد مركبات فعلي مقابل خطة، تقرير وفر.
البدائل
يدوي + جدول بيانات + حكم المنسّق
مجانيبلا ترخيص
لمن مناسبة: 1-3 مركبات، 15-30 عميلًا يوميًا، منطقة ثابتة
- + تكلفة برمجية صفر
- + خبرة المنسّق في الواجهة
- + تعديلات سريعة بالهاتف
- − تتدهور جودة الخطة فوق 30-50 عميلًا
- − لا ضمان لاستخدام السعة الأمثل
- − منحنى تعلّم طويل لمنسّقين جدد
- − لا سجلّ تاريخي لكيلومترات/مركبة
برنامج توجيه محلّي (سوق KOBİ)
مؤسسي10-40 ألف TRY إعداد + 3-10 آلاف TRY/شهر اشتراك
لمن مناسبة: 5-15 مركبة، 50-200 عميل يوميًا، مستودع واحد
- + بيانات عناوين وخرائط TR مدمجة
- + واجهة تركية، دعم محلّي
- + تطبيق سائق محمول مضمَّن
- − محرّك نموذجي بأسلوب 'الوفورات' أو nearest-neighbor بسيط؛ ضعيف مع القيود الثقيلة
- − متعدّد المستودعات أو الأسطول بسعات متفاوتة ضعيف
- − شفافية الخوارزمية محدودة — صعب الإجابة 'لماذا هذه الجولة'
برنامج توجيه دولي متخصّص
مؤسسي100-500 EUR/مركبة/شهر اشتراك أو 1,5-8M TRY/سنة ترخيص
لمن مناسبة: 20-100 مركبة، متعدّد المستودعات، أسطول غير متجانس، قيود ثقيلة
- + ناضج: التخطيط بسعة وامتداداته (أسطول بسعات متفاوتة، جولات بلا عودة إلى المستودع، متعدّد المستودعات) مدعوم بالكامل
- + محرّكات بحث متقدّمة للأحجام الكبيرة
- + مقارنة سيناريوهات قويّة
- − ترخيص مرتفع + 3-6 أشهر تنفيذ
- − الدعم التركي قد يكون محدودًا
- − برنامج تدريب واسع
solver مفتوح المصدر + تطوير داخلي
مفتوح المصدرالترخيص مجاني؛ تطوير داخلي 8-16 أسبوعًا أو 300K-1M TRY استشارة
لمن مناسبة: موزّع لديه فريق تقني، تكامل ERP مطلوب
- + بلا رسوم ترخيص
- + التخطيط بسعة مدعوم جيّدًا في solvers مفتوحة المصدر
- + تطبيقات مرجعية لطريقة 'الوفورات' + تحسين محلّي واسعة الانتشار
- − يلزم خبرة في التحسين والبرمجيات داخل المؤسّسة
- − 6-12 شهرًا للوصول إلى نضج ميداني
- − عبء الصيانة على المشغّل
التوصية
اسأل في الاجتماع
- ما المحرّك — طريقة 'الوفورات'، solver بضمانة الـoptimum، محرّك بحث متقدّم، أم nearest-neighbor بسيط؟ في عرض على 50 عميلًا، أيّ طريقة تنتج النتيجة؟
- أسطول بالسعة نفسها فقط، أم أنّ الأسطول بسعات متفاوتة مدعوم؟ في الأسطول بسعات متفاوتة، هل يتّخذ المحرّك قرار تعيين المركبة-العميل؟
- هل الجولات بلا عودة إلى المستودع (مركبات مستأجَرة، تنتهي عند آخر عميل) والتوجيه متعدّد المستودعات مدعومان؟
- كيف تُحسب مصفوفة المسافات — خطّ مستقيم، مسافة طريقية حقيقية، أم زمن مع ازدحام؟ كيف تمّ التحقّق من الدقّة الإقليمية؟
- إذا وصل طلب جديد أثناء النهار، هل تُعاد عملية الحلّ؟ في كم ثانية تصل الجولة المحدَّثة إلى السائق؟
- هل تُفرَض حدود طول الجولة (مثلًا 6 ساعات أو 300 كم) ووردية السائق على مستوى المحرّك أم تُرشَّح لاحقًا؟
- في تجربة 8-12 أسبوعًا ببيانات تشغيلية حقيقية، ما تقرير التوفير الذي يمكن تقديمه مقارنةً بالتخطيط اليدوي السابق؟
- إذا أنهينا العقد، بأيّ صيغة مفتوحة (CSV، GeoJSON أو ما شابه) يمكننا تصدير مواقع العملاء وسجلّ الطلبات وسجلّ الجولات ومصفوفة المسافات؟
تفاصيل تقنية
ملاحظة المحرّر
في الكلام اليومي تُسمّى هذه المسألة “تخطيط المسارات” أو “خطّة التوزيع” أو “تسلسل التوصيل”. في الأدبيات الأكاديمية اسمها Capacitated Vehicle Routing Problem (CVRP) — أقدم وأكنس عضو في عائلة VRP. افتتح Dantzig وRamser الحقل عام 1959. السؤال الذي تطرحه كلّ صباح — “كم مركبة، أيّ مركبة لأيّ عملاء، بأيّ ترتيب، دون تجاوز السعة” — هو السؤال الذي يعمل عليه البحث منذ أكثر من 60 عامًا.
هذه الصفحة يجب ألّا تُخلط مع VRPTW (#002): VRPTW يضيف نافذة زمنية لكلّ عميل (“المتجر يفتح فقط 09:00-12:00”). CVRP بلا نوافذ — العميل متاح طوال اليوم. هو الفرق بين ساعات التسليم النباتية وتسليم B2B بوقت مرن. CVRP أسهل (ألين)؛ VRPTW أكثر واقعية لكنّه أصعب رياضيًا. إذا كانت ساعات استلام عملائك مرنة فعلًا — توزيع للوكلاء، قطع غيار B2B، توزيع مياه-مشروبات — فهذه صفحتك. إذا كانت النوافذ ضيّقة (توصيل منزلي للتجارة الإلكترونية، سلسلة تبريد) فانظر #002.
أكثر النقاط إغفالًا في القطاع: القوّة العملية لخوارزمية Clarke-Wright Savings. طُوِّرت عام 1964 لتُحسب بالورقة والقلم قبل توفّر الحواسيب، وبعد ستين عامًا لا تزال تصل إلى 5-10% من الأمثل في العمليات المتوسطة، في دقائق. عندما يروّج مورّد لـ"محرّك خوارزمي حصري" أو “محرّك تحسين مسجَّل ببراءة”، اطلب منه مقارنة benchmark على 50 عميلًا مقابل Clarke-Wright + 2-opt. إذا كان الفرق دون 2%، فلا تستحقّ التكلفة الإضافية للترخيص. النقطة المُغفَلة الثانية: جودة مصفوفة المسافات. كثير من الأدوات تستخدم مسافة إقليدية (مستقيمة)؛ المسافة الحضرية الفعلية أكبر بـ1,3-1,8 مرّة. المسافة الخاطئة تعني مسارًا خاطئًا — يجب اختبار مصفوفة الطرق الفعلية أثناء التجربة.
خطوة بخطوة — للشركة المتوسطة
المرحلة 1 — قِسْ أوّلًا ثمّ خطِّط. على الأقلّ 4 أسابيع جدول: كم يومي لكلّ مركبة، عدد العملاء، نسبة استخدام السعة (تحميل/الحدّ الأقصى)، مدّة جولة المستودع-المستودع، ساعات السائق. بلا هذا الأساس لا يمكن تقييم أيّ برنامج.
المرحلة 2 — اِبنِ جدول العميل-الطلب. لكلّ عميل: كمية الطلب النموذجية (كغ أو م³)، العنوان، الإحداثيات، القيود (حدّ حجم المركبة — “الشاحنة الكبيرة لا تدخل”، زمن التفريغ اليدوي). في معظم KOBİ هذه المعلومات تعيش فقط في رأس المنسّق؛ تدوينها وحده يعطي 5-10% كفاءة.
المرحلة 3 — التجربة. 6-10 أسابيع. 1-3 مركبات. معيار النجاح مكتوب قبل البدء: “خلال 60 يومًا، كم إجمالية -10%، استخدام السعة +5%، عدد مركبات يومي -1.” إذا لم يتحقّق، تنتهي التجربة — احفظ حقّ الخروج في العقد.
المرحلة 4 — الانتشار. 2-4 أشهر إلى الأسطول الكامل. تدريب السائقين 1-2 أسبوع. سائق “بطل” لكلّ منطقة. اجتماع تشغيلي شهري: كم فعلية مقابل خطّة، استخدام السعة، تكلفة لكلّ عميل.
المخاطر — ما الذي يمكن أن يخطئ
- انجراف توقّع الطلب. إذا كان الطلب اليومي للعميل يبتعد 20-50% عن الخطّة، فالسعة إمّا نصف فارغة أو متجاوَزة. cut-off الطلبات وحساب المسارات أقرب ما يمكن؛ إعادة التخطيط بأفق rolling إلزامية.
- عطل مركبة في النهار. إذا تعطّلت مركبة على الطريق، فإنّ إعادة التوزيع الحدسي لبقية العملاء على مركبات أخرى تتجاوز السعة أو تتخطّى عميلًا. يجب أن يدعم البرنامج إعادة الحلّ في النهار وأن يُنتج خطّة في 30 دقيقة.
- ظهور طلب نافذة زمنية لاحقًا. عميل يقول “في الحقيقة أستلم فقط صباحًا” يكسر نموذج CVRP — تصبح المسألة VRPTW. عندما يتجاوز عدد النوافذ في المحفظة 10-20، يلزم الانتقال إلى solver لـVRPTW.
- الاعتماد على مزوّد TMS واحد. بدون بند تعاقدي بتصدير سنوي بصيغة قياسية (CSV أو GeoJSON) لمواقع العملاء وسجلّ الطلبات وسجلّ المسارات، يعني ترك النظام فقدان الذاكرة التشغيلية للموزّع.
نظرة تقنية على طريقة الحلّ
المناهج الرئيسية في أدبيات CVRP:
| النهج | الحجم النموذجي | الزمن | الأمثلية مضمونة؟ |
|---|---|---|---|
| تجريبي (منسّق + قاعدة) | 1-3 مركبات، 15-30 عميلًا | فوري | لا، 50-80% أمثل |
| Clarke-Wright Savings (1964) | 50-200 عميل | ثوانٍ-دقائق | لا، 5-10% من الأمثل |
| Clarke-Wright + 2-opt / Or-opt | 50-300 عميل | دقائق | لا، 3-7% من الأمثل |
| MIP دقيق — branch-and-cut-and-price | 50-200 عميل | دقائق-ساعات | نعم (في مقياس محدود) |
| ALNS ميتاهيرستيك | 200-1000 عميل | دقائق | لا، 2-5% من الأمثل |
| توليد الأعمدة | 100-500 عميل، multi-tour | ساعات | عمليًا قرب الأمثل |
اختيار الصياغة:
- صياغة بفهرسين: متغيّر قرار لكلّ حافّة (i, j). سهلة الفهم، لكن ثقيلة بحجم كبير بسبب قيود إقصاء الجولات الفرعية (SEC).
- صياغة بثلاثة فهارس: متغيّر قرار لكلّ (i, j, مركبة k). أكثر مرونة للأسطول غير المتجانس أو open VRP؛ يتضاعف عدد المتغيّرات.
اختيار دالّة الهدف:
- أدنى مسافة إجمالية: الأكثر شيوعًا؛ تركيز على الوقود + الصيانة.
- أدنى وقت إجمالي: عندما تكون تكلفة السائق أعلى من الوقود.
- عدد المركبات + المسافة (هرمي): المركبات أوّلًا ثمّ المسافة — قرار تقليص الأسطول.
- الوقود + الأجر مجتمعين: التكلفة التشغيلية المباشرة كهدف.
التوسعات — أقارب CVRP العملية:
- VRP بأسطول غير متجانس: مركبات بسعات مختلفة — يجتمع مع “المركبة الكبيرة لا تدخل وسط المدينة”.
- Open VRP: المركبة تنتهي عند آخر عميل ولا تعود.
- VRP متعدّد المستودعات: عدّة مستودعات؛ كلّ عميل يُسنَد إلى الأنسب.
- VRP بقيد المسافة: طول الجولة محدود بوردية السائق.
- CVRP غير متماثل: A→B يختلف عن B→A بسبب اتجاهات أحادية في المدن.
VRPTW (#002)، PDPTW (#046)، DARP (#047) وTSP (#068) أقارب قريبون. CVRP الأبسط والأقدم؛ فهمه هو الخطوة الأولى نحو الباقي.
المراجع الأكاديمية
مُدرَجة في sources من frontmatter.
المصادر
- Dantzig, G. B. وRamser, J. H. (1959). The truck dispatching problem. Management Science, 6(1), 80-91. الورقة المؤسِّسة لعائلة VRP — أوّل تعريف بوصفها ‘TSP مع سعة’.
- Clarke, G. وWright, J. W. (1964). Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, 12(4), 568-581. خوارزمية الوفورات الكلاسيكية — لا تزال benchmark عمليًا.
- Toth, P. وVigo, D. (2014). Vehicle Routing: Problems, Methods, and Applications (الطبعة الثانية). SIAM-MOS. الكتاب الكنسي لحقل VRP.
- Laporte, G. (1992). The vehicle routing problem: An overview of exact and approximate algorithms. European Journal of Operational Research, 59(3), 345-358. نظرة تاريخية ومنهجية.
- Fukasawa, R., Longo, H., Lysgaard, J., Aragão, M. P., Reis, M., Uchoa, E. وWerneck, R. F. (2006). Robust branch-and-cut-and-price for the capacitated vehicle routing problem. Mathematical Programming, 106(3), 491-511. خوارزمية CVRP دقيقة حديثة.
- مركز رسائل YÖK — كلمة مفتاحية: ‘kapasiteli araç rotalama’ أو ‘CVRP’ — أكثر من 30 رسالة من الأكاديميا التركية. tez.yok.gov.tr
المسرد
- توجيه المركبات بسعة محدودة
- تصميم مسارات مركبات بأقلّ تكلفة تبدأ وتنتهي في مستودع واحد، وتزور كلّ عميل مرّةً واحدة بالضبط، دون أن يتجاوز إجمالي طلب المسار سعة المركبة.
- خوارزمية Clarke-Wright للوفورات
- خوارزمية تجريبية كلاسيكية من عام 1964 لمسألة Capacitated VRP: كلّ عميل يبدأ على جولته الخاصّة، ثمّ تُدمج أزواج الجولات تدريجيًا بحسب أكبر 'وفر' في المسافة، إلى أن تمنع السعة مزيدًا من الدمج.
- VRP
- قرار أي المركبات — منطلقةً من مستودع واحد أو عدة مستودعات — تزور أي عملاء وبأي ترتيب.
- MIP
- نموذج تحسين تكون فيه بعض متغيرات القرار أعداداً صحيحة (مثل: عدد الشاحنات، عدد الورديات).
مشاكل ذات صلة
أي مركبة لأي زبون، وفي أي ساعة؟
أسطول توصيل محلي من 5 إلى 30 مركبة يخطّط مساراته اليومية. لكل عميل نافذة زمنية للاستلام (متجر يقبل التسليم بين 09:00 و12:00، ومطعم لا يقبل إلا قبل 14:00). القرار: أي عميل لأي مركبة، بأي ترتيب، كي تُحترم كل النوافذ، وتبقى ساعات الوقود والسائق عند حدودها الدنيا، ولا تتجاوز أي مركبة طاقتها. المنسّق يستطيع تخطيط 30–50 نقطة ذهنياً؛ بعد هذا الحد تنخفض جودة الخطة — كيلومترات فارغة، تسليمات متأخرة، جولات ثانية، وساعات إضافية للسائقين.
أين أفتح المستودع الجديد؟
موزّع أو متجر إلكتروني أو مصنع متوسط يخطّط لافتتاح 1–5 مستودعات أو فروع أو مراكز توزيع جديدة خلال 2–5 سنوات. القرار: في أي مدينة أو منطقة، كم منشأة، بأي حجم، وأي من المستودعات الحالية ينقل أي حجم من العملاء/الطلبات إلى أي منشأة جديدة. الموقع الخاطئ يعني 5–10 سنوات من ارتفاع تكاليف النقل وتأخر التسليم وفقدان عملاء؛ والموقع الصحيح يعني توفيراً سنوياً 300 ألف – 1.5 مليون دولار خلال الفترة نفسها. حين يُؤخذ القرار حدسياً (مثلاً «إلى جانب المصنع، العمال يسكنون قرباً») نادراً ما يصيب الأمثل — لأن تكلفة النقل والإيجار والضرائب وكلفة العمالة وزمن الخدمة قيود ينبغي موازنتها معاً.