ارائه‌‌ی روشی نوین برای کنترل هوشمند فرود هواپیماها در فرودگاه‌های متراکم

نوع مقاله: مقاله علمی فارسی

نویسندگان

1 دانش‌آموخته‌ی کارشناسی‌‌‌ارشد مهندسی برق، دانشگاه آزاد اسلامی واحد گناباد- گناباد- ایران

2 - دانشیار، دانشکده مهندسی برق وکامپیوتر- دانشگاه بیرجند- بیرجند- ایران

3 استادیار، دانشکده مهندسی برق وکامپیوتر- دانشگاه بیرجند- بیرجند- ایران

چکیده

امروزه با توجه به مزایای متعدد سفرهای هوایی از جمله راحتی، آسایش، سرعت و امنیت بالا، ترافیک هوایی رشد چشمگیری داشته است و انتظار می‌رود این نرخ رشد در سال‌های آینده فزآینده‌تر شود. تراکم ترافیک هوایی و محدودیت‌های مختلف در توسعه‌ برخی فرودگاه‌ها سبب شد که مسأله‌ کنترل فرود هواپیماها به‌عنوان یکی از مهم‌ترین مسائل مطرح در حوزه‌ حمل‌ و ‌‌نقل هوایی، توجه بسیاری از پژوهشگران را به خود معطوف سازد. در این مقاله، در قالب یک رویکرد هوشمند نوین با اعمال دانشی غنی و مؤثر به فرآیند بهینه‌سازی (برای افزایش سرعت همگرایی و قابلیت حذف پاسخ‌های غیربهینه‌ بدیهی)، از الگوریتم Particle Swarm Optimization with Constriction Coefficient (CPSO) برای مسأله‌ کنترل هوشمند فرود هواپیماها استفاده شده است. نتایج شبیه‌سازی‌ها نشان می‌دهند که در مقایسه با روش‌های قدرتمند ارایه شده‌ قبلی، از جمله روش‌های مبتنی بر الگوریتم‌های ژنتیک، بیونومیک، جستجوی Scatter و GLS، کمینه‌سازی مجموع تأخیرهای پروازی (هدف اساسی بهینه‌سازی) به بهترین نحو ممکن تحقق یافته است. به ‌دست آمدن مجموع تأخیرهای پروازی صفر برای دو مسأله با داده‌های واقعی فرودگاه دالاس فورت ورث تگزاس، بیانگر قابلیت بیشتر رویکرد هوشمند پیشنهادی در مقایسه با سایر روش‌‌ها در یافتن پاسخ بهینه برای مسأله است.

کلیدواژه‌ها


عنوان مقاله [English]

A New Intelligent Airplane Landing Planning Method in Congested Airports

نویسندگان [English]

  • Kazem Dastgerdi 1
  • Nasser Mehrshad 2
  • Mohsen Farshad 3
1 Dept. of Electrical Engineering, Islamic Azad University of Gonabad, Gonabad, Iran
2 Dept. of Electrical Engineering, University of Birjand, Birjand, Iran
3 Dept. of Electrical Engineering, University of Birjand, Birjand, Iran
چکیده [English]

Nowadays considering many advantages of air traveling, we notice that traffic congestion has significantly increased in airspace of countries, and it is expected that this growth rate, increases even more in the forthcoming years.This growth rate and different limitations posed on developing some airports led to the problem of landing airplanes to become one of the most important issues formed in the field of aviation. In this paper, in the form of a new approach based on CPSO algorithm for intelligent landing planning, determining optimal landing times, optimal allocation of runways, and at last the order of successive landings of planes has been done in a way that appropriately fulfills the main goal of the problem (minimizing the total flights delays) thus helping significantly to controlling air traffic congestion in airports approaches. The simulation results show that compared to the last presented methods, including methods based on genetic algorithms, GLS and Bionomic, has decreased the total amounts of flight delays considerably. Getting zero for total amount of flight delays for the two problems with real data of DFW airport in Texas, United States, confirms the more capability of CPSO algorithm compared to the other intelligent methods for obtaining optimal solutions to the problem.

کلیدواژه‌ها [English]

  • Airplane Landing Planning
  • PSO
  • Total Delay Minimizing
  • Landing Constrainسt

با توجه به روند رو‌ به ‌رشد تراکم ترافیک هوایی در سال‌های اخیر و پیش‌بینی رشد فزآینده‌ آن در دهه‌های آینده، ارایه‌ راهکارهای مؤثر، کارآمد و ایمن در زمینه‌ کنترل ‌ترافیک‌ هوایی، یکی از چالش‌های پیش روی دست‌اندرکاران حمل و نقل هوایی است. تراکم ترافیک هوایی، به‌‌علت عدم تعادل مناسب بین تقاضاهای حمل و نقل هوایی و ظرفیت ترافیک هوایی در مسیرها، سکتورها، فضای ترمینال‌ها و فرودگاه‌ها، ایجاد شده و عدم ساماندهی مناسب آن می‌تواند باعث تأخیرهای پروازی زیاد، افزایش میزان سوخت مصرفی هواپیماها، ایجاد هزینه‌های اضافی برای شرکت‌های هواپیمایی، آلودگی‌های زیست محیطی و خطاهای عملیاتی در واحدهای کنترل ترافیک شود [1- 3]. روند رو‌ به‌ رشد تراکم ترافیکی و مشکلات متعدد ناشی از آن سبب شد که مسئولان و کارشناسان صنعت هوانوردی به‌ دنبال راهکارهایی عملی و مناسب برای مدیریت و کنترل بهینه‌ ترافیک هوایی در بخش‌های مختلف عملیات پروازی باشند، که یکی از مهم‌ترین این بخش‌ها مربوط به مسأله‌ فرود هواپیماهاست (ALP) [1][4]. بدیهی ‌است کارکنان کنترل ترافیک هوایی فرودگاه‏ها با کم بودن تعداد هواپیماهای موجود در محدوده‌ تحت پوشش راداری یک فرودگاه یا زیاد‌ بودن فاصله‌ زمانی بین زمان‌های برنامه‌ریزی شده فرود پروازها (PLT) [2]، به‌‌راحتی بتوانند برنامه‌ریزی ساده و مناسبی را برای فرود هواپیماها انجام دهند. اما اگر تراکم ترافیکی در فضای هوایی تحت کنترل از حد مشخصی تجاوز کند، با توجه به NP-hard بودن‌ مسأله‌ زمان‏بندی فرود هواپیماها (ALS) [3] و مشخصه‌ غیرخطی و غیر‌محدب تراکم ترافیکی، کنترلر در اداره و کنترل بهینه‌ ترافیک هوایی با مشکلات متعددی مواجه خواهد شد [5 و 6]. مشکل مهم پیش‌ روی کنترلر در این شرایط، حجم ‌کاری بالا و پیچیدگی‌های محاسباتی در پیدا کردن پاسخ‌های بهینه برای مسأله بوده، که ممکن است سبب عدم اتخاذ تصمیمات درست در زمان مناسب شود [7]. از طرفی راهکارهایی چون ساخت باندهای جدید در فرودگاه‌ها یا احداث فرودگاه‌های جدید، می‌توانند آخرین راه‌حل‌ها برای مسأله‌ باشند که این راه‌حل‌ها نیز بسیار پر‌هزینه، زمان‌بر و با محدودیت‌های فراوان مواجه است. برای مثال ممکن است در یک فرودگاه، قابلیت توسعه‌ سطوح پروازی و احداث باندهای جدید وجود نداشته باشد. بنابراین، در بیشتر پژوهش‏های اخیر، پژوهشگران درصدد استفاده‌ بهینه از ظرفیت‌های موجود در فرودگاه‌‌ها برای کمینه کردن مجموع تأخیرهای پروازی و به‌طور هم‏زمان بیشینه کردن تعداد پذیرش هواپیماها در فرودگاه‌ برآمده‌اند.

