در تحقیق دیگر دینگ و همکاران (2005)، اقدام به ارائه یک روش ترکیبی با ترکیب دو روش جستجوی ممنوعه و تبرید شبیه‌سازی شده برای حل مسأله کردهاند. با بررسی بر روی مسائل نمونه کارایی روش هیبریدی نسبت به شبیه‌سازی تبرید اثبات‌شده است. البته شبیه‌سازی تبریدی ازلحاظ زمان حل عملکرد بهتری نسبت بهتری نسبت به روش هیبریدی دارد.
دورندورف و همکاران (2008) مدل ریاضی تخصیص هواپیماها به ورودی‌های مسافری را به مسأله تفکیک گروهک تبدیل کردهاند و با استفاده از الگوریتم تخلیهای زنجیرهای این مسأله را حل نمودهاند این روش بر روی یک مسأله با داده‌های واقعی اجراشده و جواب قابل‌قبولی ارائه کرده است.
درکس و نیکولینیگل (2007) با استفاده از روش شبیه‌سازی تبریدی اقدام به حل این مسأله کرده‌اند. مسائل نمونهی این تحقیق برای فرودگاهی با 20 ورودی مسافری در افق زمانی 4 ساعت و 30 دقیقه و 100 هواپیما ورودی در نظر گرفته‌شده است.
در جدیدترین تحقیقی که انجام‌شده، کومار و همکاران (2011) مدلی ارائه کردهاند که به تخصیص پویای هواپیماها به ورودیهای مسافر به‌منظور کمینه کردن هزینهها و بیشینه کردن درآمدها میپردازد و این مدل را با استفاده از زبان برنامه‌نویسی بهینه‌سازی حل کردهاند و با استفاده از این روش مسألهای به‌اندازه‌ی 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- مدل برنامه‌ریزی خطی برنامه
در این بخش به بیان مدل ریاضی مسأله خواهیم پرداخت. فرضیات موردنظر در این تحقیق عبارت‌اند از:
در هنگام فرود دو هواپیما متوالی اولین و مهمترین عاملی که یک کنترلر فرودگاهی باید در نظر بگیرد فاصله‌ی زمانی فرود دو هواپیما از یکدیگر است. دلایل حفظ این فاصله زمانی مربوط به مسائل آئرودینامیک هواپیما است. هر هواپیمایی که در آسمان در حال حرکت است یک گرداب از جریان ناپایدار هوا در پشت سرخود ایجاد می‌کند. شدت این گرداب با اندازهی هواپیما رابطه مستقیم دارد و با بزرگ‌تر شدن یک هواپیما، شدت ناپایداری این جریان افزایش می‌یابد. این جریان همچنین باکم شدن سرعت هواپیما شدت بیشتری می‌گیرد. درصورتی‌که یک هواپیما وارد این جریان ناپایدار شود، این جریان باعث برهم خوردن تعادل هواپیما میشود و حتی ممکن است باعث سقوط هواپیما شود. در هنگام فرود به دلیل اینکه هواپیما با پایینترین سرعت ممکن خود در حال پرواز است شدت‌جریان ناپایدار بیشینه خواهد بود. به همین منظور کنترلرهای فرودگاهی یک‌زمان جداسازی بین دو هواپیمای متوالی که بر روی یک باند در حال نشستن هستند در نظر می‌گیرند. در این تحقیق زمان جداسازی به‌صورت یک عدد ثابت در نظر گرفته‌شده است.
هر هواپیما دارای یک پنجره زمانی برای رسیدن به فرودگاه مقصد است. این پنجرهی زمانی شامل سه پارامتر است. اولین پارامتر زودترین زمان رسیدن هواپیما است این پارامتر بر اساس بالاترین سرعت هواپیما و فاصلهی بین دو فرودگاه محاسبه می‌شود. دومین پارامتر دیرترین زمان رسیدن هواپیما است. مدت‌زمانی که یک هواپیما با توجه به سوخت خود می‌تواند پرواز کند به‌عنوان دیرترین زمان رسیدن هواپیما در نظر گرفته می‌شود. آخرین این پارامتر زمان هدف فرود هواپیما است. این زمان، همان زمان مدنظر شرکت هواپیمایی برای فرود هواپیما است. این پارامتر توسط شرکت هواپیمایی در هنگام عقد قرارداد با فرودگاه تعیین میشود.
بعد از فرود هواپیماها در فرودگاه، بعضی از هواپیماها نسبت به دیگر هواپیما اولویت تخصیص به ورودی‌های مسافری را دارا هستند. این اولویت بستگی به نوع هواپیما و شرکت هواپیمایی دارد. به‌عنوان‌مثال یک هواپیما ایرباس A380 با بیش از 650 مسافر مطمئناً نسبت به هواپیمایی با 100 مسافر ارجحیت دارد؛ زیرا خدمت‌دهی به هواپیمای ایرباس از طریق جابه‌جایی مسافرها با اتوبوس بسیار زمانگیر است. یکی دیگر از دلایل ارجحیت یک هواپیما نسبت به هواپیمای دیگر، شرکت هواپیمایی است. به‌عنوان‌مثال در فرودگاه امام خمینی هواپیماهای خط هوایی امارت نسبت به خط هوایی ایران ایر ارجحیت دارند زیرا اصولاً مسافرین این خط هوایی تجار و دیپلمات‌ها هستند. این ارجحیت بر اساس تجربه‌ی کنترلرهای فرودگاه و با درخواست شرکت‌های هواپیمایی به دست می‌آید.
بعد از ارجحیت تخصیص هواپیما به ورودی مسافر، ارجحیت تخصیص هواپیما به یک ورودی مسافری خاص وجود دارد؛ یعنی ترجیح برای برخی از هواپیما تخصیص به یک ورودی مسافری خاص است. این ترجیح بیشتر بر اساس مبدأ هواپیما است. به‌عنوان‌مثال در فرودگاه امام خمینی هواپیمایی که از کشور مالزی وارد کشور میشوند بیشتر ترجیح داده میشود که به ورودیهای مسافری سمت شرق سالن مسافری تخصیص داده شوند. زیرابه تجربه ثابت‌شده است که مسافرین این هواپیماها مشکلات گمرکی بیشتری نسبت به دیگر مسافرین دارند؛ بنابراین در صورت بروز مشکل، برای رسیدن به انبار گمرک نباید مسافت زیادی را طی کنند.
فاصله دو هواپیما در دو ورودی مسافری مجاور یکی از محدودیت‌های ایمنی فرودگاه است. این محدودیت که تأثیر مستقیم در تخصیص دو هواپیما در مجاورت یکدیگر دارد بدین‌صورت است طبق قوانین سازمان جهانی هوانوردی فاصله دو سر بال دو هواپیمای در کنار هم پارک شده باید از یک مقدار ایمنی بیشتر باشد. این فاصله در شکل 2-1 نمایش داده‌شده است:

مطلب مرتبط :   منبع تحقیق درمورد اصحاب پیامبر (ص)

شکل 2-1- فاصله ایمنی بین دو سر بال.
این فاصله‌ی ایمنی می‌تواند باعث عدم تخصیص دو هواپیما در کنار یکدیگر شود. در بعضی از موارد حتی با حضور یک هواپیما بزرگ در یک ورودی مسافر تا دو ورودی مجاور خود را اشغال کند و امکان استفاده از آن‌ها را سلب نماید.
در این تحقیق، تابع هدف از دو بخش تشکیل‌شده است. مجموع خسارت زود کرد و یا دیرکرد هواپیماها و مجموع درآمد فرودگاه از تخصیص هواپیماها به ورودی‌های مسافری. برای ایجاد توازن بین این دو تابع هدف از یک ضریب a برای مجموع درآمد فرودگاه از تخصیص هواپیماها به ورودی‌های مسافری استفاده کرده‌ایم و از ضریب (1-a) برای خسارت زود کرد و یا دیرکرد هواپیماها استفاده‌شده است.