基于受限位移约束的蚁群算法在航班着陆调度问题中的应用研究

Ant Colony Algorithm Based on Constraint Position Shifting for Aircraft Landing Problem

航班着陆调度问题是机场跑道调度中的重要问题,合理的调度策略将极大的减少航班延误。本文提出基于受限位移约束的蚁群算法(CPS-AC),该算法利用了蚁群算法高效的全局搜索能力,同时结合CPS确保调度的可操作性和公平性,能够为实际的空中交通流量管理提供理论方法和依据。数值模拟实验结果表明,CPS-AC算法明显优于经典的先到先服务(FCFS)的调度方法和标准的蚁群算法(AC),能在较短时间内有效减少着陆航班的总延迟时间,且具有较好的收敛性。这些对于减少航班延误,提高着陆容量具有推动作用。

Aircraft landing scheduling problems are salient in the airport runway system. A reasonable scheduling method can greatly reduce the total delay time of aircrafts, Thus, an increasing number of scholars focus on developing various optimization methods to tackle these problems. Two prominent approaches are Constraint Position Shifting （CPS） and Ant Colony （AC） algorithm. CPS stipulates that all aircrafts are only allowed to move at most k positions forward or backward from their FCFS （First-Come-First-Served） order, where k is the maximum position shift. It reduces the search space for large scale problems and maintains some level of fairness among different airlines. AC algorithm, another widely used method, is a highly efficient heuristic algorithm, which is firstly developed by Dorigo in travelling salesman problems （TSP）. It has many important advantages, such as positive feedback mechanism, greedy search mode and strong global searching ability. By combining the advantages of AC and CPS mentioned above, we propose the resultant CPS-AC strategy. This new strategy is effective to tackle aircraft landing scheduling problems. It has strong global-search ability and ensures the maneuverability of scheduling and fairness among airlines. At the same time, it reduces controllers＇ workload to a certain extent. More importantly, in the course of solving CPS model, a reasonable solution can be obtained when the value ofk is not small. This is an important achievement since the classical Dynamic Programming, which is widely used to solve CPS model, only presents effective solutions when k is typically small. AC is an important supplement of problem-solving technology for CPS when k is large. To test the efficiency of the CPS-AC algorithm, we present some experimental tests where FCFS strategy （First Come First Served） and traditional ant colony algorithm （AC） are used to compare with CPS-AC. First, we test a case where k is set to be 2 and the number of aircrafts （/＇/） is 30. The results show that CPS-AC algorithm reduces 53.27% of the total delay time more than FCFS strategy, whereas AC reduces 30.70% of the total delay time. The runtime of CPS-AC algorithm is also smaller than that of AC algorithm. That is to say, CPS-AC algorithm is more efficient in reducing the total delay time when k is small. To verify the performance of CPS-AC algorithm when the scale of problem is large, we conduct a series of tests where/7 is set from 40 to 200 and k is set to be 5 and 10, respectively. Similarly, the results also reveal that CPS-AC algorithm is still very promising. CPS-AC algorithm not only outperforms FCFS but also AC algorithm. At last, we analyze the convergence of the CPS-AC algorithm, which has a good convergence. The paper is concluded with a summary of our research findings, implications and future research directions.