← أحدث الأبحاث
🤖 AI

Integrating Column Generation and Large Neighborhood Search for Bus Driver Scheduling with Complex Break Constraints

تقدم هذه الورقة إطار تحسين هجين يدمج بشكل وثيق بين تقنية "التفريع والسعر" (Branch and Price) و"البحث في الجوار الكبير" (Large Neighborhood Search)، مستفيداً من توليد الأعمدة المشترك لتحقيق حلول رائدة لمسألة جدولة سائقي الحافلات عبر مختلف أحجام النماذج.

المؤلفون الأصليون: Lucas Kletzander, Tommaso Mannelli Mazzoli, Nysret Musliu, Pascal Van Hentenryck

نُشر 2026-04-23
📖 5 دقيقة قراءة🧠 قراءة متعمّقة
CC BY 4.0

المؤلفون الأصليون: Lucas Kletzander, Tommaso Mannelli Mazzoli, Nysret Musliu, Pascal Van Hentenryck

البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل

تخيل أنك مدير لشركة حافلات ضخمة. مهمتك هي وضع جدول زمني لمئات من سائقي الحافلات. لديك قائمة برحلات الحافلات التي يجب أن تتم، ولكن عليك أيضاً اتباع جبل من القواعد: لا يمكن للسائقين العمل لأكثر من 9 ساعات، ويحتاجون إلى أوقات استراحة محددة (بعضها مدفوع الأجر وبعضها غير مدفوع)، ولا يمكنهم تغيير الحافلات كثيراً، ويجب أن يعودوا إلى منازلهم في وقت معقول.

هدفك مزدوج:

  1. توفير المال: لا توظف سائقين أكثر مما هو ضروري.
  2. إسعاد السائقين: تجنب الجداول الزمنية المرهقة، أو فترات الاستراحة الطويلة غير المدفوعة، أو التي تتطلب الكثير من تغيير الحافلات.

هذه هي مشكلة جدولة سائقي الحافلات (BDSP). إنها لغز ضخم، حيث يجب أن تتناسب كل قطعة (نوبة عمل السائق) تماماً مع القطع الأخرى دون كسر أي قواعد.

تقدم هذه الورقة طريقة جديدة وذكية جداً لحل هذا اللغز باستخدام استراتيجيتين رئيسيتين: التفريع والتعمية (Branch and Price - B&P) و البحث في الجوار الكبير (Large Neighborhood Search - LNS)، ثم تُظهر كيفية دمجهما في "فريق خارق".

إليك تفصيل نهجهم باستخدام تشبيهات بسيطة:

1. حل "اللغز المثالي": التفريع والتعمية (B&P)

تخيل التفريع والتعمية كمهندس معماري دقيق للغاية ومحب للكمال.

  • كيف يعمل: يحاول بناء الجدول المثالي من الصفر. يقوم بتفكيك المشكلة إلى قطع صغيرة. يسأل: "إذا أعطيت هذا السائق المحدد هذا المسار المحدد، هل هو قانوني؟" إذا كان نعم، يحتفظ به. إذا كان لا، يتخلص منه.
  • المشكلة: بالنسبة للمدن الصغيرة (الألغاز الصغيرة)، يكون هذا المهندس مذهلاً؛ فهو يجد الحل الأمثل المطلق. ولكن بالنسبة لمدينة ضخمة بها آلاف الرحلات، يصاب المهندس بالارتباك. عدد الاحتمالات ضخم جداً لدرجة أنه يستغرق وقتاً طويلاً للتحقق منها جميعاً. الأمر يشبه محاولة العثور على حبة رمل معينة على الشاطئ من خلال فحص كل حبة رمل واحدة تلو الأخرى.
  • حل الورقة: أدرك المؤلفون أن المهندس يقضي وقتاً طويلاً في فحص حبات الرمل التي من الواضح أنها خاطئة. أضافوا "مرشحات ذكية" (مثل أشجار k-d و التقنين القوسي - arc throttling) لتجاهل الخيارات السيئة فوراً، مما جعل المهندس أسرع بكثير.

2. حل "المصلح المبتكر": البحث في الجوار الكبير (LNS)