برای حل مشکلات تراکم ترافیک هوایی، در ابتدا روش‌های سعی و خطا با استفاده از نرم‌افزارها و شبیه‌سازهای رایانه‌ای مورد توجه قرار گرفتند. اگر چه استفاده از این سامانه‌های برنامه‌ریزی کمک مؤثری برای حل مسأله‌ ترافیک هوایی بود، اما در عین حال یک روش کنترل بهینه محسوب نمی‌شد. همین امر سبب شد که در ادامه توجه پژوهشگران به استفاده از الگوریتم‌های مختلف جستجوی ابتکاری برای یافتن پاسخ بهینه برای مسأله معطوف شود. از این‌ رو برای مسأله‌ ALS چندین روش بهینه‌سازی مختلف مطرح شد. مقایسه‌ نتایج حاصل از شبیه‌سازی روش‏‌های مختلف بهینه‌سازی مطرح شده در این زمینه، نشان دادند که این روش‌ها و روش‏‌های بهینه‌سازی مختلف دارای عملکردها و نتایجی متفاوت هستند‏.

در سال 1999 Cheng و همکارانش چهار شیوه‌ جستجوی ژنتیکی را برای مسأله فرود هواپیماها ارایه کرد‏ند [8]. سپس، توصیفی کلی از مدل، اهداف و فرمولاسیون ریاضی مسأله‌ ALS، توسط Beasley و همکارنش ارایه شد [9]. علاوه بر این، مطالعات زیادی در زمینه برنامه‌ریزی و تعیین ترتیب‌ فرودهای متوالی، به‌ حداقل رساندن انحراف زمانی زمان‌های به دست آمده از مسأله ‌‌‌‌زمان‌بندی از زمان‌های تخمینی فرود [10 -13]، کاهش زمان اجرای برنامه‌ریزی [13- 15] و کاهش هزینه‌ سوخت هواپیماها با اختصاص زمان‌های بهینه برای فرود هواپیماها [16] انجام شد. Hansen با استفاده از چهار شیوه‌ جستجوی ژنتیکی مطرح شده توسط Cheng و همکارانش، و Hu و Paolo با به‌ کار بردن یک الگوریتم ژنتیک مؤثر با استفاده از تزویج یکنواخت و با رویکرد به ‌‌حداقل رساندن مجموع تأخیرهای پروازی، راهکارهایی مفید را در زمینه‌ زمان‌بندی و تعیین ترتیب‌های فرود هواپیماها (ALSS) [4] ارایه کرد‏ند [5 و 17]. در ادامه با توجه به اهمیت بالای مسأله‌ برنامه‌ریزی فرود هواپیماها، Tang و همکارانش الگوریتم تکاملی MONSDE[5]، Salehipour و همکارانش الگوریتم VND[6]، Yu و همکارانش الگوریتم CAO[7] را برای کنترل هوشمند فرود هواپیماها ارایه کرد‏ند [18- 20]. در استفاده‌ ترکیبی از الگوریتم‌های بهینه‌سازی مختلف برای حل مسأله‌ فرود هواپیماها نیز، Jia و همکارانش الگوریتمCSA-RHC[8] را معرفی کرد‏ند، که در طراحی این الگوریتم از روش‏‌های EGSS[9] برای سرعت بخشیدن به روند همگرایی الگوریتم و IFD[10] برای هدایت مؤثر فرآیند بهینه‌سازی استفاده شده بود [21]. از دیگر روش‌های ترکیبی در این زمینه می‌توان به روش ترکیبی ارایه شده توسط Bencheikh و همکارانش که مبتنی بر دو الگوریتم‌ ژنتیک و ACO[11] بود، اشاره کرد‏ [22]. در بحث تأثیر تأخیرهای پروازی بر هزینه‌های شرکت‌های هواپیمایی، Forbes در پژوهشی میزان تأثیر هر دقیقه تأخیر پروازی انجام شده‏ در نشست و برخاست هواپیماها را بر هزینه‌ها در صنعت حمل ‌و ‌نقل هوایی بررسی کرد [23].

