基于冲突避免的离场调度优化算法

徐 磊，胡明华,谢 华,王 也

(1.国家飞行流量管理技术重点实验室，南京 211106；2.南京航空航天大学 民航学院，南京 211106)

我国航空业持续蓬勃的发展使机场系统面临运行与管制的压力.而离场航班调度优化问题作为机场流量管理的重要组成部分，是近年来各国学者研究的热点.针对离场排序目前主流的算法包括先到先服务(FCFS)算法[1]、带有位置约束转移的算法[2]和动态规划法[3]等.

国内外对于离场航班调度优化展开了广泛深入的研究，Montoya[4]等人以航班延误最小和增加跑道容量作为多目标优化问题，使用多目标动态规划方法进行建模并设计算法求解了帕累托前沿解集，最后在达拉斯国际机场验证了模型效果.Sama M[5]等人将终端区进场航班调度问题和航空器轨迹优化问题结合在一起并采用字典式优化框架，其中航班调度问题以总航班延误最小为目标而轨迹优化以飞行时间和油耗最小为目标函数.2012年，张启钱，胡明华[6]将航班总延误最小设为目标函数，以最大位置偏移为约束建立多跑道进离场航班排序模型，并采取滚动时域结合遗传算法的方式对模型求解，最后以白云机场30条仿真数据作验证，结果相较于FCFS延误大幅下降.周姝媛，罗军[7]在机场约束条件的基础上建立了航班协同模型，并以成都终端区为实例，结合具体的航班时刻表进行预测，并将最后结果与FCFS作比较.在离场航班优化调度中，目前对于多跑道机场的航空器离场问题方面的研究较为欠缺，在实际运行中，管制员通常采用FCFS算法进行调度.然而FCFS算法在很大程度上依赖管制员的经验，导致平均延误时间较长，降低了安全和效率.

该本文针对多跑道机场，结合跑道分配[8]和航班排序，建立了以航班总延误最少为目标函数的优化模型.模型使用遗传算法进行求解，并将所得优化结果与FCFS方式作对比，结果表明所用算法明显优于FCFS算法.

1 模型建立

1.1 机场节点-边网络模型

机场的场面结构网络可以表示为一个有向图G=(V，E)[9]，其中V与E分别代表机场各路段节点与滑行路径的集合.机场结构示意图见图1.

图1 机场结构示意图

1.2 参数和变量

1.3 目标函数

本文以离场航班总延误最小为目标函数，航班总延误可由所有离场航班的实际起飞时间与预计起飞时间的差值求和得到.

(1)

其中：k表示航空器号，r表示跑道号，AT表示离场航班实际起飞时间，ET表示预计起飞时间.

1.4 约束条件

(2)

(3)

tATk-tATj≥Sjkyjk,

(j,k=1,2,…,N,j=k-1)

(4)

tATk≥tETk,(k=1,2,…,N)

(5)

tATk-tETk≤Tdmax,(k=1,2,…,N)

(6)

式(2)表示任意一架航班k只能从一条跑道起飞；式(3)表示在跑道端排队的航空器数量不能超过在该段时间的跑道容量；式(4)表示以航班的尾流间隔为约束，场面上连续两架航班j、航班k在同一条跑道起飞的间隔应不小于Sik.对于Sik，采用国际民航组织规定的最小尾流间隔标准.式(5)表示任意一架航班k不能在规定的预计起飞时间前起飞.式(6)表示任意一架航班延误时间不能超过极限值.

2 基于遗传算法的算法设计

2.1 算法优化步骤

由于上述模型是典型的NP-Hard[10]问题，伴随着问题规模的增加，用一般线性整数规划[11]进行精确求解难度较大且速度较慢，为了在较短时间内能得到一个实用性高的解，本文在这里选用遗传算法[12](Genetic Algorithm, GA)进行求解.遗传算法虽然不一定能在最短时间内求出一个全局最优解，但是可以在较短时间内获得一个实用性较强的局部最优解.

根据调度优化模型的建立思路，设计如下推出时刻优化步骤：

1)根据离场航班数据以及FCFS原则求出航班推出时刻参考值序列.根据离场航班的预计起飞时间与无冲突滑行时间，按照FCFS原则对离场航班进行排序并计算出每架航班的推出时刻及航班总的延误时间；

2)根据航班数据得出所有航班的最小安全时间间隔矩阵；

3)根据计算得出的最小时间间隔矩阵利用遗传算法求出离场航班最优序列AR1；

4)依据每架航班的无冲突滑行时间，求得所有航班的滑行时间数组，以步骤3)得出的序列AR1为基础，计算得到每架航班的推出时刻，如果发生多架离场航班推出时刻相同的情况时，则将优先级较低的航班延误到下一时刻，这时可得最优的航班推出序列AR2.

