• 0
عماد حمدي احمد

حل مشكلة اضطراب جدول مواعيد الرحلات الجوية باستخدام ال Meta-heuristics

سؤال

السلام عليكم ورحمة الله

اخوانى الافاضل بارك الله فيكم

كنت قد قمت بقراءة وتقديم بحثا عن احدى تطبيقات طرق الذكاء الاصطناعى فى مجال الرحلات الجوية , وذلك ضمن انشطة المعمل الذى ادرس به حاليا. والحمد لله قمت بتقديم وشرح البحث بطريقه نوعا ما جيدة. ولأنى اشعر ان الموضوع شيق وظريف :) سأحاول ان اضع ملخص عن هذا البحث هنا فى منتدى طرق الذكاء الاصطناعى عله يكون مفيد للبعض.

فى الحقيقة كنت اريدترجمة البحث كاملا , ولكنى تراجعت لما شعرت ان هذا سيحتاج منى مجهود كثير قد لا اقدر عليه , وربما سيغرق القارئ فى تفاصيل كثيرة غير حيوية بالنسبة له , ولذلك آثرت ان اقوم بتقديم ملخص سريع عن البحث وما يتناوله. وكلمة ملخص سريع هنا , لا تعنى عدة اسطر teeth_smile.gif ولكن تعنى عرض الفكرة بشكل عام بحيث لا نخل بالمضمون ولا نغرق فىالتفاصيل الدقيقة.

سأقوم إن شاء الله تعالى بعرض البحث على صورة اربعة مشاركات متتالية (بخلاف الحالية) وستكون المشاركات مقسمة بالشكل التالى

1) مقدمه عن المشكلة محل الدراسة.

2) توصيف المشكلة علميا وتوضيح ماهية الحلول التى نبحث عنها.

3) تقديم سريع لطرق الذكاء الإصطناعى المستخدمه فى البحث.

4) مناقشة النتائج العددية التى حصل عليها الباحث.

ولكننى للأسف لم انتهى من الترجمة لكل المشاركات بعد , ولكى الزم نفسى بإنهاء هذا الامر ان شاء الله , فسأقوم بوضع المشاركات تباعا عندما انتهى منها.

وحتى نترك المشاركات فى هذا الموضوع مترابطه ومتصله , سأقوم بفتح موضوع اخر لتلقى الأسئلة والإستفسارات والنقاشات ان شاء الله تعالى.

البحث الأصلي: مشكلة اضطراب جدول مواعيد الرحلات الجوية.pdf

والأن لننطلق الى اول مشاركة بعون الله. بالله التوفيق ,,,

تم تعديل بواسطه عماد حمدي احمد
5

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه

4 إجابة على هذا السؤال .

  • 0

حل مشكلة اضطراب جدول مواعيد الرحلات الجوية باستخدام الـ Meta-Heuristics

Solving theflight perturbation problem with meta-heuristics

Tobias Andersson

Journal of Heuristics (2006) 12: 37–53

الكلمات المفتاحية:

Aircraft recovery, Irregular operations, Operational airline scheduling, Simulated annealing, Tabusearch and Path relinking

================================================

مقـــدمــــــــــة:

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

فى مثل هذه الحالات , تلجأ شركات الطيران الى اتخاذ بعض الإجراءات لعلاج هذا الإضطراب ولتقليل الأثار السلبية المترتبة عليه بأقل التكاليف الممكنه. وغالبا تتمثل هذه الإجراءات فى بعض او كل الخيارات التالية

1) تأجيل مواعيد بعض الرحلات: لو كان التأجيل محدود ومقبول.

2) إلغاء بعض الرحلات: وإعادة توزيع المسافرين على رحلات جديدة.

3) عمل تبديل بين بعض الطائرات من نفس النوع: بحيث تؤدى الطائرة B الرحلة الجوية بدلا عن الطائرة A.

4) عمل تبديل بين بعض الطائرات من انواع مختلفه: وهنا يجب ان تكون الطائرة البديله قادرة على استيعاب عدد المسافرين على الطائرة الأصلية.

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

1) مشكلة إضطراب جدول مواعيد الرحلات الجوية: وهى العصب الأساسى لهذا البحث.

2) مشكلة إسترضاء المسافر: حيث ان المسافر سيتأثر بشكل مباشر بأى تأخير او إلغاء للرحلات. وبالتالى على الشركة ان تحاول اعادة توزيع وتخصيص رحلات جديدة للمسافرين المتضررين , وربما تضطر ان تدفع لهم بعض التعويضات لإسترضائهم.

3) مشكلة إضطراب جدول طاقم الطائرة: لكل طاقم يعمل على رحلة ما جدول خاص به , بحيث انه سينتقل بعد الرحلة A الى رحلة اخرى B وهكذا , وربما تكون على نفس الطائرة او طائرة اخرى. وبالتالى اى اضطراب فى جدول مواعيد الرحلات , سيؤثر بشكل مباشر على جدول مواعيد طاقم الطائرة , وعلى الشركة ان تجد جدول بديل للطاقم المتضرر.

