نشریه تخصصی مهندسی صنایع، دوره 45، شماره 2، مهر ماه 1390، از صفحه 175 تا 185
زمانبندي ماشینهاي سري انعطافپذیر با مدل دومعیاره براي بهینهکردن
ظرفیت بخش هوایی فرودگاه

علی عبدي*1، ابراهیم اسدي2، محمود صفارزاده 3، فریبرز جولاي 4 و نسیم نهاوندي5
1دکتراي مهندسی عمران، دانشکده فنی و مهندسی، دانشگاه تربیت مدرس
2دانشجوي دکتراي مهندسی صنایع، دانشکده فنی و مهندسی، دانشگاه تربیت مدرس
3استاد مهندسی عمران، دانشکده فنی و مهندسی ، دانشگاه تربیت مدرس
دانشیار مهندسی صنایع، پردیس دانشکده فنی، دانشگاه تهران
استادیار مهندسی صنایع، دانشکده فنیومهندسی، دانشگاه تربیت مدرس
(تاریخ دریافت 14/11/87، تاریخ دریافت روایت اصلاح شده 4/3/90، تاریخ تصویب 27/6/90 )

چکیده
در این تحقیق براي اولین بار از مدل ماشینهاي سري انعطافپذیر (flexible flow shop) براي در نظر گرفتن تخصیص همزمان باندها و برنامهریزي عملیاتی استفاده شده است. یکی از مزایاي توسعه این مدل، در نظر گرفتن مسیرهاي هوایی داخل فضاي هوایی فرودگاهها است که سبب تشابه مدل با شرایط واقعی میشود. همچنین با توجه به ماهیت دو مرحله مسیرهاي هوایی و باندها از حالت No-Wait بین دو مرحله استفاده شده است. با توجه به اینکه در ادبیات موضوع فرودگاهی توابع هدف متفاوتی وجود دارد، یک مدل دومعیاره براي این مسئله ارائه شده و براي حل این مدل از روش فراابتکاري SA استفاده شده است. از مزایاي مدل پیشنهادي، در نظر گرفتن فاصله جدایی بین هواپیماها است. از این رویکرد می توان به عنوان یک سیستم کمککننده در تصمیمگیري استفاده کرد که کاهش دهنده تأخیرات و بهبود دهنده توان عملیاتی فرودگاهها است.

واژه هاي کلیدي: تخصیص، برنامهریزي عملیاتی، توالی، مدل ترکیبی،Simulated annealing ، ماشینهاي سري انعطافپذیر، تابع هدف دومعیاره

مقدمه
امروزه با افزایش تقاضا در فرودگاهها، باندهاي پروازي به عنوان نقطه گلوگاهی مطرح شدهاند. در بسیاري از فرودگاه ها که در اکثر ساعات روز با حداکثر ظرفیت خود کار میکنند، باندها به عنوان یک منبع بحرانی مطرح هستند، به گونهاي که ظرفیت آنها دستخوش تغییراتی ناشی از شرایط آبو هوایی و شرایط دید قرار می گیرند که سبب به وجود آمدن تأخیرات زیادي در پروازهاي ورودي و خروجی میشود. بنابراین ظرفیت باندها باید به صورت کارا مورد استفاده قرار گیرد [1].
Email: [email protected] ، 82884322 : نویسنده مسئول : تلفن : 26407160, فاکس *

ظرفیت فرودگاه بر اساس مجموع عملیات ورودي و خروجی بیان میشود [2]. سطوح تقاضاي موجود و پیش-بینی شده باعث می شود که نیاز به افزایش ظرفیت فرودگاهها، کاهش تأثیرات محیطی (تشعشعات امواج موتور) و هزینههاي ناشی از عملیات غیرکارا (مصرف سوخت) بیشتر حس شود. براي تأمین این نیازها، وجود یک سیستم پشتیبان تصمیم گیري که شامل الگوریتم هاي کنترل و برنامه ریزي باشد، ضروري به نظر میرسد [3].
یکی از روشهاي افزایش ظرفیت باندها، افزایش تعداد آنها است؛ ساخت باندهاي جدید اغلب به دلیل تحمیل هزینههاي زیاد و اشغال زمین، امکانپذیر نیست. همچنین افزایش تعداد باندها بدون تخصیص و برنامه ریزي عملیاتی بهینه، تأثیر چندانی نخواهد داشت. اینکه از کدام باند، براي کدام عملیات و در کدام زمان استفاده شود، مهم ترین بخش تعیین ظرفیت سیستم باندها را تشکیل میدهد.
افزایش تعداد، پیچیدگی هندسی، مکان و تعیین موقعیت باندها، نقاط تقاطع باندها، مسیر پایانی باندها و بار کاري کنترلکنندگان ترافیک هوایی، از جمله موارد مهمی هستند که بدون برنامهریزي عملیاتی و تخصیص بهینه، سبب اتلاف مقدار زیادي از ظرفیت باندها و در نهایت فضاي هوایی میشوند. بهعلاوه تأخیرات بهوجود آمده منجر به پیامدهایی نظیر از بین رفتن منابع اقتصادي ورضایت نداشتن استفادهکنندگان (خطوط هوایی ومسافران) از فرودگاهها میشود [4].
در این تحقیق، براي اولین بار از مدل ریاضی سري انعطاف پذیر در حالت No-wait براي تخصیص همزمان باندها و برنامهریزي عملیاتی استفاده شده است. در این مدل، از زمان آمادهسازي مبتنی بر توالی براي نشان دادن فاصله جدایی بین هواپیماها استفاده شده است که سبب میشود مدل، به شرایط واقعی نزدیکتر شود. همچنین از یک تابع هدف دومعیاره (مدن زمان تأخیر و مدت زمان اشغال باندها و مسیرهاي هوایی به وسیله هواپیماها) براي این مدل ریاضی استفاده شده است. براي حل این مدل از روش فراابتکاري SA استفاده شده است که جواب اولیه آن با استفاده از سه روش تصادفی، روش WEDD و روش ابتکاري تولید شده است.
بخشهاي مختلف این تحقیق بدین صورت است: در ادامه، توضیحاتی درباره موضوع تخصیص هواپیماها به باندها و نقش بخشهاي مختلف فرودگاهی در این زمینه داده خواهد شد. سپس با استفاده از رویکرد زمانبندي، این مسئله مدل میشود و مدل ریاضی مربوطه شرح داده میشود. در بخش بعدي، رویکردهاي مختلف براي حل این مسئله شامل الگوریتم WEDD، الگوریتم ابتکاري و الگوریتم SA به طور خلاصه توضیح داده میشود و در نهایت نتایج مربوط به حل این مدل ارائه خواهد شد.

