Scheduling and Routing with Degradation-Triggered Job Arrivals: An Application to Forest Firefighting with an Unmanned Aerial Vehicle Fleet
تتناول هذه الورقة مشكلة الجدولة والتوجيه المتداخلة لإطفاء حرائق الغابات باستخدام الطائرات بدون طيار، حيث يؤدي تأخير التدخل إلى ظهور مهام جديدة نتيجة انتشار الحريق، وذلك عبر تطوير نماذج برمجة مختلطة الأعداد ونماذج هجينة لتعظيم القيمة المستبقاة في المناطق المهددة.
المؤلفون الأصليون:Erdi Dasdemir, Esther Jose, Rajan Batta
في عالم الاستجابة للكوارث عالي المخاطر، غالبًا ما يكون التوقيت هو الفارق بين حادثة يمكن احتواؤها وكارثة محققة. وينطبق هذا بشكل خاص على حرائق الغابات، حيث لا يكون سلوك الحريق ثابتًا، بل هو كيان حي يتنفس ويتغير في اللحظة التي يُترك فيها بمفرده. فإذا لم يتم التعامل مع الحريق فورًا، فإنه لا يكتفي بالبقاء في مكانه؛ بل يكبر، ويستهلك المزيد من القيمة، وينتشر في النهاية إلى مناطق جديدة، مما يخلق حالات طوارئ جديدة تتطلب الاهتمام. وهذا يخلق لغزًا معقدًا للقادة الميدانيين: إذ يتعين عليهم تقرير ليس فقط أين يرسلون مواردهم، ولكن أيضًا متى، مع علمهم بأن كل ثانية من التأخير تغير طبيعة المشكلة نفسها. ويتمثل التحدي في الموازنة بين الحاجة الملحة لمكافحة الحريق وبين الضرورة الاستراتيجية لمنع اشتعال حرائق جديدة قريبة، كل ذلك مع إدارة أسطول من المركبات التي يجب أن تعيد التزود بالوقود لمواصلة العمل.
لقد تصدى فريق من الباحثين لهذه المشكلة المعقدة عبر تطوير طريقة جديدة لجدولة وتوجيه الطائرات بدون طيار (الدرونز) لإطفاء حرائق الغابات. ويركز عملهم على واقع محدد وصعب: وهو الحرائق التي تسبب حرائق أخرى. في نموذجهم، يبدأ حريق في موقع محدد مع نافذة زمنية محددة لإخماده. وإذا تُرك الحريق يحترق لفترة طويلة جدًا، فإنه ينمو حتى يصل إلى حجم حرج، وعند هذه النقطة ينتشر طبيعيًا إلى المناطق المجاورة، مما يخلق مهامًا جديدة يجب مكافحتها. والهدف ليس مجرد إخماد النيران الأولية، بل التدخل في وقت مبكر بما يكفي لوقف هذا التفاعل المتسلسل، وبالتالي الحفاظ على قيمة الأرض والمنازل والبنية التحتية في المنطقة. وقد أنشأ الباحثون إطارًا رياضيًا يعمل كمحرك لاتخاذ القرار، يقوم بحساب المسار الأمثل لأسطول من الطائرات بدون طيار لتعظيم مقدار القيمة التي يتم إنقاذها عبر منطقة غابية بأكملة.
اختبر الباحثون نهجهم باستخدام نموذج حاسوبي يحاكي شبكة غابة، حيث تمثل كل مربعة قطعة من الأرض لها قيمتها الخاصة وإمكانية انتشار الحريق فيها. وقد برمجوا النموذج ليفهم وجوب زيارة الطائرة بدون طيار لمصدر مياه لإعادة ملء خزانها بين المهمات، مما يضيف طبقة أخرى من التعقيد إلى عملية التوجيه. وفي عمليات المحاكاة الخاصة بهم، أدخلوا سيناريوهات متنوعة، بما في ذلك أعداد مختلفة من الطائرات بدون طيار، وسرعات طيران متفاوتة، وأنماط مختلفة من الحرائق الأولية. ووجدوا أن طريقتهم الجديدة، التي تجمع بين الحساب الدقيق وعملية تحسين مرنة وخطوة بخطوة، كانت أسرع وأكثر موثوقية من الطرق السابقة. وبينما كانت النماذج القديمة غالبًا ما تعاني لإيجاد الحل الأفضل ضمن وقت معقول، خاصة عندما يكون عدد الحرائق مرتفعًا، نجح النهج الجديد باستمرار في إيجال خطط عالية الجودة بسرعة. لقد نجح في التنقل بين المقايضة بين الاندفاع نحو أقرب حريق وبين الانتظار لمنع احتراق منطقة أكثر قيمة، مما ضمن استخدام الطائرات بدون طيار حيث يمكنها إنقاذ أكبر قدر من القيمة.
ولإثبات عملية عملهم، طبق الفريق نموذجهم على سيناريوهات واقعية مستمدة من التضاريس المتنوعة لولاية كاليفورنيا. فقد أنشأوا خرائط رقمية تمثل أنواعًا مختلفة من التضاريس، من المناطق الحضرية المكتظة بالسكان ذات الغطاء النباتي الكثيف إلى المناطق النائية غير المأهولة. وفي هذه المحاكاة، نجح النموذج في توجيه أساطيل من الطائرات بدون طيار لإخماد الحرائق ومنع انتشارها إلى المناطق الحرجة. وأظهرت النتائج أنه باستخدام هذا الجدولة المثلى، ظلت القيمة الإجمالية للمنطقة المحمية أعلى بكثير مقارنة بالجهود الأقل تنسيقًا. كما أتاح الباحثون كودهم البرمجي للجمهور، مما يسمح للخبراء الآخرين باختبار النظام ببياناتهم الخاصة وتطوير الاستراتيجيات للنشر في العالم الحقيقي. ويقدم هذا العمل أداة ملموسة لمديري الكوارث، توفر وسيلة لتحويل الطبيعة الفوضوية والمتسارعة لحرائق الغابات إلى مجموعة قابلة للإدارة من القرارات التي يمكن أن تنقذ الأرواح والممتلكات.
ملخص تقني: الجدولة والتوجيه مع وصول المهام الناجم عن التدهور
تعريف المشكلة تتناول هذه الورقة نوعًا جديدًا من مشكلة المركبات المتكاملة (VRP) ومشكلة جدولة المهام (JSP)، والتي تُسمى "الجدولة والتوجيه مع وصول المهام الناجم عن التدهور". يكمن التحدي الجوهري في شبكة من مواقع المهام المحتملة حيث لا تظهر المهام الجديدة بشكل عشوائي، بل يتم تحفيزها ديناميكيًا من خلال تدهور المهام الحالية.
في السياق المحدد لإطفاء حرائق الغابات جوًا باستخدام الطائرات بدون طيار (UAVs)، يتم تعريف المشكلة كما يلي:
هيكل الشبكة: رسم بياني قائم على الشبكة (grid-based graph) يمثل منطقة غابات تحتوي على عقد معرضة للحرائق، وعقد مقاومة للحرائق (حواجز)، ومصادر مياه، وقاعدة للطائرات بدون طيار.
ديناميكيات المهام: لكل منطقة مشتعلة (مهمة) نافذة زمنية محددة. خلال هذه النافذة، ينمو الحريق (يتدهور في الحجم) وتتدهور قيمة العقدة.
الوصول الناجم عن التدهور: إذا لم يتم إخماد الحريق قبل وصوله إلى عتبة حجم حرجة (tm)، فإنه ينتشر إلى العقد المجاورة، مما يؤدي إلى تحفيز وصول مهام جديدة. وهذا يخلق تفاعلًا ثنائي الاتجاه: تحدد قرارات التوجيه والجدولة متى تنتشر الحرائق (وبالتالي متى تصل المهام الجديدة)، بينما يؤثر وصول المهام الجديدة على قرارات التوجيه اللاحقة.
الهدف: تعظيم إجمالي القيمة المتبقية للمنطقة. يتضمن ذلك إخماد الحرائق قبل أن تتسبب في فقدان القيمة الكلية ومنع انتشار الحرائق إلى العقد المجاورة ذات القيمة العالية. يأخذ النموذج في الاعتبار قيود الطائرات بدون طيار، بما في ذلك الحاجة إلى زيارة موارد المياه لإعادة ملء الخزانات بين المهام ومتطلبات إطلاق حمولات المياه الكاملة بغضًا عن حجم الحريق.
المنهجية طوّر المؤلفون إطار عمل للتحسين الرياضي يتكون من نموذجين أساسيين:
نموذج البرمجة الخطية المختلطة الدقيق (EM):
يصيغ نموذج EM المشكلة باستخدام متغيرات ثنائية لتوجيه المركبات، واختيار المهام، ومنطق انتشار الحريق، إلى جانب متغيرات مستمرة للوقت والقيمة. بإدراج تقريبات خطية لنمو حجم الحريق وتدهور القيمة لتحقيق التوازن بين الواقعية والقدرة على المعالجة الحسابية.
يربط النموذج صراحةً بين قرارات الجدولة (أوقات الوصول) ومنطق تقدم الحريق. يستخدم قيود "Big-M" لنمذجة أربع حالات متميزة لانتشار الحريق بناءً على ما إذا كانت العقدة تحتوي على حريق، وما إذا كانت المركبة قد وصلت، وتوقيت هذا الوصول بالنسبة لمرحلة النمو الحرجة للحريق.
دالة الهدف تعظم مجموع قيم العقد التي تم جمعها، مع فرض عقوبة على الوقت المستغرق للعودة إلى القاعدة.
النموذج الهجين: نموذج تأجيل إعادة الملء الموجه بالنموذج الدقيق (E-RDM):
إدراكًا بأن نموذج EM يعاني من صعوبة في التوسع بسبب ضعف استرخاء البرمجة الخطية (LP) وتعقيد قيود إعادة ملء المياه، اقترح المؤلفون نهجًا هجينًا.
نموذج EM لتأجيل إعادة الملء (RDM): نسخة مسترخية من نموذج EM تستبعد القيود المحددة التي تتطلب زيارة موارد المياه بين المهام المتتالية وقيود الربط الزمني المرتبطة بها.
الفرع والقطع مع القيود المؤجلة (Branch-and-Cut with Deferred Constraints): يقوم خوارزمية E-RDM أولاً بحل RDM لتوليد حلول عالية الجودة. بعد ذلك، يستخدم إطار عمل "الفرع والقطع" مع استدعاء للقيود المؤجلة. إذا كان الحل ينتهك قيود إعادة ملء المياه أو قيود الربط الزمني المستبعدة، يتم إضافة القيود المقابلة ديناميكيًا كـ "قطع" (cuts).
استراتيجية مرحلتين: تخصص الخوارزمية جزءًا من إجمالي الوقت المتاح لحل نموذج EM الكامل (لإيجاد الحلول المثلى بسرعة إن أمكن) والجزء المتبقي لنموذج RDM مع توليد القيود الديناميكي (لتحسين الحدود والتعامل مع الحالات الأكبر).
المساهمات الرئيسية حددت الورقة ثلاث مساهمات رئيسية:
التقدم النظري: قدمت مفهوم وصول المهام الناجم عن التدهور إلى أدبيات الجدولة والتوجيه. على عكس نماذج VRP الديناميكية القياسية حيث يكون الوصول عشوائيًا أو مستقلًا عن القرارات، يتميز هذا النموذج بتفاعل ثنائي الاتجاه حيث تؤثر القرارات مباشرة على وصول المهام الجديدة.
تطبيق إدارة الكوارث: توفر نموذجًا لاتخاذ القرار التوجيهي لإطفاء حرائق الغابات جوًا. يدمج النموذج اللوجستيات (التوجيه، إعادة الملء) مع التخطيط العملياتي (توقيت إخماد الحريق) لمعالجة "مشكلة حماية الأصول" (APP) في سيناريوهات حرائق الغابات.
قابلية التكرار والأدوات: طور المؤلفون واجهة برمجية (قائمة على الجداول البيانات) مرتبطة ببرمجية Python/Gurobi الخاصة بهم، مما يسمح للممارسين بتوليد حالات المشكلة وإيجاد الحلول المثلى دون التعامل مع الكود الخام. ويتم مشاركة قاعدة الكود عبر GitHub لتسهيل قابلية التكرار.
النتائج أُجريت التجارب الحسابية على محطة عمل ذات نواتين و28 خيط معالجة باستخدام Gurobi Optimizer 10.0.1.
مقارنة الأداء: تفوق نموذج E-RDM الهجين بشكل كبير على نموذج EM الدقيق. بينما فشل EM غالبًا في إثبات المثالية ضمن الحد الزمني (3,600 ثانية) للحالات ذات أعداد المهام المرتفعة أو القدرة المحدودة للأسطول، حقق E-RDM باستمرار فجوة مثالية أقل من 3% عبر 1,260 تشغيل.
القابلية للتوسع: أظهر نموذج E-RDM متانة عبر أحجام الأساطيل المتفاوتة (2 مقابل 4 طائرات بدون طيار) والسرعات (60 مقابل 120 كم/ساعة). وقد حل الحالات بمتوسط وقت تشغيل قدره 47 ثانية.
تأثير وصول المهام: أكدت الدراسة أنه مع زيادة عدد المهام الواصلة (المدفوعة بالحرائق الأولية ومعدلات الانتشار)، تزداد الصعوبة الحسابية لنموذج EM بشكل حاد. وقد نجح E-RDM في التخفيف من ذلك بفعالية من خلال الاستفادة من الصيغة المسترخية لتوجيه عملية البحث.
دراسة حالة: أظهرت دراسة حالة قائمة على خصائص حرائق الغابات في كاليفورنيا (باستخدام بيانات تصنيف الأراضي SILVIS) قدرة النموذج على التعامل مع المناظر الطبيعية المتنوعة، من الواجهات الحضرية عالية الكثافة إلى المناطق النباتية غير المأهولة. نجح النموذج في توليد خطط إخماد تعظم الاحتفاظ بالقيمة عبر سبعة أنواع مختلفة من السيناريوهات.
الأهمية والادعاءات تضع الورقة عملها كتطبيق عملي للمثل القائل "درهم وقاية خير من قنطار علاج"، مؤكدة أن التدخل المبكر والمنسق جيدًا يمنع الضرر غير المتناسب. يدعي المؤلفون أن نموذجهم يقدم تحسنًا كبيرًا عن النهج الحالية من خلال نمذجة الرابط السببي بين تأخير الإخماد وتوليد مهام حريق جديدة (الحرائق الناتجة عن الانتشار).
لا تدعي الدراسة حل الفيزياء المستمرة لسلوك الحريق، بل تسعى لتحقيق توازن بين الواقعية والقدرة على المعالجة باستخدام التقريبات الخطية لانتشار الحريق وتدهور القيمة. تكمن الأهمية في توفير نظام دعم قرار يمكنه التعامل مع الطبيعة الديناميكية والمترابطة لإخماد حرائق الغابات، حيث يمكن أن يؤدي تأخير مهمة واحدة إلى زيادة عبء العمل بشكل أسّي وتقليل إجمالي القيمة للمنطقة المحمية. ويخلص المؤلفون إلى أن نهجهم الهجين يقدم مسارًا قابلاً للتطبيق لحل مشاكل لوجستيات الاستجابة للكوارث المعقدة في العالم الحقيقي والتي كانت سابقًا مستعصية حسابيًا.