0 引言
近来，航空运输的运输量越来越大。作为客货集散中心的机场，如何合理有效地使用各种资源成为了需要深入研究和解决的问题。其中，飞机在滑行道上的滑行效率对机场和航空公司的经济效益影响很大;滑行过程也是飞机事故多发环节等。因此研究飞机进近排序问题有着重要的经济价值和安全意义。
飞机排序问题(airplane sequencing prob⁃lem, ASP)研究的是终端区管制员在不违反飞机安全飞行间隔的前提下，有效地为进场飞机安排着陆时间，以使所有飞机的总延误最小。传统的方法是采用先到先服务(FCFS)的调度方法，这种方法计算简单，但通常会产生重大时间延误的问题，已经无法适应当前空中交通流量管理的要求。而多跑道飞机排序又有比单跑道难的地方，这个难点在于不仅需要考虑一条跑道上的飞机的顺序，同时还需要考虑把哪架飞机安排到哪条跑道上。
国内外对此问题也有较多的研究。Dear使用约束位置交换策略研究了静态ASP问题，由于飞机排序问题是个组合优化问题，属于NP hard问题，随着飞机的规模的增大，该方法求解时间剧增，实际效用很差;Shiwei等把此问题分成两部分，先把所有将要到来的飞机按照特定顺序排列，然后通过自适应控制的模型调整飞机之间的间隔，从而得到稳定而平滑的着陆序列，但是该方法不适用于多跑道的情况;杜实等采用改进的先到先服务策略，利用递归重复调用这一性质，使用以最小化总调度时间为目标函数的递归模型，来提高机场多跑道的效率，但是即便是改进的FCFS，也无法得到优良的结果;为了得到飞机排序的优良结果，很多学者采用启发式算法，如使用遗传算法、蚁群算法、模拟退火算法和粒子群算法。这些算法能够得到良好的结果，特别是启发式算法。但是作为启发式算法中效率优良的模拟退火算法，还没有将其运用在多跑道飞机排序上的研究。
本文针对飞机排序问题，以飞机着陆时间最少为目标，给出单跑道和多跑道飞机排序问题模型，设计详细的模拟退火算法。通过仿真实验，可以看出本算法可有效地得到多跑道飞机排序的优良解。
1 飞机排序问题模型
某机场的一航班波内，在∆T时间内有N架飞机在预计的时间期间内着陆。着陆要求在满足最小安全时间间隔的基础上，安排飞机队列的着陆顺序，使得飞机序列着陆完成时间最小。例如，连续两架飞机的最小安全时间间隔相应的不低于表1所示时间间隔。
2单跑道飞机排序模型
根据以上飞机排序问题的描述，单跑道飞机排序模型为：在给定的时间窗口∆T时间内，找出在本跑道中的合适的飞机着陆顺序S(S为飞机序号的一维集合)，以使整列飞机着陆时间最短。
3 ASP问题的模拟退火算法设计
由于ASP问题是典型的NP-hard问题，很难找到多项式时间的求解算法，而启发式算法是解组合优化问题的优良算法，因而本文使用模拟退火算法求解ASP问题，特别针对多跑道飞机排序问题进行详细的设计。
4 实际算例仿真
本文使用第2节中的飞机排序问题中的实例，使用表1中的最小尾流间隔标准和表2中实际飞机序列时刻表的数据。因为跑道数越多，代表资源越多，那么需要优化的需求就会比较少，因此本仿真实验运行在跑道数M=2。每种温度下都进行 L=100N3次扰动，对于着陆时间点在预计时间期间之外的惩罚因子设置为 =3 。在2.87 GHz双核处理器，2.5 G内存的机器上，使用VS2010 开发环境，对比模拟退火算法(SA)和FCFS的结果。
5 结论
本文研究了模拟退火算法在多跑道飞机排序优化问题上的有效性。首先详细地设计了单跑道的飞机排序模型，并由此扩展成多跑道飞机排序模型;接着使用效率优秀的模拟退火算法原型，设计出单跑道的飞机排序算法，继而很自然地得出模拟退火算法下的多跑道飞机排序算法。仿真结果表明，本算法很清晰地处理了多跑道飞机排序问题，获得了满意的解。