توضیح مسئله
باندهاي فرودگاه از جمله منابعی هستند که باید به عملیات فرودگاهی مختلف (ورود، خروج و تقاطع) تخصیص یابند. چون سیستم باندها به عنوان منبعی که باید بین همه هواپیماها تقسیم شود، بنابراین باندها گلوگاه سیستم فرودگاهی است که سبب بهوجود آمدن محدودیت ظرفیت فرودگاه و یا افزایش تأخیرات میشود؛ در نتیجه باید از منابع فرودگاهی حداکثر استفاده شود. در این تحقیق، سعی در تخصیص هواپیماها به مسیرهاي هوایی و باندها شده است، به گونهاي که مقدار تابع هدف مورد نظر که ترکیبی از مدت زمان تأخیر و زمان اشغال باندها توسط هواپیماها است، کمینه شود. در این تحقیق، از مدل زمانبندي ماشینهاي سري انعطافپذیر استفاده شده است که مرحله اول به تعداد مسیرهاي هوایی، ماشین در نظر گرفته میشود که به شکل موازي قرار دارند. در مرحله دوم این مدل، مانند مرحله اول، به تعداد باندها، ماشین وجود دارد که سرعت انجام کار این ماشینها متفاوت است. در این مدل، هواپیماها به عنوان کار در نظر گرفته شده است.

ساختار مدیریت ترافیک هوایی
در تعدادي از تحقیقات اخیر، ساختار جدیدي براي ATM1 پیشنهاد شده است که پایه این مقاله است. این ساختار می تواند سبب استفاده مفید از سیستمهاي کمک-کننده در تصمیم گیري2 براي کنترلکنندگان ترافیک هوایی شود؛ زیرا این ساختار سبب ایجاد ارتباط بین بخشهاي مهم ترافیک هوایی می شود. مهم ترین بخش ترافیک هوایی ROM 3 است که در واقع جزئی از سیستم سراسري ATMاست و از تصمیمات گرفته شده در سایر بخشهاي ROM تأثیر می پذیرد. وظایف اصلی ROM عبارتند از:
1) مدیریت ترکیب باندها که شامل برنامهریزيهاي راهبردي مانند ترکیب ساختار باندهاي مورد استفاده، روشهاي عملیاتی مورد استفاده در هر ترکیب و زمانهاي تغییر این ترکیبها است؛ 2) مدیریت تخصیص باندها که تعیین کننده باندي است که باید به یک هواپیماي مشخص تخصیص یابد؛
3) برنامهریزي عملیات باندها، یعنی برنامهریزي تاکتیکی استفاده از باندها براي پروازهاي ورودي و خروجی [5].
اگر چه بعضی از محققان این 3 بخش را به صورت سلسله مراتبی در نظر گرفتهاند، اما در این تحقیق مدیریت تخصیص باندها و برنامهریزي عملیات باندها با هم در نظر گرفته شده است.

برنامهریزي عملیاتی باندها
فرآیند تخصیص زمان باندها به عملیات مربوطه، یک وظیفه چالشبرانگیز در همه فرودگاه هاي شلوغ است.
برنامه ریزي و کنترل، دو وظیفه تاکتیکی هستند که باید بدون صرفنظرکردن از رابطه آنها، از یکدیگر تمییز داده شوند. این رابطه اغلب روشن و قابل رؤیت نیست، زیرا در بسیاري از مواقع، کنترلکننده، این دو کار را همزمان و به طور ذهنی انجام میدهد. یک طرح موفق از سیستم ROP4، باید یکپارچگی لازم میان تابع هدفهاي مختلف،محدودیتها، کنترلها و ورودي همه بخشهاي موجود در عملیات زمینی را فراهم کند. پس مسئله برنامهریزي عملیاتی فرودگاه یک مسئله بهینهسازي است که بهوسیله بخشهاي عملیاتی و مالی مانند استفادهکنندگان از فرودگاهها (خطوط هوایی و مسافران) و فراهم کننده خدمات ATM (تصمیمگیرندگان در فرودگاه و کنترل-کنندگان هوایی) تحت تاثیر قرار میگیرد [5].