2.2 遗传算子与参数调整

1)由于算法既要对离场航班进行排序又要对跑道进行分配，因此在编码方法上采取双层编码[13]的方式.上层采用实数编码，表示航班的起飞顺序；下层采用二进制编码，表示每架离场航班对应的跑道.编码示意图如图2所示

图2 航班编码示意图

2)初始化：本文采取随机生成一系列1～N的离场航班序列组成可行解，重复这一过程P次则生成数量为P的初始种群，本文将初始种群数量设为10.

3)选择：对种群中的个体采取轮盘赌的方式进行选择，按这种方式进行选择时个体被选中的概率与其适应度函数成比例.因此适应度最高的个体最有可能被选中进行重组.同时采取最优保存策略，在每一代种群中，适应度在前20%的个体会被保留而剩下则会被新一代个体取代.

4)交叉：本文采取单点交叉的方式，随机选取截断点切割再组合并且按照交叉概率Pc确定交叉位置，在本文中交叉概率设置为0.8.

5)变异：变异概率通常会被设置的较低，一般在0.005～0.1之间.变异概率不能设置的过高因为很高的变异概率Pm会导致算法扩展搜索空间而使收敛时间变长.因此在本文中变异概率设置为0.1，且由于离场航班是用实数进行编码，因而在本文中采取实值变异的方式进行.为了保证解的可行性，当变异发生时将变异的两个位置的基因进行对调.

6)适应度函数：本文取目标函数的倒数为适应度函数，具体表示如下：

(7)

式(7)表明离场航班在地面的总延误时间越短时适应度值越高.在多次迭代期间适应度值决定了种群可行解的性能.

3 算例仿真

本文选取南京路口机场的部分航班仿真数据在Matlab上进行仿真以验证模型的正确性.禄口机场为双跑道，因此将跑道的容量值设为13，选取4月份某日10∶00～10∶20共计20 min内20架离场航班数据作为样本仿真，主要包括每架航班的机型以及航班时刻信息包括预计起飞时间、无冲突滑行时间、航班号、跑道号等.依据ICAO规定可得知航空器按照不同的机型可以分为轻型(L)、中型(M)、重型三类(H)，任意两种类型航空器的最小尾流间隔标准矩阵Sjk[14]可表示如下：

(8)

其中：前后机分别为j,k，单位为 min.

航班的无冲突滑行时间通过离场航班从停机位到跑道的距离与滑行速度计算获得.按照相关管理[15]规定，航空器的滑行速度不得小于2.78 m·s-1，不得超过13.9 m·s-1.本文取其平均值，即8 m·s-1.

离场航班信息如表1所示.

表1 离场航班信息

根据FCFS法则，先到跑道端的航班优先起飞，后续飞机按照优先级原则依次排队，如果后续航班预计起飞时间不满足尾流间隔则对起飞时间进行相应延误，最后再依据无冲突滑行时间计算出航班推出时刻.结果如表2所示.

表2结果表明利用FCFS方法对求各航班离场推出时刻，产生的航班延误总时间为36 min.根据表中结果能够看出当离场航班以FCFS原则排序时，当某一架航班出现延误时，后续航班受前面航班的影响也会出现相应延误，延误累计也会伴随航班量增加而增加.与此相对的按照本文中的遗传算法求解时，求得的仿真结果如表3所示.

表2 采用FCFS所得推出时刻表

表3结果表明利遗传算法求出各航班离场推出时刻，产生的航班总延误时间为23 min，相较于FCFS算法求得的总延误时间少13 min，同比减少了约36%，且并不会产生延误累积的情况.此外，由于算法在对推出时刻优化的同时对跑道也做出了分配，航班的滑行路径会有所不同，航班的无冲突滑行时间也会随之变化.针对本问题利用启发式算法很好的优化了航班推出时刻，提高了离场航班的准点率，为推出航班排序提供了更加可靠的依据.

表3 采用遗传算法所得推出时刻表

采用FCFS排序与遗传算法排序时结果对比图如图3所示.

图3 FCFS与遗传算法对比图

由图3结果可以得知遗传算法相对于FCFS算法不仅在推出时刻上进行了优化，同时对起飞跑道也做出了合理的分配，在减少了航班延误时间的同时增加了起飞跑道的利用率.

4 结 语

本文研究了多跑道机场的离场航班调度问题，在考虑离场航班排序和跑道分配的条件下建立了以航班总延误时间最小为目标的优化模型，采用遗传算法对模型进行求解并将最终结果与FCFS算法作比较，发现了使用遗传算法求解得到的航班总延误明显减少，且跑道分配更加合理，提高了场面运行效率.