Clear Sky Science
شروحات قائمة على الأدلة وخفيفة المصطلحات

Clear Sky Science · ar

حل مسألة البائع المتجول متعددة المستودعات بمسارات مغلقة باستخدام تجميع k-means++ الهرمي وشبكات التوليف العصبية

· العودة إلى الفهرس

مسارات أذكى للعديد من السائقين

من شاحنات الطرود إلى الطائرات بدون طيار الناقلة والإسعاف في حالات الكوارث، يواجه المخططون غالبًا لغزًا: كيف يمكن لعدة مركبات تنطلق من مواقع مختلفة أن تتقاسم مهمة زيارة مئات أو آلاف الوقفات دون إهدار الوقود أو الوقت؟ يقدم هذا البحث طريقة جديدة لتقسيم هذا اللغز والتغلُّب عليه، بدمج تقنية تجميع كلاسيكية مع شبكة عصبية حديثة بحيث تستطيع الحواسيب رسم مسارات فعالة خلال ثوانٍ بدلًا من دقائق أو ساعات.

Figure 1. كيف يحول التجميع مع الشبكات العصبية خريطة توصيل متعددة المركبات المعقدة إلى مسارات سريعة وفعالة.
Figure 1. كيف يحول التجميع مع الشبكات العصبية خريطة توصيل متعددة المركبات المعقدة إلى مسارات سريعة وفعالة.

تحدي تعدد المستودعات وتعدد السائقين

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

حدود البحث الكلاسيكي والتقسيم البسيط

لسنوات اعتمد المهندسون على «الطرق فوق الذكية» مثل الخوارزميات الجينية، وبحث مستعمرات النمل، وسرب الجسيمات. تحاكي هذه الأساليب العمليات الطبيعية لاستكشاف العديد من المسارات المرشحة وتحسينها تدريجيًا. يمكن أن تكون مرنة لكنها تحمل عيبين كبيرين: لا تقدم ضمانات قوية على جودة الحل، وقد تكون بطيئة جدًا للخرائط الكبيرة، خاصة عندما يتطلب كل مهمة جديدة إعادة بدء البحث. تسريع شائع هو أولًا تجميع المدن إلى مناطق باستخدام أدوات مثل k-means ثم حل لغز أصغر داخل كل مجموعة. بينما يساعد هذا التقسيم ثم الحل، تظل الجودة النهائية محدودة بأسلوب البحث المستخدم، والسعي لحلول أفضل عادة ما يعني دفع ثمن زمن تشغيل أطول.

تدريب شبكة للتوجيه ثم مساعدتها على التوسع

جلبت السنوات الأخيرة فكرة مختلفة: تدريب شبكة عصبية لإخراج مسارات جيدة مباشرة. بعد التعلم على الكثير من أمثلة تخطيطات المدن، يمكن لمثل هذه الشبكة اقتراح جولة كاملة في تمريرة أمامية واحدة، تمامًا كما يكتب نموذج لغوي جملة. تعمل هذه المحللات العصبية جيدًا بشكل ملحوظ على مشاكل سائق واحد ذات حجم معتدل، لكنها تتعثر عند طلب تنسيق العديد من السائقين أو عندما تكون مجموعة المدن أكبر بكثير من تلك التي دُرِّبَت عليها. التحرك الأساسي للمؤلفين هو تغليف مثل هذا المحلل العصبي داخل عملية من خطوتين تعيد تشكيل مهمة ضخمة متعددة السائقين إلى العديد من المشكلات الفرعية الصغيرة والمألوفة التي يمكن للشبكة التعامل معها بسهولة.

Figure 2. كيف تُقسّم مناطق التوصيل الكبيرة، وتُحلّ بواسطة نموذج عصبي، ثم تُعاد ربطها إلى حلقات فعالة لكل مركبة.
Figure 2. كيف تُقسّم مناطق التوصيل الكبيرة، وتُحلّ بواسطة نموذج عصبي، ثم تُعاد ربطها إلى حلقات فعالة لكل مركبة.

كيف تعمل الطريقة ذات المرحلتين

تبدأ الطريقة المقترحة، المسماة KHC-NCN، باستخدام نسخة محسنة من تجميع k-means لتعيين المدن إلى مستودعات وسائقين مختلفين. إذا احتوت منطقة ناتجة على عدد كبير جدًا من المدن بحيث لا تستطيع الشبكة العصبية التعامل معها بثقة، تقوم الطريقة تلقائيًا بتقسيم تلك المنطقة إلى قطع أصغر، كل واحدة بحجم قريب من ما رأت الشبكة أثناء التدريب. تُعاد تحجيم الإحداثيات في كل قطعة إلى مربع معياري بحيث تشبه بيانات التدريب عن كثب. ثم تنتج الشبكة العصبية مسارًا لكل قطعة صغيرة. أخيرًا، تخيط خطوة الدمج هذه المسارات الفرعية معًا إلى حلقة واحدة لكل سائق، مستخدمة قواعد هندسية بسيطة لربط القطع حيث يضيف ذلك أقل مسافة إضافية.

السرعة والجودة على خرائط معيارية حقيقية

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

ما الذي يعنيه هذا لتوجيه العالم الحقيقي

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

الاستشهاد: Zhao, CS., Wong, LP. & Fung, C. Solving multi-depot closed-path multiple traveling salesman problem using k-means++ hierarchical clustering and neural combinatorial networks. Sci Rep 16, 15631 (2026). https://doi.org/10.1038/s41598-026-45824-3

الكلمات المفتاحية: توجيه المركبات, الشبكات العصبية, التجميع, التحسين, اللوجستيات