مدیریت تخصیص باندها
تخصیص هواپیماها (ورودي و خروجی) به باندها همیشه یکی از مهم ترین نگرانیهاي کنترل کنندگان است.
زیرا آنها اغلب در تقاضاهاي زیاد باید تصمیمات سریعی بگیرند که اغلب منجر به استفاده کامل از ظرفیت در دسترس باندها نمیشود [6].
تخصیص هواپیماهاي ورودي به باندها، یک تصمیم تاکتیکی است که به وسیله کنترلکنندگان انجام میگیرد.
فرآیند برنامه ریزي تاکتیکی مربوط به زمانبندي هواپیماهاي ورودي، نیاز به هماهنگی بین کنترل کنندگان دارد و در نهایت منجر به افزایش بار کاري و تأخیرات می-شود[7]. در ضمن چنین فرآیندي براي عملیات خروجی هم وجود دارد، اگر چه تخصیص عملیات ورودي و خروجی به طور مستقل انجام میگیرد.
اغلب بسیاري از تحقیقات انجام گرفته در این زمینه در مورد هواپیماهاي ورودي انجام شده است؛ چون پروازهاي ورودي نسبت به پروازهاي خروجی اولویت دارند[6]. در این تحقیق نیز تمرکز بر پروازهاي ورودي است و از پروازهاي خروجی صرفنظر شده است.

موارد مورد نیاز براي ترکیبROP و ROM
تخصیص باند به هواپیماها در یک فرودگاه تک بانده، موضوع مهمی نیست و فقط برنامهریزي عملیات ورودي و خروجی در این نوع فرودگاهها مهم است. اما در فرودگاه-هاي چندبانده علاوه بر برنامهریزي عملیاتی نیاز به تخصیص هواپیماها به باندها است که این خود کار پیچیدهایی است. این پیچیدگی سبب افزایش بار کاري کنترلکننده شده و در نهایت منجر به استفاده از روش هاي ساده براي تخصیص باندها میشود (مثلاً یک باند به عملیات ورودي و یک باند به عملیات خروجیتخصیص مییابد). همان طور که مشخص است این نوع تصمیمگیري لزوماً منجر به برنامهریزي و استفاده بهینه از باندها نمیشود.
بعضی از تحقیقات فقط برنامه ریزي عملیات ورودي و هزینه خطوط هوایی را در نظر میگیرند [8]. به دلیل وابستگی میان پروازهاي ورودي و خروجی، انتظار میرود که اگر این پروازها با هم در نظر گرفته شوند، باعث صرفه-
جویی زیادي در هزینهها شود [1]. بعضی از محققان تخصیص همزمان پروازهاي ورودي و خروجی را در نظر می گیرند. بنابراین براي افزایش توان عملیاتی فرودگاه، باید تخصیص عملیات ورودي و خروجی و تخصیص باندها به طور همزمان انجام گیرد.

استفاده از زمانبندي براي تجزیهوتحلیل مسئله
زمانبندي، تخصیص منابع در طول زمان براي انجام کارهاي مشخص است. فرآیند زمانبندي اغلب نیازمند توالی و تصمیم گیري در مورد تخصیص منابع است [9]. براي اینکه تابع هدف ارضا شود، نه تنها باید توالی پروازهاي ورودي و خروجی در هر باند به شکل بهینه انجام گیرد، بلکه باید این کار در همه باندها انجام گیرد. یکی از تصمیمگیريهاي مهم در زمینه زمانبندي، انتخاب تابع هدف مناسب است. تابع هدفهایی که اغلب در ادبیات فرودگاهی استفاده می شود شامل حداقل کردن میانگین زمان اشغال باند، حداقل کردن حداکثر زمان اشغال باند، حداقل کردن میانگین تأخیر هواپیماها، حداقل کردن حداکثر تأخیر هواپیماها، حداقل کردن تعداد کارهاي دیرکرددار است. در این تحقیق، از تابع هدف دومعیاره استفاده شده است که شامل مدت زمان تأخیر هواپیماها و مدت زمان اشغال باندها و مسیرهاي هوایی توسط هواپیماها (Flow Time) است.
در اینجا لازم به ذکر است که در ادامه از مدل گراهام براي نشان دادن مسائل موجود در زمان بندي استفاده می-شود. این مدل به صورت // است که در آن  نشان دهنده نوع مسئله،  نشان دهنده خصوصیات کارها و  نشان دهنده معیار بهینهسازي است [10].

مدل ریاضی
براي مدلسازي مسئله، از مدل زمانبندي ماشینهايسري انعطاف پذیر (FFS) استفاده می شود. اغلب درفرودگاهها و قبل از مرحله باندها، تعدادي مسیر هوایی وجود دارد که می توان آنها را به عنوان یک مرحله مجزا در نظر گرفت که در آن تعدادي ماشین به طور موازي قرار دارد. در مرحله دوم نیز که مانند مرحله اول است، تعدادي باند به طور موازي قرار دارند. در نتیجه میتوان مدل مسئله را به شکل ماشینهاي سري انعطافپذیر دو مرحلهاي در نظر گرفت که در هر مرحله تعدادي ماشین با سرعتهاي متفاوت وجود دارند. در این مدل از حالت No-Wait در زمان تکمیل کار هواپیماها در بین دو مرحله استفاده شده است؛ چون هر هواپیما بلافاصله بعد از طی مسیر هوایی بدون هیچگونه تأخیري باید وارد باندها شود و نمیتواند در بین این دو مرحله منتظر بماند.
یکی از مهم ترین مزایاي این مدل نسبت به مدلهاي قبلی این است که سبب شده است این مدل به شرایط واقعی نزدیک است استفاده از فاصله جدایی هواپیماها میباشد.
در این مدل فاصله جدایی و زمان در دسترس بودن هواپیماهاي ورودي (خروجی) به (از) نقاط ثابت در نظر گرفته میشود. تابع هدف استفاده شده در اینجا، ترکیبی از مدت زمان تأخیر و زمان اشغال باندها توسط هواپیماها است. در این مدل از پارامترهایی زیر استفاده شده است:

