تعيين توالي فرود هواپيما با استفاده از الگوريتم فراابتكاري نزول همسايگي متغير

A VND META-HEURISTIC FOR AIRCRAFT LANDING PROBLEMS

«تعيين زمان‌بندي فرود هواپيماها روي باند فرودگاه» مسيله‌يي پركاربرد و در عين حال به‌لحاظ پيچيدگي محاسباتي دشوار است. اين مسيله عبارت است از تخصيص هواپيماها براي فرود به باند فرودگاه، به‌طوري‌ كه مجموع خسارات ناشي از ديركرد و زودكرد در فرود همه‌ي هواپيماها كمينه شود. پيچيدگي محاسباتي اين مسيله باعث توجه خاص به الگوريتم‌هاي ابتكاري و فراابتكاري به‌عنوان رويكردي براي حل مسيله شده است. لذا در اين نوشتار براي حل بهينه‌ي مسايل با ابعاد بيشتر از 100 هواپيما، الگوريتم فراابتكاري نزول همسايگي متغير طراحي مي‌شود. نتايج محاسباتي نشان از توانايي الگوريتم در يافتن جواب‌هاي با كيفيت بالا در يك زمان محاسباتي كوتاه براي مسايل تا اندازه 200 هواپيما و 5 باند فرود را دارند.

Aircraft landing problems consist of determining an optimal schedule of landing aircraft on airport runways and also allocating arriving aircraft to available runways. The objective of the schedule is to minimize the total deviation of landing time from the target time (both earliness and tardiness). The problem is known to be NP-hard. Thus, it is very difficult to solve large instances of the problem in a reasonable time. Therefore, the major contribution of this paper is to derive optimal and near optimal solutions for problems with up to 200 aircrafts, by developing an efficient meta-heuristic. Although the computational complexity of the problem motivates heuristics, these routines have not been well studied. In this study, at first, a mixed integer goal programming formulation, with the objective of minimizing both earliness and tardiness, is developed. The model is solved using the Cplex solver on available instances. The results are promising and show that, except for the single runway problem with 100 aircraft, all problems with up to 100 aircraft can be solved optimally very quickly. Several multi-runway larger instances with up to 200 aircraft were also solved optimally, but, for the rest, the associated computational time of the solver grows exponentially. It is very difficult to solve those instances optimally, hence, a variable neighborhood descent (VND) meta-heuristic is developed such that initial solutions are randomly generated using a simple routine, and improved using four local searches. Computational results of the meta-heuristic show that the proposed algorithm can obtain optimal solutions for all small instances, as well as for several larger instances. Besides this, it is very fast, to the extent that the maximum spent time is about 1 minute. Comparing these results with previous studies reveals several important facts: 1) the proposed mathematical formulations solve larger instances, 2) for several instances, new best solutions were reported by the VND meta-heuristic, and 3) from a resource requirement point of view, the proposed VND competes well against state-of-the-art algorithms.