基于态势感知的滑行路径优化算法

张兆宁，余洲

(中国民航大学空中交通管理学院，天津 300300)

近年来民航业蓬勃发展的同时也暴露出了许多问题，由于快速增长的客流量超过了部分机场的承受能力，而导致许多机场出现了延误现象，这不仅严重影响了机场的运行效率，而且降低了旅客的乘坐满意度。其中滑行道延误就是一个关键问题，由于滑行道内超负荷的航班量与突发事件，在航空器滑行过程中出现延误的可能性极高，也严重影响了机场的正常运转。

中外学者对滑行路径的优化研究从模型建立和算法应用方面已经取得了较多的研究成果。在建模方面，姜雨等[1]在双层规划算法的基础之上，将航空器的路径与滑行开始时间结合起来建立了航空器滑行时空协同优化模型；康瑞等[2]为解决交叉道口冲突范围定义不完整等问题，以T型交叉口为例，基于实时速度、位置变化构建了考虑等待位置的航空器交叉滑行冲突概率模型；Tancredi等[3]以滑行耗时最短、油耗最低、成本最低、滑行效率最高及安全性为目的建立了航空器滑行路径多目标优化模型。张兆宁等[4]针对使用远端绕行滑行道优化航空器的滑行路径问题，建立了航空器脱离跑道时间优化模型。

在算法应用方面，李楠等[5]针对多目标优化算法等难以在短时间内得出结果的问题，提出了Bellman-Ford算法和A*算法启发式搜索方法结合使用以提高算法效率；马永杰等[6]针对现有的动态多目标优化算法种群收敛速度慢、多样性难以保持等问题，提出了一种基于Pareto解集分段预测策略的动态多目标进化算法BPDMOP；张兆宁等[7]利用Dijkstra算法，在考虑航空器滑行过程的基础之上，以滑行时间和优化作为优化目标进行优化。

虽然上述的滑行路径优化模型和算法在一定程度上降低了延误发生的可能，但由于这些算法大多是只针对最短路的优化，并没有考虑滑行道的实际运行情况，所以延误还是会存在，并且当延误发生时需要管制员干预解决，这进而也增加了管制员的工作量。态势感知可以根据滑行道的运行数据准确的评估判断滑行道的运行情况，使管制员可以快速、准确地制定方案提升滑行道的运行效率以及避免不安全事件地发生。

目前中外大多数的研究成果都只考虑使航空器的滑行路径达到最优，但并未考虑调整航空器的滑行起始时间。由于许多机场受制于滑行道的网络空间构型及其设计容量，只是单纯地改变滑行路径这种方法受限较多，但若是改变了滑行起始时间便能够从时间上避免区域拥堵和冲突的发生。基于态势感知的滑行道路径优化算法从滑行道的运行负荷以及航空器滑行效率和安全性的角度出发，综合考虑航空器滑行路径和滑行起始时间，并将二者协同优化，提出一种在确保航空器滑行过程安全无冲突的前提下，减少航空器总的运行时间，进而提高了航空器场面运行的效率以及动态容量，为大型繁忙机场场面资源调度提供决策依据。

1 基于态势感知的滑行路径优化模型

1.1 滑行态势感知

滑行态势是对滑行道总体状况的数据形式的反映，对管制员评估滑行道运行状态有着至关重要的作用。对于态势感知的应用，最早出现在航空领域，后续在军事、工业生产和交通等领域也有广泛应用[8]。滑行态势感知可被划分为3个层级：感知、理解和投射[9]，如图1所示。

图1 滑行道态势感知的闭环控制过程

1.1.1 运行数据感知

态势感知的第一层就是感知层，是对滑行道中的不确定因素和潜在的会导致延误的因素的感知。在滑行态势感知中，数据的采集、传输和储存是后续处理的基础。通过对航空器滑行过程的分析，以及对滑行道整体运行的分析后，得到了5类主要影响因素，并将其称为滑行态势指数。

