基于路径检测的航空器动态滑行路径优化模型

张兆宁，孙英然

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

1 引言

随着近年来航空器数量的不断增加、扩建的机场和新机场的不断出现，与此同时滑行道系统越来越复杂，所以需要在保证安全的前提下，尽可能提高航空器在场面的滑行效率。

在航空器滑行路径优化方面，国外学者提出了多种方法，2011年，Gillian L.Clare等将路径优化和跑道排序结合，并考虑航班离场时间，构建MILP模型，实现了滑行路径优化[1]；2014年，Zafar N A用图理论和Z标记法模拟航空器在机场的滑行和起飞过程，动态规划了离场航班的最优滑行路径[2]；IoannisSimaiakis等提出控制航空器起飞率，即减少了滑行时间有节省了燃油[3]；2016年，Sassi N等将Petri网与机场地面约束相结合，规划航空器的滑行路径[4]；2017年，Okuniek等为提升A-SMGCS服务水平，提出为每架航空器设计无冲突的优化路线和相关速度值组成，即航空器四维滑行轨迹(4DT)[5]。

国内在这一方面的研究有：2016年，邢志伟等针对航空公司满意度和滑行道负载率，提出了基于背压路由的离港滑行路径优化算法[6]；2018年，张红颖等使用了多Agant策略来优化滑行路径[7]；2019年，姜雨等引入双层规划方法，考虑了成本与冲突对场面航空器运行效率和安全的影响，构建了场面航空器滑行时空协同优化模型[8]；张兆宁等采用远端绕行滑行道的办法优化了航空器的滑行路径，并使用改进的遗传算法求解[9]；2020年，李善梅等提出滑动时间窗和A*算法相结合的方法，构建以总滑行时间最短为目标的模型，优化了滑行路径[10]；张兆宁等提出在航空器着陆后，分析其滑行运动过程，选择最优的跑道出口滑行道脱离跑道来节省滑行总时间[11]。

综上，近年来为提高飞机滑行效率，国内外学者使用了多种模型和算法以优化飞机的滑行路径，但在路径选择的方法上，大部分的研究都是从某时间段内航班波滑行总时间最短或滑行距离最短的角度出发直接得到规划方案，当冲突出现时再采取解脱冲突的办法，这种方法在机场航班过多的情况下，很容易出现拥堵的情况，也会导致滑行道使用不均衡。

所以本文提出基于路径检测的方法，对航空器进行动态路径优化，当某条滑行道被检测到发生拥堵情况时，航空器将选有可能选择其滑行道来提高航班波的整体滑行效率，也能提高航班运行的安全性。本文的创新点体现在：

1)给出路径规划中路径的检测方法，提出多航空器在同一路径上可能产生拥堵这一类新约束；

2)提出了动态路径优化策略，提高航空器滑行路径规划效率；

3)针对滑行路径问题提出改进的蚁群算法。

2 航空器动态滑行路径优化模型

建立航空器动态滑行路径优化模型，首先对航空器滑行过程及需解决的问题进行描述，然后设计动态路径优化策略，明确检测冲突和拥堵的办法，构建以总滑行时间最短为目标，无冲突，无拥挤的数学规划模型。

2.1 问题描述

航空器在场面的滑行是指航空器在跑道入口/出口和停机位之间的滑行。在航空器滑行过程中可能发生的冲突有尾追冲突、相向冲突、节点交叉冲突。图1为有两条跑道的机场的滑行系统水平布局图，其中航空器可能存在的冲突如图所示。在其机场布局中的冲突情况也类似。

图1 机场滑行系统水平布局图

航空器滑行过程中首先要避免这三种冲突，也要尽量避免在机场繁忙时段，滑行道上出现的拥堵情况，使航班波安全高效地从停机坪滑到跑道入口或者从跑道出口滑入指定的停机坪。

2.2 动态路径优化思路

为避免滑行过程中冲突和拥堵情况的发生，本文采用动态路径优化模型，即对随机生成的滑行路径进动态监控，若出现冲突和拥堵的现象，及时采取解决措施。

动态路优化模型分为两个模块：航空器的路径生成模块将其搜索到的路径实时反馈给滑行网络的状态模块，滑行网络的状态模块再对路径生成模块进行动态监控，两个模块相互配合相互制约，对路径进行动态优化。

图2 动态路径优化模型

2.3 路径检测方法

1)冲突检测

对航空器运行空间的检测：检测各架航空器的滑行路径之间是否存在相同的路径或节点；并且检测航空器之间是否满足最小安全滑行间隔；