شاخص هواپیما (کار) j,l شاخص مراحل i
تعداد هواپیماها n تعداد مراحل m تعداد مسیرهاي هوایی z
مدت زمان فرآیند هواپیماي j در مرحله Pijk i روي باند یا مسیر هوایی
عامل وزنی هواپیماها wj
زمان ورود jامین هواپیما به فضاي هوایی rj
موعد تحویل هواپیماي d j j
زمان تکمیل کار هواپیماي j در مرحله Cij i عدد بسیاربزرگ M
متغیر صفر و یک،اگر هواپیماي j به مسیر Xijk هوایی یا باندk درمرحله i تخصیص یابد برابر با 1 و در غیر اینصورت 0
متغیر صفر و یک،اگر lامین هواپیما قبل از Yilj
j امین هواپیما فرود آید (در مرحلهي i) برابر با 1 و در غیر اینصورت 0
Tمیزان تأخیر هواپیماي j j

میزان اشغال باند و مسیر هوایی بهوسیلهي Fjهماپیماي هواپیماي j
ضریب اهمیت معیارها

مدل ریاضی مسئله به این شرح است:
nn
MinZ j1wj..Tj j1wj.(1).Fj
Subject to:
si
k1 Xijk 1

j :1  j  ni :1  i  2
s1
C1 j k1 p1 jk .X1jk
j :1 j  n C2 j  C1, j si pijk .X ijk (4)
k1 j :1 j  n Cij M(3Xijk XilkYilj)Cil pijk.Xijk (5)
j,l :1 j,l  n,i :1  i  2.

Cil M(2XilkXijkYilj)Cij pilk.Xilk (6)
j,l :1 j,l  n,i :1  i  2.

Fj C j2 rj(7)
Tj C j2 d j (8) C j ,Tj  0 (9)
Xijk {0,1}, Yilj {0,1}

حال در این قسمت محدودیت فاصله جدایی به مدل اضافه می شود. براي نشان دادن فاصله جدایی دو محدودیت زیر به مدل اضافه میشوند:
Cij pijk.Xijk M(3Xijk Xilk Yilj)
Cil Slj
j,l :1 j,l  n,i :1  i  2.
Cil pilk.Xilk M(2Xilk Xijk Yilj)
Cij S
jl

j,l :1 j,l  n,i :1  i  2.

در این مدل Sl, j فاصله جدایی بین دو هواپیماي l,j است که در آن هواپیمايl قبل از j سرویس میگیرد.

توضیح مدل
در این بخش، مدل ریاضی ارائه شده در قسمت قبل شرح داده میشود:
(تابع هدف): تابع هدف این مدل دو معیار دارد که با استفاده از روش وزنی با هم ترکیب شدهاند. معیار اول مقدار تأخیر وزندار هواپیماها و معیار دوم مدت زمان اشغال باندها و مسیرهاي هوایی به وسیله هواپیماها است.
(محدودیت تخصیص هواپیماي j در هر مرحله): این محدودیت بیان میکند که هر هواپیماي مفروضی مانند j فقط به یکی از مسیرهاي هوایی یا باندها تخصیص مییابد.
(محدودیت بین زمان اتمام کار هواپیماي j در مرحله مسیرهاي هوایی و زمان در دسترس بودن هواپیماي مفروض): این محدودیت این مطلب را بیان میکند که زمان اتمام کار هواپیماي j در مرحله اول یا مسیرهاي هوایی حداقل به اندازه زمان در دسترس بودن هواپیماي j، بهعلاوه مدت زمانی است که طول میکشد تا هواپیماي مفروض از مسیر هوایی مربوطه عبور کند.
(محدودیت بین زمان تکمیل کار هواپیماي مفروضj در مرحله اول (مسیرهاي هوایی) و مرحله دوم (باندها)): این محدودیت نشان میدهد که زمان تکمیل کار هواپیماي j در مرحله دوم، به طور دقیق برابر با زمان تکمیل کار هواپیماي مفروض در مرحله اول، به-علاوه مدت زمان عبور هواپیما از باند مربوطه است.
5و6. (محدودیت عدم همپوشانی سرویسدهی به هواپیماها در یک مسیر هوایی یا باند (با توجه به زمان پردازش)): در اینجا اختلاف بین زمان اتمام کار دو هواپیماي متوالی در مرحله مسیرهاي هوایی یا باند، برابربا مدت زمان فرآیند هواپیماي پسرو است.
7و8. محاسبه پارامترهاي تابع هدف: این دو محدودیت به ترتیب نشاندهنده میزان اشغال باندها به-وسیله هواپیماها و مقدار تأخیر است.
9و10. متغیرها: این دو محدودیت نوع متغیرها را نشان میدهد.
11و12. (محدودیت فاصله جدایی هواپیماها در مسیرهاي هوایی و باندها): در اینجا اختلاف بین زمان آغاز کار هواپیماي پسرو در مرحله مسیرهاي هوایی یا باندها برابر با فاصله جدایی این دو هواپیما به علاوه مدت زمان جدایی دو هواپیما است.

