基于蚁群算法的航空器滑行路径优化

吴 虹， 赵 征

(南京航空航天大学 民航学院， 南京 211106)

滑行道是连接停机位和跑道的必经通道，在机场场面运行中起着至关重要的作用，尤其对已经实现机坪管制的机场而言，是仅次于停机位的重要资源.在大型枢纽机场，提高滑行道的运行效率，一方面可以降低航空公司运行成本，减少航空器运行产生的环境污染;另一方面可以减轻机坪管制员的工作负荷，提高机场场面运行的安全裕度.

提高滑行道运行效率，主要方法是优化航空器滑行路径.在航空器滑行路径优化研究方面，国外起步较早，主要研究领域有静态滑行优化和动态滑行优化.在静态滑行优化领域，2013年Lucas P·Rosa等[1-2]采用遗传算法进行航空器滑行路径优化，通过实验数据分析，遗传算法解决了航空器滑行冲突问题，提高了大型繁忙机场场面运行效率.在动态滑行优化领域，2015年Hang Zhou等[3-4]通过动态的对航空器滑行路径进行冲突检测，并在此基础上通过A*算法进行航空器滑行路径规划.国内相关研究起步较晚，主要是在国外研究成果的基础上进行开拓和创新，例如，2015年杜姗姗等[5]融合遗传算法和蚁群算法各自的优点，采用两阶段法求解最优路径，2017年付宇晓等[6]采用人工神经网络算法进行动态滑行路径研究.总的来说，国内外学者研究的焦点集中在模型和算法上，对具体约束条件下的典型问题缺乏指导意义，本文在蚁群算法的基础上，根据约束条件设计出符合现场实际运行情况的仿真系统，并不断验证和优化算法.

本文以南京机场为例，首先建立场面结构数学模型，通过有向图的方式，将机场场面抽象成节点路段型数学模型.其次，建立基于冲突检测的滑行路径优化模型，并采用蚁群算法对模型进行求解.最后结合机场实际运行情况开发仿真系统，最后通过实例验证说明了算法的可行性和有效性，降低了航空器滑行冲突概率，提升了滑行道系统的运行效率.

1 模型建立

1.1 基于有向图的场面结构模型

目前，国内外在机场场面结构建模领域，采用的方法主要包括MILP模型、有向图模型及Petri网建模等[7-9].本文采用有向图模型进行机场场面结构建模.图1为采用有向图建模方法对机场场面结构进行抽象后的模型.场面模型中的节点表示机场场面运行中的关键位置点，比如跑道与滑行道之间的交叉点、滑行道之间的交叉点以及滑行道与停机坪之间的交叉点等.模型中的有向边则表示场面中两个节点间的路径.

图1 机场场面有向图模型Figure 1 Airport surface directed figure model

在机场场面模型中，节点根据用途可分为跑道节点(如图1中节点1和节点2)、滑行道节点(如图1中节点11和节点15)、停机位节点(如图1中节点58～63).节点的属性信息包括唯一标识、位置坐标、节点属性、使用情况等.有向边属性信息包括唯一标识、单双向、航班类型、进离场、最大速度、最大数量、使用情况等.有向图模型具有构建简洁，能直观反映场面各区域连接关系和相对位置关系，但对场面运行规则的表达有所欠缺，本文通过在节点和有向边上增加通行判断条件，使得模型更加符合现场运行规则和约束条件.

1.2 模型构建

以机场某个时间段内进离港航班为研究对象进行场面滑行路径规划，建立航空器滑行路径优化模型的基本原则是：进港航空器滑行优先级高于同时段内的离港航空器，这一原则的目的是减少航空器占用跑道时间；离港航空器中正常航班滑行优先级高于延误航班，这一原则的目的是减少航空器起飞延误.以所有进离港航空器总滑行时间最小为目标进行航空器路径规划.

以航空器总滑行时间最小为目标的模型目标函数为：

(1)

2 算法设计

蚁群算法作为一种用于求解最短路径问题的算法，结合了启发式算法和正反馈的优点，具有分布式计算、鲁棒性等特点.航空器在场面滑行过程中，可能产生交叉冲突、追尾冲突、对头冲突等各种冲突情况，航空器滑行的这种相互联系制约与蚁群中转移策略、信息素更新等机制存在着相似之处[10-12].本文采用蚁群算法对航空器滑行路径优化问题进行求解，算法步骤如下：

1)读取某个时间段内的航班信息，初始化模型参数：具体包括最大迭代次数iter_max、信息素重要程度因子α、启发函数因子β、挥发程度因子ρ、蚁群数量N、每个蚁群蚂蚁数量M、节点数量G等；

2)进入新一次迭代，当前迭代次数iter+1，每轮搜索把N只蚂蚁放在起点，循环进行M轮搜索；