对航空器运行时间的检测：若存在空间冲突，则要检测出现在冲突的路径或节点上是否有时间重叠。

2)拥堵检测

采用交通流理论刻画航空器滑行路径的拥堵程度和航空器滑行速度：随着滑行道上航空器密度的增加，导致航空器滑行速度逐渐减小，直至拥堵态。航空器滑行路段拥堵程度可根据交通流理论得

K=RN/RL

(1)

式中，K为滑行道路段的拥堵程度；RN为滑行道路段中航空器数量；RL为滑行道路段中可容纳航空器总数。

航空器的滑行速度

v=vf(1-K)

(2)

式中，vf为航空器的最大滑行速度，本文根据机场滑行系统运行规定vf=10m/s。

2.4 模型构建

在动态路径优化策略，基于上述路径检测的方法，建立路径优化模型，假设如下：

1)航空器实际滑行过程中，所有航空器最小间隔相同；

2)所有飞机已经指定好停机位或跑道入口；

模型参数定义如下：

M={1，2…m}为需要规划航班的集合；N={1，2…n}为机场滑行道节点的集合；R={1，2…r}为机场滑行道中所有路段的集合；Dr为路段r的长度；L为航空器之间所需的最小安全间隔；H为滑行可利用时间。

模型变量定义如下：

其中

(7)

模型的目标函数如下

模型的约束条件如下

(11)

式(8)保证航空器数量不超过此条滑行道上的容量；式(9)保证每个节点最多只有一架航空器；式(10)保证两架相互冲突的航空器到达下一路段时间差不小于优先级低的航空器的等待时间；式(11)保证滑行过程中不能出现相向冲突的情况。

3 求解算法

本文针对航空器在滑行道上的滑行规则及特点，设计了改进的蚁群算法对问题进行求解。

3.1 算法思路

运用蚁群算法对航空器滑行路径进行优化，将每一架航空器的滑行任务抽象为蚂蚁组，每一组中包括多只蚂蚁。在蚂蚁为航空器搜索滑行路径时，采用动态规划策略，其算法基本思路如下：

1)路径搜索：蚂蚁根据其任务和转移概率搜索下一节点，并留下信息素，该信息素仅对同组其蚂蚁有效。

2)信息更新和记录：根据蚁群的路径搜索和信息素值更新和记录路网状态表、蚁群状态表、信息素表。

3)目标：以所有蚁群组的总运动时间最短为目标，找出最优路径。

3.2 算法的基本规则设置

1)初始蚁群设置

以往运用蚁群算法求解航空器滑行路径问题时，将全都蚂蚁的起点设置在航空器的起始位置然后开始路径搜索，导致航空器开始滑行的一段路径基本相同，从而导致算法的全局搜索能力不足。

因此本章引入双向搜索机制，对于每个蚁群，将其分为两组，其中第一组的蚂蚁起点设置为航空器的起始位置(对于离场航空器为航空器所在的停机位位置，对于进场航空器则为跑道出口位置)，然后向航空器的目标位置开始搜索路径；第二组的蚂蚁起点设置为航空器的目标位置，然后向航空器的起点位置开始搜索。当两只蚂蚁相遇后会生成一条新的路径。

2)转移策略

蚁群算法中各个蚂蚁根据下一可达节点的选择概率选择路径，根据上文路径优化模型，适当调整传统蚁群算法的转移概率公式，改进公式如下

(12)

式(12)中，Pm(i，j)表示航空器m在节点i上选择转移到节点j的概率；τij表示路段(i，j)上信息素浓度；Cij表示路段(i，j)的航空器容量；vmij表示规划的航空器m在路段(i，j)上的速度；Li表示节点i的可达节点的集合；α、β、γ各个因素对于路径选择的相对重要程度。

3)状态表更新规则

在蚂蚁对某一路段进行选择后，先更新路网状态表；然后根据当前路段情况和式(4)中得到蚂蚁在路段中的滑行速度、式(6)中得到的蚂蚁滑行总时间，更新蚁群状态表。

4)信息素更新规则

本文采用信息素全局更新规则，完成一次循环后，信息素按式(13)更新

(13)

(14)

式中，Q是信息素的强度，为定值，Lk是蚂蚁k在本次循环中走过路径的总长度。根据所需搜索的路径特点，引进奖惩因子，增加最优路径的信息素，减少最差路径的信息素。如式(15)(16)(17)(18)

(18)

