شکل 1-1- حل مسأله ASP به روش FCFS5
شکل 2-1- فاصله ايمني بين دو سر بال23
شکل 3-1- طرح کلي الگوريتم تکاملي28
شکل 3-2- فلوچارت الگوريتم ICA33
شکل 3-3- اجزاي اجتماعي و سياسي تشکيل‌دهنده کشور35
شکل 3-4- چگونگي شکلگيري امپراطوريهاي اوليه38
شکل 3-5- شماي کلي حرکت مستعمرات به سمت امپرياليست39
شکل 3-6- حرکت واقعي مستعمرات به سمت امپرياليست40
شکل 3-7- تغيير جاي استعمارگر و مستعمره42
شکل 3-8- کل امپراطوري پس از تغيير موقعيت42
شکل 3-9- شماي کلي رقابت استعماري43
شکل 3-10-سقوط امپراطوري ضعيف47
شکل 3-11- گراف همسايگي با پنج گره49
شکل 3-12- بهبوددهنده سه‌نقطه‌اي50
شکل 3-13- فلوچارت راهکار پيشنهادي52
جدول 1-1- حداقل زمان فاصله6
جدول 4-1 نتايج مربوط به الگوريتم ERT و AATCSR براي 15 نمونه59
جدول 4-2 نتايج مربوط به الگوريتم ICA براي 15 نمونه60
جدول 4-3 نتايج مربوط به الگوريتم ترکيبي MICA و ERT براي 15 نمونه60
جدول 4-4 مقايسه نتايج مربوط به 15 پرواز60
جدول 4-5 نتايج مربوط به الگوريتم ERT و AATCSR براي 20 نمونه61
جدول 4-6 نتايج مربوط به الگوريتم ICA براي 20 نمونه61
جدول 4-7 نتايج مربوط به الگوريتم ترکيبي MICA و ERT براي 20 نمونه61
جدول 4-8 مقايسه نتايج مربوط به 20 پرواز62
جدول 4-9 نتايج مربوط به الگوريتم ERT و AATCSR براي 25 نمونه62
جدول 4-10 نتايج مربوط به الگوريتم ICA براي 25 نمونه62
جدول 4-11 نتايج مربوط به الگوريتم ترکيبي MICA و ERT براي 25 نمونه63
جدول 4-12 مقايسه نتايج مربوط به 25 پرواز63
1- مقدمه طرح پيشنهادي
1-1- مقدمه
يکي از موضوعات موردتوجه در صنعت هوانوردي، مبحث برنامهريزي فرود هواپيماهاي ورودي به فرودگاه است. با ورود هواپيماهاي مختلف به محدودهي راداري فرودگاه، مراقبين پرواز در برج مراقبت بايد ترتيب فرود هواپيماهايي که در آن لحظه در آسمان فرودگاه در حال پرواز هستند را مشخص نمايند. براي اختصاص چنين ترتيب فرودي محدوديتهاي مختلفي موردتوجه قرارميگيرد که از آن جمله مي‌توان به محدوديت جداسازي دو هواپيما اشاره نمود. اين محدوديت از ديدگاه مباحث آئروديناميک اهميت زيادي دارد و در صورت عدم رعايت آن امکان بروز حادثه براي هواپيماهاي متوالي وجود دارد.
مهمترين نتيجهي موردنظر برنامهريزي فرود هواپيماها، کمينه کردن تأخيرها است که از ايجاد هزينهي سوخت اضافه براي هواپيماها و همين‌طور ايجاد نارضايتي مسافران جلوگيري مي‌کند. ازآنجايي‌که هزينههاي مربوط به سوخت ناوگان پروازي درصد قابل‌توجهي از هزينههاي شرکت‌هاي هواپيمايي را شامل ميشود، برنامهريزي فرود هواپيماها موردتوجه شرکت‌هاي هواپيمايي و همچنين شرکت‌هاي فرودگاهي قرارگرفته است. همين امر باعث شده است که اغلب فرودگاههايي که عملکرد بهتري در خصوص مديريت ترافيک پروازي دارند، توجه شرکت‌هاي هواپيمايي بيشتري را به خود جلب کنند. از سوي ديگر، در صورت دستيابي به عملکردي مناسب در مديريت ترافيک پروازها، شرکت‌هاي فرودگاهي اين امکان را خواهند داشت که در بازه زماني ثابت، پذيراي تعداد بيشتري از هواپيما باشند.
شرکت‌هاي فرودگاهي بخشي از درآمد خود را از هزينهي اجارهي جايگاه پارک1 به دست ميآورند. هزينهي جايگاههاي پارک، بسته به امکانات آن، متغير است. امکاناتي نظير برق زميني2 و يا وروديهاي مسافري3 در قيمت جايگاه پارک تأثيرگذار هستند. در تمامي فرودگاههاي جهان دو نوع جايگاه پارک موجود است. جايگاه پارک با ورودي مسافر و جايگاه پارک دور از سالن4. جايگاه پارک با ورودي مسافر يا بانام ديگر جايگاه پارک با خرطومي اتصال، جايگاه‌هاي پارکي هستند که مسافرين يک هواپيما بدون نياز به ورود به محوطه فرودگاه به‌طور مستقيم با استفاده از يک راهرو (خرطومي اتصال) به هواپيما وارد و يا از آن خارج ميشوند.
نياز به ورود به محوطه فرودگاه به‌طور مستقيم با استفاده از يک راهرو (خرطومي اتصال) به هواپيما وارد و يا از آن خارج ميشوند؛ اما هواپيماهاي واقع در جايگاه پارک دو از سالن، براي مسافر گيري و يا پياده کردن مسافران خود نياز به سرويس اتوبوس5 دارند. از بين اين دو نوع جايگاه، جايگاه پارک با ورودي مسافر داراي قيمت بالاتري است. قيمت اين جايگاهها بدين‌صورت محاسبه ميشود که به ازاي هر مسافري که از يک هواپيما از ورودي مسافري استفاده مي‌کند مبلغي ثابت از خط هواپيمايي مربوطه دريافت ميشود که قيمت سرويس اتوبوس در مقابل آن ناچيز است. عليرغم قيمت بالاتر جايگاه پارک با ورودي مسافر، شرکت‌هاي هواپيمايي براي کسب رضايت بيشتر مسافران خود ترجيح ميدهند تا هواپيماهايشان به جايگاه پارک با ورودي مسافر تخصيص پيدا کند. جايگاه پارک با ورودي مسافر داراي يک مزيت ايمني نيز هست، با استفاده مسافرين از ورودي مسافر ديگر خطرات ناشي از حضور مسافران در محوطه فرودگاه وجود ندارد و از ايجاد اتفاقات مختلف جلوگيري ميشود.
با توجه به اينکه در هنگام عقد قرارداد خطوط هواپيمايي با فرودگاهها، خطوط هواپيمايي نميتوانند در مورد نوع جايگاه پارک خود شرايطي را اعلام کنند و نوع جايگاه پارک يک هواپيما بر عهده‌ي کنترلر فرودگاه در لحظهي فرود هواپيما است؛ بنابراين در صورت برنامهريزي صحيح مي‌توان هواپيماهاي بيشتري را به جايگاههاي پارک با ورودي مسافري اختصاص داد و از اين طريق به افزايش درآمد فرودگاه کمک کرد.
با توجه به مطالب بيان‌شده، مديريت فرودگاهها براي جذب شرکت‌هاي هواپيمايي و همين‌طور بالا بردن درآمد خود بايد بتوانند توازني بين دو موضوع کنترل ترافيک هواپيماهاي ورودي (توالي فرود هواپيماها) و تخصيص هواپيماها به وروديهاي مسافري ايجاد کنند تا بتوانند علاوه برافزايش درآمد خود، مشتريان خود (شرکت‌هاي هواپيمايي) را راضي نگه‌دارند؛ اما تنها مشکل در اين زمينه وابستگي بسيار زياد اين دو مسأله به يکديگر است. بدين معنا که هواپيماها به‌محض فرود در فرودگاه بايد جايگاه پارکي به آن‌ها تخصيص يابد و آن جايگاه پارک بايد در لحظهي فرود هواپيما مذکور خالي و آماده به خدمتدهي باشد.
اين موضوع باعث ميشود که زمان فرود هواپيماها تأثير مستقيمي در جايگاه پارک تخصيصي به يک هواپيما داشته باشد. يا به‌عبارت‌ديگر، ممکن است در بعضي از مواقع فرود يک هواپيما با تأخيري چنددقيقه‌اي باعث خالي شدن يک جايگاه پارک داراي ورودي مسافر بشود و با تخصيص اين هواپيما به همان جايگاه باعث بالا رفتن درآمد فرودگاه شد؛ اما هميشه فرودگاهها بايد در نظر داشته باشند که ميزان اين تأخير تأثيري مستقيم در رضايت شرکت‌هاي هواپيمايي دارد. در اين فصل مروري بر ادبيات اين دو موضوع داريم.

