من أكثر مهام التحسين شيوعًا توجيه المركبات، والهدف منها العثور على أفضل المسارات لأسطول المركبات التي تزور مجموعة من المواقع الجغرافية. عادة ما تعني كلمة "أفضل" المسارات التي أقل مسافة أو تكلفة إجمالية. في ما يلي بعض الأمثلة على مشاكل التوجيه:
- تريد شركة توصيل الطرود تعيين مسارات للسائقين لإجراء عمليات التسليم.
- لنفترض أن هناك شركة تلفزيون كبلي تريد تعيين مسارات للفنيين لإجراء مكالمات خدمات منزلية.
- تريد شركة مشاركة الرحلات تعيين مسارات للسائقين لاصطحاب الركاب وإنزالهم.
إنّ أكثر مشاكل التوجيه شهرة هي مشكلة مندوب المبيعات المسافر (TSP): ابحث عن أقصر طريق لمندوب المبيعات الذي يحتاج إلى زيارة العملاء في مواقع جغرافية مختلفة والعودة إلى نقطة البداية. يمكن تمثيل مقدّم خدمة الرموز المميزة بواسطة رسم بياني حيث تتوافق العُقد مع المواقع الجغرافية، وتشير الحواف (أو الأقواس) إلى التنقّل المباشر بين المواقع. على سبيل المثال، يُظهر الرسم البياني أدناه مقدّم خدمة مع أربعة مواقع جغرافية فقط مسماة "أ" و"ب" و"ج" و"د". يتم تحديد المسافة بين أي موقعين من خلال الرقم المجاور للحافة التي تربطهما.
من خلال حساب المسافات لجميع المسارات الممكنة، يمكنك معرفة أن
أقصر مسار هو ACDBA، حيث تبلغ المسافة الإجمالية 35 + 30 + 15 + 10 = 90.
تصبح المشكلة أكثر صعوبة عندما يكون هناك المزيد من المواقع. في المثال أعلاه، هناك ستة مسارات فقط. ولكن إذا كانت هناك عشرة مواقع (لا تحسب نقطة البداية)، فإن عدد المسارات هو 362880. بالنسبة إلى 20 موقعًا جغرافيًا، سينتقل الرقم إلى 2432902008176640000. سيضمن البحث الشامل عن جميع المسارات الممكنة العثور على الأقصر، إلا أن ذلك يستدعي حلًا حسابيًا لكل المجموعات ما عدا المجموعات الصغيرة. بالنسبة للمشكلات الأكبر، هناك حاجة إلى أساليب التحسين للبحث بذكاء في مساحة الحل والعثور على الحل الأمثل (أو شبه الأمثل).
ثمة إصدار أكثر عمومية من مقدّم خدمة الرموز المميّزة يتمثّل في مشكلة توجيه المركبة (VRP) حيث توجد مركبات متعدّدة. في معظم الحالات، تكون هناك قيود مفروضة على نماذج معاينة الفيديو (VRP): على سبيل المثال، قد تحتوي المركبات على السعات اللازمة لوزن أو حجم البضائع التي يمكن حملها، أو قد يُطلب من السائقين زيارة المواقع الجغرافية خلال فترات زمنية محدّدة يطلبها العملاء.
يمكن أن تحل أدوات OR حلول العديد من أنواع VRP، بما في ذلك ما يلي:
- مشكلة مندوب مبيعات مسافر، مشكلة التوجيه الكلاسيكية حيث تكون هناك مركبة واحدة فقط.
- مشكلة في توجيه المركبات، وهي عبارة عن تعميم مقدّم خدمة الرموز المميّزة الذي يتضمّن عدة مركبات.
- VRP مع قيود على السعة: تتضمّن المركبات السعة القصوى للعناصر التي يمكنها حملها.
- VRP مع فترات زمنية، حيث يجب أن تقوم المركبات بزيارة المواقع الجغرافية خلال فترات زمنية محددة.
- VRP مع قيود على الموارد، مثل المساحة أو الموظفين لتحميل المركبات وتفريغها في المستودع (نقطة البداية للمسارات).
- VRP مع انخفاض في عدد الزيارات: عندما لا يكون مطلوبًا من المركبات زيارة جميع المواقع الجغرافية، ولكن يجب دفع عقوبة عن كل زيارة يتم إغفالها.
القيود على حل مشكلات توجيه المركبات
تعد مشكلات توجيه المركبات قابلة للحل بطبيعتها، حيث يتزايد طول الوقت اللازم لحلها بشكل كبير مع حجم المشكلة. بالنسبة للمشكلات الكبيرة بما فيه الكفاية، قد يستغرق الأمر OR-أدوات (أو أي برنامج توجيه آخر) سنوات للعثور على الحل الأمثل. نتيجة لذلك، تُرجع أدوات OR أحيانًا حلولاً جيدة، ولكنها ليست مثالية. للعثور على حل أفضل، عليك تغيير خيارات البحث الخاصة بأداة الحلّ. للاطّلاع على مثال، راجِع تغيير استراتيجية البحث.