基于元胞自动机的航空器地面滑行优化算法

摘要：本文采用元胞自动机模型来模拟双跑道机场场面活动过程，考虑了可变滑行时间，以最小化滑行总时间为目标，定义其更新规则，得到理想的滑行路线分配结果，并推算其从登机门推出的最迟时间。研究结果表明，该模型在保障安全的前提下有效的提高了离港航空器的调度效率，总滑行时间减少了11.7%，降低了航空器运行成本，能够为繁忙机场滑行调度提供决策支持。

关键词：空中交通管理;滑行调度;元胞自动机;计算机数值仿真

中图分类号：V355

一、引言

为航班分配合理的滑行路径，使其满足运行安全，计算其滑行时间，能够为管制员乃至航空公司提供更加准确的推出时间，减少航班地面等待的时间和滑行时间，提高整个机场的场面运行效率，减少拥塞和延误。

国内外学者对滑行路线分配问题进行了深入研究，王艳军[1]等在时间依赖最短路径算法的基础上，提出了基于冲突回避的动态滑行路径分配模型，动态提升运行效率。王翀[2]等采用动态路径规划求解滑行路径优化问题，减少了滑行冲突和航空器等待时间。李睿馨[3]等提出一种基于最小费用流的多因素约束滑行优化模型，可在短期内缓解滑行冲突，减小滑行成本;邢志伟[4]等提出了多目标免疫优化的方法，在降低总滑行时间和油耗的同时找出最佳滑行路径。黄邦菊[5]等考虑了不同航空器的地面滑行成本，对航空器滑行路径进行了优化。这些研究成果大都以航空器最优滑行路径入手，缺少对航空器推出时间的调度，一旦开始滑行时间变化，则各规划好的路线能出现新的拥堵与冲突。航班的场面运动与普通的地面交通有很多相似之处，已有学者提出使用元胞自动机模型对场面运动进行模拟，并取得了比较好的效果，郑攀[6]采用了元胞自动机模型来进行机场地面停机位分配。Ryota[7]则使用元胞自动机对机场的地面滑行过程进行了模拟。因此本文将元胞自动机模型引入到双跑道机场的滑行路径分配中，建立滑行路径分配模型，为起飞航班进行滑行路径的分配和导引。

二、地面滑行元胞自动机模型建立

本文以国内某机场为基础，建立元胞自动机模型，来模拟航空器地面滑行的运动过程，模型中航空器的速度和位置都由元胞状态和位置表达，模拟中使用的经验数据来自于机场历史统计数据。元胞0表示起点，定义元胞链的格子总数为元胞。若飞机起飞时隙为，该时段的管制裕度为，则飞机最迟到达跑道入口处的时间为。航班队列依照起飞时间分布在（0， ）之间。为当前时间，表示航班在时刻在滑行路径段上的位置;表示航班的起飞时隙;表示航班预计推出的时间;表示航班的滑行速度，表示航班在交叉点处的最大速度，速度均由航班的尾流类型决定;表示同一路径段上航班之间的安全间隔; 表示时刻航班距离目标跑道头的距离;则航班的更新规则如下：

（一）速度更新规则：

令新加入队列的飞机以速度加入到队列，从元胞开始向前运动，如无特殊情况匀速滑行。

1）减速规则：

为了更符合飞机在地面运行平均速度慢，加减速反应不够灵敏的实际情况，每次减速最大值限定为1元胞。

2）交叉口规则：

为保证飞机在交叉口处有序安全的通过，飞机在接近交叉口处弯道时开始按照式4-23减速，并根据交叉口规则1和2来确定是否在交叉口处等待，若不需要等待，则飞机减速飞机减速至后通过交叉点进入下一路径段，若需要等待则飞机减速至0;

交叉口规则1：航班在接近交叉口时，要先发出请求信号，若已有航班占用该交叉点，则航班在交叉口处等待，待行驶条件允许后，按照所分配的起飞时隙先后顺序排队通过交叉点。