آنالیز حل مسئله
از آنجا که مسئله NP-HARD ،1|| wj.Tj
است [10و11]، در نتیجه مسئله
FFS| rj,nowait| wj..Tj wj.(1).Fj که مشتق مسئله بالا است، نیز NP-HARD است. به همین دلیل حل این مدل با استفاده از روشهاي دقیق براي مسائل بزرگ امکان پذیر نیست. در نتیجه در این تحقیق از روشهاي ابتکاري استفاده شده است.

الگوریتم SA
الگوریتم SA یک روش جستجوي تکراري است که در آن جواب اولیه با استفاده از یک سري تغییرات محلی کوچک بهبود می یابد، تا زمانی که جواب به دست آمده دیگر بهبود نیابد. این روش در سال 1983 توسط کرکپاتریک و همکاران [12] به وجود آمد. الگوریتم SA یک شبیهسازي از مکانیزمی براي بازپخت فیزیکی مواد جامد است. این مفهوم از بحث علم مواد می آید که در آن، مواد جامد ابتدا ذوب میشوند و سپس به طور آهسته سرد میشوند تا به یک تعادل ترمودینامیک برسند.
روش SA اغلب یک روش بهینهسازي است که تابع هدف F را در فضاي گسسته S حداقل میکند. با شروع از یک جواب اولیه s S جواب دیگري sS را در همسایگی s با استفاده از روشهاي ابتکاري بهوجود می-آورد. در این حالت مقدار (f (s را با مقدار (f (s مقایسه میکند و میزان (  f (s)  f (s را محاسبه میکند. اگر میزان تابع هدف کاهش یابد (0  ) جواب جدید به طور خودکار انتخاب میشود واین جواب نقطه جدید براي جستجو است. اما اگر میزان تابع هدف افزایش یابد (0  )، این جواب ممکن است با یک احتمال قبول شود که مقدار آن برابر با (exp(

T است. در اینجا TR پارامتر کنترلی الگوریتم است که دما نام دارد. اهمیت T در اجراي الگوریتم کاملاً مشهود است. این درجه حرارت هر NT مرحله کاهش مییابد که در آن NT تعداد تکرارهاي لازم (مقدار epoch) در هر مرحله است [13].

جستجوي همسایگی
یکی از مهم ترین بخشها در الگوریتم SA، استفاده از یک الگوریتم همسایگی مناسب است، به گونهاي که بتواند با یک مکانیزم ساده به اکثر فضاي حل دست پیدا بکند.
در ادامه مکانیزمی شرح داد میشود که با وجود سادگی، میتواند جوابهاي زیادي در فضاي حل فضاي را تولید کند. این مکانیزم به این شرح است:
مرحله 1) قرار دادن همه هواپیماها در یک ردیف؛
مرحله 2) انتخاب دو هواپیما به طور تصادفی و تغییر جاي آنها؛
مرحله 3) تقسیم ترتیب هواپیماها به z قسمت؛ مرحله 4) تخصیص بخش 1 به مسیر هوایی 1، بخش 2 به مسیر هوایی 2، … و بخش z به مسیر هوایی z؛ مرحله 5) قرار دادن همه هواپیماها در مرحله باندها در یک ردیف؛
مرحله 6) انتخاب دو هواپیما به طور تصادفی و تغییر جاي آنها؛
مرحله 7) تقسیم ترتیب هواپیماها به m قسمت؛
مرحله 8) تخصیص بخش 1 به باند 1، بخش 2 به باند 2، … و بخش m به باند m .

روشهاي تولید جواب اولیه
یکی از عوامل تأثیرگذار بر کیفیت جواب نهایی SA، کیفیت جواب اولیه استفاده شده است. استفاده از جواب اولیه خوب باعث میشود که الگوریتم فقط در بخشی از فضاي حل جستجو کند و در کیفیت جواب و مدت زمان حل بهبود حاصل شود. در ادامه 3 روش متفاوت براي به-دستآوردن جواب اولیه مطرح میشود.

– روش تصادفی
در این روش همه فرآیند تولید جواب اولیه به طور تصادفی انجام میگیرد. گامهاي این روش بهاین شکل است:
تولید ترتیب اولیه هواپیماها به طور تصادفی؛
تقسیم این ترتیب به طور تصادفی به تعداد مسیرهاي هوایی و قرار دادن روي مسیرهاي هوایی
تقسیم این ترتیب به طور تصادفی به تعداد باندها و قرار دادن روي باندها.

– الگوریتم WEDD
روش دومی که براي بهدست آوردن جواب اولیه استفاده شده است، الگوریتم WEDD است. گام هاي این روش به این صورت است:
مرتب کردن هواپیماها با استفاده از ترتیب زیر:
d(1) d(2)d
28385100200

 …