در این مقاله، با توجه به اهمیت بالای موضوع ALS، در قالب رویکردی نوین به ارایه‌ راهکارهایی مؤثر و کارآمد برای مسأله‌ ALSS پرداخته شده، که این راهکار‏ها به کنترل بهینه‌ تراکم ترافیکی در فضای تحت کنترل ترمینال (TCA) [12] منجر می‏شود. این کار با استفاده از یک فرآیند برنامه‌ریزی هوشمند شامل عملیات تخصیص باند، زمان‌بندی فرود و تعیین ترتیب فرودهای متوالی با رعایت ضوابط خاص جدایی ایمن بین فرودهای متوالی انجام شده است. ادامه‌ این مقاله این‏گونه سازماندهی شده است: در بخش دوم فرمول‌بندی ریاضی مسأله آورده شده است. در بخش سوم شرح مختصری از الگوریتم CPSO ارایه شده، که برای نخستین‏ بار برای مسأله‌ فرود هواپیماها به کار گرفته شده است. در ادامه در بخش چهارم به بیان رویکرد‌ هوشمند پیشنهادی برای کنترل بهینه‌ فرود هواپیماها پرداخته می‌شود. در بخش پنجم به ارایه‌ نتایج حاصل از شبیه‌سازی روش‌ هوشمند پیشنهادی با داده‌های واقعی و مقایسه‌ی آن با نتایج روش‌های بهینه‌سازی انجام شده‏ در گذشته پرداخته شده و سرانجام در بخش ششم جمع‌بندی و نتیجه‌گیری آورده شده است.

 

1- فرمول‌بندی ریاضی مسأله

زمان‌های تخمینی برنامه‌ریزی شده‌ برای فرود هر هواپیما می‌تواند یکی از شاخص‏‏های مهم و اساسی در برنامه‌ریزی فرود هواپیماها باشد. هر چه زمان‌های حاصل از برنامه‌ریزی به این زمان‌های تخمینی نزدیک‌تر باشند، تأخیرهای پروازی کمتر خواهند بود. از این رو بر اساس فرمول‌بندی ارایه شده توسط Salehipour و همکارانش [19] و با هدف انجام یک برنامه‌ریزی مؤثر با کمینه‌ مجموع تأخیرهای پروازی، با تعریف متغیرهای زیر به تحلیل‏‏ ریاضی مسأله پرداخته می‌شود:

: تعداد هواپیماهایی که قصد عملیات فرود در یک فرودگاه متراکم را دارند.

: تعداد باندهای عملیاتی فرودگاه.

: زمان برنامه‌ریزی شده (زمان تخمینی فرود) برای فرود هواپیمای  در باند  

: زمان تخصیص یافته‌ (حاصل از برنامه‌ریزی) برای فرود هواپیمای  در باند  : حداقل زمان جدایی ایمن مورد نیاز که باید بین هواپیمای  و هواپیمای در هنگام عملیات فرود و در فضای هوایی تحت ‌‌‌‌کنترل در نظر گرفته شود.

: تأخیر هواپیمای  برای فرود در باند

با در نظر گرفتن این متغیرها، برای آنکه پاسخ‌های به‌ دست آمده برای مسأله معتبر باشند، باید حدود و شروط زیر در نظر گرفته شوند:

(1)

 

شاخص مربوط به تعیین ترتیب فرود هواپیماها با استفاده از رابطه (2) محاسبه می‌شود. این شاخص به‌ گونه‌ای تعریف شده، که خواص بیان شده در رابطه‏های‏ (3) و (4) را دارا باشد.

(2)

 

(3)

 

(4)

 

 

شاخص مربوط به تعیین باند مشترک برای دو هواپیمای ام و ام در رابطه (5) تعریف شده است. با دقت در این رابطه مشخص می‌شود که این شاخص خاصیت یاد شده در رابطه (6) را داراست.

(5)

 

(6)

 

شاخص ارتباط دهنده‌ هواپیمای ام به باند ام توسط رابطه (7) بیان شده که خواص یاد شده در رابطه‏های‏ (8) و (9) را نیز داراست.

 

(7)

 

(8)

 

(9)

 

 

شاخص‏‏ مهم دیگری که در برنامه‌ریزی عملی نیز در نظر گرفته می‌شود، حداقل جدایی ایمن بین فرودهای متوالی  است. در نظر گرفتن این شاخص‏‏ مهم برای حفظ پایداری آیرودینامیک هواپیماهای بعدی در اثر اغتشاشات[13] تولید شده توسط هواپیماهای قبلی در عملیات فرود است [24]. از این رو با توجه به نوع هواپیماها و بر اساس استانداردهای FAA[14] باید در برنامه‌ریزی، بین فرودهای متوالی سه نوع هواپیمای Small (S)، Large (L) و Heavy (H) از حداقل جدایی ایمن[15] مناسب استفاده کرد‏ [25].

 

2- الگوریتم هوشمندCPSO

الگوریتم PSO یک الگوریتم مبتنی بر هوش ‌جمعی است، که نخستین‏ بار در سال 1995 توسط James Kennedy و Russell Eberhart با الهام از رفتار اجتماعی و جنبش پویای پرندگان و ماهی‌ها ارایه شد [27 ‚26]. در این روش جستجو برای الگوی حرکت جمعی پرندگان، گروهی از پرندگان که در واقع هر کدام یک جواب مسأله هستند‏ در یک فضای جستجوی مشخص پخش شده و هدف موقعیتی است که غذا در آن وجود دارد. هر پرنده در این الگوی حرکت جمعی برای یافتن غذا، همانند یک "ذره" در بین گروهی از ذرات است‏. تابع برازشی، مقدار شایستگی هر ذره را ارزیابی کرده و هر ذره که در فضای جستجو به هدف نزدیک‌تر باشد، شایستگی بیشتری خواهد داشت. هر ذره دارای سرعت بوده و با دنبال کردن بهترین ذرات به حرکتش در فضای جستجو ادامه می‌دهد. در PSO تغییر مکان ذرات جاری شده در فضای جستجو، تحت تأثیر تجربه و دانش خود ذرات و همسایگانشان است. بنابراین، موقعیت و شایستگی دیگر ذرات روی روند جستجوی یک ذره اثر می‌گذارند. نتیجه‌ی مدل‌سازی این رفتار اجتماعی، فرآیند جستجویی است که ذرات به سمت یک سری موقعیت‌های برتر از نظر برازندگی هدایت می‌شوند. ذرات از یکدیگر می‌آموزند و بر مبنای دانش به دست آمده، به سمت موقعیت بهترین همسایگانشان هدایت می‌شوند. بنابراین، اساس کار PSO بر این اصل استوار است که در هر لحظه، هر ذره مکان خود را در فضای جستجو با توجه به بهترین مکانی که تاکنون در آن قرار گرفته و بهترین مکانی که در همسایگی‌اش وجود دارد، تنظیم می‌کند. این عملکرد را می‌توان در قالب 6 مرحله زیر برای یک الگوریتم PSO استاندارد در نظر گرفت [28].

