李媛祯，杨 群，段 汐

(南京航空航天大学计算机科学与技术学院，江苏 南京 210016)

0 引言

随着航空运输业的飞速发展，空中交通日趋繁忙，空中交通管制(Air Traffic Control，ATC)的重要性愈加突出。飞机排序调度问题(Aircraft Arrival Sequencing and Scheduling，ASS)研究在空中交通繁忙的机场终端区，如何在保证飞机安全飞行间隔的前提下，有效地优化到港飞机着陆序和着陆时间，达到使飞机总延误最小、提高系统容量、增加飞行安全性等目标［1-2］。它是空中交通管制的一个关键问题。飞机排序调度中，到港飞机到达机场终端区以后，按照预定的进港路线飞行并着陆，n 架到港飞机的着陆次序可以有n!种排列，其组合优化是NP-难解问题。蚁群算法是一种能行之有效地解决组合优化问题的智能进化算法，本文拟采用一种基于均衡更新的蚁群算法处理飞机排序调度问题。

1 相关工作

随着我国经济迅速发展，航空运输量持续增加，合理有序地调度到港飞机的顺序是目前空中交通管制急需解决的问题。近年来，国内外学者已有许多相关研究，提出了许多解决飞机排序调度问题的方法［6-9］。传统飞机排序调度采用先到先服务(First Come First Service，FCFS)的调度算法［4］，这种方法基于航空管制员人工经验进行，在满足一定约束条件的前提下对飞机着陆序可以进行调整，保持大部分飞机之间的相对位置，最终确定着陆时间。虽然算法简单易行，但造成的飞机延误时间较大，不能很好地满足空中交通流量管制需求［16-17］。Hu 等［2-3，5］使用改进的遗传算法处理飞机排序调度问题，取得一定效果，但算法模型中未考虑实际旅客数量，没有区别对待不同载客量的飞机，忽略了不同载客量的飞机延误所带来的不同影响。……