نشریه تخصصی مهندسی صنایع، دوره 48، شماره 1، فروردین ماه 1393، از صفحه 67 تا 72 (یادداشت فنی) 67 مدل ریاضی چند هدفه براي تخصیص بهینه کانتر و گیت به پروازهاي
ورودي (فرودگاه امام خمینی)

علیرضا رشیدي کمیجان1، مرضیه حسنی دوغآبادي*2 و کامران جمالی فیروزآبادي3
1و 3 استادیار گروه مهندسی صنایع – دانشگاه آزاد اسلامی- واحد فیروزکوه
2کارشناس ارشد مهندسی صنایع- دانشگاه آزاد اسلامی- واحد فیروزکوه- باشگاه پژوهشگران جوان
(تاریخ دریافت 4/8/92، تاریخ دریافت روایت اصلاح شده 5/11/92، تاریخ تصویب 18/12/92 )

چکیده
امروزه با توجه به بالا رفتن سطح توقع مسافران و محدودیت منابع، لازم است مدیران و مسئولان فرودگاهها، براي تدوین برنامه مناسب در راستاي تخصیص هر چه بهینهتر منابع، گام بردارند. از جمله منابع یک فرودگاه، گیت و کانتر هستند. در این تحقیق با در نظـر گـرفتن مسئله تخصیص کانتر و گیت به طور همزمان به پروازهاي ورودي، مدل ریاضی مربوطه ارائه شده است. اهداف مدل شامل حداقل کردن طول مسیر پیادهروي مسافران، حداقل کردن تعداد پروازهاي تخصیص یافته به پارکینگ و تخصیص یک در میان گیتها (به عنوان محدودیت نرم) است. براي حل مدل ریاضی صفر و یک با تابع هدف چندگانه (١MODM) پس از نرمالسـازي و تبـدیل آن بـه یـک هـدف، از روش دقیـق(توسط نرمافزار GAMS) استفاده شده است. از جمله محدودیتهاي مدل که در تحقیقات دیگر کمتر به آن پرداخته شده است، میتوان به تخصیص پروازهاي مشابه به یک ترمینال و برقراري توازن در ترمینالهاي فرودگاه اشاره کرد.

واژه هاي کلیدي: کانتر، گیت، پروازهاي ورودي، تخصیص، مدل ریاضی صفر و یک

مقدمه
امروزه با توجه به کمبود امکانات و تجهیزات در مقابل تقاضاهاي موجود و بالا رفتن سطح توقع مسافران، مسائل و مشکلات فرودگاهها اهمیتی دوچندان یافته است. بنابراین لازم است مدیران و مسئولان فرودگاهی براي بهبود عملیات خود از ابزارها و تکنیکهاي علمی بهره گیرند تا در جهت افزایش کارآیی منابع موجود از آنها استفاده کنند. از جمله منابع یک فرودگاه، گیتها و کانترها هستند که براي سرویسدهی به پروازها از آنها استفاده میشود.
Email: [email protected] ،09151098646 :نویسنده مسئول: تلفن *