1- مقداردهی اولیه سرعت‌ها و موقعیت‌ها: مقداردهی اولیه جمعیتی از ذرات با سرعت و موقعیت‌های تصادفی در فضایN بعدی مسأله با استفاده از یک تابع توزیع یکنواخت.

2- ارزیابی برازندگی ذرات: ارزیابی مقدار برازندگی هر ذره. به‌عنوان مثال بیشینه‌سازی یا کمینه‌سازی یک تابع هدف در یک مسأله‌ بهینه‌سازی.

3- مقایسه برازندگی هر ذره با personal best (pbest).

4- مقایسه برازندگی هر ذره با global best (gbest)، که همان بهترین ذره در بین تمام ذرات است.

5- به ‌روز رسانی[16] سرعت‌ها و موقعیت‌ها.

اگر ذرهام در تکرار  دارای بردار موقعیتی به شکل  و بردار سرعتی به‌‌ شکل  باشد، آن‏گاه سرعت و مکان هر ذره با استفاده از معادلات زیر به ‌روز می‏‏شود:

 

(10)

 

(11)

 

 

که در آن  نشان ‌دهنده‌ ذرات جمعیت،  موقعیت ذره،  سرعت ذره،  بهترین موقعیت تجربه شده و بهترین موقعیت به‌ دست ‌آمده در بین تمامی جمعیت ذرات است. برای تغییر سرعت ذره به  و  از ثابت‌های مثبت شتاب  و  که به ‌ترتیب ضرایب یادگیری خودی و یادگیری اجتماعی هستند، استفاده شده است. اعداد  و  نیز اعداد تصادفی (مستقل) بوده، که دارای مقداری بین صفر و یک هستند‏ [29].

6- بازگشت به مرحله‌ 2 تا فراهم‌ آمدن شرایط توقف. شرایط توقف می‌تواند سپری ‌شدن تعداد معینی از تکرارها یا رسیدن به حد مطلوبی از جواب باشد.

پس از معرفی نسخه‌ی اولیه‌ الگوریتم PSO برای بهبود توانایی کاوش در فضای جستجو، تولید جواب‌هایی با کیفیت بالاتر و کنترل سرعت همگرایی الگوریتم، با تغییر و توسعه‌ الگوریتم PSO استاندارد و استفاده از constriction coefficient به‌عنوان یک نتیجه از تجزیه و تحلیل نظری دینامیک ازدحام، الگوریتم CPSO توسط Clerk و Kennedy ارایه شد. با تغییر معادله‌ (10) که بیانگر به‌ روز رسانی سرعت ذره در الگوریتم PSO استاندارد است و اعمال شاخص‏‏ χ برای تضمین همگرایی الگوریتم، می‌توان به یک الگوریتم CPSO دست یافت [30- 32]. با استفاده از CPSO دامنه‌ نوسان ذرات کاهش می‌یابد، که این امر به همگرایی الگوریتم در طول زمان منجر می‌شود. بنابراین، در CPSO سرعت و موقعیت هر ذره با استفاده از رابطه‏های‏ زیر به‌ روز می‌شود.

 

(12)

 

(13)

 

 

که در آن χ (constriction coefficient) به‌عنوان ضریبی متأثر از  و ، از طریق رابطه‌ (14) قابل تعریف است‏.

(14)

 

 

 

3- معرفی رویکرد هوشمند پیشنهادی

برای حل هر مسأله‌ بهینه‌سازی با الگوریتم‌های جستجوی ابتکاری، به تابع برازندگی خاصی نیاز است‏. تابع برازندگی، با توجه به اهداف از پیش تعیین شده برای مسأله‌ تعیین می‌شود. هدف از تحلیل‏‏ مسأله‌ ALS ارایه‌ راهکارهایی مؤثر برای کنترل تراکم ترافیکی در یک فرودگاه متراکم به‌ گونه‌ای است، که راهکار کنترلی پیشنهادی کم‏ترین مجموع تأخیرهای پروازی را نتیجه دهد. بدیهی است هر پاسخی از برنامه‌ریزی انجام شده‏ که به تأخیرهای پروازی کمتری منجر شود، از برازندگی بیشتری برخوردار خواهد بود. بنابراین، تابع هدف در نظر گرفته شده برای این مسأله، به‌‌ شکل زیر قابل تعریف است‏:

(15)

 

(16)

 

 

که در این رابطه‏ها‏  تأخیر هواپیمای  برای فرود در باند بوده و  و به ‌ترتیب زمان‌های تخمینی (برنامه‌ریزی شده) و تخصیص یافته‌‌ حاصل از برنامه‌ریزی هوشمند برای فرود هواپیمای  در باند هستند‏.

برنامه‌ریزی هوشمند شامل تخصیص باند، زمان‌بندی فرود و تعیین ترتیب فرودهای متوالی با رعایت استاندارهای خاص حداقل جدایی ایمن بین فرودهای متوالی است. داده‌های ترافیکی مسأله شامل شناسه‌ پروازها، تعداد و نوع هواپیماها (S, L, H)، تعداد باندهای عملیاتی فرود و زمان‌های تخمینی (برنامه‌ریزی شده) برای فرود هر هواپیما در هر باند است‏. فرآیند‏‏ هوشمند پیشنهادی بدین گونه است که در ابتدا توسط الگوریتم‌ هوشمند به هر یک از پروازها یک باند به‌‌ شکل تصادفی تخصیص داده شده و سپس، پروازهای مربوط به هر باند با توجه به زمان‌های تخمینی فرود و به‌ شکل صعودی مرتب می‌شوند. در مرحله بعد بر طبق مقادیر ارایه شده در جدول‌ (1)، حداقل جدایی ایمن بین فرودهای متوالی بررسی می‌شود. اگر زمان‌های برنامه‌ریزی شده برای فرود به گونه‌ای باشد که این حداقل جدایی ایمن رعایت نشده باشد، متناسب با مقادیر جدول (1) فرود برخی پروازها با تأخیر مواجه می‌شود.

 