(n)
w(1) w(2)w(n)
که در آن (d( j و (w( j به ترتیب موعد تحویل و وزن هواپیما j هستند
تقسیم ترتیب بهوجود آمده به طور تصادفی به تعداد مسیرهاي هوایی و قرار دادن روي مسیرهاي هوایی ٣) تقسیم این ترتیب به طور تصادفی به تعداد باندها و قرار دادن روي باندها.

– الگوریتم ابتکاري پیشنهادي
این روش یک روش کاملاً ابتکاري بوده که بر پایه الگوریتم WEDD است که تغییراتی روي آن انجام گرفته است. گامهاي این روش به این ترتیب است:
گام 1: زمان پردازش مجازي هواپیماي jام روي باند iام را از رابطه زیر محاسبه کنید:
Pij  kRunwaymin (i) Pkj  Pij* (30)

گام 2: هواپیماها را بر اساس الگوریتم WEDD اولویت دهی شده و با توجه به زمانهاي پردازش مجازي به باندها تخصیص داده میشوند (در این گام فرض می-شود مرحله مسیرهاي هوایی وجود ندارد).
گام3: پس از تعیین تخصیص هواپیماها به باندها، در مسئله اصلی به صورت پسرو، عمل زمانبندي انجام میشود تا زمان شروع عملیات نشست هر هواپیما روي باند مربوطه بهدست آید (نحوه انجام عملیات زمانبندي پسرو در ادامه شرح داده می شود).
گام 4: این زمانهاي شروع نشست براي مرحله مسیرهاي هوایی به عنوان موعد تحویل خواهند بود. حال بر اساس این موعد تحویلها براي مرحله اول، از طریق الگوریتم WEDD تخصیص هواپیماها به مسیرهاي هوایی مختلف و زمان اتمام عملیات آن بهدست میآیند.
گام 5: بر اساس تخصیصهاي به دست آمده در گام
2 براي مرحله باندها و زمان اتمام عملیات مربوط به مرحله مسیرهاي هوایی، زمانبندي نهایی هواپیماها با توجه به زمان پردازش واقعی در مرحله باندها تعیین می-شوند (در این مرحله زمان آغاز و اتمام هر عملیات نشست بهدست میآیند).
گام6: الگوریتم را خاتمه دهید.
رویه انجام عملیات پسرو به این ترتیب است:
براي هر باند عملیات زیر را انجام دهید:
گام 1: تعداد کارهاي تخصیص داده شده به باند مورد نظر را q بنامید.
گام2: هواپیماي qام را طوري زمانبندي کنید که زمان اتمام عملیات نشست به طور دقیق برابر موعد تحویل آن ( (d(q) شود. در این حالت زمان آغاز نشست را stq بنامید. همچنین قرار دهید u=q.
گام 3: قرار دهید 1-u=u.
گام 4: اگر (d(uموعد تحویل هواپیماي uام باشد، هواپیماي uام را طوري زمانبندي کنید که زمان اتمام عملیات نشست آن به طور دقیق برابر عبارت زیر شود:

min{d(u),st(u1)} (31)

در این حالت زمان آغاز نشست را stqبنامید.
گام 5: اگر u=1 آنگاه الگوریتم را خاتمه دهید. در غیر این صورت به گام 3 بروید.

بهبود عملکرد SA
اغلب دو راه براي بهبود عملکردSA وجود دارد. یکی از این روشها استفاده از سایر الگوریتمها براي فراهم کردن یک جواب اولیه خوب براي روش SA است و روش دوم استفاده از جواب هاي SA، براي جواب اولیه سایر روشها است. روش اول توسط چمس و همکاران [14] هنگام بررسی مسئله Graph coloring مطرح شد. درسال 1987 جانسون و همکاران [15] از همین رویکرد براي حل مسئله Graph partitioning استفاده کردند. آنها نشان دادند که کیفیت و زمان حل با استفاده از این رویکرد بهبود مییابد. اما از روش دوم براي فراهم کردن جواب اولیه خوب با استفاده از الگوریتم SA براي سایر روشها، مانند شاخهوکران استفاده میشود. در این تحقیق از روش اول، یعنی استفاده از سایر الگوریتمها براي فراهم کردن یک جواب اولیه خوب براي روش SA، استفاده شده است.

انتخاب مقادیر اولیه
براي استفاده از روش SA لازم است که مقادیر پارامترهاي اولیه که شامل ضریب کاهش دما، درجه حرارت اولیه، درجه حرارت نهایی و تعداد تکرارهاي لازم در هر دما (epoch) تعیین شوند. براي این منظور از پارامترهایی مرجع [16] استفاده شده است که به این ترتیب است:

جدول 1: پارامترهاي اولیه الگوریتم SA
مقدار پارامتر
10000 تعداد تکرارها در هر دما
0,9 ضریب کاهش دما
1 درجه حرارت اولیه
0,000005 درجه حرارت نهایی

نتایج محاسباتی
براي حل مدل ترکیبی مطرح شده در ابعاد بزرگ تر، SA روش خوبی است. در این بخش، 3 مسئله با استفاده از جدول (2) تعریف شدهاند. براي این مسئله از سه روش توضیح داده شده در بالا (روش WEDD، ابتکاري و تصادفی) براي به دست آوردن جوابهاي اولیه استفاده شده است.
جدول 2: اطلاعات مسئله
AN RT CL WT DD RWY1 RWY2 RWY3 RWY4 PCR1 PCR2 PCR3 PCR4 PCR5 PCR6
1 0 4 0,8 15 6 7 8 4 6 7 9 10 5 7
2 2 1 1 13 2 2 4 5 2 2 4 3 9 9
3 17 2 0,6 29 4 5 3 3 4 5 4 4 8 8
4 7 4 0,5 24 6 6 5 4 7 6 5 2 8 8
5 9 3 0,5 18 4 6 3 4 5 6 3 5 4 10
6 10 1 0,5 27 5 6 6 3 6 6 6 5 10 7
7 3 4 0,7 26 2 3 4 3 3 3 5 5 9 6
8 3 2 0,6 16 2 5 4 5 3 5 4 8 11 3
9 11 3 0,7 35 6 3 4 3 6 3 5 8 12 4
10 19 4 0,5 38 5 4 6 4 6 5 6 10 5 6
11 20 1 0,8 18 2 6 8 6 7 7 10 11 4 4
12 20 1 0,7 19 4 7 8 4 2 7 2 10 5 5
13 20 3 0,7 21 3 7 5 5 2 2 3 8 4 9
14 21 2 0,7 22 3 6 6 4 3 5 5 6 6 10
15 23 3 0,3 23 5 4 7 3 7 3 4 6 7 11
16 25 4 0,5 25 6 3 3 4 5 3 6 6 10 8
17 25 4 0,6 26 3 5 4 4 7 4 6 7 9 4
18 25 1 0,3 26 4 4 4 5 2 6 6 8 8 10
19 25 2 0,4 26 5 4 5 3 3 5 7 11 3 8
20 25 4 0,6 26 5 4 4 6 8 6 8 10 5 4
مسیر هواییPCR= و باند, RWY= موعد تحویل, DD= وزن, WT= کلاس, CL= زمان در دسترس بودن, RT= شماره هواپیماAN=

جدول 2: مقدار میانگین و انحراف معیار تابع هدف مسئله 1 (15 هواپیما ، 3 مسیر هوایی و 3 باند)
WEDD روش روش تصادفی روش ابتکاري
ضریب میانگین انحراف معیار میانگین انحراف معیار میانگین انحراف معیار
3,0و7,0 70,85 2,17 74,67 4,11 70,23 2,66
2,0و8,0 65,90 2,42 66,80 3,24 58,41 2,56
1,0و9,0 59,90 1,53 60,54 2,79 54,00 1,67
05,0و95,0 59,55 1,65 55,62 2,14 53,53 2,51
1و0 48,68 2,08 48,78 2,20 51,44 1,40

جدول 3: مقدار میانگین و انحراف معیار تابع هدف مسئله 2 (20 هواپیما ، 3 مسیر هوایی و 3 باند)
WEDD روش روش تصادفی روش ابتکاري
ضریب میانگین انحراف
معیار میانگین انحراف
معیار میانگین انحراف
معیار
3,0و7,0 114,84 2,68 118,70 3,76 110,47 2,62
2,0و8,0 109,85 2,84 97,00 3,29 104,40 1,88
1,0و9,0 105,00 1,65 97,19 1,75 99,68 2,04
05,0و95,0 93,40 2,19 94,13 3,01 95,80 1,94
1و0 95,96 2,25 85,71 2,84 78,65 3,70

جدول 4: مقدار میانگین و انحراف معیار تابع هدف مسئله 3 (20 هواپیما ، 6 مسیر هوایی و 4 باند)
WEDD روش روش تصادفی روش ابتکاري
ضریب میانگین انحراف معیار میانگین انحراف معیار میانگین انحراف معیار
3,0و7,0 161,54 4,81 171,10 4,64 164,56 2,21
2,0و8,0 157,51 4,21 156,63 3,96 153,20 1,72
1,0و9,0 148,63 4,08 154,50 3,56 140,94 2,36
05,0و95,0 128,53 5,06 146,80 3,90 139,72 2,14
1و0 127,04 4,00 144,43 3,17 129,00 2,18

نتایج محاسباتی این 3 مسئله در جداول (3)، (4) و(5) نشان داده شده است. در این جداول براي ضرایب مختلف تابع هدف ()، مقدار میانگین و انحراف معیار تابع هدف با توجه به جواب اولیههاي مختلف بهدست آمده است.
قابل ذکر است که ضریب  براي تأخیر هواپیماها و ضریب 1 براي میزان اشغال باندها و مسیرهاي هوایی توسط هواپیماها در نظر گرفته شده است. چون مقدار عددي تأخیرات در مسائل اغلب بیشتر مدت زمان اشغال است، در نتیجه ضریب تأخیرات در این تحقیق، بزرگ تر در نظر گرفته شده است.
همان طور که در جدول (4) دیده میشود، در ضریب 7,0 و 3,0 تقریباً میانگین دو روش ابتکاري و WEDD با هم برابر است، ولی در سایر ضرایب به جز 1 و 0 روش ابتکاري جواب بهتري نسبت به سایر روشها ارائه می دهد.
فقط در ضریب 1 و 0 روش WEDD بهترین جوابها را ارائه میدهد.
با توجه به جدول (5) فقط در ضریب 95,0 و 05,0 است که روش WEDD جوابهاي بهتري را تولید می-
کند، در حالی که در سایر روشها مانند بالا، روش ابتکاري بهترین جوابها را ارائه میکند.

همان طور که در جدول (6) ملاحظه میشود، در
ضرایب 7,0 و 3,0 ، 95,0 و 05,0 ، 1 و 0 روش WEDD جوابهاي بهتري را تولید میکند و در سایر ضرایب، روش ابتکاري جوابهاي بهتري را تولید میکند.
با توجه به این توضیحات میتوان دریافت که در بیشتر ضرایب، روش ابتکاري جوابهاي بهتري به دست میآورد و در تعداد معدودي، روش WEDD جواب هاي بهتري را تولید میکند که هر چه ابعاد مسئله بزرگ تر میشود این مورد را بیشتر می توان مشاهده کرد.

نتیجهگیري
با توجه به این واقعیت که افراد خبره مدت زمان محدودي براي انتخاب گزینه خوب دارند (که اغلب هم به یک توالی بهینه ختم نمیشود)، در نتیجه این افراد نیاز به یک ابزار تصمیمگیري براي تخصیص پروازها به باندها دارند. بنابراین استفاده از این ابزارها اجتناب ناپذیر به نظر میرسد.
در این تحقیق براي اولین بار، از روش زمانبندي و توالی عملیات، براي برنامهریزي و تخصیص باندها استفاده شده است. براي این مسئله از مدل ماشینهاي سري انعطافپذیر (Flexible Flow Shop) دومرحلهاي با در نظر گرفتن حالت No-wait با تابع هدف دو معیاره استفاده شده است.
براي حل مدل این تحقیق از روش فراابتکاري SA استفاده شده است که این روش میتواند در مسائلی با ابعاد بزرگ (در ترافیک سنگین) و در مدت زمان کم به جوابهاي قابل قبولی دست یافت. این تحقیق نشان می-دهد که اگر جوابهاي روش ابتکاري به عنوان جواب اولیه براي الگوریتم SA استفاده شود، می تواند در اکثر موارد بهترین نتایج را ارائه کند.
نتایج این تحقیق نشان میدهد که در بیشتر موارد
(حدود 70%) جواب اولیه حاصل از روش ابتکاري، بهترین نتایج را ارائه میکند و در تعداد محدودي از موارد روش WEDD جوابهاي بهتري را به دست می دهد.

فهرست علائم
َATM: مدیریت ترافیک هوایی ROM: مدیریت عملیات باند
ROP: برنامهریزي عملیات باند
SPT: کوتاهترین مدت زمان فرآیند
WEDD: زودترین موعد تحویل وزندار
مراجع
Soomer, M. J. (2006). “Equitable hub airport scheduling using airline costs.” November, National aerospace
Laboratory NLR.
Jason, A.D., Atkin, Edmund K., Burke, John S., Greenwood and Reeson, D. (2007). “Hybrid meta-heuristics to aid runway scheduling at London Heathrow airport.” Transportation Science, Vol. 41, No. 1, PP. 90–106.
Anagnostakis, I., H.R., Clarke, J-P., Ferone, E., Hansman, R.J., Odoni, A. and Hall, W.D. (2000). “ A conceptual design of a departure planner decision aid.” Presented at the 3rd USA/EUROPE AIR TRAFFIC MANAGEMENT R&D SEMINAR, Naples, Italy, 13th – 16th June.
Saffarzadeh, M., Kordani, A. A. and Beheshtinia, M. A. ( 2007). “A New Approach in Runway Operations
Management for Airside Capacity Enhancement.” Air Transport research Society, Conference ATRS 2007, Berkeley.
Anagnostakis, I., Clarke J-P, B¨ohme D., V¨olckers Uwe, (2001). “Runway operations planning and control, sequencing and scheduling.” Proceedings of the 34th Hawaii International Conference on System Sciences (HICSS-34), Hawaii, January 3-.6
Isaacson, D.R. and Robinson, J.E. (2001). “A knowledge-based conflict resolution algorithm for terminal area air traffic control advisory generation.” American Institute of Aeronautics and Astronautics, 2001-.6114
Isaacson, D.R., Davis, T.J. and Robinson, J.E. (1997). “Knowledge-based runway assignment for arrival aircraft in the terminal area.” To be published at the AIAA Guidance, Navigation, and Control Conference, New Orleans, LA August 11-.31
Soomer, M.J. and Franx, G.J. (2006). “Scheduling aircraft landings using airlines’ preferences.” European Journal of Operations Research, Submitted for publication (in revision).
Baker, Kenneth R. (1974). “Introduction to sequencing and scheduling. John Wiley & Sons.”
Lawler, E.L. (1977). “A pseudopolinomial algorithm for sequencing jobs to minimize total tardiness.” Annals of Discrete Mathematics 1, 331-342.
Lenstra, J.K. (1977). “Sequencing by enumerative methods.” Mathematical Center Tracts 69, Mathematical Centrum, Amsterdam.
Santos, D.L., Hunsucker, J.L. and Deal, D.E. (1996). “An evaluation of sequencing heuristics in flow shops with multiple processors.” Computers & Industrial Engineering, 30(4), PP. 681–91.
Kirkpatrick, S., Gelatt Jr CD, Vecchi, M.P. (1983). “Optimization by simulated annealing.” Science; 220(4598):671–80.
Saffarzadeh, M., Kordani, A. A. and Beheshtinia, M. A. (2007). A New Approach in Runway Operations
Management for Airside Capacity Enhancement. Air Transport research Society, Conference ATRS 2007, Berkeley.
Chams, M., Hertz, A. and de Werra, D. (1987). “Some experiments with simulated annealing for colouring graphs.” European Journal of Operational Research, 32, 260-266.
Johnson, D.S., Aragon, C.R., McGeogh, L.A. and Schevon, C. (1987). “Optimization by simulated annealing: An experimental evaluation.” Part I. AT&T Bell Laboratories, Murray Hill, N J, preprint.
Saffarzadeh, M., Kamal Abadi, I.N., Kordani, A.A. and Gangraj, E.A. ( 2008). “A New Approach in Airport Capacity Enhancement Based on Integrated Runway Assignment and Operations planning Model.” Journal of Applied Science, Volume 8, No. 17.
واژه هاي انگلیسی به ترتیب استفاده در متن
Air Traffic Management
Decision Aiding
Runway Operation Management 4- Runway Operation Planning



قیمت: تومان


دیدگاهتان را بنویسید