مدل‌سازی چند هدفه مساله تخصیص گیت با استفاده از الگوریتم NSGA-II ومحدودیت اپسیلون

خطیبی, ساناز; خاکزار بفروئی, مرتضی; رحمانی, مرتضی

doi:10.22075/jme.2017.2855

اداره چاپ و انتشارات دانشگاه سمنان

تعداد نشریات	21
تعداد شماره‌ها	610
تعداد مقالات	9,027
تعداد مشاهده مقاله	67,082,824
تعداد دریافت فایل اصل مقاله	7,656,336

	مدل‌سازی چند هدفه مساله تخصیص گیت با استفاده از الگوریتم NSGA-II ومحدودیت اپسیلون
مدل سازی در مهندسی
مقاله 30، دوره 15، شماره 51، دی 1396، صفحه 397-410 اصل مقاله (684.02 K)
نوع مقاله: پژوهشی
شناسه دیجیتال (DOI): 10.22075/jme.2017.2855
نویسندگان
ساناز خطیبی؛ مرتضی خاکزار بفروئی^* ؛ مرتضی رحمانی
پزوهشکده توسعه تکنولوژی
تاریخ دریافت: 13 اردیبهشت 1394، تاریخ بازنگری: 13 مهر 1394، تاریخ پذیرش: 17 آبان 1394
چکیده
برنامه‌ریزی گیت یکی از فعالیت‌های کلیدی در فرودگاه‌هاست که به عنوان یک مسأله بهینه‌سازی تعریف می‌شود. هدف اصلی این پژوهش پیدا کردن یک تخصیص مناسب برای پروازهای ورودی و خروجی با درنظر گرفتن مجموعه‌ایی از محدودیت‌های کاربردی است. یکی از اهدافی که کمتر مورد توجه قرار گرفته است، بالانس نمودن بار کاری گیت‌ها با استفاده از تعداد مسافران می‌باشد. در این مقاله، این هدف به همراه دو هدف کمینه‌کردن تأخیرهای بوجود آمده در زمان تخصیص گیت به هواپیما و بیشینه کردن امتیاز اولویت تخصیص گیت (کنترل ازدحادم مسافران) که تاکنون باهم در نظر گرفته‌ نشده‌اند، به عنوان اهداف این مسأله در نظر گرفته شده است. مسأله به شکل برنامه‌ریزی عدد صحیح مختلط مدل‌سازی شده است. همچنین این مدل با استفاده از داده‌های واقعی فرودگاه بین‏المللی مهرآباد در ابعاد کوچک و متوسط حل شده است. به منظور یافتن مجموعه جواب‌های پارتو، الگوریتم NSGA-II پیشنهاد و برای نشان دادن کارآیی الگوریتم جواب‌های بدست آمده در ابعاد کوچک با جواب‌های بدست آمده از روش محدودیت اپسیلون مقایسه شده است. نتایج نشان می‌دهد که درصد خطای توابع هدف نسبت به روش محدودیت اپسیلون در تمامی مسایل حل شده کمتر از 1.5% است که کارآیی الگوریتم پیشنهادی را نشان می‌دهد. افزایش نمایی زمان حل با استفاده از روش محدودیت اپسیلون در مقابل افزایش خطی توسط NSGA-II نشان دهنده کارآیی روش حل توسعه داده شده، برای حل مساله در ابعاد واقعی و بزرگ است.
کلیدواژه‌ها
حمل و نقل هوایی؛ برنامه‌ریزی گیت؛ تصمیم‌گیری چند هدفه؛ برنامه‌ریزی عدد صحیح مختلط؛ الگوریتم NSGA-II؛ روش محدودیت اپسیلون
عنوان مقاله [English]
Multi objective Model of airport gate scheduling problem using NSGA-II algorithm and epsilon constraint
نویسندگان [English]
sanaz khatibi؛ Morteza khakzar Bafruei؛ Morteza Rahmani