交叉口规则2：为保证滑行道上不会发生对头冲突，每一时刻任意滑行路段上只能由同向运动的航空器占用，航空器在接近上的起点时，要预先减速，并查看该路径段有没有被其他航空器占用，若已经有航班占用，并且运动方向与航班不同，飞机按照式1减速到0，并在交叉口处等待，直至该航段上行驶条件允许（没有其他航班）為止。

3）加速规则：

在满足安全间隔的前提下（式4-24），若飞机滑行速度没有达到，则可以加速;仍然是每次1元胞。

4）位置更新规则：

运行过程中，每个时步先计算航班的滑行速度，再进行位置更新。

元胞自动机模型是一种自组织模型，上述模型能够得到滑行路线优化分配结果以及预计推出的时间。

三、算例分析

以国内某机场构建如图1中的场面模型仿真航空器滑行过程，取10架次起飞航班为例进行仿真实验。取 =10000元胞，其中每1米为一个元胞，每个时步长1秒。按照机型长度不同，重型机占70个元胞，中型机占50元胞，小型机占30个元胞，航空器的平均滑行速度重型机约为13m/s，中型机和小型机约为11m/s，转弯处航空器的最大速度为5m/s，滑行转弯半径25m，管制裕度取值范围为20-180秒。其他参数描述如下：

为消除随机影响，仿真过程重复20遍，得到20个数据样本的平均值，仿真结果如下表所示：

利用本文算法执行的路径优化结果见表2，该时段的管制裕度为30s。表中的历史平均时间由数据统计而来，特别的是，数据统计时去除了推出后进行了长时间地面等待的航班数据，以符合模型需要，实际的平均滑行时间要更长一些。表中的最短滑行时间，则表示航班以理想的滑行速度且不考虑与其他航空器的间隔，在该路径上滑行所需要的最短时间。从表中结果可以看出，与历史平均滑行时间相比，本算法分配后的路径滑行总时间减少了11.7%，而仅仅比最短滑行时间增加了0.23%，说明比较接近最短路径。其中5班为满足与航班2的安全间隔，延误了50s推出。7班为满足与前机6路径段的安全间隔，延误了80s推出。因此依据本文算法给出的滑行路径和最迟推出时间，管制员可以按照机场当时运行状态合理的为航空器分配路径并进行导引。

本文提出的航班地面滑行路径分配算法，避免了航空器对头冲突和违反安全间隔的情况，保证了场面运行安全，采用元胞自动机模型求解算法复杂度低，运行速度快，符合场面运行控制的实时性要求。

参考文献：

[1]王艳军，胡明华，苏炜.基于冲突回避的动态滑行路径算法[J].西南交通大学学报，2009，44（6）：933-939

[2]王翀，汤新民，安宏锋.A-SMGCS航空器动态最优滑行路径规划研究[J].武汉理工大学学报（交通科学与工程版），2012，36（05）：1069-1073.

[3]邢志伟，宋晓鹏，罗谦.基于多目标免疫优化的飞机滑行轨迹[J].计算机工程与设计，2016，37（05）：1224-1228.

[4]黄邦菊，李婷.航空器场面滑行路径优化研究[J].海峡科技与产业，2016（06）：96-98.

[5]李睿馨，徐国标.一种航空器地面滑行路径决策优化算法[J]。高师理科学刊，2017，37（9）：14-19.

[6] 郑攀. 民用机场停机位分配问题优化模型与算法的研究[D]. 北京交通大学，2011.

[7] Ryota Mori. Aircraft gound-taxiing model for congested airport using cellular automata[J]. IEEE Transactions on intelligent transportation systems， 2013，14（1）：180-188.

作者简介：

周天琦（1981—），女，博士，研究方向：空中交通流量管理。

基金项目：中国民航飞行学院青年基金资助项目（Q2014-064）