بنابراین ضروري است با در نظر گرفتن مسئله تخصیص گیت و کانتر به پروازها، تا حد امکان بتوان در جهت بهبود وضعیت فرودگاه و نیز جلب رضایت مسافران، گام برداشت. در این راستا در تحقیق حاضر، مدلسازي ریاضی تخصیص کانتر و گیت به پروازهاي ورودي ارائه شده است. مدل مربوطه سه هدفه بوده و شامل حداقل کردن فاصله پیادهروي مسافران و حداقل کردن تعداد پروازهاي تخصیص یافته به پارکینگ است. هدف سوم نیز مربوط به محدودیت نرم مدل است که تخصیص یک در میان گیتها را برقرار میکند. از جمله محدودیتهاي مدل میتوان به تخصیص هر پرواز به یک گیت، نبود تخصیص دو پرواز همزمان به یک گیت، برقراري توازن در گیتهاي ترمینالها، محدودیت تخصیص در برخی گیتها و تخصیص پروازهاي با مشخصات یکسان به گیت هاي یک ترمینال در طول افق برنامهریزي، اشاره کرد.
لازم به ذکر است تخصیص همزمان گیت و کانتر به پروازهاي ورودي، تخصیص پروازهاي مشابه به یک ترمینال، برقراري توازن در ترمینالهاي فرودگاه و تخصیص یک در میان گیتها، از جمله مسائلی است که کمتر به آن پرداخته شده و یا اصلاً در مورد آن تحقیقی ارائه نشده است. در اکثر تحقیقات انجام شده در زمینه گیت، حداقل فاصله پیادهروي مسافران به عنوان یک هدف مهم مد نظر بوده است. از جمله این تحقیقات میتوان به موارد زیر اشاره کرد: مهارجان و همکاران2 (2011) [1] مدل برنامهریزي عدد صحیح صفر و یک را براي تخصیص مجدد بهینه هواپیماها به گیتها براي پاسخ به تغییرات روزانه با هدف حداقل کردن فاصله پیادهروي پروازهاي ارتباطی یا اصلی ارائه دادند. برخی از تحقیقات ارائه شده براي حل، از رویکرد فراابتکاري استفاده کردند. چنگ و همکاران3 (2012) [2] مسئله تخصیص گیت را با هدف حداقل کردن فاصله پیادهروي مسافران با استفاده از الگوریتمهاي فراابتکاري ژنتیک4، تبرید تدریجی5 و جستجوي ممنوع6 و رویکرد ترکیبی تبرید تدریجی و جستجوي ممنوع حل کردند. حسنآبادي (1381) [3] یک مدل ریاضی براي تخصیص هواپیما به گیت را ارائه کرد. در این تحقیق، برخی از پارامترهاي مدل که قطعیت نداشتند، به صورت فازي در نظر گرفته شده و مدل با استفاده از روش فراابتکاري الگوریتم ژنتیک حل شده است. عبدي و همکاران (1390) [4] براي بهینه کردن ظرفیت بخش هوایی فرودگاه، زمانبندي ماشینهاي سري انعطافپذیر با مدل دو معیاره را ارائه کرده و مسئله را با روش فراابتکاري تبریدي تدریجی حل کردند. ژنگ و همکاران7 (2010) [5] مسئله تخصیص گیت را با هدف حداقل کردن واریانس کل زمان کمبود ارائه کردند. مدل ارائهشده توسط الگوریتم فراابتکاري جستجوي ممنوع، حل شده است. درندرف و همکاران8 (2012) [6] مسئله تخصیص گیت به پرواز را با در نظر گرفتن تابع چند هدفه ارائه و براي حل آن از یک الگوریتم ابتکاري استفاده کردند. در زمینه تخصیص کانتر به پروازها نیز میتوان تحقیقات زیر را نام برد:
چان9 (1996) [7] مسئله زمانبندي چند بعدي را ارائه کرد که در آن، زمانبندي کانترهاي ورودي در فرودگاه بینالمللی مد نظر قرار گرفت. پارك و همکاران10 (2003) [8] مدل عملیات کانتر را بر اساس رفتار مسافران (الگوي ورود) ارائه کردند. مدل با استفاده از الگوي توزیع ورود مسافران، مناسبترین تعداد کانترها را محاسبه میکند. یان و همکاران (2004) [9] مسئله تخصیص کانترهاي ورودي را بررسی کردند که در آن دو مدل ارائه شد. در مدل اول ،هدف، حداقل فاصله پیادهروي و در مدل دوم حداقل کردن مقدار ناسازگاري همه پروازها در نظر گرفته شد. این مدل با استفاده از روش سیمپلکس و
شاخه و حد حل شد. استولز11 (2010) [10] برنامهریزي نیروي کار براي کانترهاي ورودي فرودگاه را مدلسازي کرد و مسئله توسط CPLEX حل شد.
بر اساس این موارد در ادامه مدل، متغیرها و پارامترهاي آن، محدودیتها و تابع هدف ارائه شده است.
سپس مدل مورد بررسی حل شده و نتایج حاصل و تجزیه
و تحلیل نتایج بیان شده و در پایان نیز نتیجهگیري وپیشنهادات بعدي مطرح شده است.

2- شرح مدل
مدلسازي براي یک بازه دو روزه از پروازهاي ورودي فرودگاه امام خمینی انجام شده است. در ادامه، اجزاي مدل بیان شده است.

2 -1 – مفروضات مدل
مفروضات مدل به این ترتیب است:
− ورود پروازها قطعی و معلوم است.
− در صورت نبود گیت خالی، پروازهاي ورودي به پارکینگ خواهند رفت.
− کل فرودگاه یک پارکینگ دارد.
− ظرفیت پارکینگ نامحدود است.
− برنامهریزي گیت و کانتر براي 2 روز انجام میشود.
− تعداد گیتهاي قابل تخصیص به پروازهاي ورودي مشخص است.
− در هر زمان که تخصیص گیت انجام گرفت، در همان دوره تخصیص کانتر نیز انجام میشود.
− مسافران ترانزیت در نظر گرفته نشده است.

