基于改进Dijkstra算法的滑行路径优化

翟文鹏，刘润南，朱承元

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

为了缓解航空运输压力、机场滑行道拥堵、航班延误、机场容量不足等问题，民航界学者对场面滑行路径优化展开了大量研究[1]，选取的优化目标主要包括：航班滑行时间最短与延误时间最少[2]、航班无冲突与滑行距离最短[3]、航班等待与延误时间最少[4]等。这些研究考虑了多个优化目标，但均假设滑行路径规划起始时刻航班均处于停机位或快速脱离道入口，场面无正在滑行的航班。这与大型繁忙机场24 h 全天候运行情况不符。其次在优化算法方面，多以精确求解算法（如混合整数规划[5]）、智能算法（如遗传算法[6]、蚁群算法[7]等）为主。在大规模航班滑行路径优化问题上，精确求解算法计算量大、求解时间长；智能算法求解时间大大缩短，但求解得出的规划方案严重依赖场面的精确运行，发生一次滑行道入侵或航班延误，就必须对全局重新规划。同时航班在场面滑行过程中受诸多随机因素影响，文献[8]对20 多个滑行路径优化算法进行了优缺点分析和评价，其中总结的算法皆属于离线静态算法，无法动态规划路径，实用性不高，如能结合动态路径搜索思路则更具有现实意义。文献[9]针对这一问题提出了滚动时域的滑行路径优化算法，较好地实现了航班滑行路径中的动态搜索，但滚动时域算法对时间精度要求高，实际操作难度大，计算错误易被叠加放大。

综上，现有研究方法不仅局限于静态搜索，研究思路也大多考虑战术性优化滑行路径，而实际运行中，以预战术的思路对航班进行规划更能提高机场工作效率。因此，提出对处于机场终端区的航班预先进行战术性的滑行路径动态优化。以降低场面拥堵、航班延误及地面管制人员的工作负荷为目的，借鉴滚动时域算法的动态搜索思想[10]对传统Dijkstra 算法[11-12]进行改进，综合算法优点计算最优解。以滑行时间最短和冲突避免为目标，建立大型繁忙机场的运行环境，通过TAAM（total airspace and airport modeller）仿真软件结合Matlab 编程，对滑行路径动态优化方法进行研究，验证提出方案的可行性。

1 滑行路径动态优化算法

通过在终端区对航班进行预战术性优化，提前将终端区的航班进行分类。对需要优化的航班建立优化模型，在每次优化计算航班滑行路径前，对当时机场场面具体情况进行预测。通过改进Dijkstra 算法对每架在中间进近阶段前的航班进行滑行路径优化，减少航班降落后地面管制人员的工作负荷。

1.1 航班集合划分

出于预战术侧重的思想，首先对终端区航班进行提前分类。在保证不出现航班冲突等失误的前提下，进一步对特定航班集合进行优化，以达到滑行路径的最优选择。图1 展示了依据时间划分航班集合的原理。

图1 航班集合划分原理图Fig.1 Principle diagram of flight assembly division

图1 中t 为时钟，记录和更新当前时刻，每当终端区雷达扫描到新航班时（t3时刻），便将此航班由航班集合3（未优化）移到航班集合2（进行优化）中，航班集合2 即为后文进行改进算法优化的航班集合。随着时间的进行（t2时刻），航班集合2 中最早进入的航空器将被推送到航班集合1（已优化）中，考虑到航空器必须满足安全间隔，冻结时间不能过小，冻结区域的航空器不会参与下一次的排序计算，航班集合1 中的航空器滑行路径不会再变更。

航班集合的分类涉及实际时间与规划时间，在仿真操作中分别对应后文中两次TAAM 仿真运行。两者的具体关系如图2 所示。

图2 实际时间与规划时间关系Fig.2 Relationship between actual time and planning time