چکیده [English]
Gate scheduling is a key activity at airports that is proposed as an optimization problem. The main purpose of this problem is to find an assignment for the flights arriving and departing while satisfying a set of practical constraints. Studies show that the gate assignment tables have been used to minimize the gate flights delay and maximize the gate efficiency and productivity. Depending on the situation, different objectives become important. If the load balancing with number of passengers in the gates becomes a bottleneck one has to make sure that the flights are equally spread over the different gates. This load balancing objective function has to be balanced with other objectives, especially minimization total delay time and maximization of the total gate assignment preference score. The related problem is formulated as a mixed-integer programming (MIP). We address this problem using real life data from Mehrabad International Airport for both small and medium size problem. To find the set of Pareto solutions, NSGA-II algorithm is proposed to demonstrate the effectiveness of the solutions which is obtained in small dimensions compared with the results obtained by the method of epsilon constraint. The results show that the percentage of error of objective function compared to epsilon constraint method is less than 1.5% for all problems. Indeed, this shows the efficiency of proposed algorithm which is recommended for solving the medium and large size problem.
کلیدواژه‌ها [English]
Air Transportation, Gate Scheduling, Multi-objective decision making, Mixed Integer Programming, NSGA-II, Epsilon constraint

مراجع
[1] Dorndorf, U., Drexl, A., Nikulin, Y., and Pesch, E., "Flight gate scheduling state-of-the-art and recent development", The international Journal of management science, Vol.35, 2007, PP.326-334. [2] Babic O, Teodorovic D, Tosic V., "Aircraft stand assignment to minimize walking", Journal of Transportation Engineering, Vol. 110, 1984, PP.55–66. [3] Mangoubi DFX, Mathaisel RS., "Optimizing gate assignments at airport terminals", Transportation Science, Vol.19, 1985, PP. 173–88. [4] Haghani A, Chen MC., "Optimizing gate assignments at airport terminals", Transportation Research A, Vol. 32, 1998, PP. 437–54. [5] Yan S, Chang C-M., "A network model for gate assignment", Journal of Advanced Transportation, Vol. 32(2), 1998, PP.176–89. [6] Xu J, Bailey G., “The airport gate assignment problem: Mathematical model and a tabu search algorithm”, Proceedings of the 34th Hawaii International Conference on System Sciences, Island of Maui, Hawaii, USA, 2001. [7] Yan S, Huo C-M., "Optimization of multiple objective gate assignments", Transportation Research Part A, Policy and Practice, Vol. 35, 2001, PP. 413–32. [8] Ding H, Lim A, Rodrigues B, Zhu Y., “Aircraft and gate scheduling optimization at airports”, Proceedings of the 37th Hawaii International Conference on System Sciences, Big Island, Hawaii, USA, 2004. [9] Ding, H., Lim, A., Rodrigues, B., Zhu, Y., "The over-constrained airport gate assignment problem", Computer & Operation Research, Vol. 32, 2005, PP. 1867-1880. [10] Lim, A., Rodrigues, B., Zhu, Y., "Airport gate scheduling with time windows", Artificial intelligence Review, Vol. 24, 2005, PP. 5-31. [11] Pintea, C., Pop, P., Chira, C., Dumitrescu, D., "A hybrid ant-based system for gate Assignment Problem", Springer-Verlag Berlin Heidelberg, 2008, PP. 273-280. [12] Drexl, A., Nikulin, Y., "Multicriteria airport gate assignment and pareto simulated annealing", IIE Transactions, Vol. 40, 2008, PP.385-397. [13] Das, N., "The airport gate assignment problem with some practical constraints", Applied Management Science, Vol. 1, No. 3, 2009, PP. 315-323. [14] Nikulin, Y., Drexl, A., "Theoretical aspect of multicriteria flight gate scheduling: deterministic and fuzzy models", Springer Science, 2009. [15] Jaehn, F., "Solving the flight gate assignment problem using dynamic programming", Zeitschrift für Betriebswirtschaft, Vol. 80, No. 10, 2010, pp. 1027-1039. [16] Diepen, G., Pieters, B., van den Akker, J., Hoogeveen, J., "Finding a robust assignment of flights to gates at Amsterdam Airport Schiphol", Journal of Scheduling, Vol. 15, No. 6, 2012, pp. 703-715. [17] Bouras, A., Ghaleb, M., Suryahatmaja, U., Salem, A., "The airport gate assignment problem: A survey", The scientific world journal, 2014, PP. 1-27. [18] Marinelli, M., Dell'Orco, M., Sassanelli, D., "Transportation Research Procedia", Vol 5, 2015, PP. 211-220. [19] پایاننامه کارشناسی ارشد مهندسی صنایع، دانشگاه تربیت ،» حل مسئله تخصیص مجدد ورودیها در فرودگاهها « ، س. برازجانی مدرس، ایران، 1380 . [20] پایاننامه کارشناسی ،» حل و تجزیه تحلیل مسئله تخصیص هواپیماها به گیتهای فرودگاه در شرایط عدمقطعیت « ، م. حسنآبادی ارشد مهندسی صنایع، دانشگاه علم و صنعت، ایران، 1381 . [21] ،» مدلسازی تخصیص هواپیماها به گیتهای فرودگاه در شرایط عدمقطعیت با استفاده از الگوریتمهای فراابتکاری « ، ف. امیر جاوید پایاننامه کارشناسی ارشد مهندسی صنایع، دانشگاه آزاد واحد تهران جنوب، ایران، 1388 . [22] پایاننامه کارشناسی ارشد رشته مهندسی صنایع، سیستمهای اقتصادی و ،» بهینهسازی برنامهریزی گیتهای فرودگاه « ، س. خطیبی اجتماعی، مؤسسه آموزش عالی الغدیر تبریز، ایران، 1388 . [23] متدولوژی سیستم پشتیبان تصمیمگیری ) « ، ک. کهنسال D.S.S.) پایاننامه ،» جهت تخصیص گیت در فرودگاههای بینالمللی کارشناسی ارشد رشته برنامهریزی حملونقل، دانشگاه آزاد اسلامی، واحد علوم و تحقیقات تهران، ایران، 1390 . [24] Deb, K., Pratap, A., Sameer A. and Meyarivan T., "A fast elitist multiobjective genetic algorithm", NSGA-II, IEEE Transactions on Evolutionary Computation, Vol. 6, 2008, pp. 182-197. [25] Mavrotas G., "Effective implementation of the e-constraint method in Multi-Objective Mathematical Programming problems", Applied Mathematics Computation, 213, 2009, PP. 455–465. [26] N. Srinivas and K. Deb, (1995), "Multiobjective function optimization using nondominated sorting genetic algorithms", Evol. Comput., Vol. 2, No. 3, 1995, pp. 221–248. [27] Deb, K., Agrawal, S., Pratap, A., Meyarivan, T., "A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization", NSGA-II, Parallel problem solving from nature PPSN VI, Vol. 1917,2000, pp. 849-858. [28] Pinedo, M.L., Scheduling Theory, Algorithms and Systems, Springer, 2008. [29] آرش حبیبی، صدیقه ایزدیار و اعظم سرافرازی، تصمیمگیری چندمعیاره فازی، انتشارات کتیبه گیل، ایران، 1393
آمار تعداد مشاهده مقاله: 1,649 تعداد دریافت فایل اصل مقاله: 3,451

سامانه مدیریت نشریات علمی. قدرت گرفته از سیناوب

پیوندهای مفید

پیوندهای مفید

آمار

مدل‌سازی چند هدفه مساله تخصیص گیت با استفاده از الگوریتم NSGA-II ومحدودیت اپسیلون