بخشی از مقاله
خلاصه
زمانبندی فرود هواپیماها یکی از مسایل مهم در مدیریت ترافیک هوایی میباشد. در این مقاله مساله زمانبندی فرود هواپیما با هدف کمینهسازی حداکثر زمان فرود هواپیماها بر روی چند باند فرود و وابستگی بین باندها مورد بررسی قرار خواهد گرفت. این مساله از گروه مسایلNP-hard بوده و شامل تخصیص هر هواپیما به باند در دسترس و تعیین زمان فرود هر هواپیما بر روی باند اختصاص داده شده میباشد. هر هواپیما ملزم به فرود در یک پنجره زمانی شامل زودترین و دیرترین زمان فرود خواهد بود. همچنین جهت افزایش ایمنی، حداقل زمان جداسازی بین فرود هواپیمای متوالی در نظر گرفته خواهد شد. مدل ریاضی مساله مورد نظر معرفی شده و با استفاده از الگوریتم فراابتکاری ژنتیک و نرم افزار لینگو حل خواهد شد. در انتها نتایج محاسباتی در قالب مثال عددی تا 200 هواپیما و2باند بررسی شده است. نتایج حاصل نشانگر این موضوع است که نرم افزار لینگو به عنوان یکی از ابزارهای حل مسایل برنامهریزی عدد صحیح مختلط ، قادر به ارایه جواب بهینه بوده، هرچند که در بهینهسازی مسایلی که پیچیدگی بالایی دارند از ارایه نتیجه باز میماند. این در حالی است که الگوریتم ژنتیک به جواب مطلوبتری همگرا میگردد.
کلمات کلیدی: زمانبندی فرود هواپیما، کنترل ترافیک هوایی، فرودگاه چند باند، الگوریتم ژنتیک
.1 مقدمه
در دهههای اخیر شاهد روند رو به رشد تقاضای حمل و نقل هوایی بودهایم. این افزایش مستمر تقاضا در سالهای آتی موجب خواهد شد تا فرودگاهها در برابر پاسخگویی به تقاضا به دلیل محدودیتهای زیر ساختی ناتوان گردند [1-2] و این نشان خواهد دادکه ترافیک هوایی به صورت پیوسته در حال رشد است و پیش بینی میشود که در دو دهه آینده بکارگیری هواپیماهای تجاری دو برابر خواهد شد.[3] باندهای فرودگاه به عنوان گلوگاه در سیستم عملیاتی شناخته می-شوند که موجب افزایش صف انتظار هواپیماها برای فرود و برخاست و به تبع آن موجب افزایش حجم ترافیک هوایی،تاخیرات پروازی، افزایش هزینههای سوخت و آلودگی زیستمحیطی میشوند.[4] از طرفی افزایش تقاضای حمل و نقل هوایی موجب افزایش حجمکاری کنترلکننده برج مراقبت میگردد. این افزایش حجمکاری بخصوص در ساعات اوج ترافیک هوایی که گنجایش ناحیه کنترل ترمینال - TCA - 1 در حال پر شدن است، رشد مییابد. اینامر حداقل در ارتباط با فرودگاههای بزرگ اروپایی که با مشکل محدودیت ایجاد زیر ساختهای لازم روبرو هستند، وجود خواهد داشت.[5] بنابراین یک راهمقرون به صرفه و مناسب برای افزایش ظرفیتهای موجود، بهبود در برنامهریزی سیستم فرود و برخاست خواهد بود[6]
.2 بیان مساله
مساله زمانبندی فرود هواپیما - ALSP - 2 یکی از مهمترین بخش هایی است که کنترلکنندگان برج مراقبت با آن روبرو می شوند. زمانیکه هواپیما وارد محدوده رادار فرودگاه میشود، خلبان اطلاعاتی از قبیل شماره پرواز، ارتفاع و سرعت را به کنترلکننده برج مراقبت مخابره میکند.[7] مساله زمان بندی فرود هواپیما زمانی اهمیت پیدا میکند که در یک فرودگاه شلوغ و در لحظات اوج ترافیک، کنترلکننده برج مراقبت بخواهد برنامهریزی موثر و کارا و با سرعت محاسباتی بالا انجام دهد.[8]مساله زمانبندی فرود هواپیما در حالت چندباند را میتوان با مسائل ماشینهای موازی یکسان3 معادل سازی نمود.[9] در واقعALSP عبارت است از برنامهریزی فرود آمدن مجموعهای از n هواپیما برروی m باند با توجه به محدودیت پنجره زمانی4 و همچنین زمانجداسازی بین هواپیماها.5 در این رابطه، باندها به عنوان ماشینها و هواپیماها به عنوان کارها فرض میشوند.
هر هواپیما که به عنوان یک کار شناخته میشود دارای یک زودترین زمان فرود6 و یک دیرترین زمان فرود7 خواهد بود. زودترین زمان فرود زمانی است که هواپیما با بیشترین سرعت خود حرکت نماید و در زودترین زمان ممکن بتواند فرود آید. این زمان معرف زمان در دسترس بودن8 هر کار - هواپیما - میباشد. دیرترین زمان فرود نیز زمانی میباشد که هواپیما تمام سوخت خود را مصرف کرده و فرود آید این زمان معرف آخرین مهلت9 هر کار - هواپیما - می باشد. در این پنجره زمانی، زمان هدف قرار دارد و در ایده آلترین حالت هواپیماها باید در این زمان فرود آیند تا تاخیر و تعجلی توسط هواپیماها صورت نگیرد.[10]
علاوه بر محدودیت مربوط به پنجره زمانی، محدودیت حداقل زمان جداسازی بین هواپیما از مهمترین موارد در زمان-بندی فرود هواپیما میباشد. زمانی که دو هواپیما ی متوالی در حرکت میباشند برای حفظ پایداری آیرودینامیکی هواپیما و اثرات اغتشاشات جریانهای حلقوی بال10 و همچنین گازهای خارج شده از موتور جت هواپیماها11 باید یک حداقل زمان جداسازی ایمن بین هواپیماهای متوالی در نظر گرفت.این زمان جداسازی برای دو هواپیمای متوالی - با سرعت فرودثابت - با توجه به اندازه هواپیماهای متوالی - کوچک، بزرگ،متوسط - تعیین میگردد.[6] به طور مثال هواپیماهای غول پیکر آشفتگی فضایی زیادی در اطراف خود ایجاد میکنند.
در حالیکه یک هواپیمای کوچک و یا سبک، اغتشاشات و گردابه های اندکی ایجاد می کند و بنابراین فاصله جدایی ایمن بین این هواپیما و هواپیمای پشت سر آن کم خواهد شد. حداقل زمان جداسازی را میتوان معادل زمان پردازش وابسته به توالی با زمان آماده سازی صفر1 و یا زمان آماده سازی وابسته به توالی با زمان پردازش صفر2در نظر گرفت[11,9] در جدول 1 نمونه ای از حداقل زمان جداسازی بین دو هواپیمای متوالی با توجه به سایز هواپیماها بر حسب ناتیکال مایل نشان داده شده است.از این رو تلاشهایی در خصوص ساماندهی تراکم ترافیک هوایی با استفاده از سادهترین روش تعیین توالی و زمان-بندی فرود هواپیما،3FCFS صورت گرفته است.
در این روش اولین هواپیمایی که وارد محدوده رادار فرودگاهی میشود، نخستین هواپیمایی میباشد که فرود میآید .با این حال مطالعات نشاندهنده آن است که این روش به ندرت زمانبندی بهینهای را ایجاد میکند.[4,11] بنابراین وجود مشکلاتی در ارتباط با زمانبندی فرود هواپیماها، پژوهشگران را به استفاده از روشهای بهینهسازی مختلف برای حل این مساله علاقهمند کرده است. به طور کلی مسایل زمانبندی فرود هواپیما را میتوان در دو دسته استاتیک4 و داینامیک5 مورد بررسی قرار داد. در حالت استاتیک، اطلاعات کاملی از تعداد هواپیماهایی که قصد فرود دارند وجود دارد، در حالی که در حالت داینامیک تعداد هواپیماها از قبل مشخص نیست و به طور پیوسته در حال تغییر است.[12]
تحقیقات بسیاری در زمینه زمان بندی فرود هواپیما انجام شده است. نخستین تحقیقات صورت گرفته در رابطه با مسالهALSP در حالت تک باند و با هدف حداقلسازی هزینهها، توسط سارافتیس پیشنهاد داده شد. او مساله برنامهریزی فرود در فرودگاهها را با توجه به مدل کار کارگاهی ارائه داد. هدف این پژوهش، حل مساله با استفاده از برنامهریزی پویا به منظور حداقلسازی میزان خسارات ناشی از تاخیر و تعجیل فرود هواپیما بود.[13] سپس آبلا و همکاران اولین فرمول ریاضی برنامهریزی عدد صحیح مختلط را برای این مساله - با تابع هدف حداقل سازی تاخیرات - مدلسازی نمودند.[14] بیسلی و همکاران با اضافه کردن 6 نوع محدودیت اضافی به مدل ریاضی ارائه شده توسط آبلا ، مساله ALSP را گسترش داده و با استفاده از جستجوی درختی6 مساله را برای اندازه نمونه حداکثر 50 هواپیما حل نمودند.[11]
سپس بیسلی و همکاران به دنبال توسعهی مطالعهی قبلی خود مساله را در حالت داینامیک نیز بررسی نمودند.[15] محققانی مساله زمانبندی فرود هواپیما را در یک محیط انتقال موقعیت در حالت داینامیک به منظور بیشینهسازی توان عملیاتی باند در نظر گرفتند .[16] همچنین محققین دیگری مدل ریاضی عدد صحیح مختلط که بیسلی و همکاران توسعه داده بودند را با استفاده از الگوریتم ابتکاری تا اندازه نمونه 150 هواپیما و یک باند فرود حل نمودند.[10] همچنین توکلی مقدم و همکاران مساله زمانبندی فرود هواپیما را با هدف حداقلسازی حداکثر زمان فرود به صورت فازی برای تک باند ارایه دادند.[7]
در ادامه تحقیقات، مسائل در حالت تک هدفه و چند باند مورد بررسی قرار گرفت. پینول و بیزلی در یک کار تحقیقاتی با بهرهگیری از الگوریتم فراابتکاری جستجوی پراکنده7 و الگوریتم بوم شناسی8جوابهایی با کیفیت بالا را برای مسائل تا 500 هواپیما و 5باند فرود برای تابع هدف مینیممسازی هزینههای ناشی از دیرکرد و زودکرد فرود ارایه دادند.[12] صالحیپور و همکاران مساله تک هدفه ALSP را برای حالت چند باند و تابع هدف مینیممسازی کل هزینه-