(1)航空器滑行时间指数。航空器滑行时间指数是指从跑道到参考航空器的停机位的滑行时间。对于任一进场或者离场的航空器，航空器滑行时间指数都包含滑行状态指数τd、τa。对于参考航空器d0，若其为离场状态，那么航空器滑行时间指数τd为其滑出时间；若其为进场状态，那么航空器滑行时间指数τa为滑入时间。

(2)场面瞬时流量指数。场面瞬时流量指数指的是当参考航空器推出时或者着陆时，场面正在滑行中的航空器数量。对任一进场或离场的参考航空器来说，场面瞬时流量指数都包含两个滑行状态指数∂d和∂a。对于参考离场航空器d0，若其正在着陆，∂d为滑出航空器数量，∂a为滑入航空器数量；对于参考进场航空器a0，若其正在被推出，∂d为滑出航空器数量，∂a为滑入航空器数量。

(3)场面累计流量指数。场面累计流量指数指的是在参考航空器的整个滑行过程中已经滑出或者正处于滑行状态的航空器的数量。对于任一进场或离场的参考航空器来说，场面累计流量指数都包含两个滑行状态指数σd和σa，其中，σd为滑行期与参考离场航空器d0或者参考进场航空器a0的滑行期重合的离场航空器数量，σa为滑行期与参考离场航空器d0或者参考进场航空器a0的滑行期重合的进场航空器数量。

(4)航空器排队长度指数。航空器排队长度指数指的是在参考航空器的整个滑行过程中从跑道上起飞或者降落在跑道上的航空器的数量。对于任一进场或离场的参考航空器来说，航空器排队长度指数都包含两个滑行状态指数λd和λa，其中，λd为参考离场航空器d0或者参考进场航空器a0的滑行过程中离场航空器从跑道上起飞的数量，λa为参考离场航空器d0或者参考进场航空器a0的滑行过程中进场航空器在跑道上降落的数量。

(5)时隙资源需求指数。时隙资源需求指数指的是在一定的时间间隔[t0-δ,t0+δ]内在登机口被推回或是降落在跑道上的航空器数量，其中，t0为参考航空器撤轮档的时间或是着陆的时间，δ为可动态设定的统计阈值，在考虑到正常的起降时间，对于任一进场或离场的参考航空器来说，时隙资源需求指数都包含两个滑行状态指数μd和μa，其中，μd为参考离场航空器d0或者参考进场航空器a0的统计时间间隔内被推回的离场航空器数量，μa为参考离场航空器d0或者参考进场航空器a0的统计时间间隔内在跑道上着陆的进场航空器数量。

1.1.2 理解

理解层是指对感知到的数据对于滑行道实时状态评价的意义和作用。根据所感知到的数据，利用正则化模型将其处理，使其成为标准化的滑行态势指数。对于任一滑行态势指数，都有一个统一适用的正则化模型，可表示为

i=1,2,…,n

(1)

式(1)中：Tr(xi)为正则化后的值;n为滑行样本的数量；xi、xj、xk为参考滑行态势指数的值。

再应用主成分分析法简化上述模型，将标准化的滑行态势指数分解为总方差相同的无关线性滑行态势指数组合Fi(i=1,2,…,p)，可表示为

(2)

式(2)中：aki为单位矩阵中的第k行第i列的元素，ξk为航空器滑行态势指数，ai=(a1i,a2i,…,api)T为单位列向量；ξ=(ξ1,ξ2,…,ξp)T为标准化的航空器滑行态势指数列向量。

主成分的选取标准是累计贡献率达到了90%，而Fi的贡献率的计算公式为

(3)

式(3)中：{γi|i=1,2,…,p}为ξ的协方差矩阵的特征值，且γ1≥γ2≥…≥γp。

比较矩阵a中的元素，可以得到当参考航空器开始滑行时滑行道的复杂度。

1.1.3 投射

投射层是态势感知的最后一层，是基于当前状态、感知信息和预测趋势对系统未来行为的预测。基于态势感知的滑行道路径优化算法将投射模块与传统的滑行道路径优化模型相结合，对整个滑行道的演进进行分析。

