برنامهریزی خدمهی پروازی
برنامهریزی هواپیماها
این مسائل دارای وابستگیهای زیادی با یکدیگر هستند و عموماً خروجی یک دسته از مسائل ورودی دیگر مسائل است. به‌طور مثال خروجی برنامهریزی هواپیماها به‌عنوان ورودی مسألهی خدمهی پروازی است.
با توجه به مباحث مطرح‌شده، در این پایاننامه مسائل توالی فرود هواپیماها و تخصیص ورودیهای مسافری موردبررسی قرارگرفتهاند.
2-2- توالی فرود هواپیماها
تلاشهای زیادی در خصوص حل مسأله برنامهریزی فرود در فرودگاهها صورت گرفته است. سارافتیس (1980) برای اولین بار این مسأله را موردبررسی قرار داد و مدلی کارگاهی برای این مسأله ارائه نموده است. در این پژوهش مسائلی با اندازهی 15 هواپیما در یک فرودگاه یک باند توسط رویکرد برنامهریزی پویا حل‌شده است. ارائه چنین مدلی توجه محققین را در جهت ارائه مدلهایی باهدف حل مسأله در ابعاد بزرگ‌تر و در زمان کمتر را به خود جلب کرد.
آبلا و همکاران (1995) دو روش برای حل مسأله توالی فرود هواپیماها ارائه کردهاند یک روش با استفاده از الگوریتم ژنتیک است و روش دیگر شاخه و برگ است که با فرموله کردن مسأله به‌صورت برنامهریزی عددی آمیخته امکان استفاده از این روش را در مسأله مهیا کرده‌اند. در این تحقیق مسائلی تا اندازهی 25 هواپیما با دو باند فرود حل‌شده است. در این تحقیق بیان‌شده است که الگوریتم‌های تقریبی بر روی مسائل کوچک عملکرد قابل‌قبولی دارند درحالی‌که روشهای دقیق زمان‌گیر است.
سیسلکی و همکاران (1998)، نشان دادند که استفاده از الگوریتم ژنتیک برای مسائل زمان‌بندی فرود هواپیماها برای دادههای فرودگاه سیدنی در شلوغترین روز سال باعث پیدا کردن جواب‌های باکیفیتی میشود. همچنین در این تحقیق توانستند با واردکردن اطلاعات هواپیماها در هر بار تولید نسل، الگوریتم ژنتیکی برای مسائل توالی فرود هواپیماها به‌صورت پویا ارائه کنند.
ارنست و همکاران (1998) اقدام به حل این مسأله برای چند باند با استفاده از یک روش دقیق و دو روش ابتکاری کردند. روش دقیق ارائه‌شده در این تحقیق روش سیمپلکس است که با استفاده از یک توالی فرود تولیدشده کار می‌کند. روش جستجوی فضای جواب و روش شاخه و برگ نیز برای حل مسائلی با 10 الی 44 هواپیما و دو الی چهار باند فرود استفاده‌شده‌اند. در پایان این تحقیق به بررسی عملکرد سه الگوریتم پرداختهاند که نتایج این بررسی کارایی بهتر روش دقیق را نمایش میدهد.
بیلسی و همکاران (2000) توانستند با ارائه یک مدل عدد صحیح آمیخته برای مسأله توالی فرود هواپیماها، مسائلی با اندازه 50 هواپیما و 4 باند فرود را با روش جستجوی درخت حل کنند. نتایج این تحقیق کارایی این الگوریتم در حل سریع مسائل را اثبات کرده است.
تلاشهای زیادی برای حل مسأله توالی فرود هواپیماها در ابعاد مختلف شده است و در سالهای اخیر، یواپینگ و همکاران (2008) اقدام به حل توالی فرود هواپیماها با دو تابع هدف کمینه کردن هزینهها و تأخیرها نمودهاند، یکی از نوآوریهای مهم این تحقیق ایجاد تفاوت بین هواپیماها بوده است.
بنشیخ و همکاران (2009) یک روش ترکیبی برای حل این مسأله ارائه کردهاند. روش ترکیبی ارائه‌شده در این تحقیق ترکیب الگوریتم ژنتیک و الگوریتم کلونی مورچه‌ها است که مسائلی تا ابعاد 50 هواپیما و 4 باند فرود را حل می‌کند. در این تحقیق جواب‌های خروجی الگوریتم ترکیبی ازلحاظ زمان و کیفیت با جواب دقیق مسأله مقایسه کردهاند که عملکرد قابل‌قبولی داشته است.
بویسن و فلیدنر (2010) مسألهی توالی فرود هواپیماها را با توجه به ایجاد توازن کار برای نیروهای فرودگاهی بررسی کردهاند. در این تحقیق توابع هدف جدیدی همچون تعداد مسافرین فرود آمده، تعداد فرودهای هواپیماهای یک شرکت هواپیمایی و تعداد مسافرین فرود آمده از یک شرکت هواپیمایی معرفی‌شده‌اند.
شنگ پنگ و همکاران (2011) اقدام به ارائه‌ی روشی کردهاند که مسأله توالی فرود هواپیماها را در کمتر از 4 ثانیه حل می‌کند این روش بر روی 6 مسأله نمونه با اندازه‌ی 50 هواپیما و 7 مسأله نمونه با اندازه‌ی 500 هواپیما مورد آزمایش قرارگرفته است. ازآنجایی‌که تصمیم‌گیری در مورد تعیین توالی فرود هواپیماها در دنیای امروزی باید سریع انجام گیرد این روش وسیله‌ای برای تصمیم‌گیری آنی در مورد این نوع مسأله است و به‌نوعی امکان استفاده از این نوع برنامهریزی را در فرودگاهها فراهم آورد. روش پیشنهادی این تحقیق بر پایه‌ی Cellular Automata Optimization است. محققین به ارزیابی این الگوریتم در مقایسه با الگوریتم‌های موجود در ادبیات پرداختهاند و با استفاده از 13 مسأله نمونه ذکرشده، برتری الگوریتم پیشنهادی را اثبات کردهاند.
2-3- تخصیص ورودیهای مسافری
تخصیص ورودیهای مسافری به هواپیماهای ورودی یکی دیگر از مسائل مطرح در عرصهی هوانوردی است. تخصیص هواپیماها به ورودیهای مسافری سالن فرودگاه، میبایست قبل از فرود هواپیما برنامهریزی شود. وظیفهی این برنامهریزی با کنترلر فرودگاه است. برای بهبود بخشیدن به این برنامهریزی محققین در این زمینه تحقیقاتی انجام دادهاند که در زیر به بررسی آن‌ها پرداخته‌شده است.
حقانی و چین چن (1998) به ارائه یک روش ابتکاری برای حل مسأله تخصیص هواپیماها به ورودیهای مسافری نمودهاند. تابع هدف این الگوریتم کمینه کردن مسافت پیاده‌روی مسافرین در سالن فرودگاه است. این الگوریتم برای مسائلی از 3 هواپیما با 2 ورودی مسافری الی 30 هواپیما و 7 ورودی مسافری حل‌شده و سپس با مقدار تابع هدف بهینهی این مسائل مقایسه شده است. در تمام مسائل مطرح‌شده الگوریتم پیشنهادی جواب بهینه داده است.
بولات (2001) یک مدل برنامهریزی خطی باهدف کمینه کردن زمان بیکاری ورودیهای مسافری ارائه کرده است و شرایطی برای به دست آوردن جواب بهینه در زمان چندجمله‌ای بیان کرده است. همچنین یک الگوریتم فرا ابتکاری بر پایه الگوریتم ژنتیک برای حل این مسأله ارائه کرده است که کارایی آن با مسائلی از 26 تا 106 هواپیما موردبررسی قرارگرفته است.
یان و هیو (1999)، به ارائه یک مدل ریاضی صفر و یک با توابع هدف کمینه کردن زمان انتظار مسافرین و میزان پیادهروی مسافرین کردهاند. سپس به مقایسه عملکرد 4 روش وزنی ، تولید ستون ، روش سیمپلکس و شاخه و حد کردهاند. از دادههای فرودگاه چیانگ کی شک برای مقایسه روش‌ها استفاده‌شده است. الگوریتم تولید ستون نسبت به دیگر روش‌ها کارایی بهتری داشته است.
خو و بیلی (2001)، یک مدل صفر و یک‌خطی شده برای تخصیص هواپیما به ورودی مسافری ارائه کرده‌اند. در این تحقیق از الگوریتم فرا ابتکاری جستجوی ممنوعه استفاده‌شده است و تمام پارامترهای این روش بررسی و مقداردهی شدهاند. مسائل نمونه‌ی این تحقیق را تا 50 ورودی مسافری بررسی کردهاند. در تمام این بررسی‌ها کارایی الگوریتم جستجوی ممنوعه ازلحاظ زمان و مقدار خطا نسبت به روشهای دقیق اثبات‌شده است.
تابع هدفی که در این تحقیق موردبررسی قرارگرفته است بیشینه کردن تعداد هواپیماهای تخصیص‌یافته به ورودی‌های مسافری است. در این زمینه دینگ و همکاران (2004) مدلی ارائه کردهاند که علاوه بر این تابع هدف، به کمینه‌سازی میزان پیاده‌روی مسافرین در سالن نیز می‌پردازد. در این تحقیق از دو الگوریتم جستجوی ممنوعه و الگوریتم حریصانه استفاده‌شده است. از الگوریتم حریصانه برای کمینه کردن تعداد هواپیماهای تخصیص نیافته به ورودی مسافری استفاده‌شده است و از جواب نهایی این الگوریتم به‌عنوان جواب اولیه الگوریتم جستجوی ممنوعه استفاده‌شده است.