در این سایت فقط تکه هایی از این مطلب با شماره بندی انتهای صفحه درج می شود که ممکن است هنگام انتقال از فایل ورد به داخل سایت کلمات به هم بریزد یا شکل ها درج نشود

شما می توانید تکه های دیگری از این مطلب را با جستجو در همین سایت بخوانید

ولی برای دانلود فایل اصلی با فرمت ورد حاوی تمامی قسمت ها با منابع کامل

اینجا کلیک کنید

1-2- طرح موضوع
در ايالات‌متحده برآورد شده است که هزينه تأخير در پروازهاي داخلي حدود 3.5 بيليون دلار در سال ميباشد که با افزايش رقابت تجاري بين ايرلاينهاي مختلف اين هزينهها بار مالي زيادي در پي خواهد داشت؛ درنتيجه برنامهريزي و توالي پروازها به يکي از مهمترين مسائل کاري در حوزه کاري مراقبت پرواز شده است. براي مواجهه با اين معضل و در شرايطي که فرودگاه داراي چندين باند پروازي است، از الگوريتم‌هاي مختلفي استفاده ميشود. برنامهريزي پروازهاي ورودي براي چند باند پروازي تابعي از تخصيص پروازهاي ورودي به باندهاي پروازي مختلف در يک فرودگاه ميباشد به‌طوري‌که توالي ورودي پروازها و زمان فرود آن‌ها با حفظ جدايي استاندارد بين پروازها و ظرفيت موجود در فرودگاه باعث کاهش تأخيرات پروازي گردد.
براي حل مسأله ASP در فرودگاههاي داراي چند باند پروازي از راهحل سادهاي به نام اولين ورودي- اولين سرويسدهي6 (FCFS) استفاده ميشود که بر اساس زمان فرود برنامه‌ريزي‌شده7 (PLTs) در آن فرودگاه ميباشد. در شکل 1-1 مثال سادهاي از حل مسأله به روش FCFS نشان داده‌شده است
شکل 1-1- حل مسأله ASP به روش FCFS
اما در تعيين ترتيب ورود پروازها انتخاب باند مناسب فرود براي کاهش تأخير پروازي، فاصله زماني فرود8 (LTI) را در نظر ميگيرند که حداقل زمان جدايي قابل‌قبول براي دو پرواز ورودي پشت سر هم به يک باند پروازي را نشان ميدهد. اساساً LTI يک کميت تغييرپذير مي‌باشد زيرا:
1. براي حفظ ايمني پروازها لازم است که دو پرواز هم‌ارتفاع داراي حداقل جدايي افقي بر اساس نوع هواپيما و موقعيت واقعي آن‌ها باشند.
2. سرعت هر هواپيما هنگام فرود متفاوت ميباشد.
3. تسهيلات و تجهيزات هر باند پروازي، براي تعيين زمان LTI تأثيرگذار است.
جدول 1-1 نمونهاي از حداقل زمان LTI مربوط به انواع مختلف هواپيماهاي مسافربري را نشان مي‌دهد. همانطور که مشاهده ميکنيد اين جدول غيرمتقارن ميباشد به‌طوري‌که زمان LTI هواپيماي B727 پشت سر هواپيما B747 200 ثانيه است درصورتي‌که فقط 70 ثانيه در شرايطي که ترتيب دو هواپيما جابجا شود زمان لازم است. اگرچه راهکار FCFS عدالت را بر اساس PLT رعايت مي‌کند ولي با توجه به نامتقارن بودن زمان LTI، با جابجايي موقعيت هواپيما در صف ورود هر باند پروازي و يا جابجايي آن‌ها در بين صفوف باندهاي پروازي مختلف مي‌توان تأخيرات پروازي را کاهش داد و ظرفيت پروازي فرودگاه را افزايش داد.
جدول 1-1 حداقل زمان LTI
1-3- مفروضات، محدوديت‌ها
همانطور که قبلاً توضيح داديم در مسأله ASP قصد داريم ايمني، کارايي و دقيق بودن توالي پروازهاي ورودي را در فرودگاه موردنظر بررسي کنيم. ازآنجايي‌که ايمني با LTI تضمين ميشود پس تابع هدف براي اين مسأله لازم است بر روي کارايي عمليات فرودگاهي و دقت در سرويس‌دهي پروازها به دست آورده شود.
* NAC تعداد هواپيمايي که طبق برنامهريزي انجام‌شده براي نشستن در فرودگاه موردنظر ميآيند
* NR شماره باند مورداستفاده در مدت‌زمان مشخص
* Ai زمان فرود تخصيص‌يافته (9ALT) براي هواپيماي i-ام
* Qr صف ورودي پرواز براي فرود بر روي باند r
* Qr(j) هواپيماي j-ام در صف Qr که r=1,…,NR و j=1,…,Hr (Hr تعداد هواپيماها در صف Qr)
اساساً ما دو تابع هدف در نظر ميگيريم:
(1-1)
(1-2)
در رابطههاي بالا J1 مجموع تأخيرات پروازي به وجود آمده براي تمام هواپيماها است و J2 حداکثر طول تمامي صفوف پروازهاي ورودي را ثبت مي‌کند. مجموع تأخيرات J1 بر روي هزينه عمليات شرکت‌هاي هواپيمايي تأکيد دارد درصورتي‌که حداکثر طول صفوف در J2 بيشتر بر روي کارايي استفاده از ظرفيت فرودگاه تمرکز دارد. در خيلي از موارد حداقل مجموع تأخيرات به‌طور همزمان باکم کردن حداکثري طول تمامي صفوف به دست ميآيد، اما بدين معنا نيست که هر دو با يکديگر برابر هستند. رابطه بين J1 و J2 بيشتر در قسمت شبيه‌ساز موردبررسي قرار ميگيرد. مسأله ASP را مي‌توان به‌صورت زير فرمول‌بندي کرد:
(1-3)
(1-4)
با توجه به رابطههاي 1-1 الي 1-4 واضح است که مي‌توان پروازهاي ورودي براي باندهاي پروازي مختلف را مشخص کرد و همچنين ترتيب هواپيماها در هر صف را سازمان‌دهي کرد.
1-4- اهداف تحقيق
کارشناسان خبره در مديريت ترافيک هوايي همواره به دنبال بالا بردن کارايي و بهرهوري بودهاند. افزايش ظرفيت فرودگاهها، گسترش باندها و تاکسي وي‌هاي پروازي، افزايش تجهيزات ناوبري و کمک ناوبري، تغييرات درراه‌ها و فضاي هوايي، استفاده از تجهيزات ماهوارهاي، تجهيز خطوط هواپيمايي، تربيت و آموزش نيروهاي کارآمد و غيره، دو هدف مهم در صنعت حمل‌ونقل مسافر هوايي را دنبال مي‌کند و آن ابتدا حفظ ايمني پروازها و سپس تسريع جريان ترافيک هوايي و کاهش تأخيرات پروازي ميباشد. کاهش تأخير پروازها جدا از شعار احترام به مشتري يک هدف مهم را در پي خواهد داشت و آن صرفهجويي اقتصادي ميباشد. در اين تحقيق ضمن ارائه الگوريتمي کارا و جديد در حل مسائل بهينهسازي براي حل مسأله توالي پروازها نيز به کار ميرود و موجب کاهش هزينههاي بيليون دلاري شرکت‌هاي هواپيمايي نيز خواهد شد.
الگوريتم رقابت استعماري (Imperialist Competitive Algorithm – ICA) روشي در حوزه محاسبات تکاملي است که به يافتن پاسخ بهينه مسائل مختلف بهينهسازي مي‌پردازد. اين الگوريتم با مدل‌سازي رياضي فرايند تکامل اجتماعي- سياسي، الگوريتمي براي حل مسائل رياضي بهينه‌سازي ارائه مي‌دهد. ازلحاظ کاربرد، اين الگوريتم در دسته الگوريتم‌هاي بهينهسازي تکاملي همچون الگوريتم‌هاي ژنتيک (Genetic Algorithms)، بهينهسازي انبوه ذرات (Particle Swarm Optimization)، بهينه‌سازي کلوني مورچگان (Ant Colony Optimization) ، تبريد شبيهسازي شده (Simulated Annealing) و … قرار ميگيرد. همانند همه الگوريتم‌هاي قرارگرفته در اين دسته، الگوريتم رقابت استعماري نيز مجموعه اوليهاي از جواب‌هاي احتمالي را تشکيل ميدهد. اين جواب‌هاي اوليه در الگوريتم ژنتيک با عنوان “کروموزوم “، در الگوريتم ازدحام ذرات با عنوان “ذره ” و در الگوريتم رقابت استعماري نيز با عنوان “کشور ” شناخته ميشوند. الگوريتم رقابت استعماري با روند خاصي اين جواب‌هاي اوليه (کشورها) را به‌تدريج بهبود داده و درنهايت جواب مناسب مسأله بهينه‌سازي (کشور مطلوب) را در اختيار ميگذارد. پايه‌هاي اصلي اين الگوريتم را سياست همسانسازي (Assimilation)، رقابت استعماري (Imperialistic Competition) و انقلاب (Revolution) تشکيل مي‌دهند. اين الگوريتم با تقليد از روند تکامل اجتماعي، اقتصادي و سياسي کشورها و با مدل‌سازي رياضي بخشهايي از اين فرايند، عملگرهايي را در قالب منظم به‌صورت الگوريتم ارائه مي‌دهد که مي‌توانند به حل مسائل پيچيده بهينه‌سازي کمک کنند. درواقع اين الگوريتم جواب‌هاي مسأله بهينه‌سازي را در قالب کشورها نگريسته و سعي مي‌کند در طي فرايندي تکرارشونده اين جواب‌ها را رفته‌رفته بهبود داده و درنهايت به جواب بهينه مسأله برساند. درروش پيشنهادي هدف استفاده از يک الگوريتم رقابت استعماري است که يک اصلاح روي آن انجام‌شده است به‌گونه‌اي که به بهترين شکل بتواند مسأله توالي هواپيما را مديريت کند.
1-5- جنبه‌ي جديد بودن و نوآوري
در اين روش، نوعي اصلاح در روش ICA ارائه شد كه در آن براي افزايش كارايي الگوريتم از تابع جذب نزديكترين همسايه اصلاحي و روش انقلاب بهبوددهنده دونقطهاي استفاده شد. همچنين براي افزايش كيفيت جواب‌هاي به‌دست‌آمده روش بهبوددهنده سهگانه به کار گرفته شد.
1-6- نتايج حاصل از تحقيق
روش پيشنهادي اين پايان‌نامه با به‌کارگيري يك الگوريتم اصلاحي رقابت استعماري براي حل مسأله برنامهريزي توالي هواپيماها راه‌حلي را براي پاسخ به مسأله توالي هواپيما ارائه کرده است. مسأله توالي هواپيما يك مسأله NP-سخت است، الگوريتمهاي دقيق كارايي خود را بر روي اين مسأله در ابعاد بالا از دست ميدهند و نميتوانند به جواب بهينه در يک‌زمان قابل‌قبول دست يابند. درنتيجه امروزه براي حل اينگونه مسائل از الگوريتمهاي ابتكاري و فرا ابتكاري استفاده ميشود كه عليرغم اينكه نميتوانند جواب بهينه را به دست آورند اما ميتوانند جواب نزديك به بهينه را در يک‌زمان قابل‌قبول به دست آورند. توجه به اين نكته ضروري است كه الگوريتمهاي ابتكاري در يک‌زمان اندك به جواب زير بهينه ميرسند اما چون داراي ساختار خوبي براي فرار از نقاط بهينه محلي نيستند، معمولاً به جواب‌هاي باكيفيت همگرا نميشوند. درحالي‌که با توجه به شبيه‌سازي روش مطرح‌شده در اين پايان‌نامه مي‌توان گفت که روش پيشنهادي داراي ساختار تصادفي براي رسيدن به جواب مسأله بوده و ميتوانند تا حد امكان از بهينههاي محلي فرار كنند و به جواب‌هاي بسيار خوبي همگرا شوند.
1-7- ساختار پايان‌نامه
اين پايان‌نامه در چهارفصل تهيه‌شده است.
فصل اول که شرح آن گذشت، بر تشريح مقدمه پاياننامه تمرکز مي‌کند.
فصل دوم که مروري بر کارهاي گذشته نام دارد ابتدا به تشريح مفاهيم پايه ميپردازد و سپس بهطور اجمالي در مورد توالي پروازها، تخصيص وروديهاي مسافري و پارامترهاي مسأله توضيح ميدهد و در ادامه کارهاي گذشته در اين زمينه را توصيف مي‌کند.
فصل سوم به شرح کامل روش پيشنهادي ميپردازد اما قبل از شرح روش پيشنهادي، الگوريتم رقابت استعماري به‌تفصيل شرح داده خواهد شد. روش ارائه‌شده با استفاده از شبيه‌سازي در بوتهي ارزيابي قرار ميگيرد تا صحت نتايج حاصل از به‌کارگيري آن موردبررسي قرار گيرد.
سرانجام در فصل چهارم که فصل پاياني است به‌طور اجمالي نتايج حاصل از روش پيشنهادي بيان ميشود.
2- مروري بر کارهاي گذشته
2-1- مقدمه
درزمينه‌ي صنعت هوانوردي چهار موضوع همواره موردتوجه محققين تحقيق در عمليات بوده است. اين موضوعات عبارت‌اند از:
* توالي فرود هواپيماها
* تخصيص وروديهاي مسافري10
* برنامهريزي خدمهي پروازي11