جدول (1): حداقل زمان جدایی ایمن بین فرودهای متوالی هواپیماهای مختلف [5، 8 و 33].

Trailing Traffic

حداقل زمان جدایی ایمن مورد نیاز (در واحد زمانی)

Heavy

Large

Small

1

1

1

Small

Leading Traffic

1

5/1

5/1

Large

1

5/1

2

Heavy

 

برای مثال اگر هواپیمای اول هواپیمایی H همچون بوئینگ 747 و هواپیمای بعدی یک هواپیمای S همچون Islander باشد، در این‌ صورت باید در برنامه‌ریزی هوشمند دو واحد زمانی جدایی، بین این دو پرواز در نظر گرفته شود. پس از تعیین برازندگی یک تخصیص، با سپری شدن تعداد مشخصی از مراحل تکرار؛ الگوریتم CPSO به دنبال یافتن پاسخی با کمینه‌ مجموع تأخیرهای پروازی خواهد بود.

 

4- نتایج شبیه‌سازی‌ها

 در این بخش به شبیه‌سازی رویکرد هوشمند پیشنهادی برای چهار مسأله‌ی ترافیکی مختلف مربوط به فرودگاه DFW[17] در تگزاس ایالات متحده پرداخته شده و سپس، نتایج شبیه‌سازی‌ها، با نتایج روش‌های بهینه‌سازی انجام شده‏ قبلی مقایسه شده است [5].

 

 

4-1-  مسأله‌ ترافیکی اول

امروزه برخی از فرودگاه‌های شلوغ و پرترافیک، دارای چند باند مجزا برای عملیات فرود هواپیماها هستند‏. در برخی فرودگاه‌ها این باندها به‌ شکل موازی، مایل و یا ترکیبی از این دو نسبت به یکدیگر واقع شده‌اند. با توجه به جدول (2) در ابتدا به بررسی مسأله‌ای با سه باند فرود پرداخته شده، که 12 هواپیما با توجه به زمان‌های تخمینی فرود‌شان قصد عملیات فرود را دارند. نوع هر هواپیما و زمان تخمینی فرود آن‏ها در هر یک از این سه باند، بر اساس جدول (2) مشخص شده است. بیان این نکته ضروری است که مقادیر عددی حداقل فاصله‌ ایمن بین هواپیماها و زمان‌های تخمینی فرود در داده‌های ترافیکی، به شکل‏‏ واحدهای زمانی بوده و هر واحد زمانی بسته به فرودگاه و شرایط مختلف در حوزه‌ی عملیات هوانوردی، می‌تواند به شکل‏‏ فواصل زمانی 2 دقیقه‌ای، 5 دقیقه‌ای و غیره در نظر گرفته شود.

 

جدول (2): ‌زمان‌های تخمینی فرود 12 هواپیما برای 3 باند

فرود مسأله‌ ترافیکی اول.

 

نوع هواپیما

شناسه‌ی پرواز

باند3

باند2

باند1

10

11

12

H

DL130

19

17

15

S

AA335

8

9

7

H

UA123

8

7

6

H

DL1920

15

13

10

L

UA1133

5

6

7

H

NW2123

19

17

15

L

AA205

9

8

7

H

DL3319

8

7

6

S

SW200

15

12

9

H

DL510

4

5

6

H

UA410

6

7

9

L

SW185

 

 

برای اجرای الگوریتم CPSO جمعیت اولیه برابر 40 و شاخص‏های C1 و C2، برابر 05/2 در نظر گرفته شده‌ است. بر این اساس در برنامه‌ هوشمند مبتنی بر CPSO، هر ذره به اندازه‌ تعداد پروازها بعد داشته و به هر بعد که معرف شناسه‌ی پرواز است؛ یک باند اختصاص می‌یابد. برای ‌مثال در این مسأله، الگوریتم هوشمند 40 ذره‌ 12 بعدی تولید می‌کند. هر عدد مربوط به این بعدها که یکی از اعداد 1، 2 و یا 3 است، بیانگر یکی از سه باند اختصاص یافته برای فرود هر هواپیماست. اعمال چنین دانشی به فرآیند بهینه‌سازی، سبب حذف پاسخ‌های غیربهینه‌ بدیهی می‌شود. در ادامه، فرآیند برنامه‌ریزی مطابق آنچه در بخش 4 تشریح شد؛ انجام می‏شود. در جدول (3) نمونه‌ای از بهترین نتایج برنامه‌ریزی هوشمند فرود برای مسأله‌ اول، ارایه شده است.

 

جدول (3): نمونه‌ای از نتایج حاصل از برنامه‌ریزی

هوشمند فرود برای 12 هواپیما و سه باند عملیاتی.

   

باند تخصیص یافته به هواپیما

شناسه‌ی پرواز

0

6

باند 1

SW200

0

9

باند 1

SW185

0

15

باند 1

AA205

0

5

باند 2

UA410

0

7

باند 2

DL1920

0

9

باند 2

UA123

0

11

باند 2

DL130

0

13

باند 2

UA1133

0

5

باند 3

NW2123

0

9

باند 3

DL3319

0

15

باند 3

DL510

0

19

باند 3

AA335

0 = مجموع تأخیرها

ثانیه 40/13 = زمان محاسباتی

 

صحت نتایج به‌دست آمده از برنامه‌ریزی هوشمند، به آسانی از طریق اطلاعات داده شده در جدول‏های (1) و (2) قابل بررسی است‏. برای مثال به پرواز DL130 باند 2 و 11 واحد زمانی اختصاص داده شده، که اختصاص این زمان بر اساس جدول (2) صحیح است‏. از طرفی بر اساس جدول (1) این هواپیما که از نوع Heavy است، می‌بایست حداقل با یک واحد زمانی جدایی ایمن نسبت به پرواز قبلی UA123 فرود آید. از آن‏جا که زمان‌های تخصیص داده شده‌ فرود این دو هواپیما، دو واحد زمانی فاصله نسبت به هم دارند و محدودیت‌ ارایه شده در جدول (1) نقض نشده؛ این زمان‌ها به‌عنوان زمان نهایی فرود این دو هواپیما در نظر گرفته شده‌اند.

 

