An Enhanced Large Neighborhood Search Approach for the Capacitated Facility Location Problem with Incompatible Customers
تقترح هذه الورقة طريقة بحث الجوار الكبير المحسنة التي تجمع بين مشغلات التدمير الهجينة وحلال إصلاح دقيق للتفوق على المنهجيات الاستدلالية المتطورة الحالية في حل مسألة تحديد مواقع المرافق ذات السعة المحدودة مع العملاء غير المتوافقين، محققةً حلولاً هي الأفضل لجميع نماذج الاختبار.
المؤلفون الأصليون:Ida Gjergji, Lucas Kletzander, Nysret Musliu, Andrea Schaerf
تخيل أنك مدير لشركة توصيل ضخمة. لديك قائمة من العملاء الذين يحتاجون إلى طرود، وقائمة من المستودعات المحتملة حيث يمكنك تخزين تلك الطرود. هدفك بسيط: افتتاح المستودعات الصحيحة وإرسال الطرود المناسبة إلى الأشخاص المناسبين بحيث تنفق أقل قدر ممكن من المال على تكاليف الافتتاح ورسوم الشحن.
هذه هي "مسألة تحديد موقع المرافق" الكلاسيكية. ولكن في هذه الورقة البحثية تحديداً، أضاف المؤلفون التواءً صعباً: عدم توافق العملاء.
الالتواء: "الأعداء" في الحي
تخيل أن بعض عملائك هم شركات متنافسة (مثل شركتي مياه غازية متنافستين) أو أنهم يتعاملون مع مواد خطرة لا يمكن خلطها. لا يمكنك وضع هؤلاء العملاء "الأعداء" في نفس المستودع؛ فإذا فعلت ذلك، ستحدث كارثة. هذا يضيف طبقة من التعقيد تجعل العثور على الحل المثالي أمراً صعباً للغاية، مثل محاولة حل أحجية (بازل) ضخمة ومتغيرة، حيث تتنافر بعض قطعها مغناطيسياً مع بعضها البعض.
الحل: البحث في "الحي الكبير"
يقترح المؤلفون طريقة جديدة لحل هذه الأحجية تسمى البحث في الجوار الكبير (Large Neighborhood Search - LNS). لفهم كيفية عملها، تخيل أنك تحاول إعادة ترتيب الأثاث في غرفة معيشة لجعلها تبدو أفضل.
مرحلة "التدمير" (صانع الفوضى): بدلاً من تحريك كرسي واحد في كل مرة، تأخذ الخوارزمية جزءاً كاملاً من الغرفة — لنقل الأريكة، والسجادة، وطاولة القهوة — وتخرجها من الباب. بلغة الورقة البحثية، هذا هو مشغل التدمير (Destroy Operator). لقد ابتكروا ثلاث طرق خاصة لاختيار أي "أثاث" (العملاء والمستودعات) سيتم إزالته:
المرافق الأكثر تكلفة: اختيار المستودعات التي تكلف حالياً أغلى ثمن للاستخدام.
العملاء الهجين (Hybrid Customers): مزيج ذكي بين اختيار العملاء الأكثر تكلفة لخدمتهم وبين إيجاد أفضل أماكن جديدة لهم.
العشوائي: مجرد التقاط مجموعة عشوائية لإحداث نوع من التغيير.
مرحلة "الإصلاح" (المهندس المعماري الخبير): الآن لديك غرفة فوضوية بها فجوة في المنتصف. أنت لا تخمن مكان وضع الأثاث مرة أخرى؛ بل تستدعي مهندساً معمارياً فائق الذكاء (وهو محلل رياضي دقيق يسمى Guroju) لينظر فقط إلى تلك الفجوة المحددة. يكتشف المهندس أفضل طريقة لإعادة ترتيب تلك العناصر المحددة فقط لتناسب المكان تماماً، مع احترام قواعد "الأعداء". هذا هو مشغل الإصلاح (Repair Operator).
الدورة (The Loop): تكرر الحوسبة هذه العملية آلاف المرات: تكسير جزء من الحل، ثم استدعاء الخبير لإصلاح ذلك الجزء المحدد، ثم معرفة ما إذا كان شكل الغرفة بأكملها قد أصبح أفضل. إذا كان الأمر كذلك، احتفظ بالتغيير. إذا لم يكن كذلك، جرب كسر قطعة مختلفة في المرة القادمة.
لماذا هذه الورقة مميزة؟
لم يكتف المؤلفون ببناء هذه الآلة فحسب، بل قاموا بضبطها بدقة مثل سيارة سباق.
خط البداية: أدركوا أن البدء بخطة أولية جيدة أمر بالغ الأهمية. فقد اختبروا طرقاً مختلفة لإعداد "الغرفة" الأولى ووجدوا أن البدء باستراتيجية "جشعة" (Greedy) محددة منحهم انطلاقة قوية.
قواعد القبول: قاموا بتعديل القواعد الخاصة بمتى يتم قبول ترتيب جديد. قرروا السماح بقبول الترتيبات "المتساوية" (وليس فقط الأفضل) أحياناً. يساعد هذا الخوارزمية على الهروب من "الفخاخ المحلية" — وهي المواقف التي تبدو فيها الغرفة جيدة، لكنها في الواقع عالقة في زاوية ولا يمكن أن تتحسن دون عملية تغيير كبيرة.
النتائج: اختبروا طريقتهم على مجموعتين ضخمتين من البيانات (بعضها يحتوي على ما يصل إلى 3,000 مستودع و8,000 عميل). كانت النتائج مبهرة: تفوقت طريقتهم على جميع الطرق السابقة "الأحدث في المجال" (state-of-the-art). في الواقع، في كل حالة اختبار حاولوا فيها، وجدوا أفضل حل جديد، مما وفر المال مقارنة بكل ما هو معروف سابقاً.
الخلاصة
فكر في هذه الورقة البحثية كأنها تقدم فريقاً جديداً وعالي الكفاءة من المرممين. الطرق السابقة كانت تشبه أشخاصاً يحاولون إصلاح منزل عن طريق تحريك طوبة واحدة في كل مرة. أما هذه الطريقة الجديدة، فتأخذ جداراً كاملاً، وتستدعي بناءً ماهراً لإعادة تصميم ذلك الجدار بدقة، ثم تعيده مكانه. ومن خلال القيام بذلك مراراً وتكراراً، تمكنوا من بناء "منزل" (خطة لوجستية) أرخص وأكثر كفاءة من أي خطة أخرى تم العثور عليها من قبل، حتى في أكثر السيناريوهات تعقيداً واحتواءً على "أعداء".
ملخص تقني: نهج بحث الجوار الكبير المحسن لمشكلة تحديد مواقع المرافق ذات السعة مع عدم توافق العملاء
تعريف المشكلة تتناول هذه الورقة مشكلة تحديد مواقع المرافق ذات السعة متعددة المصادر مع عدم توافق العملاء (MS-CFLP-CI). يوسع هذا المتغير مشكلة MS-CFLP الكلاسيكية من خلال إدخال مجموعة من أزواج العملاء غير المتوافقين (I) الذين لا يمكن خدمتهم من قبل نفس المرفق. تتضمن المشكلة تحديد أي المرافق سيتم فتحها (مما يتسبب في تكاليف فتح fj) وكيفية توزيع طلب العملاء (di) بين المرافق المفتوحة (مما يتسبب في تكاليف شحن cij) لتقليل التكلفة الإجمالية. يجب أن يلبي الحل قيود سعة المرافق (sj)، ويلبي طلب العملاء بالكامل، ويضمن عدم مشاركة أي اثنين من العملاء غير المتوافقين لنفس المرفق. إن وجود قيود عدم التوافق يجعل المسألة الفرعية لإيجاد التوريد الأمثل من المرافق المفتوحة مسألة صعبة (NP-hard)، حتى عندما تكون مجموعة المرافق المفتوحة ثابتة.
المنهجية يقترح المؤلفون إطار عمل للبحث عن الجوار الكبير (LNS) لحل مشكلة MS-CFLP-CI. يعتمد جوهر النهج على تدمير جزء من الحل الحالي بشكل متكرر وإصلاحه باستخدام برنامج حل البرمجة الخطية المختلطة (MIP) الدقيق (Gurobi).
تمثيل الحل: يتم تمثيل الحلول كمصفوفات من الكميات المشحونة، مدعومة بهياكل بيانات مساعدة تتبع المرافق المفتوحة/المغلقة والعملاء المعينين.
الحل الأولي: يقوم نموذج استدلالي ببناء حل أولي عن طريق فرز المرافق حسب تكلفة الفتح، واختيار عدد كافٍ لتلبية الطلب الإجمالي، وإضافة عدد محدد من المرافق الإضافية (k=5) للتعامل مع عدم التوافق. يتم تعيين العملاء بناءً على استراتيجية موحدة.
عوامل التدمير (Destroy Operators): يقدم البحث ثلاثة عوامل تدمير مبتكرة مصممة خصيصًا لقيود عدم التوافق:
المرافق الأرخص (CF): يختار مرفقًا عشوائيًا وعملائه، ثم يحدد المرافق المفتوحة الأخرى التي تقدم أقل متوسط تكلفة شحن لمجموعة العملاء المحددة تلك.
العملاء الهجين (HC): وهو إعادة دمج لاستراتيجيتين. يختار مرفقًا عشوائيًا وعملائه، ثم يحدد "العملاء الأرخص" (الذين لديهم تكاليف شحن منخفضة للمرفق) و"العملاء الأغلى" (الذين لديهم تكاليف شحن عالية). ثم يختار مرافق إضافية تقدم أفضل خدمة لهذه المجموعات الفرعية المحددة من العملاء.
المرافق المغلقة: يتم تضمين كل من المرافق المغلقة العشوائية وتلك التي لديها مقياس التكلفة الأدنى (Qg) في المسألة الفرعية لاستكشاف فتح مرافق جديدة.
عامل الإصلاح: يتم حل المسألة الفرية المحددة بالعناصر المدمرة بدقة باستخدام Gurobi. ولإدارة وقت الحوسبة، يتضمن مرحلة الإصلاح قيدًا يحد من عدد المرافق المفتوحة حديثًا إلى مرافق أكثر بمقدار اثنين فقط مما هو مشارك حاليًا في المسألة الفرعية. يتم توفير قيمة قطع (تكلفة المسألة الفرعية الحالية) للمحلل لتسريع التقارب.
التكوين والضبط: يستخدم المؤلفون أداة irace للضبط القائم على الميزات، حيث يتم ضبط معلمات مثل حجم المسألة الفرعية (ν) بناءً على حجم النموذج (تحديدًا التمييز بين النماذج التي تحتوي على ≤700 و >700 مرفق). يجمع الخوارزم النهائي، المسمى LNSinit,accept، بين عوامل التدمير المقترحة وهيكل حل أولي محسّن ومعيار قبول يسمح بقبول الحلول ذات التكلفة المتساوية، مما يسهل الهروب من الحلول المحلية المثلى.
المساهمات الرئيسية
إطار عمل خوارزمي مبتكر: هذا هو التطبيق الأول للبحث عن الجوار الكبير على مشكلة MS-CFLP-CI.
عوامل متخصصة: تصميم عوامل تدمير (CF و HC) تأخذ في الاعتبار صراحةً قيود عدم التوافق، متجاوزةً بذلك معايير تحديد المواقع القياسية للمرافق.
إصلاح هجين دقيق/استدلالي: دمج برنامج حل MIP دقيق داخل مرحلة الإصلاح، مع تحسينه بقيود محددة لموازنة جودة الحل ووقت التشغيل.
تحليل صارم: دراسة استئصال شاملة وتحليل إحصائي (باستخدام اختبارات Friedman و Nemenyi) لتقييم تأثير المكونات الفردية (التهيئة، معايير القبول، الأوزان التكيفية).
قياس مرجعي واسع النطاق: التقييم على مجموعتي بيانات كبيرتين (wlp و cflp-ci) تحتويان على ما يصل إلى 3,000 مرفق و 8,000 عميل.
النتائج التجريبية تم اختبار طريقة LNSinit,accept المقترحة مقابل أحدث الأساليب الاستدلالية (metaheuristics)، بما في ذلك Multi-Start Iterated Local Search (MR-MS-ILS) القائم على MineReduce، و GRASP، و Permutation-coded Evolutionary Algorithm (PcEA)، و Multi-start Greedy (MG)، و Simulated Annealing (SA).
الأداء: تفوقت الطريقة المقترحة بشكل كبير على جميع الأساليب الموجودة في كلتا مجموعتي البيانات تحت حدين زمنيين مختلفين (10m و m ثانية).
أفضل الحلول الجديدة: وجد النهج أفضل الحلول الجديدة لجميع الـ 80 حالة عبر مجموعتي البيانات.
الدلالة الإحصائية: أكدت الاختبارات الإحصائية أن التحسينات على أفضل طريقة سابقة (SA) هي تحسينات ذات دلالة إحصائية.
القابلية للتوسع: بينما تمكنت الحلول الدقيقة (Gurobi/CPLEX) من حل الحالات التي تصل إلى 150 مرفقًا فقط للوصول إلى الحل الأمثل ضمن وقت معقول، تمكن نهج LNS من التعامل بفعالية مع حالات تصل إلى 3,000 مرفق.
تقليل الفجوة: بالنسبة لمجموعة بيانات wlp، حققت الطريقة تحسينات في الفجوة تتراوح بين -0.68% و -1.84% مقارنة بأفضل الحلول المعروفة. وبالنسبة لمجموعة بيانات cflp-ci، تراوحت التحسينات بين -0.46% و -2.09%.
الأهمية والادعاءات يزعم المؤلفون أن طريقتهم تمثل أحدث ما توصل إليه العلم (state-of-the-art) لمشكلة MS-CFLP-CI. تكمن أهمية العمل في قدرته على التعامل مع التعقيد الحسابي الناتج عن عدم توافق العملاء، والذي كافحت الأساليب الاستدلالية السابقة لتحسينه بالكامل، خاصة في الحالات الأكبر حجمًا. تؤكد الورقة أن الجمع بين عوامل التدمير المبتكرة، ومرحلة إصلاح دقيقة، وضبط خوارزمي محدد، يسمح للطريقة باستكشاف أحياء متوسطة الحجم بفعالية، وإيجاد حلول متفوقة حيث تتوقف طرق SA وغيرها عن التحسن. يشير المؤلفون بتواضع إلى أنه بينما تعد طريقتهم هي الأفضل حاليًا، فإن العمل المستقبلي يمكن أن يتضمن تحليل مساحة الحالة (Instance Space Analysis) لفهم مدى صعوبة الحالات بشكل أفضل وتوسيع النهج ليشمل متغيرات أخرى لتحديد مواقع المرافق.