4) مشكلة جدول الصيانة الدورى للطائرات: عند تخصيص طائرة بديلة لتنفيذ رحلة جوية بدلا عن الطائرة الاصلية , فالطبيعى ان لهذه الطائرة جدول صيانه محدد حسب جدول رحلاتها الاصلى , وبعد التعديل الجديد ستحتاج الى تعديل جدول الصيانه الخاصة بها.

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

يرجى وضع تعليقاتكم واستفساراتكم على الرابط التالى هــــــــــــــــنا

يتــــــــــــبع إن شـــاء الله تعـــالى ,,,

===============

تم تعديل بواسطه عماد حمدي احمد
3

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

2) توصيف المسألة وماهية الحل المطلوب:

كما ذكرنا من قبل , فإن المشكلة لدينا هنا , انه لدينا جدول مواعيد للرحلات الجوية التابعة لشركة طيران معينة , وهذا الجدول موضوع بعناية ودقة عالية. ولكن لسبب ما – مثل تعطل او تأخير طائرةاو اكثر - حدث اضطراب لهذا الجدول. والمطلوب الان ايجاد حل سريع لهذه المشكلة , وذلك بتوليد جدول جديد يعمل مؤقتا كبديل عن الجدول الأصلى حتى استقرار الامور. والأن الى مزيد من الإيضاح حول خصائص الحل (الجدول) المطلوب:

1) يجب ان يتم تحديد زمن بداية تطبيق الحل الجديد , وتسمى هنا بــ "وقت البدأ".

2) الجدول الجديد سيتم تطبيقه لمدة محددة تسمى "مدة التنفيذ"

3) عند انتهاء مدة التنفيذ سننتقل الى العمل بالجدول الأصلى , وتسمى هذه اللحظة بـ "وقت الانتهاء".

كما هو واضح من النقاط السابقة , فإن الجدول الجديد , سيكون محدد بمدة معينة وبعدها يجب الرجوع الى الجدول الأصلى لأنه موضوع بعناية ودقة اعلى. وكما اشرنا سابقا فإن الإجراءات المتاحةلدينا لتوليد الجدول الجديد هى:

1) تأجيل مواعيد بعض الرحلات delay.

2) الغاء بعض الرحلات cancel.

3) عمل تبديل بين الطائرات من نفس النوع swap.

4) عمل تبديل بين الطائرات من انواع مختلفه , مع التأكد من سماحية سعة كلطائرة لعدد المسافرين عليها swap-f.

ويمكننا الأن بسهولة استنتاج الخصائص الجيدة التى يجب ان تتوفر فى الجدول الجديد المقترح وهى:

1) يجب الحصول على الجدول الجديد فى اسرع وقت ممكن (اشار بعض الباحثين الى انه يجب ان يكون اقل من ثلاث دقائق).

2) يجب ان يتم تطبيق الجدول الجديد لفترة محددة (مدة التنفيذ).

3) يجب ان يتوافق الجدول الجديد تماما مع الجدول الأصلى عند "وقت الإنتهاء" لضمان العودة بسلام للجدول الأصلى.

4) يجب ان يتم بناء الجدول الجديد بأقل عدد من التغيرات (الإجراءات) وذلك لتخفيض التكلفة.

والأن كما رأينا , فإن المفاضلة بين الحلول المقترحة ستتم على حسب التكلفة. وبالتالى الجدول الذى يعالج المشكلة بأقل تكلفة ممكنه اى اقل عدد تغييرات ممكن , سيكون هو الجدول صاحب الحظ الأوفر فى الاختيار. عامة لحساب تكلفة اى حل مقترح , فإنه توجدطريقتين

1) حساب التكلفة الفعلى:

2) استخدام طريقة الأوزان:

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

اما بالنسبة لإستخدام فكرة "الأوزان" فهى تعنى ببساطه , انه يمكن للشركة وضع اولويات معينة (اوزان) للإجراءات المتاحة. بمعنى انه لو كانت الشركة تفضل تأخير ميعاد الرحلة عن إلغاءها , يمكنها وضع "الوزن 1" مثلا للتأخير "والوزن 5" للألغاء ومثلا "الوزن 100" للتبديل وهكذا. ولحساب التكلفه فى هذه الحالة فنقوم بالأتى:

1) فى حالة تأخير الرحلة ستكون التكلفه هو حاصل ضرب عدد المسافرين فى عدد دقائق التأخير فى وزن التأخير.

2) اما فى حالة الإلغاء سيتم حساب التكلفة لتكون حاصل ضرب عدد المسافرين فى وزن الإلغاء.

3) وأخيرا فى حالة التبديل , ستكون التكلفه عبارة عن وزن التبديل نفسه (لأن المسافر غير متضرر فى هذه الحالة).