4-2- مسأله‌ ترافیکی دوم

در این بخش با افزایش 25 درصدی تعداد پروازها نسبت به مسأله‌ اول و بر اساس داده‌های ارایه شده در جدول (4)، به شبیه‌سازی رویکرد هوشمند پیشنهادی پرداخته می‌شود.

جدول (4): ‌زمان‌های تخمینی فرود 15 هواپیما برای 3 باند

فرود مسأله‌ ترافیکی‌دوم.

 

نوع هواپیما

شناسه‌ی پرواز

باند3

باند2

باند1

10

11

12

H

DL130

19

17

15

L

AA335

8

9

7

H

UA123

8

7

6

H

DL1920

15

13

10

S

UA1133

5

6

7

H

NW2123

19

17

15

L

AA205

9

8

7

H

DL3319

8

7

6

H

SW200

15

12

9

S

DL510

4

5

6

H

UA410

6

7

9

L

SW185

9

8

7

S

DL200

8

7

6

L

NW410

7

8

9

H

AA1225

در جدول (5) نمونه‌ای از بهترین نتایج حاصل از برنامه‌ریزی، برای 20 هواپیما و سه باند عملیاتی ارایه شده است. به‌‌دست آمدن یک واحد زمانی تأخیر برای این مسأله بیانگر آن است که در عین رعایت محدودیت‌های حداقل جدایی ایمن بین فرودهای متوالی، از ظرفیت‌های محدود سطوح پروازی فرودگاه به شیوه‌ای مناسب در برنامه‌ریزی استفاده شده است. یک واحد زمانی تأخیر به وجود آمده در برنامه‌ریزی به این علت است که پرواز SW200 که از نوع Heavy است، نسبت به هواپیمای DL200 تقدم فرود داشته است. از این رو باید بر اساس جدول (1) حداقل 2 واحد زمانی جدایی ایمن بین این دو پرواز در نظر گرفته شود، تا پایداری آیرودینامیک پرواز DL200 حفظ شود.

 

جدول (5): نمونه‌ای از نتایج حاصل از برنامه‌ریزیهوشمند فرود برای 15 هواپیما و سه باند عملیاتی.

   

باند تخصیص یافته به هواپیما

شناسه‌ی پرواز

0

6

باند 1

NW410

0

7

باند 1

NW2123

0

10

باند 1

UA1133

0

15

باند 1

AA205

0

5

باند 2

UA410

0

7

باند 2

DL1920

0

8

باند 2

DL3319

0

9

باند 2

UA123

0

11

باند 2

DL130

0

17

باند 2

AA335

0

6

باند 3

SW185

0

7

باند 3

AA1225

0

8

باند 3

SW200

1

10

باند 3

DL200

0

15

باند 3

DL510

1 واحد زمانی = مجموع تأخیرها

ثانیه 27/32 = زمان محاسباتی

 

 

4-3- مسأله‌ ترافیکی سوم

در این بخش در قالب یک مسأله‌ ALS جدید و مطابق جدول (6) با در اختیار داشتن زمان تخمینی فرود 20 هواپیما برای پنج باند، به شبیه‌سازی مسأله پرداخته شده است.

 

جدول (6): ‌زمان‌های تخمینی فرود 20 هواپیما برای 5 باند.

 

نوع هواپیما

شناسه‌ی پرواز

باند5

باند4

باند3

باند2

باند1

 

 

9

10

10

11

12

H

DL130

18

18

19

17

15

L

AA335

8

7

8

9

7

H

UA123

8

7

8

7

6

H

DL1920

14

15

15

13

10

S

UA1133

5

6

5

6

7

H

NW2123

18

19

19

17

15

L

AA205

9

8

9

8

7

H

DL3319

8

7

8

7

6

H

SW200

14

15

15

12

9

S

DL510

6

6

4

5

6

H

UA410

8

9

6

7

9

L

SW185

8

7

9

8

7

S

DL200

8

7

8

7

6

L

NW410

9

8

7

8

9

H

AA1225

11

10

10

11

10

S

SW442

7

6

8

7

6

L

AA127

7

8

7

8

9

L

AA1410

9

7

9

8

7

H

UA555

10

9

11

10

9

L

SW250

 

در جدول‌ (7) نمونه‌ای از بهترین نتایج برنامه‌ریزی هوشمند برای مسأله‌ ‌سوم ارایه شده است. نیم واحد زمانی تأخیر برای پرواز AA1410 برای حفظ جدایی ایمن بین این پرواز و پرواز قبلی که هر دو از نوع Large بوده‌اند، است‏.

جدول (7): نمونه‌ای از نتایج حاصل از برنامه‌ریزی هوشمند فرود برای 20 هواپیما و 5 باند عملیاتی.

   

باند تخصیص یافته به هواپیما

شناسه‌ی پرواز

0

6

باند 1

NW410

0

7

باند 1

UA123

0

9

باند 1

AA1225

0

12

باند 1

DL130

0

15

باند 1

AA335

0

5

باند 2

UA410

0

6

باند 2

NW2123

0

7

باند 2

SW200

0

8

باند 2

UA555

0

11

باند 2

SW442

0

6

باند 3

SW185

5/0

5/7

باند 3

AA1410

0

9

باند 3

DL200

0

11

باند 3

SW250

0

15

باند 3

UA1133

0

19

باند 3

AA205

0

6

باند 4

AA127

0

7

باند 4

DL1920

0

8

باند 4

DL3319

0

15

باند 4

DL510

5/0 واحد زمانی = مجموع تأخیرها

ثانیه 45/38 = زمان محاسباتی

 

4-4- مسأله‌ ترافیکی چهارم

