توصيفگر ها :
حمل و نقل هوايي , مسئله ي توالي هواپيما , زمانبندي باند فرودگاه , الگوريتم ژنتيك , مدل رياضي
چكيده فارسي :
با رشد روزافزون جمعيت، استفاده از سيستم حمل و نقل هوايي بيش از پيش مورد توجه قرار گرفته است به گونه‌اي كه تعيين توالي و زمانبندي باند يا هواپيماها، تبديل به گلوگاه و معضل در سيستم مديريت ترافيك هوايي شده و طي ساليان پژوهشگران متعددي به دنبال راهكاري جهت برنامه‌ريزي بهتر پروازهاي فرودگاه بوده‌اند. با نگاهي به مطالعات پيشين مي‌توان متوجه شد كه ماهيت مسئله‌ي زمانبندي هواپيما، NP-hard است و حل اين مسئله تنها با استفاده از مدل رياضي و حل‌كننده‌هاي تجاري جوابگوي يك برنامه‌ريزي مناسب كه در مدت زمان كوتاه حاصل شود، نيست. چرا كه اين مسئله در دنياي واقعي حساسيت بالايي دارد، بنابراين سرعت دستيابي به توالي و زمانبندي مناسب در اينگونه مسائل از اهميت ويژه‌اي برخوردار است. بنابراين پژوهشگران با استفاده از ساير روش‌هاي حل شامل روش‌هاي دقيق مانند شاخه و كران و روش‌هاي غيردقيق مانند الگوريتم‌هاي ابتكاري و فراابتكاري اقدام به حل اين مسئله كرده‌اند. در پايان‌نامه‌ي حاضر نيز با استفاده از يك الگوريتم فراابتكاري ژنتيك و مدل رياضي به حل و بررسي مسئله‌ي زمانبندي هواپيماپرداخته شده است. در اين روش پيشنهادي، در دو مرحله از مراحل الگوريتم ژنتيك، مدل رياضي رايج در ادبيات موضوع براي پيشبرد الگوريتم جهت دستيابي به جواب‌هاي با كيفيت بيشتر به كار رفته است. هدف از بررسي اين مسئله در پايان‌نامه‌ي حاضر كمينه‌سازي ميزان كل ديركرد وزن‌دار با در نظرگيري محدوديت‌هاي رايج شامل ظرفيت باندها، جداسازي‌هاي لازم و پنجره‌هاي زماني با در نظرگيري هر دو عمليات فرود يا بلند شدن در يك فرودگاه غيرنظامي چند بانده است. پس از حل اين مسئله توسط الگوريتم پيشنهادي و 450 نمونه داده معيار در دست، جواب‌هاي به‌دست آمده با جواب‌هاي حاصل از سه عدد از بهترين روش‌هاي موجود در ادبيات موضوع مقايسه شده‌اند. همچنين مدل رياضي رايج در ادبيات موضوع در مدت زماني كه الگوريتم پيشنهادي به جواب دست يافته است به اجرا گذاشته مي‌شود و جواب‌هاي حاصل در اين حالت نيز با جواب‌هاي الگوريتم پيشنهادي تركيبي مقايسه خواهند شد. نتايج حاكي از آن است كه روش حل اين پايان‌نامه قادر است به ترتيب در 352 و 49 نمونه بهتر و برابر با بهترين جواب ادبيات موضوع و با ميانگين مدت زمان 35 ثانيه عمل كند. با توجه به كيفيت جواب‌ها و مدت زمان حل مي‌توان نتيجه گرفت كه اين الگوريتم قابليت استفاده در شرايط دنياي واقعي و زمانبندي فرودگاه‌هاي پررفت و آمد را دارد.
چكيده انگليسي :
By growing the population, the use of aviation transportation systems has become more and more notable, so that the sequencing and scheduling of runways and aircrafts have become a bottleneck and a significant problem in the air traffic management system. So, many researchers have been looking for a way and method to better plan airport flights over the years. Due to the high sensitivity of this issue in the real world, the speed of obtaining proper sequence and scheduling in such sequencing problems is of particular importance. By Looking at previous studies, it can be understood that the nature of the air-craft scheduling problem is NP-hard, and solving this problem using mathematical models with commercial solvers is not the appropriate method to achieve proper planning in a short time. Therefore, researchers have investigated this problem using other solution methods, including exact methods like a branch and bound and non-exact ones like heuristic and metaheuristic algorithms. The thesis uses a hybrid genetic and mathematical model algorithm to solve the aircraft sequencing and scheduling problem. In this proposed method, in two stages of the hybrid algorithm, the typical mathematical model of literature is used to empower the algorithm to achieve higher-quality answers. The purpose of this the-sis is to minimize the total weighted tardiness by considering the typical constraints, including runway capacity, necessary separations, and time windows regarding both landing and take-off operations in a multiple runway airport. After solving 450 instances of a famous benchmark by the proposed algorithm, the obtained solutions are compared with the ones from three of the best methods in the literature. Additionally, the typical mathematical model in the literature is implemented within the time equal to the solution time of the proposed hybrid algorithm. Finally, the results of this case will be compared with the solutions of the algorithm mentioned above. As results indicate, the method of solving, with an average duration of 35 seconds, has better and equal performance, respectively in 352 and 49 instances. According to the quality of solutions and solution time, it can be concluded that this hybrid algorithm can be used in actual-world conditions and the scheduling of busy airports.
