【作者】 俞盛朋；

【导师】 曹先彬；

【作者基本信息】 中国科学技术大学 ， 计算机应用技术， 2010， 硕士

【摘要】 航班着陆调度(Aircraft Landing Scheduling, ALS)是机场终端区空中流量管理(Air Traffic Flow Management, ATFM)的核心,它旨在为待着陆的航班给出有效的着陆调度方案,保证这些航班能够安全且经济地着陆。研究终端区航班调度问题对确保飞行安全和提高飞行效益具有重大的意义。航班着陆调度是一个典型的组合优化问题,其存在的多约束等复杂性使得这一问题成为公认的一个难解问题;同时,应用时的调度实时性要求进一步增加了这一问题的求解难度。目前,业内实际采用的先来先服务调度方案简单快速,但它无法进一步提高飞行效率,而且在航班较密集的情况下该算法可能无法给出合理的调度方案;研究界提出的线性规划算法具有高效性和正确性,但缺乏全局搜索能力,在很多情况下很难找到最优解;计算智能算法是近年来解决航班着陆调度问题的一个研究热点,但计算代价过大,特别是在较为繁忙的机场终端区,所以它需要结合有效的启发式方法才能更好的解决航班着陆调度问题。本文提出了一种新型的优化调度方法来解决航班着陆调度问题。与以往侧重于寻找最优解的方法不同,本文将重点放在达到航班着陆调度的实时性要求上。提出了一种航班着陆调度的实时优化方法。它由两个部分组成:首先,建立基于元胞自动机(Cellular Automate,CA)模拟的虚拟航班着陆过程,得到一个相对较好的航班着陆序列;然后,提出了一种简单但有效的针对性的航班着陆优化调度算法,进一步优化航班着陆序列。在标准的数据集OR-library上的对比实验表明,该方法不仅可以得到高质量的解,而且其速度要快得多,可以满足实际航班着陆调度的性能要求。更多还原

【Abstract】 As one of the core contents of Air Traffic Flow Management (ATFM) in terminal area, Aircraft Landing Scheduling (ALS) determines an efficient landing scheduling scheme for a given set of aircrafts in order to insure the safety of aircrafts. Researches about ALS problem have great significance for flight safety and improving flight benefit.ALS is a typical combinatorial optimization problem, the existence of such complex multi-constraint makes this problem an intractable problem; and the real-time requirement increases the difficulty of the solving this problem. When there are too many planes waiting for landing, FCFS may not provide a feasible solution. Until now, there have been two kinds of scheduling algorithms for addressing ALS problem, one is Linear Programming (LP) algorithm, and the other is Computational Intelligence (CI) algorithm. LP shows high effectiveness and correctness, however it can hardly find the global optimal solution owing to lack of the ability for global search. Nevertheless CI not only has the powerful ability for global search, but also is able to handle nonlinear constraint and goal function. Therefore it has become a hot topic to resolve ALS using CI. However CI likely produces large computational cost especially at busy airports. Thereby CI needs to combine some heuristic methods to address ALS better.In this paper, we propose a novel approach to address the ALS problem. Compared to previous studies, we put more emphasis in meeting the requirement of real-time scheduling rather than securing a global optimal solution. Our approach, named Cellular-Automata-based Optimization (CAO) consists of two main steps. First, we aim to seek a considerably good aircraft landing sequence via a fast heuristic search base on a Cellular Automata (CA) model. Second, the landing sequence obtained by the CA model is further fine-tuned by a simple yet effective local search procedure.Experimental study on the standard database was conducted to compare the CAO method and several popular approaches in the literature. It was observed that the CAO method not only managed to attain solutions of higher quality, but also was much faster (in CPU time) than the compared methods. The latter property is of significant importance to applying our method in real-world.更多还原