گاهی در برخی فرودگاه‌ها وضعیت یک باند، به ‌گونه‌ای است که استانداردهای لازم برای عملیات نشست و برخاست نوع خاصی از هواپیماها را ندارد. در این بخش با اعمال محدودیت برای فرود هواپیماهای Heavy در باند سوم و استفاده از داده‌های ترافیکی ارایه شده در جدول (2) (12 هواپیما و 3 باند فرود)، به تحلیل‏‏ این مسأله پرداخته می‌شود. نتایج شبیه‌سازی‌ها‌ نشان می‌دهند که با وجود سخت‌تر شدن مسأله (به علت عدم امکان فرود هواپیماهای H در باند سوم)، با رویکرد هوشمند پیشنهادی می‌توان به پاسخ‌هایی بهینه برای این‌ قبیل مسائل دست یافت.

 

جدول (8): نمونه‌ای از نتایج حاصل از برنامه‌ریزی هوشمند

فرود‌ با محدودیت فرود هواپیماهای H در باند سوم.

   

باند تخصیص یافته به هواپیما

شناسه‌ی پرواز

0

6

باند 1

DL1920

0

7

باند 1

DL3319

0

15

باند 1

AA205

0

5

باند 2

UA410

0

6

باند 2

NW2123

0

9

باند 2

UA123

0

11

باند 2

DL130

0

12

باند 2

DL510

0

17

باند 2

AA335

0

6

باند 3

SW185

0

8

باند 3

SW200

0

15

باند 3

UA1133

0 = مجموع تأخیرها

ثانیه 24/17 = زمان محاسباتی

 

4-5- مقایسه‌ نتایج

در این مرحله برای بررسی کیفیت رویکرد هوشمند پیشنهادی مطابق جدول (9)، نتایج حاصل از شبیه‌سازی‌ها با نتایج مطالعات قبلی نظیر روش‌های جستجوی مبتنی بر الگوریتم ژنتیک، جستجوی Scatter، الگوریتم GLS و الگوریتم بیونومیک مقایسه شده است.

 


 

 

جدول (9): مقایسه‌ نتایج حاصل از برنامه‌ریزی هوشمند فرود با نتایج روش‌های ارایه شده قبلی.

مورد آزمایش

روش

مسأله‌ اول [5].

مسأله‌ دوم [5].

مسأله‌ سوم [5].

مسأله‌ چهارم [5].

GA[18] [5]

TD

5/3

9

12

5/8

GA [17]

TD

1

5/5

65/7

30/4

SS[19] [12]

TD

75/3

25/12

75/8

50/5

CT

8

10

12

7

BA[20] [12]

TD

75/3

25/12

75/9

25/4

CT

49

47

49

47

GLS[21] [33]

TD

5/3

25/12

75/7

25/3

CT

24/0

07/1

50/8

32/0

رویکرد پیشنهادی

CPSO

 (best)

TD

0

1

5/0

0

CT

40/13

27/32

45/38

24/17

CPSO

 (mean)

TD

58/0

45/1

11/1

87/0

CT

18/11

32/34

13/39

24/18

TDمجموع تأخیرها :

CTزمان محاسباتی بر حسب ثانیه :

Mean: میانگین ده بار اجرای برنامه‌ی هوشمند

 

 

همان‌‌گونه که از نتایج ارایه شده در جدول (9) پیداست، برنامه‌ریزی هوشمند با هدف اساسی کمینه‌سازی مجموع تأخیرهای پروازی به شیوه‌ای مناسب انجام شده است.

 

5- نتیجه‌گیری

در این مقاله، در قالب رویکردی نوین، با اعمال دانشی غنی و مؤثر به فرآیند بهینه‌سازی و استفاده از الگوریتم CPSO، به برنامه‌ریزی هوشمند فرود هواپیماها پرداخته شد. فرآیند برنامه‌ریزی با تخصیص باند، زمان‌بندی مناسب فرود، تعیین ترتیب فرودهای متوالی و رعایت استانداردهای خاص حداقل جدایی ایمن به شیوه‌ای مناسب انجام شد. شبیه‌سازی‌ها با داده‌های واقعی نشان دادند که با تخصیص تصادفی باند به هر پرواز در برنامه‌ی هوشمند، می‌توان تا حدود زیادی پاسخ‌های غیربهینه‌ی بدیهی را حذف کرد‏. مقایسه‌ نتایج به‌دست آمده از شبیه‌سازی‌ها با نتایج روش‌های ارایه شده‌ قبلی بیانگر آن است که با این روش، مجموع تأخیرهای فرآیند برنامه‌ریزی به میزان چشمگیری‏‏ کاهش یافته است. از این رو استفاده از این روش برنامه‌ریزی هوشمند، می‌تواند به‌عنوان یک ابزار کمکی مناسب در مراکز کنترل ترافیک هوایی استفاده شود.

 



1Aircraft Landing Problem

2 Planned Landing Time

3 Airplane Landing Scheduling

4 Airplane Landing Sequencing and Scheduling

5 Multi-Objective Neighborhood Search Differential Evolution

6 Variable Neighborhood Descent

7 Cellular Automata Optimization

8 Clonal Selection Algorithm- RecedingHorizon Control

9 Excellent Gene Segment Spread

10 Infeasibility Degree

11 Ant Colony

12 Terminal Control Area

13 Turbulence

14 Federal Aviation Administration

15 Minimum safe Seperation

16 Update

17 Dallas Fort Worth

18 Genetic Algorithm

19 Scatter Search

20 Bionomic Algorithm