3)进入新一轮搜索，当前搜索轮数k+1，寻找N个航班的滑行路径.为每个航班定义两个列表，一个是允许列表，用于存放蚂蚁下次允许前往的所有可行节点集合，初始化为起点允许前往的所有可行节点；一个是禁忌列表，用于存放蚂蚁已经访问过的节点，初始化为起点(跑道或者停机位)；

4)计算所有蚂蚁的转移概率，根据计算结果选择从节点i移动到下一个节点j，将节点j从允许列表转移到禁忌列表中，并将节点j允许前往的所有可行节点放入允许列表中；

5)判断各个蚁群的蚂蚁在移动到下一个节点的过程中是否存在路径冲突，如果存在则按照冲突热点避让机制进行避让；

6)判断所有蚂蚁当前节点是否为航班的终点，如果是则记录当前N个航班的滑行路径和总滑行时间；如果不是则转至步骤4)；

7)判断是否已经完成M轮搜索，如果是则更新N个航班的最小总滑行时间及相应的滑行路径，并更新信息素；如果不是则转至步骤3)；

8)判断是否已经完成iter_max次迭代，如果是则算法结束，输出N个航班的最小总滑行时间及相应的滑行路径；如果不是则转至步骤2).

信息素的更新方法分为三种：1)局部更新法，当某一只蚂蚁找到某一条路径后进行局部信息素更新；2)全局更新法，当蚁群找到某一条最优路径后进行全局信息素更新；3)冲突更新法，当两个蚁群间存在路径冲突时，进行全局信息素更新[13].采用蚁群算法求解航空器滑行路径优化问题的流程图见图2.

3 仿真系统设计

为验证本文提出的优化算法，开发了航空器滑行路径优化仿真系统.系统主要包括场面模型编辑模块、运行环境配置模块、航空器路径规划模块和航空器运行仿真模块等四个模块.仿真系统采用Microsoft VisioStudio平台基于C++语言开发.其中场面模型编辑模块通过直接在界面上编辑生成有向图，提供给路径规划和运行仿真模块使用，具有增加、修改、删除、加载、保存等功能.在场面运行环境配置模块完成相应的参数配置后，路径规划模块调用优化算法计算航空器滑行最优路径，最后通过运行仿真模块在用户界面上模拟航空器滑行轨迹.通过对航空器运行的仿真模拟，检验航空器滑行路径优化算法的准确性、有效性和可用性.

4 案例分析

以南京机场为研究对象进行实际算例的验证，对南京机场3号机坪航空器进离港滑行路径进行研究.航空器起飞使用06跑道方向，降落使用07跑道方向，选取某个运营日的1200～1300时间段的航班为研究对象.

下面针对上述两个冲突航班HO1748和HO1657滑行路径进行分析研究.进港航班HO1748在跑道07方向降落，计划停机位为229，离港航班HO1657计划停机位211，在跑道06方向起飞，两个航班在冲突热点HS5相遇，根据冲突热点避让机制，进港航空器优先离港航空器通过热点区域，因此需要对离港航班HO1657重新规划滑行路径.

通过滑行路径优化算法，对航班HO1657滑行路径进行优化，通过冲突热点避让机制，将冲突热点作为约束条件，重新计算滑行路径，得到HO1657航班的次优滑行路径.离港航班HO1657次优滑行路径结果如图3.新的滑行路径避开了冲突热点，提高了该区域的安全水平和运行效率.

图3 冲突航班优化前后的滑行路径Figure 3 Before and after conflict flight optimization

对1200～1300时间段内的航班，采用滑行路径优化算法进行优化，优化后的滑行时间和实际滑行时间对比如图4.

图4 路径优化结果对比Figure 4 Comparison of path optimization results

优化后有3架航班滑行路径发生了变化，航班HO1657、DZ6257、MU2855通过优化后滑行时间分别节省了55、38、43 s，这几个航班滑行路径优化后有效避免了冲突情况，减少了冲突热点区域的冲突架次和概率，提高了机场安全运行裕度.1200～1300时间段内的航班优化后的总滑行时间比实际滑行总时间减少了136 s，对提高滑行道运行效率和减少滑行冲突起到了积极的作用.

5 结 语

本文以最短滑行时间为目标建立了航空器滑行路径优化模型，采用蚁群算法对滑行路径优化模型进行求解，提出基于冲突检测的航空器滑行优化算法[14-15]；结合南京机场的实际运行资源配置和约束，开发了南京机场的滑行路径优化仿真系统.通过实例验证，经过优化后的方案，符合南京机场实际情况，有效降低了冲突发生的频率，减少了航空器地面滑行时间，提高了机场安全水平和运行效率.