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

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

作　　者：马卫民[1,2] 杨文娟[1] 徐博[2] 

机构地区：[1]西安工业大学经济管理学院,陕西西安710021 [2]同济大学经济与管理学院,上海200092

出　　处：《管理工程学报》2016年第1期191-196,共6页Journal of Industrial Engineering and Engineering Management

基　　金：国家自然科学基金(71071113;71161016);全国优秀博士论文作者专项资金资助项目(200782);高等学校博士学科点专项科研基金(20100072110011);上海市哲学社会科学规划课题(2010BZH003)

摘　　要：航班着陆调度问题是机场跑道调度中的重要问题,合理的调度策略将极大的减少航班延误。本文提出基于受限位移约束的蚁群算法(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 result

关 键 词：受限位移约束(CPS) 蚁群算法 航班着陆调度 

分 类 号：V351.11[航空宇航科学与技术—人机与环境工程]