* برنامهريزي هواپيماها12
اين مسائل داراي وابستگيهاي زيادي با يکديگر هستند و عموماً خروجي يک دسته از مسائل ورودي ديگر مسائل است. به‌طور مثال خروجي برنامهريزي هواپيماها به‌عنوان ورودي مسألهي خدمهي پروازي است.
با توجه به مباحث مطرح‌شده، در اين پاياننامه مسائل توالي فرود هواپيماها و تخصيص وروديهاي مسافري موردبررسي قرارگرفتهاند.
2-2- توالي فرود هواپيماها
تلاشهاي زيادي در خصوص حل مسأله برنامهريزي فرود در فرودگاهها صورت گرفته است. سارافتيس (1980) براي اولين بار اين مسأله را موردبررسي قرار داد و مدلي کارگاهي براي اين مسأله ارائه نموده است. در اين پژوهش مسائلي با اندازهي 15 هواپيما در يک فرودگاه يک باند توسط رويکرد برنامهريزي پويا13 حل‌شده است. ارائه چنين مدلي توجه محققين را در جهت ارائه مدلهايي باهدف حل مسأله در ابعاد بزرگ‌تر و در زمان کمتر را به خود جلب کرد.
آبلا14 و همکاران (1995) دو روش براي حل مسأله توالي فرود هواپيماها ارائه کردهاند يک روش با استفاده از الگوريتم ژنتيک است و روش ديگر شاخه و برگ است که با فرموله کردن مسأله به‌صورت برنامهريزي عددي آميخته15 امکان استفاده از اين روش را در مسأله مهيا کرده‌اند. در اين تحقيق مسائلي تا اندازهي 25 هواپيما با دو باند فرود حل‌شده است. در اين تحقيق بيان‌شده است که الگوريتم‌هاي تقريبي بر روي مسائل کوچک عملکرد قابل‌قبولي دارند درحالي‌که روشهاي دقيق زمان‌گير است.
سيسلکي16 و همکاران (1998)، نشان دادند که استفاده از الگوريتم ژنتيک براي مسائل زمان‌بندي فرود هواپيماها براي دادههاي فرودگاه سيدني در شلوغترين روز سال باعث پيدا کردن جواب‌هاي باکيفيتي ميشود. همچنين در اين تحقيق توانستند با واردکردن اطلاعات هواپيماها در هر بار توليد نسل، الگوريتم ژنتيکي براي مسائل توالي فرود هواپيماها به‌صورت پويا ارائه کنند.
ارنست17 و همکاران (1998) اقدام به حل اين مسأله براي چند باند با استفاده از يک روش دقيق و دو روش ابتکاري کردند. روش دقيق ارائه‌شده در اين تحقيق روش سيمپلکس است که با استفاده از يک توالي فرود توليدشده کار مي‌کند. روش جستجوي فضاي جواب18 و روش شاخه و برگ نيز براي حل مسائلي با 10 الي 44 هواپيما و دو الي چهار باند فرود استفاده‌شده‌اند. در پايان اين تحقيق به بررسي عملکرد سه الگوريتم پرداختهاند که نتايج اين بررسي کارايي بهتر روش دقيق را نمايش ميدهد.
بيلسي19 و همکاران (2000) توانستند با ارائه يک مدل عدد صحيح آميخته براي مسأله توالي فرود هواپيماها، مسائلي با اندازه 50 هواپيما و 4 باند فرود را با روش جستجوي درخت20 حل کنند. نتايج اين تحقيق کارايي اين الگوريتم در حل سريع مسائل را اثبات کرده است.
تلاشهاي زيادي براي حل مسأله توالي فرود هواپيماها در ابعاد مختلف شده است و در سالهاي اخير، يواپينگ21 و همکاران (2008) اقدام به حل توالي فرود هواپيماها با دو تابع هدف کمينه کردن هزينهها و تأخيرها نمودهاند، يکي از نوآوريهاي مهم اين تحقيق ايجاد تفاوت بين هواپيماها بوده است.
بنشيخ22 و همکاران (2009) يک روش ترکيبي23 براي حل اين مسأله ارائه کردهاند. روش ترکيبي ارائه‌شده در اين تحقيق ترکيب الگوريتم ژنتيک و الگوريتم کلوني مورچه‌ها است که مسائلي تا ابعاد 50 هواپيما و 4 باند فرود را حل مي‌کند. در اين تحقيق جواب‌هاي خروجي الگوريتم ترکيبي ازلحاظ زمان و کيفيت با جواب دقيق مسأله مقايسه کردهاند که عملکرد قابل‌قبولي داشته است.
بويسن24 و فليدنر25 (2010) مسألهي توالي فرود هواپيماها را با توجه به ايجاد توازن کار براي نيروهاي فرودگاهي بررسي کردهاند. در اين تحقيق توابع هدف جديدي همچون تعداد مسافرين فرود آمده، تعداد فرودهاي هواپيماهاي يک شرکت هواپيمايي و تعداد مسافرين فرود آمده از يک شرکت هواپيمايي معرفي‌شده‌اند.
شنگ پنگ26 و همکاران (2011) اقدام به ارائه‌ي روشي کردهاند که مسأله توالي فرود هواپيماها را در کمتر از 4 ثانيه حل مي‌کند اين روش بر روي 6 مسأله نمونه با اندازه‌ي 50 هواپيما و 7 مسأله نمونه با اندازه‌ي 500 هواپيما مورد آزمايش قرارگرفته است. ازآنجايي‌که تصميم‌گيري در مورد تعيين توالي فرود هواپيماها در دنياي امروزي بايد سريع انجام گيرد اين روش وسيله‌اي براي تصميم‌گيري آني در مورد اين نوع مسأله است و به‌نوعي امکان استفاده از اين نوع برنامهريزي را در فرودگاهها فراهم آورد. روش پيشنهادي اين تحقيق بر پايه‌ي Cellular Automata Optimization است. محققين به ارزيابي اين الگوريتم در مقايسه با الگوريتم‌هاي موجود در ادبيات پرداختهاند و با استفاده از 13 مسأله نمونه ذکرشده، برتري الگوريتم پيشنهادي را اثبات کردهاند.
2-3- تخصيص وروديهاي مسافري
تخصيص وروديهاي مسافري به هواپيماهاي ورودي يکي ديگر از مسائل مطرح در عرصهي هوانوردي است. تخصيص هواپيماها به وروديهاي مسافري سالن فرودگاه، ميبايست قبل از فرود هواپيما برنامهريزي شود. وظيفهي اين برنامهريزي با کنترلر فرودگاه است. براي بهبود بخشيدن به اين برنامهريزي محققين در اين زمينه تحقيقاتي انجام دادهاند که در زير به بررسي آن‌ها پرداخته‌شده است.
حقاني27 و چين چن28 (1998) به ارائه يک روش ابتکاري براي حل مسأله تخصيص هواپيماها به وروديهاي مسافري نمودهاند. تابع هدف اين الگوريتم کمينه کردن مسافت پياده‌روي مسافرين در سالن فرودگاه است. اين الگوريتم براي مسائلي از 3 هواپيما با 2 ورودي مسافري الي 30 هواپيما و 7 ورودي مسافري حل‌شده و سپس با مقدار تابع هدف بهينهي اين مسائل مقايسه شده است. در تمام مسائل مطرح‌شده الگوريتم پيشنهادي جواب بهينه داده است.
بولات29 (2001) يک مدل برنامهريزي خطي باهدف کمينه کردن زمان بيکاري وروديهاي مسافري ارائه کرده است و شرايطي براي به دست آوردن جواب بهينه در زمان چندجمله‌اي بيان کرده است. همچنين يک الگوريتم فرا ابتکاري بر پايه الگوريتم ژنتيک براي حل اين مسأله ارائه کرده است که کارايي آن با مسائلي از 26 تا 106 هواپيما موردبررسي قرارگرفته است.
يان30 و هيو31 (1999)، به ارائه يک مدل رياضي صفر و يک با توابع هدف کمينه کردن زمان انتظار مسافرين و ميزان پيادهروي مسافرين کردهاند. سپس به مقايسه عملکرد 4 روش وزني32، توليد ستون33، روش سيمپلکس و شاخه و حد کردهاند. از دادههاي فرودگاه چيانگ کي شک34 براي مقايسه روش‌ها استفاده‌شده است. الگوريتم توليد ستون نسبت به ديگر روش‌ها کارايي بهتري داشته است.
خو35 و بيلي36 (2001)، يک مدل صفر و يک‌خطي شده براي تخصيص هواپيما به ورودي مسافري ارائه کرده‌اند. در اين تحقيق از الگوريتم فرا ابتکاري جستجوي ممنوعه استفاده‌شده است و تمام پارامترهاي اين روش بررسي و مقداردهي شدهاند. مسائل نمونه‌ي اين تحقيق را تا 50 ورودي مسافري بررسي کردهاند. در تمام اين بررسي‌ها کارايي الگوريتم جستجوي ممنوعه ازلحاظ زمان و مقدار خطا نسبت به روشهاي دقيق اثبات‌شده است.
تابع هدفي که در اين تحقيق موردبررسي قرارگرفته است بيشينه کردن تعداد هواپيماهاي تخصيص‌يافته به ورودي‌هاي مسافري است. در اين زمينه دينگ37 و همکاران (2004) مدلي ارائه کردهاند که علاوه بر اين تابع هدف، به کمينه‌سازي ميزان پياده‌روي مسافرين در سالن نيز مي‌پردازد. در اين تحقيق از دو الگوريتم جستجوي ممنوعه و الگوريتم حريصانه38 استفاده‌شده است. از الگوريتم حريصانه براي کمينه کردن تعداد هواپيماهاي تخصيص نيافته به ورودي مسافري استفاده‌شده است و از جواب نهايي اين الگوريتم به‌عنوان جواب اوليه الگوريتم جستجوي ممنوعه استفاده‌شده است.
در تحقيق ديگر دينگ و همکاران (2005)، اقدام به ارائه يک روش ترکيبي با ترکيب دو روش جستجوي ممنوعه39 و تبريد شبيه‌سازي شده40 براي حل مسأله کردهاند. با بررسي بر روي مسائل نمونه کارايي روش هيبريدي نسبت به شبيه‌سازي تبريد اثبات‌شده است. البته شبيه‌سازي تبريدي ازلحاظ زمان حل عملکرد بهتري نسبت بهتري نسبت به روش هيبريدي دارد.
دورندورف41 و همکاران (2008) مدل رياضي تخصيص هواپيماها به ورودي‌هاي مسافري را به مسأله تفکيک گروهک42 تبديل کردهاند و با استفاده از الگوريتم تخليهاي زنجيرهاي اين مسأله را حل نمودهاند اين روش بر روي يک مسأله با داده‌هاي واقعي اجراشده و جواب قابل‌قبولي ارائه کرده است.
درکس43 و نيکولينيگل44 (2007) با استفاده از روش شبيه‌سازي تبريدي اقدام به حل اين مسأله کرده‌اند. مسائل نمونهي اين تحقيق براي فرودگاهي با 20 ورودي مسافري در افق زماني 4 ساعت و 30 دقيقه و 100 هواپيما ورودي در نظر گرفته‌شده است.
در جديدترين تحقيقي که انجام‌شده، کومار45 و همکاران (2011) مدلي ارائه کردهاند که به تخصيص پوياي هواپيماها به وروديهاي مسافر به‌منظور کمينه کردن هزينهها و بيشينه کردن درآمدها ميپردازد و اين مدل را با استفاده از زبان برنامه‌نويسي بهينه‌سازي46 حل کردهاند و با استفاده از اين روش مسألهاي به‌اندازه‌ي 75 ورودي مسافر و 1200 هواپيما راحل نمودهاند. در تمامي تحقيقات موردبررسي، فرض بر فرود آمدن هواپيماها در زمانهاي مشخص و از پيش تعيين‌شده بوده است که همين فرض در صورت تأخير يک هواپيما باعث بروز مشکل در برنامهريزي صورت گرفته است.
2-4- پيشينه تحقيق
با توجه به پيشرفتهاي صورت گرفته در حوزه مراقبت پرواز و اجرايي شدن طرح CNS/ATM و استفاده از امکانات و تسهيلات مختلف زميني و هوايي و بهخصوص ماهوارهاي؛ همچنان براي حفظ ايمني و تسريع امر پروازي نيازمند راهکارهاي مختلف و کارآمدتري هستيم. در حوزه کاري مديريت ترافيک هوايي در سالهاي اخير کارهاي مختلفي صورت گرفته است که مي‌توان به اين موارد اشاره کرد: ارزيابي و محاسبه پيچيدگي ترافيک هوايي و ارائه متريک مناسب[1]، سنجش ظرفيت پذيرش ترافيک توسط کنترلر مراقبت پرواز در شرايط مختلف[2]، ادغام سکتور فضاي کنترل پروازي به روش تصادفي و کلاسيک[3]، ارتقاي سامانه‌هاي هشداردهنده تصادم هوايي داخل هواپيما[4]، برنامهريزي جهت استفاده عملياتي بهينه از فرودگاه جهت کاهش آلودگي محيطي[5]، تقرب افقي چرخشي براي برنامهريزي پروازها در پايانه کنترل فرودگاههاي پرترافيک[6]، مديريت جريان ترافيک هوايي در پايانه کنترل فرودگاه هنگام شرايط نامتعارف[7]، الگوريتم حريصانه و فوق اکتشافي براي مسأله برنامهريزي توالي پروازهاي ورودي و خروجي به چند باند پروازي[8]، استفاده از فن خوشهبندي انتشار وابستگي (Affinity Propagation) در حل مسأله توالي پروازهاي ورودي و خروجي[9]، استفاده از الگوريتم ژنتيک در سيستم شبيهساز جديد مديريت ترافيک هوايي[10].
يکي از مسائل روز صنعت هواپيمايي که اين روزها به آن پرداخته ميشود بحث توالي پروازهاي ورودي و خروجي ميباشد. اگرچه براي حل مسأله ASP الگوريتم‌هاي هيوريستيک و دقيقي ارائه‌شده است اما با توجه به بزرگ بودن مسأله واقعي؛ زمان طولاني براي رسيدن به حل بهينه نياز است. Bennall ]11 [ در سال 2011 نه‌تنها از ابزارهاي تحقيق عملياتي و مديريت دانش بلکه از فن‌هاي حل شامل برنامه‌ريزي پويا، شاخه و برگ، هيوريستيک و متاهيوريستيک براي برنامهريزي نشست‌وبرخاست هواپيماها استفاده کرده است. کارهاي اوليه بر روي مسأله ASP از سال 1970 توسط Dear ]12 [بر روي ورود و خروج پروازها آغاز شد. در سال 1980 ]13 [ مسأله برنامهريزي ماشين واحد را با راه‌کار بهبود برنامهريزي پويا بر روي توالي عمليات ورودي پروازها بکار برد. در سال 1987 و 1997 Bianco ]14،15[ با استفاده از برنامهريزي عددي به حل مسأله پرداخت. Beasley ]16 [در سال 2000 هر دو الگوريتم برنامهريزي عددي و هيوريستيک را توسعه و بهبود داد. در سال 2005 ]17 [ الگوريتم تجزيه دقيق توسعه‌يافته بر مبناي تعميم‌پذيري ستوني را براي حل مسأله توالي پروازهاي ورودي ارائه داد. در سال 2009 ]18 [ براي پروازهاي خروجي فرودگاه بينالمللي دالاس از الگوريتم برنامهريزي عددي خطي ترکيبي استفاده کرد. مسأله ASP براي يک باند پروازي با الگوبرداري از مسأله فروشنده دورهگرد نامتقارن در سال 2012 ]19 [ارائه شد.
در اوايل دهه 90 براي حل مسأله ASP تحقيقات بر روي الگوريتم هيوريستيک حريصانه متمرکز شد. Dear ]20،21[ در سالهاي 1989 و 1991 براي حل مسأله به‌صورت پويا و استاتيک از روش هيوريستيکي CPS استفاده کرد. الگوريتم هيوريستيک محلي پويا و سريع به نام cheapest search heuristic(CSH) در سال 1991 براي توالي پروازها به چند باند پروازي ارائه شد. در سال 2011 ]22 [الگوريتمي به نام Cellular-Automata-based Optimization(CAO) مسأله ASP را براي پروازهاي ورودي به يک باند موردبررسي قرارداد. مطالعات گوناگوني در سالهاي 2000 و 2001 توسط Beasley ]23،24 [، سالهاي 2005 و 2008 توسط Hu و Wang ]25،26[ و بالاخره Liu ]27 [در سال 2010 با استفاده از متاهيوريستيکهايي به نام الگوريتم ژنتيک، کلوني مورچه و جستجوي پراکنده به حل اين مسأله پرداختند. به‌علاوه در سالهاي 2007 و 2008 با استفاده از الگوريتم تبريد شبيه‌سازي‌شده (SA) و جستجوي ممنوعه (TS) ]28،29[ بهصورت جداگانه براي پروازهاي ورودي و خروجي مسأله موردبررسي قرار گرفت.
مسأله برنامهريزي پروازهاي ورودي و خروجي بر روي يک باند پروازي و يا چند باند پروازي شبيه و نظير مسأله برنامهريزي ماشينها ميباشد. مطالب و نوشتهها درزمينهي برنامهريزي ماشينهاي موازي مشخص با در نظر گرفتن زمان آمادهسازي و به‌منظور کاهش مجموع تأخيرات وزندار بسيار کم و محدود ميباشد. در سال 1997 ]30 [ الگوريتم Apparent Tardiness Cost with Setups(ATCS) ارائه شد که توانست برنامهي اوليهاي براي حل سه مرحلهاي برنامهريزي کارها با زمان آمادهسازي روي ماشينهاي موازي مشخص با تنظيم وابستگي به‌توالي ارائه دهد. در سال 2008 ]31 [الگوريتم ATCS را با ارائه روشي براي اجازه برنامهريزي روي کارهاي غير آماده بهبود داد. در سال 2009 ]32 [با اصلاح الگوريتم هيوريستيک SA با راهحل اوليه ايجادشده توسط الگوريتم ATCS راهکار جديدي ارائه داد. Lin,Lu,Ying ]33 [در سال 2011 کار مشابهي با استفاده از الگوريتم حريصانه تکراري ارائه دادند. در سال 2013 توسط Hancerligullari ]8 [مسأله ASP براي پروازهاي ورودي و خروجي با استفاده از چند باند پروازي با در نظر گرفتن زمانهاي آمادهسازي، هدف، خاتمه و زمانهاي جدايي وابسته به‌توالي مدل‌سازي شد.
در سال 2004]34[ توانست با استفاده از الگوريتم ژنتيک توالي پروازهاي ورودي را مدل‌سازي کند. در اين روش که براي حل مسأله ASP براي يک باند پروازي ارائه‌شده است کروموزوم‌هاي ساخته‌شده بر اساس توالي پروازهاي ورودي در صف ميباشد و تنها راه براي نمو آن‌ها جهش ميباشد. در اين مقاله Salvatore Capri راهکار خود را با الگوريتم cheapest insertion heuristic (CIH) که در سال 1997 توسط بيانکو]15 [ براي حل همين مسأله ارائه کرده بود، مقايسه کرد و نتايج بهتري در شرايط ترافيک هوايي مختلف گرفته شد. در سال 2009 ]35[ با استفاده از همين الگوريتم ژنتيک و البته روش آميزش يکنواخت براي فرودگاههاي داراي چند باند پروازي راه‌حل بهينه و کارايي ارائه شد. از گذشته در مورداستفاده از آميزش در حوزه محاسبات تکاملي مناقشه و بحث زيادي وجود داشته است. اتفاقاً نظر مخالف در مورد همين مناقشه به پيادهسازي الگوريتم ژنتيک در مورد مسأله ASP برميگردد. ايده آميزش ازنقطه‌نظر تکاملي بدين‌صورت است: دو کروموزوم والد را برداشته و قسمت ژن آن‌ها را به‌صورت رندم جابجا کنيد به‌طوري‌که کروموزوم‌هاي فرزند، آن ژنها را از والد به ارث ببرند و در همان زمان احتمالات جديد از ترکيب دوباره آن ژنهاي مختلف را در والد پيدا کند. ژنهاي کليدي و قسمتهايي از ژنهاي مشترک با کروموزوم‌هاي مناسبتر، در حين آميزش قابل‌دستيابي توسط جهش، مي‌تواند کارا و مؤثر به ارث برده و حفاظت شود. عمليات آميزش واحد را شايد بتوان يکي از قدرتمندترين عمليات آميزش دانست زيرابه کروموزوم‌هاي فرزند اين اجازه را ميدهد تا در تمام حالات ممکن ترکيبي ژنهاي مختلف در والدها، جستجو کند. Xiao-Bing Hu ]35 [با استفاده از همين روش توانست الگوريتم کارايي براي حل مسأله ASP ارائه دهد که در مقايسه باکارهاي ديگر در اين زمينه بهتر عمل کرده است.
2-5- مدل برنامه‌ريزي خطي برنامه
در اين بخش به بيان مدل رياضي مسأله خواهيم پرداخت. فرضيات موردنظر در اين تحقيق عبارت‌اند از:
* در هنگام فرود دو هواپيما متوالي اولين و مهمترين عاملي که يک کنترلر فرودگاهي بايد در نظر بگيرد فاصله‌ي زماني فرود دو هواپيما از يکديگر است. دلايل حفظ اين فاصله زماني مربوط به مسائل آئروديناميک هواپيما است. هر هواپيمايي که در آسمان در حال حرکت است يک گرداب47 از جريان ناپايدار هوا در پشت سرخود ايجاد مي‌کند. شدت اين گرداب با اندازهي هواپيما رابطه مستقيم دارد و با بزرگ‌تر شدن يک هواپيما، شدت ناپايداري اين جريان افزايش مي‌يابد. اين جريان همچنين باکم شدن سرعت هواپيما شدت بيشتري مي‌گيرد. درصورتي‌که يک هواپيما وارد اين جريان ناپايدار شود، اين جريان باعث برهم خوردن تعادل هواپيما ميشود و حتي ممکن است باعث سقوط هواپيما شود. در هنگام فرود به دليل اينکه هواپيما با پايينترين سرعت ممکن خود در حال پرواز است شدت‌جريان ناپايدار بيشينه خواهد بود. به همين منظور کنترلرهاي فرودگاهي يک‌زمان جداسازي بين دو هواپيماي متوالي که بر روي يک باند در حال نشستن هستند در نظر مي‌گيرند. در اين تحقيق زمان جداسازي به‌صورت يک عدد ثابت در نظر گرفته‌شده است.
* هر هواپيما داراي يک پنجره زماني48 براي رسيدن به فرودگاه مقصد است. اين پنجرهي زماني شامل سه پارامتر است. اولين پارامتر زودترين زمان رسيدن هواپيما است اين پارامتر بر اساس بالاترين سرعت هواپيما و فاصلهي بين دو فرودگاه محاسبه مي‌شود. دومين پارامتر ديرترين زمان رسيدن هواپيما است. مدت‌زماني که يک هواپيما با توجه به سوخت خود مي‌تواند پرواز کند به‌عنوان ديرترين زمان رسيدن هواپيما در نظر گرفته مي‌شود. آخرين اين پارامتر زمان هدف فرود هواپيما است. اين زمان، همان زمان مدنظر شرکت هواپيمايي براي فرود هواپيما است. اين پارامتر توسط شرکت هواپيمايي در هنگام عقد قرارداد با فرودگاه تعيين ميشود.
* بعد از فرود هواپيماها در فرودگاه، بعضي از هواپيماها نسبت به ديگر هواپيما اولويت تخصيص به ورودي‌هاي مسافري را دارا هستند. اين اولويت بستگي به نوع هواپيما و شرکت هواپيمايي دارد. به‌عنوان‌مثال يک هواپيما ايرباس A38049 با بيش از 650 مسافر مطمئناً نسبت به هواپيمايي با 100 مسافر ارجحيت دارد؛ زيرا خدمت‌دهي به هواپيماي ايرباس از طريق جابه‌جايي مسافرها با اتوبوس بسيار زمانگير است. يکي ديگر از دلايل ارجحيت يک هواپيما نسبت به هواپيماي ديگر، شرکت هواپيمايي است. به‌عنوان‌مثال در فرودگاه امام خميني هواپيماهاي خط هوايي امارت نسبت به خط هوايي ايران اير ارجحيت دارند زيرا اصولاً مسافرين اين خط هوايي تجار و ديپلمات‌ها هستند. اين ارجحيت بر اساس تجربه‌ي کنترلرهاي فرودگاه و با درخواست شرکت‌هاي هواپيمايي به دست مي‌آيد.
* بعد از ارجحيت تخصيص هواپيما به ورودي مسافر، ارجحيت تخصيص هواپيما به يک ورودي مسافري خاص وجود دارد؛ يعني ترجيح براي برخي از هواپيما تخصيص به يک ورودي مسافري خاص است. اين ترجيح بيشتر بر اساس مبدأ هواپيما است. به‌عنوان‌مثال در فرودگاه امام خميني هواپيمايي که از کشور مالزي وارد کشور ميشوند بيشتر ترجيح داده ميشود که به وروديهاي مسافري سمت شرق سالن مسافري تخصيص داده شوند. زيرابه تجربه ثابت‌شده است که مسافرين اين هواپيماها مشکلات گمرکي بيشتري نسبت به ديگر مسافرين دارند؛ بنابراين در صورت بروز مشکل، براي رسيدن به انبار گمرک نبايد مسافت زيادي را طي کنند.
* فاصله دو هواپيما در دو ورودي مسافري مجاور يکي از محدوديت‌هاي ايمني فرودگاه است. اين محدوديت که تأثير مستقيم در تخصيص دو هواپيما در مجاورت يکديگر دارد بدين‌صورت است طبق قوانين سازمان جهاني هوانوردي50 فاصله دو سر بال دو هواپيماي در کنار هم پارک شده بايد از يک مقدار ايمني بيشتر باشد. اين فاصله در شکل 2-1 نمايش داده‌شده است:
شکل 2-1- فاصله ايمني بين دو سر بال.
اين فاصله‌ي ايمني مي‌تواند باعث عدم تخصيص دو هواپيما در کنار يکديگر شود. در بعضي از موارد حتي با حضور يک هواپيما بزرگ51 در يک ورودي مسافر تا دو ورودي مجاور خود را اشغال کند و امکان استفاده از آن‌ها را سلب نمايد.
* در اين تحقيق، تابع هدف از دو بخش تشکيل‌شده است. مجموع خسارت زود کرد و يا ديرکرد هواپيماها و مجموع درآمد فرودگاه از تخصيص هواپيماها به ورودي‌هاي مسافري. براي ايجاد توازن بين اين دو تابع هدف از يک ضريب a براي مجموع درآمد فرودگاه از تخصيص هواپيماها به ورودي‌هاي مسافري استفاده کرده‌ايم و از ضريب (1-a) براي خسارت زود کرد و يا ديرکرد هواپيماها استفاده‌شده است.


پاسخی بگذارید