图2 中：Tw为航班进行路径优化的时长，每架航班的优化时长（Tw）将被均匀分割成连续等长的时间片进行具体优化计算，便于与后文滑行道传输模型相结合，判断模型节点处是否存在航空器冲突；TL为前置时间，前置时间TL对应后文两次仿真运行的时间差，前置时间具体长度对应图1 中t2时刻至航班落地脱离跑道的时刻；Tc为优化计算所需时长，即程序优化计算所用时间；Tadv表示相邻两次优化计算运行的时间间隔，间隔时长Tadv会根据不同机场对应的进近程序及平均滑行时间进行调整，同时为保证冻结时间的作用，间隔时长Tadv的值应等于冻结时长的值；Twait为相邻两架航班依次出现的时间差。

基于仿真与航班运行的真实情况，不同时长的值应满足以下条件

Tadv

Twait=Tadv-Tc

Tadv>Tc或Twait>0

Tw-Tadv为进行路径优化的时间，其数值等于图1 中（t3-t2），同时t2、t3应满足

1.2 航班数据获取及预测

每架航班在终端区所处位置及对应时间可从TAAM 仿真软件中获得。假设航班时刻信息与机场场面情况均由机场场面控制人员掌握，实现空地信息共享。在每次场面路径规划前，将机场场面滑行道实际运行情况与航班的具体位置等数据作为每次航班滑行路径优化的初始数据。根据各机场不同进场程序，取平均最小值作为规划前置时间，结合已知场面情况、场面各类型航班滑行速度等，得出规划窗口中的预测基础数据，再通过基础数据进行路径优化，从而加强算法准确度，建模与优化过程均在判断航班集合2 中是否有新航班加入后进行。

1.3 滑行路径优化目标函数

对终端区航班进行分类以后，针对航班集合2，首先建立一个相对时间片内的静态场面运行模型。

1.3.1 模型假设

（1）离场航班推出时间可预测，预计离场时间已知，起飞跑道已知；

（2）进场航班预计进场时间已知，脱离跑道时间可预测，停机位已知；

（3）相较于进场航班，离场航班优先级高，同为离场或进场航班优先级相同；

（4）场内所有滑行道适用于任何航班；

（5）每架航班都具备相应属性，如机型、平均滑行速度等；

（6）在滑行道上同机型的航班滑行速度相同；

（7）地面最低尾流间隔可由速度转化为时间间隔。

1.3.2 滑行道传输模型

将机场场面看作是由节点和链路构成的网络模型，如图3 所示。

图3 机场节点网络模型Fig.3 Network model of airport node

假设G（N，L）为有向网络图，N={N1，N2，…，Nn}为节点集合。L={（Np，Nj）∈N×N}为链路集合，（Np，Nj）表示从节点Np到节点Nj，定义滑行道网络的距离矩阵D=（dNpNj）n×n，其中

航班集合2 为R={f1，f2，…，fA}，共有A 个航班。对于任一航班fa∈R 在时间片k 所在窗口内，从该时间片中起始节点Np滑行到节点Ns，在路段Ns→Nj上出现航班fb∈R，即认为节点Ns为冲突节点。

首先判断航班fa与航班fb的优先级，用H 表示优先级高低，即

若航班fa优先级低于航班fb，即H=1，航班fa在不需要重新寻找最短路径的情况下，其滑行时间需要加上一个等待时间tha加以惩罚。

若α=1，则航班fa需要进行等待或更改此时段的滑行路径。若航班fa在不需要重新寻找最短路径的情况下，最小滑行时间还需要加上一个等待时间tha。

综合以上描述可得时间当量长度表达式为

式中：lNsNj为节点Ns到节点Nj的链路长度为航班fa滑行的平均速度。

由于不同机型航空器滑行速度不同，对于同一滑行道，不同机型对应不同的时间当量长度。时间当量矩阵表示为Ts={tNsNj}，其中

如选择改变滑行路径由节点Ns更改至Nm，避免节点Ns冲突等待时间，滑行时间计算步骤同上。

由此可得k 到k+1 时段上的局部滑行路径最短时间当量T 表达式为

每两个连续时间片中，上一时间片的结束节点为下一时间段的起始节点，共有K 个时间段。航班集合2全局滑行路径优化目标函数表达式为

其中在同一个时间片内计算路径最短时间采用改进Dijkstra 算法。

1.4 改进Dijkstra 算法