21 Genetic Local Search

 
[1]  Zhao W. , Wang Y. and Guo Z. , “The Air Traffic Congestion Analysis for Landing”, International conference on Information Technology, Computer Engineering and Management Sciences (ICM), pp. 100-103, 2011.
[2]  Yifei Z. and Kai C. , “Air traffic congestion assessment method based on evidence theory”, Control and Decision Conference (CCDC), pp. 426-429, 2010.
[3]  Lee H. and Balakrishnan H. , “A study of tradeoffs in scheduling terminal-area operations”, Proceedings of the IEEE, Vol. 96, No. 12, pp. 2081-2095, 2008.
[4]  Xianru, T. , “A Mathematical Quadratic Integer Model based on Ant Colony Optimization for Air Traffic Control”, Advances in Information Sciences & Service Sciences, Vol. 4, No. 1, pp. 185-191, 2012.
[5]  Hansen J. V. , “Genetic search methods in air traffic control”, Computers & Operations Research, Vol. 31, No. 3, pp. 445-459, 2004.
[6]  Amrahov S. E. and Ibrahim Alsalihe T. , “Greedy algorithm for the scheduling aircrafts landings”, pp. 1-3, 2011.
[7]  Oussedik S. and Delahaye D. , “Reduction of air traffic congestion by genetic algorithms ”, pp. 855-864, 1998.
[8]  Cheng V. , Crawford L. and Menon P. , “Air traffic control using genetic search techniques”, IEEE International Conference on Control Applications, pp. 249-254, 1999.
[9]  Beasley J. E. , Krishnamoorthy M. , Sharaiha Y. M. and Abramson D. , “Scheduling aircraft landings—the static case,” Transportation science, Vol. 34, No. 2, pp. 180-197, 2000.
[10]   Bianco L. , Dell’Olmo P. and Giordani S. , “Scheduling models for air traffic control in terminal areas”, Journal of Scheduling, Vol. 9, No. 3, pp. 223-253, 2006.
[11]   Beasley J. , Sonander J. and Havelock P. , “Scheduling aircraft landings at London Heathrow using a population heuristic”, Journal of the operational research society, pp. 483-493, 2001.
[12]   Pinol H. and Beasley J. E. , “Scatter search and bionomic algorithms for the aircraft landing problem”, European Journal of Operational Research, Vol. 171, No. 2, pp. 439-462, 2006.
[13]   Tavakkoli-Moghaddam R. , Yaghoubi-Panah M. and Radmehr F. , “Scheduling the sequence of aircraft landings for a single runway using a fuzzy programming approach”, Journal of Air Transport Management, Vol. 25, No. 1, pp. 15-18, 2012.
[14]   Atkin J. A. , Burke E. K. , Greenwood J. S. and Reeson D. , “Hybrid metaheuristics to aid runway scheduling at London Heathrow airport”, Transportation Science, Vol. 41, No. 1, pp. 90-106, 2007.
[15]   Bianco L. , Dell'Olmo P. and Giordani S. , “Minimizing total completion time subject to release dates and sequence‐dependentprocessing times”, Annals of Operations Research, Vol. 86, No. 1, pp. 393-415, 1999.
[16]   Ernst A. T. , Krishnamoorthy M. and Storer R. H. , “Heuristic and exact algorithms for scheduling aircraft landings”, networks, Vol. 34, No. 3, pp. 229-241, 1999.
[17]   Hu X. B. , and Paolo E. D. , “An efficient genetic algorithm with uniform crossover for air traffic control”, Computers & Operations Research, Vol. 36, No. 1, pp. 245-259, 2009.
[18]   Tang K. , Wang Z. , Cao X. and Zhang J. , “A multi-objective evolutionary approach to aircraft landing scheduling problems”, pp. 3650-3656.
[19]   Salehipour A. , Moslemi Naeni L. and Kazemipoor H. , “Scheduling aircraft landings by applying a variable neighborhood descent algorithm: Runway-dependent landing time case”, Journal of Applied Operational Research, Vol. 1, No. 1, pp. 39-49, 2009.
[20]   Yu S. P. , Cao X. B. and Zhang J. , “A real-time schedule method for Aircraft Landing Scheduling problem based on Cellular Automation”, Applied Soft Computing, Vol. 11, No. 4, pp. 3485-3493, 2011.
[21]   Jia X. , Cao X. , Guo Y. , Qiao H. and Zhang J. , “Scheduling aircraft landing based on clonal selection algorithm and receding horizon control”, 11th International IEEE Conference on Intelligent Transportation Systems, pp. 357-362, 2008.
[22]   Bencheikh G. , Boukachour J. , Alaoui A. E. H. and Khoukhi F. , “Hybrid method for aircraft landing scheduling based on a Job Shop formulation”, International Journal of Computer Science and Network Security, Vol. 9, No. 8, pp. 78-88, 2009.
[23]   Forbes S. J. , “The effect of air traffic delays on airline prices”, International journal of industrial organization, Vol. 26, No. 5, pp. 1218-1232, 2008.
[24]   Bojanowski L. , Harikiopoulo D. , and Neogi N. , “Multi-runway aircraft sequencing at congested airports”, American Control Conference (ACC), pp. 2752-2758, 2011.
[25]   Tittsworth J. A. , Lang S. R. , Johnson E. J. and Barnes S. , “Federal Aviation Administration Wake Turbulence Program-Recent Highlights”, 57th Air Traffic Control Association (ATCA) Annual Conference, pp. 1-8, 2012.
[26]   Kennedy J. and Eberhart R. , “Particle swarm optimization”, IEEE International conference on Neutral Networks, pp. 1942-1948, 1995.
[27]   Mohammadi-Ivatloo B. , Rabiee A. , Soroudi A. and Ehsan M. , “Iteration PSO with time varying acceleration coefficients for solving non-convex economic dispatch problems”, International Journal of Electrical Power & Energy Systems, Vol. 42, No. 1, pp. 508-516, 2012.
[28]   M. Clerc, “The swarm and the queen: towards a deterministic and adaptive particle swarm optimization”, IEEE Congress on Evolutionary Computation, 1999.
[29]   Izakian H. and Pedrycz W. , “A new PSO-optimized geometry of spatial and spatio-temporal scan statistics for disease outbreak detection”, Swarm and Evolutionary Computation, Vol. 4, No. 1, pp. 1-11, 2012.
[30]   Sahu A. , Panigrahi S. K. and. Pattnaik S. , “Fast Convergence Particle Swarm Optimization for Functions Optimization,” Procedia Technology, Vol. 4, No 1, pp. 319-324, 2012.
[31]   Clerc M. and Kennedy J. , “The particle swarm-explosion, stability, and convergence in a multidimensional complex space”, Evolutionary Computation, Vol. 6, No. 1, pp. 58-73, 2002.
[32]   Bharat T. V. , Sivapullaiah p. V. and Allam M. M. , “Robust solver based on modified particle swarm optimization for improved solution of diffusion transport through containment facilities”, Expert Systems with Applications, Vol. 39, No. 12, pp. 10812-10820, 2012.
[33]   Liu, Y. H., “A genetic local search algorithm with a threshold accepting mechanism for solving the runway dependent aircraft landing problem”, Optimization Letters, pp. 229-245, 2011.