تخيل البحث في الجوار الكبير كمبتكر سريع الحركة ومبدع.

  • كيف يعمل: بدلاً من البناء من الصفر، يبدأ المبتكر بجدول زمني "جيد بما يكفي". ثم يقول: "دعونا نعبث بجزء من هذا الجدول ونحاول إصلاحه بشكل أفضل".
    • التدمير: يختار مجموعة من السائقين (ربما أولئك الذين يعملون في أكثر النوبات تكلفة أو إرهاقاً) ويمسح جداولهم تماماً.
    • الإصلاح: يحاول إعادة تعيين هؤلاء السائقين لمسارات جديدة ليرى ما إذا كانت التكلفة الإجمالية ستنخفض.
  • المشكلة: عادة ما يستخدم المبتكر "صندوقاً أسود" لإصلاح الفوضى. يلقي بالقطع المكسورة فقط إلى برنامج حل (solver) ويأمل الأفضل. هو لا يتذكر ما تعلمه من إصلاح "الفوضى" السابقة.
  • حل الورقة: جعل المؤلفون المبتكر أكثر ذكاءً. أدركوا أنه عندما يصلح المبتكر مجموعة من السائقين، فإنه يولد الكثير من "الأفكار الجيدة" (تركيبات مسارات جديدة). وبدلاً من رمي هذه الأفكاء، يجب عليهم حفظها واستخدامها لاحقاً عند إصلاح مجموعات أخرى من السائقين.

3. "الفريق الخارق": دمج الاثنين معاً

هذا هو الاختراق الأكبر للورقة. لم يستخدموا فقط "المثالي" (B&P) أو "المبتكر" (LNS)؛ بل جعلواهم يعملون معاً في حلقة محكمة.

  • الاستراتيجية:
    1. المبتكر (LNS) يفكك الجدول الزمني.
    2. يطلب من المثالي (B&P) إصلاح القطع المكسورة.
    3. الخطوة السحرية: المثالي لا يعيد فقط الجدول الزمني المصلح. بل يسلم أيضاً "دفتر ملاحظات" بكل أفكار المسارات الجيدة التي اكتشفها أثناء إصلاح تلك القطعة.
    4. يحفظ المبتكر هذا الدفتر. وعندما يفكك الجدول مرة أخرى لاحقاً، يفتح الدفتر ويقول: "مهلاً، أنا أعرف بالفعل طريقة رائعة لتوجيه هؤلاء السائقين! دعونا نستخدم هذه الفكرة بدلاً من البدء من الصفر".
    5. العامل في الخلفية: أضافوا أيضاً "عاملاً في الخلفية" (خيط معالجة ثاني في الكمبيوتر) يراقب باستمرار جميع الأفكار التي تم جمعها حتى الآن ويحاول بناء جدول زمني "عالمي" أفضل في الخلفية، بينما يستمر المبتكر في العمل على الجدول الرئيسي.

لماذا يعد هذا أمراً مهماً؟

  • للمدن الصغيرة: لا يزال "المثالي" (B&P) هو الملك. يجد الإجابة المثالية رياضياً في ثوانٍ.
  • للمدن المتوسطة/الكبيرة: عادة ما يكون "المبتكر" (LNS) سريعاً، لكن "الفريق الخارق" الجديد أفضل بكثير. من خلال مشاركة الأفكار (الأعمدة) بين أجزاء مختلفة من المشكلة، يجدون حلولاً أفضل وأسرع من أي شخص آخر من قبل.
  • النتيجة: اختبروا هذا على بيانات حافلات نمساوية حقيقية. بالنسبة للمشكلات الصغيرة، أثبتوا أن الإجابة مثالية. وبالنسبة للمشكلات المتوسطة والكبيرة، وجدوا حلولاً أرخص بكثير وأكثر كفاءة من أي طريقة سابقة، ليصبحوا فعلياً "أحدث ما توصل إليه العلم" (state-of-the-art).

باختصار

تخيل أنك تحاول تنظيم مخطط جلوس لحفل زفاف ضخم.

  • الطريقة (أ) (الطريقة القديمة): تحاول حساب كل ترتيب جلوس ممكن للعثور على الترتيب المثالي. (يستغرق وقتاً طويلاً لـ 500 ضيف).
  • الطريقة (ب) (الطريقة القديمة): تقوم بتحريك بعض الأشخاص، وترى ما إذا كان الأمر يبدو أفضل، ثم تكرر العملية. (سريع، لكنك قد تفوت أفضل ترتيب).
  • طريقة هذه الورقة: تقوم بتحريك بعض الأش ludzi، ولكن في كل مرة تجد فيها مجموعة جلوس رائعة، تقوم بتدوينها في دفتر ملاحظات مشترك. في المرة القالية التي تحرك فيها مجموعة مختلفة، تتحقق من الدفتر أولاً. كما أن لديك صديقاً يجلس في الخلف، يقرأ الدفتر باستمرار ويقترح ترتيبات عامة أفضل بينما تعمل أنت.

يسمح نهج "الدفتر المشترك" هذا بحل مشكلات الجدولة المعقدة التي كانت في السابق صعبة للغاية أو بطيئة جداً للتعامل معها بكفاءة.

غارق في أبحاث مجالك؟

تصلك نشرة يومية بأحدث الأبحاث المطابقة لكلماتك البحثية المفتاحية — مع ملخصات تقنية، بلغتك.

جرّب Digest →

أبحاث مشابهة

عرض الكل في هذا التصنيف 🤖 cs.AI →