2 -2 – اندیسها و مجموعهها
در این مدل، اندیسها و مجموعهها به صورت زیر تعریف میشوند:
Ft: مجموعه پروازهاي ورودي در زمان t FFt: مجموعه پروازهایی که امکان تخصیص به گیت در دوره t را دارند (یا در دوره t وارد شدهاند یا 1-t به عبارت
دیگر ∪=)
f,f’: اندیس پروازهاي ورودي ((f,f’ ∈ Ft or FFt F: مجموعه کل پروازها
Gp: مجموعه گیتهاي در دسترس ترمینال p
(g,g’ ∈ Gp) اندیس گیت :g,g’
Cp: مجموعه کانترهاي در دسترس در ترمینال p c: اندیس کانتر ((c ∈ Cp P: مجموعه ترمینالها
p,p’: اندیس ترمینال (p,p’ ∈ P) T: مجموعه کل بازه زمانی (2 روز) t,t’: اندیس زمان
Tf: مجموعه بازههاي زمانی که پرواز f میتواند به گیت اختصاص یابد (منظور همان دوره ورود و دوره بعدي است).
FLcom: مجموعهاي که هر عضو آن چندتایی مرتبی است؛ شامل همه پروازهایی که مبدأ و مشخصات یکسانی دارند.
Fcom: هر یک از اعضاي مجموعه FLcom

2 -3 – پارامترها
در مدل ارائه شده ،پارامترها به صورت زیر در نظر گرفته میشوند:
wg,c: فاصله گیت g تا کانتر c (بر حسب متر) mf: تعداد مسافران پرواز f capc: ظرفیت کانتر c
hg, f: اگر پرواز f از نظر فنی امکان ورود به گیت g را داشته باشد، برابر یک، در غیر اینصورت صفر است.
NGp: تعداد گیتهاي ترمینال p

2 -4 – متغیرهاي تصمیم
مدل ارائه شده در این تحقیق شامل سه متغیر تصمیم اصلی به صورت زیر است:
xt,p,g,f: اگر پرواز f در دوره زمانی t به گیت g در ترمینال p تخصیص یابد، یک و در غیر این صورت صفر.
yt,p,c,f: اگر پرواز f در دوره زمانی t به کانتر c در ترمینال p تخصیص یابد، یک و در غیر این صورت صفر.
rt,f: اگر پرواز f در دوره زمانی t به پارکینگ تخصیص یابد، یک و در غیر این صورت صفر.
, : متغیرهاي مربوط به محدودیت آرمانی که عدد صحیح هستند.

2 -5 – محدودیتها
محدودیتهاي مدل به صورت زیر ارائه میشود. لازم
مدل ریاضی چند هدفه ….. (یادداشت فنی) 69
برخی پروازها را نمیتوان به برخی گیتها تخصیص داد (که این مورد وابسته به نوع هواپیما است).
20726407674

∑ ∈,,,≤ ℎ , ∀∈;
; ∈

اگر یک پرواز به پارکینگ رفت، در زمان بعدي باید حتماً به گیت برود:
,= ∑ ∈ ∑ ∈(),,, ∀∈
2474976-29014

; ∈
دو پرواز در یک زمان نباید به یک گیت تخصیص یابند:
∑ ∈,,,≤ 1 ∀∈;∈;∈

(4)

5- اگر یک پرواز به هر یک از گیتهاي ترمینال p وارد شد، باید به یکی از کانترهاي آن ترمینال هم وارد شود. همچنین مجموعه کانترها باید کل مسافران هر پرواز را پوشش دهند:
∑ ∈×≤ ∑ ∈ ×
y ∀∈; ∈; ∈
(5)

6 – هر پرواز حداکثر 3 کانتر را اشغال میکند و همچنین اگر یک پرواز به هر یک از کانترهاي ترمینال p وارد شد ،باید به یکی از گیتهاي آن نیز وارد شده باشد:
726440-28691

∑ ∈ ∀∈
; ∈;
(6)
7- دو پرواز در یک زمان نباید به یک کانتر تخصیص یابند:
به ذکر است که اندیس t به عنوان هر یک ساعت تعریف ∈;∈;∈∀ 1 ≤, ,,∈ ∑
2523744190483

میشود. (7) 1- در مجموع دوره زمانی، هر پرواز به یک گیت تخصیص مجموعه پروازهایی که در کل افق برنامهریزي تکرار مییابد. میشوند، نباید به ترمینالهاي متفاوت تخصیص یابند:
3139440221040

∑ ∈∑ ∈,,,=,,,+,= 1 ∀∈;
∑ ∈∑ ∈,,, ∀∈;,∈
,< (8) (1)

9- توازن در ترمینالها برقرار شود. یعنی در هر زمان بخش سوم تابع هدف، براي حداقل کردن تعدادپروازها به تعداد برابر یا با حداقل اختلاف به ترمینالها پروازهاي تخصیص یافته به پارکینگ است:

در قسمت دوم (2(minz به علت وجود ضرب دو متغیر ((xtpgf×ytpcf تابع هدف، غیر خطی است. براي خطیسازي آن، در تابع هدف بهجاي حاصلضرب دو متغیر بالا به شکل زیر عمل میشود:
,,,×,, ,=,,, ,
(17)
بنابراین تابع هدف در بخش اول به شکل زیر بازنویسی میشود: ∑ ∈∑ ∈,,,−
∈ ′∈,′, ,≤1
∀t ∈ T; p, p ∈ P, p <′
(9)
از آنجا که وجود قدر مطلق در مدل، آن را از حالت خطی بودن خارج میکند، بنابراین براي جلوگیري از این امر به جاي عبارت بالا، عبارات زیر قرار میگیرد:
∑ ∈∑ ∈,,,−
∈ ′∈,′, ,≤1
-355592147297

تخصیص یابند: (16) ,minz= ∑ ∈ ∑ ∈r
3088640182880

∀t ∈ T; p, p ∈ P, p <
,,,, , , , , − (10)
(18)
871728195230

(11) 1−≥,<,′t ∈ T′; p∈, p ∈ P,, p∈∀در ادامه براي تکمیل کردن خطیسازي تابع هدف ،
1793240221277

موارد زیر به محدودیتها اضافه می:
,,, +,, ,,,, ,+ 1
10- گیتها در هر ترمینال به صورت یک در میان
تخصیص یابند: ; ∈; ∈ ;∈ ;
,,,,, ,,,, ,
; ∈; ∈ ;∈ ;∈
(20)

3- حل مدل و تجزیه و تحلیل نتایج
پایانه مسافري فرودگاه، مهمترین بناي فرودگاه است.
ظرفیت پذیرش پایانه مسافري امام خمینی 5/4 میلیون ∑ ∈,,,+ ∑ ∈,,,≤
1 ∀∈;∈ ; ∈ , < (12)

محدودیت بالا، به شکل یک محدودیت نرم در نظر گرفته میشود بنابراین:
∑ ∈,,,+ ∑ ∈,,,+−
−=1 ∀∈;∈ ; ∈ , <
2 ≥+
(13)نفر مسافر بینالمللی در سال است که امکان پذیرش تا 5 میلیون نفر مسافر را با امکانات رفاهی و خدماتی در سطح
2 -6 – تابع هدف
3088640703151

مدل تخصیص گیت و کانتر براي پروازهاي ورودي ،یک مدل سه هدفه است. بخش اول تابع هدف با توجه به محدودیت آخر در بالا به صورت زیر تعریف میشود:
,

3063240700780

بخش دوم تابع هدف، شامل حداقل کردن طول مسیر پیادهروي مسافران از گیت تا کانتر براي مسافران ورودي است:
m w , x , , , y , , ,
بینالمللی دارد. لازم به ذکر است که فرودگاه امام، دو ترمینال براي ورود و خروج پروازها دارد. در این تحقیق براي هر ترمینال 4 گیت و 8 کانتر به صورت فعال در نظر گرفته شده است. ظرفیت هر کانتر 300 نفر و فاصله گیتها تا کانترها نیز برحسب متر و از 1 تا 5,3 متر، تغییر میکند. چیدمان گیتها و کانترها نسبت به هم به صورت موازي و متقارن در نظر گرفته شده است.
مدل توسط نرمافزار GAMS کدنویسی و در جدول 1 نحوه تخصیص پروازها به گیتها (G) و کانترها (C) و در واقع بار کاري براي ترمینال A طی کل دوره برنامه ریزي نشان داده شده است.

همانطور که از جدول بالا مشخص است، بار کاري کانترهاي 1، 2، 7 و 8 صفر و یا بسیار کم است. با توجه به هدف کاهش فاصله پیادهروي مسافران از گیت تا کانتر ،این نحوه تخصیص کاملاً بدیهی است. همچنین در مورد محدودیت نرم مدل، تخصیص پروازها به گیتها در هر دوره به صورت یک در میان انجام شده است و نیز هر پرواز به یک گیت تخصیص یافته و دو پرواز در یک زمان به یک گیت و کانتر تخصیص نیافتهاند.
با تحلیل حساسیت مدل و تغییر مقادیر پارامترهاي آن شامل تعداد گیتها، تعداد و ظرفیت کانترها ،همه نتایج حاکی از آن است که با افزایش هر یک از این موارد، مقدار تابع هدف بهبود مییابد. نتایج تحلیل حساسیت براي تغییر همزمان تعداد گیت و کانتر در جدول 2 نشان داده شده است که این نتایج را نیز اثبات میکند. لازم به ذکر است که در هر یک از حالات جدول زیر، ترتیب چیدمان گیتها و کانترها از ابتدا انجام شده، اما چیدمان موازي و متقارن آنها نسبت به هم حفظ شده است.
همه موارد جدول ذکرشده، در حالتی که ظرفیت کانترها به 1000 نفر افزایش یافت ،بار دیگر انجام شد و
مدل ریاضی چند هدفه ….. (یادداشت فنی) 71

جدول 1: گیتها و کانترهاي مشغول در ترمینال A طی هر بازه زمانی دوره برنامهریزي

مقدار تابع هدف در هر یک از حالات بالا به نصف کاهش یافت.

جدول 2: تغییرات تابع هدف نسبت به تغییر همزمان تعداد گیت و کانتر

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

مراجع
بازه برنامهریزي را بیشتر و ابعاد آن را بزرگتر کرده و در صورت ناتوانایی حل توسط GAMS، از الگوریتمهاي فراابتکاري استفاده کرد. لازم به ذکر است که در سایر فرودگاهها نیز با مد نظر قرار دادن شرایط آنها و ایجاد تغییرات مناسب در مدل، میتوان برنامهریزي مناسب براي تخصیص گیت و کانتر را ارائه داد.
Maharjan, B. and Matis, T.I. (2011). “An optimization model for gate reassignment in response to flight delays.” Journal of Air TransportManagement, Vol. 17, Issue 5, PP. 256-261.
Cheng, C-H., Ho, S.C. and Kwan, C-L. (2012). “The use of meta-heuristics for airport gate assignment.” Expert Systems with Applications, Vol. 39, Issue 16, PP. 12430-12437.
Hassanabadi, M. (2002). Solving and analysis of aircraft-gates assignment problem of the airport in condition of uncertainty. Thesis of M.Sc, Iran University of Science and Technology.
Abdi, A., Asadi Gangraj, E., Saffarzadeh, M., Jolai, F. and Nahavandi, N. (2011). “Airside of airport capacity enhancement based on flexible flow shop multi-objective scheduling model.” Journal of Indutrial Engineering, Vol. 45, Issue 2, PP. 175- 185.
Zheng, P., Hu, S. and Zhang, C. (2010). “Airport Gate Assignments Model and Algorithm.” 3rd IEEE International Conference on Computer Science and Information Technology (ICCSIT), Chengdu, China,Vol. 2, PP. 457-461.
Dorndorf, U., Jaehn, F. and Pesch, E. (2012). “Flight gate scheduling with respect to a reference schedule.” Annals of Operation Research, Vol. 194, Issue 1, PP. 177–187.
CHUN, H.W. (1996). “Scheduling as a Multi-dimensional Placement Problem.” Engineering Application of Artificial of lntelligence, Vol. 9, Issue 3, PP. 261-273.
Park, Y. and Ahn, S.B. (2003). “Optimal assignment for check-in counters based on passenger arrival behaviour at an airport.” Transportation Planning and Technology, Vol. 26, Issue 5, PP. 397-416.
Yan, S., Chang, K-C. and Tang, C-H. (2005). “Minimizing inconsistencies in airport common-use checking counter assignments with a variable number of counters.” Journal of Air Transport Management, Vol. 11, Issue 2, PP. 107–116.
Stolletz, R. (2010). “Operational workforce planning for check-in counters at airports.” Transportation Research Part E: Logistics and Transportation Review, Vol. 46, Issue 3, PP. 414-425.
واژههاي انگلیسی به ترتیب استفاده در متن
1- Multi Objective Decision Making 2- Maharjan et al.
Cheng et al.
Genetic Algorithm
Simulated Annealing 6- Tabu Search 7- Zheng et al.
Dorndorf et al.
Chun
Park et al.
Stolletz



قیمت: تومان


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