Hybrid ICA–Local Search for the Multi-Depot Vehicle Routing Problem
تقترح هذه الورقة خوارزمية تنافس إمبريالية هجينة ثنائية الطبقة مدمجة مع البحث المحلي لتحسين تخصيصات العملاء للمستودعات ومسارات المركبات في آن واحد لمسألة توجيه المركبات متعددة المستودعات، محققةً نتائج تنافسية بفجوات تبلغ حوالي 2% في المعايير القياسية.
البحث الأصلي مرخَّص بموجب CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل
تخيل مدينة حيث يجب على مستودع واحد تسليم الطرود إلى مئات المنازل. يكمن التحدي في معرفة الطريقة الأكثر كفاءة لإرسال أسطول من الشاحنات بحيث يتم زيارة كل منزل، ولا يتم تحميل الشاحنة فوق طاقتها، وتكون المسافة الإجمالية المقطوعة هي الأقصر. هذه أحجية كلاسيكية يعرفها الرياضيون باسم مشكلة توجيه المركبات. ولكن في العالم الحقيقي، نادراً ما تكون الأمور بهذه البساطة؛ فغالباً لا تأتي البضائع من مركز واحد، بل من عدة مستودعات متفرقة عبر منطقة ما. وهذا يضيف طبقة ثانية من الصعوبة المماثلة للغز: فقبل أن يتمكن السائق حتى من تخطيط مساره، يجب على شخص ما أن يقرر أي مستودد هو المسؤول عن أي عميل. هذا التحدي الموسع، حيث يكون الهدف هو تخصيص العملاء للمستودعات الصحيحة ثم تخطيط مسارات القيادة المثالية لكل منها، يسمى مشكلة توجيه المركبات متعددة المستودعات. إنها مشكلة ذات تعقيد هائل، حيث أن عدد التوليفات الممكنة ضخم لدرجة أن العثور على الحل الأمثل المطلق أمر مستحيل حاسوبياً للمدن الكبيرة. ولهذا السبب، يعتمد الباحثون على طرق مختصرة ذكية، تُعرف باسم "الخوارزميات الاستدلالية الفائقة" (metaheuristics)، للعثور على حلول قريبة جداً من المثالية دون فحص كل الاحتمالات الممكنة.
في دراسة حديثة، تناول باحثون من جامعة "نورث ساوث" (North South University) هذا الصداع اللوجستي تحديداً عبر ابتكار طريقة هجينة جديدة تجمع بين استراتيجيتين متميزتين. لقد بنوا نظاماً يفصل المشكلة إلى طبقتين، تماماً مثل مدير يقرر أولاً أي فريق سيتولى أي منطقة، ثم يترك قادة الفرق يكتشفون أفضل طريقة للتحرك داخل تلك المنطقة. تستخدم الطبقة الأولى من نظامهم تقنية تسمى "خوارزمية المنافسة الإمبريالية" (Imperialist Competitive Algorithm). يحاكي هذا النهج شكلاً من أشكال المنافسة الاجتماعية حيث يتم تصنيف مجموعة من الحلول المحتملة، والتي تسمى "دولاً"، بناءً على أدائها. تصبح الحلول الأفضل بمثابة "إمبراطوريات"، بينما تصبح الدول الأخرى "مستعمرات" تابعة لها. ومع مرور الوقت، تحاول المستعمرات أن تصبح أكثر تشبهاً بإمبراطورياتها من خلال نسخ قراراتها، بينما تقوم أحياناً بتغييرات عشوائية للحفاظ على حيوية البحث. وفي هذه الدراسة المحددة، فإن "القرار" الذي يتم نسخه هو أي مستودد يخدم أي عميل. أما الطبقة الثانية من النظام فهي "موجه البحث المحلي" (local-search router). بمجرد أن تقوم الطبقة الأولى بتخصيص العملاء للمستودعات، يتدخل هذا الموجه لبناء مسارات القيادة الفعلية. يبدأ بإنشاء مسار أساسي باستخدام قاعدة بسيطة وهي إضافة أقرب عميل متاح، ثم يقوم بتحسين هذا المسار عبر اختبار تغييرات صغيرة، مثل تبديل ترتيب محطتين أو نقل محطة إلى جزء آخر من المسار، لمعرفة ما إذا كانت المسافة الإجمالية ستتقلص.
يكمن الابتكار في هذا العمل في كيفية تواصل هاتين الطبقتين مع بعضهما البعض. يعمل موجه البحث المحلي كـ "حكم" لخوارزمية المنافسة الإمبريالية. ففي كل مرة تقترح فيها الخوارية طريقة جديدة لتخصيص العملاء للمستودعات، يقوم الموجه فوراً بحساب إجمالي مسافة القيادة لتلك التخصيصات. تصبح هذه المسافة هي الدرجة، أو "لياقة" (fitness)، التي تحدد أي التخصيصات يتم الاحتفاظ بها وأيها يتم استبعادها. ولجعل النظام أكثر دقة، أضاف الباحثون خطوة صقل نهائية؛ فبعد انتهاء المنافسة الرئيسية بين الحلول، يأخذ النظام أفضل نتيجة تم التوصل إليها حتى الآن ويجري فحصاً يدوياً دقيقاً. حيث يقوم مؤقتاً بنقل عملاء أفراد إلى مستودعات مختلفة ليرى ما إذا كان إعادة التخصيص البسيطة يمكن أن تستخلص أي عدم كفاءة متبقي. وقد تم اختبار هذه العملية برمتها مقابل مجموعة معيارية صعبة من حالات الاختبار المعروفة باسم "نماذج كوردو" (Cordeau benchmark instances)، والتي يستخدمها الباحثون على نطاق واسع لقياس أداء خوارزميات التوجيه.
كانت نتائج هذه الطريقة الهجينة الجديدة مثيرة للإعجاب، لا سيالما بالنسبة للمشكلات الصغيرة والمتوسطة الحجم. ففي عدة حالات اختبار تتضمن ما يصل إلى مائة عميل وعدة مستودعات، وجد النظام حلولاً كانت ضمن بضعة بالمائة فقط من أفضل النتائج المسجلة على الإطلاق. وبالنسبة لحالة محددة تضم خمسة وسبعين عميلاً وخمسة مستودعات، حققت الطريقة فجوة قدرها 1.16 بالمائة فقط عن الحل الأفضل المعروف، مما يعني أنها كانت شبه مثالية. كما أثبت النظام أنه مستقر للغاية؛ فعندما قام الباحثون بتشغيل نفس الاختبار عدة مرات مع نقاط بداية عشوائية مختلفة، ظلت النتائج ثابتة، مع وجود تباين ضئيل جداً بين عمليات التشغيل. وهذا يشير إلى أن الطريقة موثوقة ولا تعتمد على الحظ للعثور على إجابة جيدة. ومع ذلك، كشفت الدراسة أيضاً عن المواضع التي تواجه فيها الطريقة حدودها. ففي أكبر حالة اختبار، والتي شملت مائة وستين عميلاً، اتسعت الفجوة بين الحل الجديد وأفضل حل معروف إلى حوالي 13.5 بالمائة. وأشار الباحثون إلى أنه في المشكلات الأكبر حجماً، تجعل المساحة الشاسعة للبحث من الصعب على البحث المحلي إيجاد تحسينات عميقة. وبالمثل، في الحالات التي تضم مستودعين فقط، واجهت الطة صعوبة أكبر قليلاً، ويرجع ذلك على الأرجح إلى وجود فرص أقل لتحسين الحل عن طريق إعادة توزيع العملاء بين المستودعات المختلفة.
في نهاية المطاف، يوضح هذا البحث أن تقسيم مشكلة لوجستية معقدة إلى مهمتين متميزتين — تخصيص العملاء للمستودعات ثم تخطيط المسارات — يمكن أن يكون استراتيجية فعالة للغاية. فمن خلال ترك الخوارزمية التنافسية تتولى التخصيصات الكبرى والبحث المحلي يتولى ضبط المسارات بدقة، ابتكر الباحثون نظاماً يعمل بقوة عبر مجموعة من السيناريوهات. ويؤكد هذا العمل أنه بينما يظل العثور على الحل الرياضي الأمثل لكل سيناريو ممكن أمراً بعيد المنال للمشكلات واسعة النطاق، فإن هذا النهج الهجين يقدم طريقة عملية وقوية للوصول إلى القرب من المثالية، مما يضمن عمل شبكات التوصيل بكفاءة أكبر وتكاليف أقل.
غارق في أبحاث مجالك؟
تصلك نشرة يومية بأحدث الأبحاث المطابقة لكلماتك البحثية المفتاحية — مع ملخصات تقنية، بلغتك.