根据Yin等[10]的研究，滑行延误时间是滑行道复杂度的主要表现形式，滑行延误是基于实际滑行时间与被称为“无限制滑行时间”的构造值之间的差。据此，当滑行道复杂度高，则代表着在其中运行的航空器出现滑行延误的可能会更大或者是滑行延误的时间会更长。因此，可以通过调整航空器滑行起始时间来推迟航空器进入滑行道的时间，从而可以降低滑行复杂度，从而达到减少滑行延误时间、提高滑行效率的目的。

1.2 基于态势感知的滑行道路径优化模型

滑行路径优化模型的目标函数为全局的运行时间，可表示为

T=min(Ttaxiing+Thold)

(4)

(5)

式中：T为所有航空器总的运行时间，T值一般在10～30 min；Thold为航空器在停机位等待的时间；Ttaxiing为所有航空器总的滑行时间；Tijk为航空器k在链路(i,j)上的无障碍滑行时间；Tijk_hold为航空器由于冲突的等待时间。

本文模型主要考虑以下约束条件。

(1)优先级约束：

(6)

(2)节点冲突探测可表示为

∀i∈Rk1∩Rk2；k1≠k2

(7)

(3)发生节点冲突时航空器的等待时间为

Tijk_hold=fk1k2(1-Wk1k2)(ts+tvk2-tvk1)，

∀v∈Rk1∩Rk2；k1≠k2

(8)

(4)对头冲突约束

xijk1tjk1-xijk2tjk2≥0

(9)

(5)超越限制

(xijk1tik1-xijk2tik2)(xijk1tjk1-xijk2tjk2)>0

(10)

(6)滑行时间安全间隔可表示为

tjk1-tjk2≥ts

(11)

式中：Wk1k2为优先级因子；pki为航空器ki的优先级；fk1k2i=1表示航空器k1与航空器k2在节点i发生冲突；Rki为航空器ki的滑行路径；tvki为航空器ki到达冲突节点v的时刻；xijki=1为航空器ki从节点i滑行到节点j，否则xijki=0；tjki为航空器ki滑行到节点j的时刻；ts为滑行的安全间隔时间。

1.3 算法设计

根据对滑行态势指数的相关性分析，航空器滑行时间指数是对航空器滑行时间影响最大的因素[11]，而根据偏相关性分析，场面航空器排队长度指数是航空器滑行时间指数最为关键的影响因素，而进场航空器不涉及排队，所以Thold指的是离场航空器在停机位的等待时间。

算法流程的设计借助了迭代法的思路，同时在算法中加入了一个判断步骤，设定了一个复杂度阈值，阈值的设定是综合了场面运行效率与旅客满意度的整体考量，对提升算法的可行性有着至关重要的作用。

设计出的基于态势感知的滑行路径优化算法具体步骤如下。

步骤1初始化，根据预先设定的起始滑行时间得到一组可行的最优滑行路径，并计算出单个航空器以及所有航空器的滑行时间。

步骤2根据步骤1的航行路径数据算得滑行态势指数，并计算出每个航空器的滑行复杂度；

步骤3将求得的滑行复杂度与预先设定的阈值相比较，若所得滑行复杂度大于所给定的阈值，则选取所有航空器中场面累计流量最大的航空器[10]，推迟其起始滑行时间，推迟时间为1 min，并返回步骤1。

步骤4若所得滑行复杂度不大于所设定的阈值，则记录当前的路径优化结果，并结束算法。

2 算例分析

以国内某大型机场的滑行道系统作为验证对象，其滑行道系统构型如图2所示。

①～为滑行道节点

航班数据选取该机场某日上午7:30—7:45的高峰期航班数据并标号，如表1所示。

表1 航空器滑行时刻表

2.1 结果分析

在运用Dijkstra算法求得初始最优解后，得到航空器的总滑行时间为4 369 s，离场航空器总的滑行时间为2 951 s，离场航空器在停机位的等待时间为0。根据前面算法设计中提到的，该求解算法主要针对离场航空器的起始滑行时间做调整，所以对数据中的10架次离场航空器再编号为1～10。所求得的离场航空器的滑行复杂度如图3(a)所示。可以看出，第8架离场航空器的滑行复杂度最高，为0.654，而此时所设定的最高复杂度阈值为0.500，因此需要进行迭代调整。

