پایان نامه ارشد مهندسی کامپیوتر: تلفیق الگوریتم رقابت استعماری و انتخاب سریع زمان آماده سازی در حل مسأله برنامه ریزی توالی هواپیماها |
1-1- مقدمه………………………………………………………………………………………………….. 2
1-2- طرح موضوع………………………………………………………………………………………… 4
1-3- مفروضات، محدودیتها……………………………………………………………………………… 6
1-4- اهداف تحقیق………………………………………………………………………………………. 8
1-5- جنبهی جدید بودن و نوآوری………………………………………………………………… 9
1-6- نتایج حاصل از تحقیق…………………………………………………………………………. 9
1-7- ساختار پایان نامه …………………………………………………………………………………. 10
2- مروری بر کارهای گذشته……………………………………………………………………….. 11
2-1- مقدمه……………………………………………………………………………………………… 12
2-2- توالی فرود هواپیما……………………………………………………………………………. 12
2-3- تخصیص ورودی مسافری…………………………………………………………………… 15
2-4- پیشینه تحقیق………………………………………………………………………………… 17
2-5- مدل برنامه ریزی خطی برنامه…………………………………………………………….. 21
3- روش پیشنهادی……………………………………………………………………………….. 25
3-1- راهکار پیشنهادی……………………………………………………………………………… 26
3-2- الگوریتم تکاملی………………………………………………………………………………. 26
3-2-1- مقدمه……………………………………………………………………………………….. 26
3-2-2- علت استفاده از الگوریتمهای تکاملی……………………………………………… 29
3-2-3- انواع الگوریتمهای تکاملی………………………………………………………….. 29
3-3- الگوریتم رقابت استعماری……………………………………………………………….. 32
3-3-1- شکلدهی امپراطوری اولیه………………………………………………………….. 34
3-3-2- مدلسازی سیاست جذب……………………………………………………………. 38
3-3-3- جابجایی موقعیت مستعمره و امپرالیسست…………………………………… 41
3-3-4- قدرت کل یک امپراطوری………………………………………………………….. 42
3-3-5- رقابت استعماری………………………………………………………………………… 43
3-3-6- سقوط امپراطوریهای ضعیف………………………………………………………. 46
3-3-7- همگرایی……………………………………………………………………………….. 46
3-4- الگوریتم رقابت استعماری اصلاحی……………………………………………….. 48
3-5- الگوریتمهای ترکیبی بکار رفته…………………………………………………… 51
4- ارزیابی سیستم…………………………………………………………………………….. 53
4-1- مقدمه…………………………………………………………………………………….. 54
4-2- مدلسازی روش پیشنهادی……………………………………………………….. 55
4-3- ارزیابی راهکار پیشنهادی……………………………………………………………. 56
4-4- مسائل مورد مقایسه…………………………………………………………………. 59
4-4-1- مقایسه نتایج پروازهای ورودی و خروجی به تعداد 15…………………. 59
4-4-2- مقایسه نتایج پروازهای ورودی و خروجی به تعداد 20……………….. 61
4-4-3- مقایسه نتایج پروازهای ورودی و خروجی به تعداد 25………………. 62
5- نتیجهگیری و ارائه پیشنهادها……………………………………………………. 64
5-1- جنبه نوآوری…………………………………………………………………………… 65
5-2- نتیجه مقایسه نتایج…………………………………………………………….. 65
5-3- پیشنهادها……………………………………………………………………………. 66
6- مراجع ………………………………………………………………………………….67
چکیده:
مدیریت ترافیک هوایی یکی از مشاغل حساس و پراسترس است که همهروزه با مشکلات و موانع مختلفی روبهرو میشود و مسأله توالی هواپیما (Aircraft Sequencing Problem) یکی از مهمترین مسائلی است که این روزها در حوزه کاری مراقبت پرواز (Air Traffic Control) به آن پرداخته میشود.
مسأله توالی هواپیما یك مسأله NP-سخت است، الگوریتمهای دقیق كارایی خود را بر روی این مسأله در ابعاد بالا از دست می دهند و نمیتوانند به جواب بهینه در یکزمان قابلقبول دست یابند؛ درنتیجه امروزه برای حل اینگونه مسائل از الگوریتمهای ابتكاری و فرا ابتكاری استفاده میشود.
در این پایاننامه سعی شده با تلفیق الگوریتم ERT(Earliest Ready Time) جهت انتخاب http://fumi.ir/%d8%af%d8%a7%d9%86%d9%84%d9%88%d8%af-%d9%be%d8%a7%db%8c%d8%a7%d9%86-%d9%86%d8%a7%d9%85%d9%87-%d8%a7%d8%b1%d8%b4%d8%af-%d8%a7%d8%b1%d8%b2%d9%8a%d8%a7%d8%a8%d9%8a-%d8%b1%d9%8a%d8%b3%da%a9-%d9%88/ بهترین هواپیمای آماده عملیات با الگوریتم استعماری اصلاحی که از روش نزدیکترین همسایه تصادفی برای تابع جذب در کنار روش بهبوددهنده سهنقطهای برای تابع انقلاب استفاده کرده، روش جدیدی در حل مسأله توالی هواپیما ارائه شود. نتایج حاصل از پیادهسازی این الگوریتم نشان میدهد که در مقایسه با سایر الگوریتمها از کارایی بالایی برخوردار است.
فصل اول: مقدمه طرح پیشنهادی
1-1- مقدمه
یکی از موضوعات موردتوجه در صنعت هوانوردی، مبحث برنامه ریزی فرود هواپیماهای ورودی به فرودگاه است. با ورود هواپیماهای مختلف به محدوده راداری فرودگاه، مراقبین پرواز در برج مراقبت باید ترتیب فرود هواپیماهایی که در آن لحظه در آسمان فرودگاه در حال پرواز هستند را مشخص نمایند. برای اختصاص چنین ترتیب فرودی محدودیتهای مختلفی موردتوجه قرارمیگیرد که از آن جمله میتوان به محدودیت جداسازی دو هواپیما اشاره نمود. این محدودیت از دیدگاه مباحث آئرودینامیک اهمیت زیادی دارد و در صورت عدم رعایت آن امکان بروز حادثه برای هواپیماهای متوالی وجود دارد.
مهمترین نتیجهی موردنظر برنامه ریزی فرود هواپیماها، کمینه کردن تأخیرها است که از ایجاد هزینه سوخت اضافه برای هواپیماها و همینطور ایجاد نارضایتی مسافران جلوگیری میکند. ازآنجاییکه هزینه های مربوط به سوخت ناوگان پروازی درصد قابلتوجهی از هزینه های شرکتهای هواپیمایی را شامل میشود، برنامه ریزی فرود هواپیماها موردتوجه شرکتهای هواپیمایی و همچنین شرکتهای فرودگاهی قرارگرفته است. همین امر باعث شده است که اغلب فرودگاههایی که عملکرد بهتری در خصوص مدیریت ترافیک پروازی دارند، توجه شرکتهای هواپیمایی بیشتری را به خود جلب کنند. از سوی دیگر، در صورت دستیابی به عملکردی مناسب در مدیریت ترافیک پروازها، شرکتهای فرودگاهی این امکان را خواهند داشت که در بازه زمانی ثابت، پذیرای تعداد بیشتری از هواپیما باشند.
شرکتهای فرودگاهی بخشی از درآمد خود را از هزینه اجارهی جایگاه پارک[1] به دست میآورند. هزینه جایگاههای پارک، بسته به امکانات آن، متغیر است. امکاناتی نظیر برق زمینی[2] و یا ورودی های مسافری[3] در قیمت جایگاه پارک تأثیرگذار هستند. در تمامی فرودگاههای جهان دو نوع جایگاه پارک موجود است. جایگاه پارک با ورودی مسافر و جایگاه پارک دور از سالن[4]. جایگاه پارک با ورودی مسافر یا بانام دیگر جایگاه پارک با خرطومی اتصال، جایگاههای پارکی هستند که مسافرین یک هواپیما بدون نیاز به ورود به محوطه فرودگاه بهطور مستقیم با بهره گرفتن از یک راهرو (خرطومی اتصال) به هواپیما وارد و یا از آن خارج میشوند.
نیاز به ورود به محوطه فرودگاه بهطور مستقیم با بهره گرفتن از یک راهرو (خرطومی اتصال) به هواپیما وارد و یا از آن خارج میشوند؛ اما هواپیماهای واقع در جایگاه پارک دو از سالن، برای مسافر گیری و یا پیاده کردن مسافران خود نیاز به سرویس اتوبوس[5] دارند. از بین این دو نوع جایگاه، جایگاه پارک با ورودی مسافر دارای قیمت بالاتری است. قیمت این جایگاهها بدینصورت محاسبه میشود که به ازای هر مسافری که از یک هواپیما از ورودی مسافری استفاده میکند مبلغی ثابت از خط هواپیمایی مربوطه دریافت میشود که قیمت سرویس اتوبوس در مقابل آن ناچیز است. علیرغم قیمت بالاتر جایگاه پارک با ورودی مسافر، شرکتهای هواپیمایی برای کسب رضایت بیشتر مسافران خود ترجیح می دهند تا هواپیماهایشان به جایگاه پارک با ورودی مسافر تخصیص پیدا کند. جایگاه پارک با ورودی مسافر دارای یک مزیت ایمنی نیز هست، با استفاده مسافرین از ورودی مسافر دیگر خطرات ناشی از حضور مسافران در محوطه فرودگاه وجود ندارد و از ایجاد اتفاقات مختلف جلوگیری میشود.
با توجه به اینکه در هنگام عقد قرارداد خطوط هواپیمایی با فرودگاهها، خطوط هواپیمایی نمیتوانند در مورد نوع جایگاه پارک خود شرایطی را اعلام کنند و نوع جایگاه پارک یک هواپیما بر عهدهی کنترلر فرودگاه در لحظهی فرود هواپیما است؛ بنابراین در صورت برنامه ریزی صحیح میتوان هواپیماهای بیشتری را به جایگاههای پارک با ورودی مسافری اختصاص داد و از این طریق به افزایش درآمد فرودگاه کمک کرد.
با توجه به مطالب بیانشده، مدیریت فرودگاهها برای جذب شرکتهای هواپیمایی و همینطور بالا بردن درآمد خود باید بتوانند توازنی بین دو موضوع کنترل ترافیک هواپیماهای ورودی (توالی فرود هواپیماها) و تخصیص هواپیماها به ورودی های مسافری ایجاد کنند تا بتوانند علاوه برافزایش درآمد خود، مشتریان خود (شرکتهای هواپیمایی) را راضی نگهدارند؛ اما تنها مشکل در این زمینه وابستگی بسیار زیاد این دو مسأله به یکدیگر است. بدین معنا که هواپیماها بهمحض فرود در فرودگاه باید جایگاه پارکی به آنها تخصیص یابد و آن جایگاه پارک باید در لحظهی فرود هواپیما مذکور خالی و آماده به خدمتدهی باشد.
این موضوع باعث میشود که زمان فرود هواپیماها تأثیر مستقیمی در جایگاه پارک تخصیصی به یک هواپیما داشته باشد. یا بهعبارتدیگر، ممکن است در بعضی از مواقع فرود یک هواپیما با تأخیری چنددقیقهای باعث خالی شدن یک جایگاه پارک دارای ورودی مسافر بشود و با تخصیص این هواپیما به همان جایگاه باعث بالا رفتن درآمد فرودگاه شد؛ اما همیشه فرودگاهها باید در نظر داشته باشند که میزان این تأخیر تأثیری مستقیم در رضایت شرکتهای هواپیمایی دارد. در این فصل مروری بر ادبیات این دو موضوع داریم.
فرم در حال بارگذاری ...
[پنجشنبه 1398-07-11] [ 03:25:00 ب.ظ ]
|