传统Dijkstra 算法由荷兰计算机科学家Dijkstra于1959年提出，是从一个顶点到其余各顶点的最短路径算法，解决了有向图中最短路径问题。现对传统Dijkstra 算法进行改进，加入时间窗口并将运行时间分为k 段时间片，每2 s 移动一次时间片。改进Dijkstra算法在每次增加后续节点时，根据所划分时间片的时间当量长度更新一次相邻的时间当量矩阵，通过不断迭代求出时间当量长度最短的优化滑行路径。

将距离矩阵D 中每条路段划分用向量In表示，In=[i1i2…in]，in表示第n 条路段。起始节点为滑行道入口，如时间片结束时该航班未处于已有节点，则根据所处位置增加临时节点临时节点不计入节点集合N 中），以记录该时间片该航班的结束位置，并作为下一时间片该航班的起始节点。由于滑行速度一定，可直接得出速度矩阵（i）。改进Dijkstra 算法的主要计算步骤如下：

步骤1初始化，对于任意航班fa，距离矩阵D，时间段向量In，速度矩阵（i）；假设第一个时间段向量内，t0时刻发生冲突，发生冲突的节点标记为Ns，航班fa出发节点记为Np。记使用节点集合P = {Np，Ns}，则未使用节点集合P′=N-P，循环次数in=1；

步骤2标记冲突节点Ns，设置Ns=（Ts，Zs）；Ts=Tp，Zs={Np}；

步骤3对任意节点Nm∈P′，且dNpNm＞0，取min{tNpNs，tNpNm}，计算公式为式（7）；

步骤4对新加入P 的节点Nm，将节点Nm作为起始节点，寻找P′中所有与Nm直接相连的节点（即dNmNj＞0），计算最小时间当量。同时令Ts= Tm，Zs={Nm}∪Zs，P={Nm}∪P，P′=P′-{Nm}；

步骤5更新滑行最短时间向量In，时间当量矩阵Ts及其最短路径前驱节点向量集合Zs；in=in+1；

步骤6若in

2 TAAM 仿真软件建模与算法实现

2.1 空中与地面仿真建模

基于西安咸阳国际机场的空中与地面数据建立TAAM 仿真模型。西安咸阳国际机场进近扇区分为5个，有6 条离场程序，7 条进场程序。地面现有3 座航站楼面积共350 000 m2；共有2 条跑道，跑道长度分别为3 000、3 800 m；停机位127 个。实验规划前置时间为12 min，移动间隔为2 s。建立机场具体仿真场景如图4、图5 所示，地面节点链路图如图6 所示。

图4 西安咸阳国际机场空中仿真模型Fig.4 Air simulation model of Xi'an Xianyang International Airport

图5 西安咸阳国际机场地面仿真模型Fig.5 Simulation model for ground of Xi'an Xianyang International Airportt

图6 机场地面节点模型Fig.6 Node model for airport ground

从2018年全年航班日流量中选取航班978 架次（2018年8月20日），图7 为部分航班时刻表。

图7 部分航班时刻表Fig.7 A part of flight schedule

2.2 算法实现

TAAM 仿真软件默认路径选取方式即为传统Dijkstra 算法。实现改进Dijkstra 算法的运用需通过TAAM 仿真软件中的两个网关，分别是TAAM 控制网关、模拟ADSI 网关。TAAM 控制网关能够使用Matlab编程在模拟运行中代替默认代码，使仿真运行时使用改进Dijkstra 算法。模拟ADSI 网关支持TAAM 仿真软件将模拟情况转换为ADSI 格式依次转发至Matlab程序，以获得模拟运行中场面各航班的具体位置。第1次运行TAAM 仿真（TAAM1）时得到Matlab 编程中关于各航班在终端区的时刻、飞行航迹、脱离跑道或停机位的具体位置与时间等内容，以此为基础编写算法。第2 次运行TAAM（TAAM2）仿真时插入两个网关，实现仿真与算法的结合。具体实现流程如图8 所示。

图8 算法实现流程图Fig.8 Flow chart of algorithm implementation

