توجيه المركبات بسعة محدودة

Capacitated Vehicle Routing Problem (CVRP) هي مسألة تصميم مجموعة مسارات مركبات بأقلّ تكلفة بحيث (أ) تبدأ وتنتهي في مستودع واحد، (ب) تزور كلّ عميل مرّةً واحدة بالضبط، (ج) يبقى إجمالي الطلب على كلّ مسار عند سعة المركبة أو دونها. لا توجد نوافذ زمنية — هذا الامتداد هو VRPTW. التكلفة عادةً هي المسافة الإجمالية، أو الزمن الإجمالي، أو مزيج من الوقود وأجر السائق. CVRP من فئة NP-صعب وهو الجدّ الكنسي لكامل عائلة VRP؛ افتتحه Dantzig وRamser (1959) باسم 'The Truck Dispatching Problem'. الكتاب المرجعي: Toth وVigo (2014). الطرق العملية تمتدّ من خوارزمية Clarke-Wright Savings الكلاسيكية (1964 — لا تزال جودتها مرجعية على الحالات المتوسطة)، مرورًا بتحسينات 2-opt وOr-opt، وخوارزميات branch-and-cut-and-price الدقيقة الحديثة (Fukasawa وآخرون 2006)، وصولًا إلى ميتاهيرستيك ALNS (Adaptive Large Neighborhood Search).