وهنا فى هذا البحث سيتم استخدام فكرة الأوزان لحساب التكلفه ان شاء الله , ومن ثم يمكننا معرفة اى الحلول المقترحة يمكننا اختيارة.

ما معنى كلمة"حل" او "جدول مقترح"؟

المعنى ببساطه هو ان كل شركة طيران لديها عدد محدد من الطائرات , وتتعامل مع عدد محدد من المطارات. ومعروف ان كل طائرة ستقوم بتنفيذ عدد محدد من الرحلات المتتابعة , بحيث تقوم الطائرة بتنفيذ الرحلة الاولى من المطار A الىالمطار B ومن ثم تقوم بتنفيذ الرحلةالثانية من المطار B الى المطار C وتستمر هكذا تنفذ الرحلات المخططه لها بشكل تتابعى. وبتجميع كل هذه الرحلات بشكل تتابعى لطائرة محددة X , سنحصل على المسار الخاص بهذه الطائرة X. وبتجميع كل هذه المسارات لجميع الطائرات التابعة للشركة سنحصل على جدول مواعيد الرحلات الخاص بهذه الشركة. وهذا ما نسميه هنا "حلا للمسألة". فى الشكل التالى يمكننا تخيل الوضع بالنظر الى مسار الطائرة X بالازرق , ومسار الطائرة Y بالاحمر.

post-52814-1261660660266_thumb.jpg

مثال لمسار طائرتين

وكما اتفقنا سابقا , فإن هدفنا هو فى حالة تلقى اى معلومات تفيد بتعطل او تأخر طائرة ما , فأننا يجب ان نقوم بتوليد جدول جديد يعمل لمدة محددة بديلا عن الجدول الاصلى وبأقل تكاليف ممكنة. لكن احيانا يكون من المفيد تقديم عدة حلول (عدة جداول) للمستخدم الذى سيتخذ القرار , فربما تكون عنده معايير اخرى لم تأخذ فى الحسبان عن توليد الجدول الجديد هنا. وبتقديم عدة حلول للمستخدم فإن هذا يعطيه سماحية اكثر فى الاختيار وحرية حركة اكثر. ولكن يجب الا يكون احد هذه الحلول -المقدمه للمستخدم- متغلب على الاخرين. بمعنى ان مجموعة الحلول يجب ان تكون جميعها حلول جيده ومتقاربة فى نسبة التكاليف , ولكنها مختلفه فى عدد فى عدد الاجراءات التى تم اتخاذها لكل حل.

عامة لكى نقول ان الحل I افضل من او متغلب على الحل J فأنه يجب ان يكون الحل I يحتاج تكاليف اقل من J وفى نفس الوقت عدد التغيرات التى يحتاجها لكل اجراء (تأجيل ,الغاء , تبديل) أقل من عدد التغيرات المناظرة التى يحتاجها الحل J. عندها نقول ان الحل I متغلب على الحل J. اما لو كان الحلان متقاربان فى التكاليف , وكان احدهما يستخدم عدد تغييرات اكثر من الاخر فى احد الإجراءات (مثلا التأجيل) وعدد تغييرات اقل من الاخر فى اجراء اخر (مثلا التبديل) , فنقول ان الحلول غير متغلبة على بعضها.

هذا والله اعلى واعلم ,,,

يرجى وضع تعليقاتكم واستفساراتكم على الرابط التالى هــــــــــــــــنا

يتــــــــــــبع إن شـــاء الله تعـــالى ,,,

===============================

تم تعديل بواسطه عماد حمدي احمد
3

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0
تم تعديل بواسطه عماد حمدي احمد
7

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

he beyond freezing temperatures of deep space?

I saw something shocking on my way to work the other day. While bundled in a long

sleeved shirt, wool sweater and coat, with a Pashmina, hat and gloves, I saw a man with his

bike a the bus stop in SANDALS. He wasn’t overly well dressed for cold weather, in jeans,

t-shirt and open jacket. Now, having lived in Oregon for the past decade I have come to be

aware of what “true Oregonians” consider winter attire. This primarily consists of the

inbred belief that flip-flops are a necessity year round, and sweaters and umbrellas are for

tourists.Based on the population of Oregon, I’m probably in the minority. Although I have

come to accept that these people are just immune to cold in a way I am not, I do still think

they are crazy. I’m guessing that the good folks at UGG Australia caught wind of these

[url= http://www.oforu.com/]wow gold[/ur

people because look at what they have to offer: sandals with fleece!

There seems to be a near constant battle between modernity and history in liter

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه

من فضلك سجل دخول لتتمكن من التعليق

ستتمكن من اضافه تعليقات بعد التسجيل



سجل دخولك الان

  • يستعرض القسم حالياً   0 members

    لا يوجد أعضاء مسجلين يشاهدون هذه الصفحة .