图8 中，TAAM1 获得每个航班进入规划终端区的时间、离开规划窗口至快速脱离道入口的时长、到达快速脱离道入口的时刻与具体位置。由于模型是提前预测，假设此时TAAM1 运行时间为t0+前置时间，则航班处在终端区的时刻应为t0。Matlab 程序从TAAM 数据库中获取航班预计降落时场面具体情况（t0+前置时间时，机场场面有多少航班，以及航班所处位置；随着时间片的移动，场面航班变化情况，以及各航班位置及对应时刻），根据获得的基础数据执行算法，对航班滑行路径进行规划。规划结束后将相应路径通过TAAM控制网关输入TAAM2 中运行，一直运行到再无新的航班进入终端区，此时TAAM2 中运行时间为t0时刻。最后通过模拟ADSI 网关获得的TAAM2 中航班的实时数据，经Matlab 处理后得到优化后的场面运行数据。

3 结果及分析

以机场2018年8月20日的部分航班为例，由于优化模型考虑可更改滑行路径使时间最短，因此有必要对航班路径更改的情况进行列举，具体情况如表1所示。表1 中航班的路径更改情况较为合理地证明了改进算法的有效性。

表1 部分航班滑行路径更改对比Tab.1 Comparison of changes of taxiway of certain flights

同时改进算法中考虑了冲突解决，在仿真中，通过GMA（generic model area）工具箱可以实现对空间内任意区域内航班详细流量进行统计；运用Reaporter 对滑行道冲突点进行统计，如图9 所示。统计流量较大滑行道为图9 中圈出区域。

图9 滑行道拥堵区域Fig.9 Congestion area of taxiway

两种算法下航班流量的对比统计情况如表2 所示。

表2 流量架次对比Tab.2 Comparison of traffic sorties

通过大流量区域的航班流量对比可以看出，改进Dijkstra 算法有效地缓解了滑行道拥堵情况，使得航班流量分配更加平均。由于改进Dijkstra 算法一定程度上进行了冲突规避，现对滑行道冲突点数量进行统计，得出优化前后的冲突点数量分别为74 和59。可以看出改进Dijkstra 算法在一定程度上减少了冲突量，减缓了场面拥堵的同时避开了冲突点，从而实现了滑行路径的优化。

最后对传统Dijkstra 算法与改进Dijkstra 算法得出的2018年8月20日所有航班平均滑行时间、平均延误时间进行对比，验证优化目标是否实现。统计结果如表3 所示。

表3 平均滑行时间与平均延误时间对比Tab.3 Comparison of average taxiing time and delay time

由表3 可知，改进Dijkstra 算法较传统Dijkstra 算法航班平均滑行时间缩短了12.2%，平均延误时间缩短了25.8%。

传统Dijkstra 算法与改进Dijkstra 算法全天滑行延误时间统计如图10 所示。

图10 全天滑行延误时间Fig.10 Taxiing delay time within a whole day

对比传统Dijkstra 算法，改进Dijkstra 算法全天滑行延误时间明显缩短，全天滑行延误峰值由239 s降至184 s，下降23%，高峰时段（18：00—22：00）总延误时长由1 653 s（约27.5 min）降至1196 s（约19.9 min），下降了27.6%。实验结果表明：改进Dijkstra 算法有效地解决了动态滑行路径优化问题，减少了延误时间。

4 结语

滑行路径优化问题直接影响机场场面运行效率，也是提升机场容量和规模的关键。结合时间窗口对机场终端区航班进行提前规划，对传统Dijkstra 算法进行改进，利用TAAM 仿真软件进行实际数据分析验证。实验结果表明，改进Dijkstra 算法克服了传统Dijkstra 算法不能应用于动态路径搜索的欠缺，通过时间片的加入较好地解决了随机性等多种问题，使机场结果数据较优于传统算法，有效地减少了场面拥挤、滑行时间、滑行冲突及延误时间，为今后机场场面航空器滑行规划提供了一种更完善的理论方法。但由于改进Dijkstra 算法计算量较大，需要的时间窗口相应较大，间接导致了精确度降低。接下来可以进一步研究如何简化计算，提高反馈精确度和预测准确性，更快速、简单、有效地解决滑行路径优化问题。