式(15)中，Δ*τij代表每次迭代最优路径经过节点i、j的信息素大小，Δ**τij代表每次迭代最差路径经过节点i、j的信息素大小。Δ*τij由式(16)得到，其中L*表示这次迭代最优路径总长度。并且根据式(17)对全局最优进行奖励，奖励因子为Re ；Δ**τij由式(18)得到，其中L**表示本次迭代中最差路径长度。式(19)引入最大最小信息素阈值，避免某路径经过多次迭代后，其上信息素浓度远高于其路径而导致的搜索停滞。

(19)

3.3 算法步骤

综上，基于改进蚁群算法的航空器动态滑行路径优化模型的求解如下所示。

算法具体步骤如下：

Step 1：参数初始化，令迭代次数NC=1；

Step 2：为各个航空器分配至不同的蚁群组，同时在航空器的滑行起点和终点放置共a只蚂蚁；

Step 3：按照目标函数和机场场面约束条件为蚂蚁分配初始路线；

Step 4：判断各蚂蚁当前所在节点i是否为其搜索路径的终点，若是转至Step7；若不是转至Step5：

Step 5：按照路径选择规则选择下一滑行节点i′；

Step 6：更新蚁群状态表，转至Step4；

Step7：判断这组蚁群是否都完成搜索，若是，则转至Step8；否则，令蚂蚁n=n+1，转至Step3；

Step8：分析蚁群的搜索结果，得到该次迭代最优路径方案，更新滑行网络状态表、全局信息素；

Step9：判断是否达到指定迭代次数，若不是，则转至Step10：若是，则转至Step11；

Step10：令NC=NC+1，开始下一次迭代，转至Step2；

Step11：算法结束，输出最优滑行方案。

算法流程如图3所示。

图3 算法流程

4 算例分析

为验证本文模型与算法的有效性，选取国内某机场的实际数据进行实验，并对比不同模型下的结果，加以分析。

4.1 算例描述

选取国内某机场地面滑行系统为算例，分析了以34L、34R两条平行跑道和T1，T2航站楼组成的地面滑行网络，其地面交通网络图如图4所示，图中显示各个滑行节点编号，本文所研究的滑行路径是指跑道中的滑行道入口/出口与停机坪前的滑行道交叉点之间的路径，因此航班的滑行路径可用连续的节点组合来模拟。

图4 国内某机场滑行道系统构型

4.2 模型仿真

根据机场运行实际情况，选取该机场2020年7月某天13：00～13：30内需要滑行的航空器，其中包括11个离场航空器和12个进场航空器，对航空器进行动态路径规划。则模型参数如下：需要规划的航班的集合M={1，2…23}；滑行系统节点的集合N={1，2…96}；航空器之间所需最小的安全间隔L=250m；航空器滑行可利用的时间H=55min。

经过多次实验，蚁群算法中的参数设定为：α=1，ρ=0.4，β=0.9，γ=2.5，a=20，Re=1.5，δ=1.5，ω=1.5，τmin=0.5，τmax=20。

在MATLAB中进行仿真，最终得出各航班滑行时间及对应的路径，如表1所示。

表1 航空器路径规划方案

图5 迭代次数与航班波滑行总时间关系

4.3 对比分析

为验证本文模型的有效性，采用同样的蚁群算法，使用传统的不考虑路段状况的模型，计算航空器的滑行路径，结果如表2，比较不同模型下航班滑行序列号和航班滑行时间的关系，如图6所示。

图6 航空器序号与航空器滑行时间关系

表2 航空器路径规划方案

由表2可知，不考虑路段状况的方案路段重复率大，由图6可知，不考虑路段状况的航空器滑行相对缓慢，其中2，3，5，8，11，12，13，14，15，20，22，23号航空器滑行时间都比实施路径检测的方案时间长，在路径搜索中进行路径检测，航空器滑行时间累计节省234s。相比之下，本文模型滑行时间较短，不同航空器之间的路径重复率较低，完成时间较为均衡，故本文模型具有一定的优化能力，可提高滑行效率。

5 结论

本文基于路经检测，对航空器在机场的滑行进行动态优化。从提高航空器整体运行效率的角度上，以滑行总时间最短为目标，建立路径规划模型，并设计了基于动态路径优化策略的改进的蚁群算法，通过实例验证了该方法的有效性。实验结果表明动态优化策略可以对航空器滑行路径进行合理优化，基于路径检测的优化模型可以有效的解决航空器滑行过程中的拥堵问题，提高滑行效率。

本文在考虑减少航空器滑行时遇到的拥堵情况时，没有计算绕开拥堵路径时成本消耗问题，航空器能够安全高效并且尽可能的节约成本的滑行，是后续研究的主要方向。