推迟第8架离场航空器的推出时间1 min后，得到新的滑行路径规划，此时总的滑行时间为2 752 s，此时离场航空器的滑行复杂度如图3(b)所示。可以看出，第9架离场航空器的滑行复杂度最高，为0.583，而此时所设定的最高复杂度阈值为0.500，因此需要进行迭代调整。

推迟第9架离场航空器的推出时间1 min后，得到新的滑行路径规划方案，此时总的滑行时间为2 648 s，此时离场航空器的滑行复杂度如图3(c)所示。

图3 离场航空器滑行复杂度

可以看出，此时所有离场航空器的滑行复杂度都小于了阈值0.500，则算法结束，此时总的滑行时间为2 648 s，航空器等待时间为120 s。初始解中总的滑行时间为2 951 s，等待时间为0。

将基于态势感知的滑行路径优化算法仿真结果与采用相同的数据、选择最短滑行时间有限的基于FCFS(first come first service，如基于Dijkstra的滑行路径优化算法和基于A*算法)的滑行路径优化的结果相比较，如表2所示。

从表2可以看出：在基于Dijkstra的滑行路径优化算法和基于A*算法的滑行路径优化的结果中，各自的总滑行时间分别为4 369 s和4 237 s；且因为这两种算法之间是按照计划排班运行的，所以航空器的总等待时间为0；基于态势感知的滑行路径优化算法的结果相较于其他两种方法，航空器平均滑行时间降低了13%和4%；航空器总等待时间为120 s，离场航空器平均等待时间为12 s，属于可接受范围。

表2 优化结果对比

在基于态势感知的滑行路径优化算法中，离场航空器为减少因避开冲突可能的绕道而选择在推出时进行等待；而其他两种目前最常用的算法都是选择了绕道避开冲突，所以浪费的时间远大于前者，且还会消耗更多的燃油。

通过上述对比，可以看出基于态势感知的滑行路径优化算法在航空器运行时间上由于当前常用的FCFS算法，且基于态势感知的滑行路径优化算法可以不断优化航空器等待时间和滑行路径，进而使航空器滑行效率有较为明显的提升。

2.2 参数分析

而针对阈值的设定，如图4所示，计算出了最高复杂度阈值在0.3～0.6范围的离场航空器总运行时间，从图中数据可得出当阈值为0.500和0.550的时候，离场航空器运行时间最短，算法效果最佳。

图4 不同复杂度阈值对应的离场航空器运行时间

当阈值为0.500和0.550时，在第二次迭代后得到的滑行复杂度均小于0.500，因此算法停止，所以两次计算得到的结果相同；当阈值变大后，所得到的离场航空器运行时间也随之增大，根据图5所示，航空器的等待时间相比较与阈值为0.500和0.550时减少，但总的滑行时间较于初始解并无太大变化；当阈值小于0.500时，航空器总的滑行时间相较于初始解有了较大幅度的减少，却但大幅度增加了航空器的总共等待时间，进而使总的运行时间延长，而且由于过长的等待时间，还会对后续进离场航空器的正常运行产生不利影响。

图5 不同复杂度阈值对应的离场航空器等待时间

分析可知，在算法中阈值的设定并不是越小越好，阈值与航空器的滑行时间、等待时间有密切的联系，还要考虑在过长的等待时间条件下，是否会对后续的航空器正常运行产生影响。而且过长的等待时间会影响旅客的情绪，降低他们对航班服务的满意度。

3 结论

滑行道运行效率极大地影响了机场场面的运行效率。为了提高繁忙机场的滑行道运行效率，在传统的先到先服务算法基础之上，加入了滑行道系统运行态势。并以国内某大型繁忙机场的滑行道系统作为算例，得出如下结论。

(1)在保证航空器正常运行的情况下，算法通过调整离场航空器滑行起始时间，均衡滑行道内流量，减少了航空器运行时间。并针对算法中的重要影响参数进行了分析验证，结果表明参数的选择合理与否会对算法运行结果产生直接影响。

(2)今后的工作是将态势感知的概念推广到整个场面运行过程中，为场面的高效率、自动化运行提供支持。