基于改进蚁群算法的改航策略问题研究

王莉莉，杨惠东，周　娟

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



基于改进蚁群算法的改航策略问题研究

王莉莉，杨惠东，周娟

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

摘要：航班改航飞行是在空域受危险天气及飞行冲突影响时的一种重要策略。为解决改航问题，恶劣天气条件下，首先基于数值气象预报特征，运用栅格法对空域场景进行改航环境建模。在考虑了空中交通规则及航空器性能的基础上，对航向改变次数、转弯角度、航段距离进行约束，提出基于改进蚁群算法的改航路径规划方法。最后，通过对贵阳—长沙航路的仿真分析，表明该算法能在局部受限区之间搜索到一条安全可行的临时改航航线，达到提高空域利用率的目的。

关键词：空中交通规划；改航策略；改进蚁群算法；栅格法

随着空中交通的不断发展，航班越来越多，航线覆盖范围也越来越大，导致空中飞行在多变气候下遭遇危险天气的概率也变大，而航空运输延误的主要原因之一是危险天气。因此，为减小危险天气对航空飞行的不利影响，并充分利用现有空域资源，通过动态变更航空器飞行航线，绕过危险区，可以使航空器安全回避危险天气，提高航空运输的运行效率。

近年来，在改航问题方面的研究越来越多，已有研究成果主要包括：基于多边形的改航路径规划算法[1-3]、基于原有航路网的启发式搜索算法[4]、基于人工势场的改航路径规划算法[5]、基于标准进离场程序的改航路径规划算法[6]。以上算法的不足之处分别在于将影响航空安全的危险天气整体外边缘简化为多边形飞行受限区，不利于提高空域利用率；对原航线依赖性强，在复杂环境下不易找到理想改航路径；规划过程中容易产生局部最优解，陷入死锁；算法运算速度慢，实时性差。为克服以上缺点，本文在考虑相关空中交通规则的基础上，首先基于数值气象预报特征，将空域环境栅格化，增加了穿越局部危险天气之间的搜索路径；采用的改进蚁群算法[7-9]具有分布式并行机制特征，能较好地适应复杂多变的天气环境模型；算法将转移概率与优化参数相结合，并对当前最优蚂蚁进行信息素全局更新，从而避免陷入局部最优解，增强了正反馈机制，提高了算法的收敛速度。最后通过仿真算例验证了基于改进蚁群算法的改航策略的可行性。

1　环境模型的建立

为更好地描述和处理航空器改航问题，对航空器的飞行环境建立相关模型。航空器按预定飞行计划飞行，若部分航段受恶劣天气影响，需对该区域进行网格的定义和栅格的划分。为简化环境模型，文中只研究二维空间也就是同一高度层内航空器在飞行受限区域侧面绕过的情况。

航线上各位置报告点之间的连线组成航路。若气象雷达探测到位于航路报告点ri与rj（i

将左上角的第1个栅格的序号定为1，然后从左到右，从上至下依次编码。记gi∈AP为任意栅格，（xi，yi）是gi的坐标，其与序号Si之间的映射关系由式（1）确定

图1　基于栅格的环境模型示意图Fig.1 Environm entm odel diagram based on grid

在基于网格的环境模型中，通过多普勒天气雷达探测气象数据，将采集到的数据用一个称为垂直累积液态含水量VIL（vertically integrated liquid-water content）[10]的算法处理后得到。计算后的VIL值大小表示该栅格区天气的恶劣程度，将受影响区域进行6个等级的划分[11]，分别用不同颜色表示。对于雷达回波≥41 dBZ，也就是在级别3以上的天气等级会严重影响航空器的飞行安全[12]。这时，航空器不可以穿越与此飞行受限区（已考虑了安全余度）所相交或重叠的网格，对于等级较低的天气环境，航空器可以选择性穿越。气象信息采用算法栅格数值化后，便能在其影响范围内生成改航环境模型，相比人工描绘受限区域边界，显得更为精准。

2　基于改进蚁群算法的改航路径寻优

2.1改进蚁群算法的基本原理

蚁群优化算法是一种通过模拟蚂蚁依赖信息素的交流以选择最短路径来达到搜索食物的目的的群集智能方法。因为改进蚁群算法具有分布式并行机制、信息素正反馈机制和鲁棒性等优点，因而其能较好地适应对流天气实时动态变化的环境并快速规划出改航航线，使保持稳定性能参数的航空器能在较短的反应时间内完成绕飞任务。恶劣天气下的改航路径规划目的是让航空器在二维网格空间内安全避让飞行受限区，以较少的航向改变次数及较短的改航航程为约束由起始节点出发沿一条优化路径至目标节点。

为适应所建立的环境模型，航空器飞行运动作如下简化：

1）相对于天气的几何尺度，航空器在二维平面上视为质点。

2）航空器在巡航阶段速度Vc保持不变，假设其各航段内做匀速直线运动。

3）出于飞行安全及航空器性能考虑，航空器在改航过程中只能进行3个方向的机动飞行，即保持原航向、左转45°、右转45°，如图2所示。

图2　栅格环境下航向的选择状态Fig.2 Course selection state in grid environm ent

4）航空器在栅格环境模型中，每单位时间均是径向飞往下一网格的中心点，航程为L或1.414 L，计算航程时改航起始点与改航结束点均以其所在栅格的中心点为准。

运动中的蚂蚁k（k=1，2，…，m）会根据相邻的栅格的连通航段上的已有信息素的多少来决定它下一步的转移方向。蚂蚁k在时刻t从栅格i向栅格j转移的概率定义为

否则

其中：τij（t）表示t时刻连通航段（i，j）上的信息素强度；ηij（t）表示能见度的启发式函数，设为1/εij（t），εij（t）为航空器航向改变因子，若保持原航向飞行其值设为0.5，机动转弯飞行则为1；λij（t）=1/μij（t）与天气的恶劣程度相关，μij（t）为t时刻栅格j处的天气等级，μij（t）= {1，2，3，4，5，6}；β、α和φ 3个参数，分别表明在运动过程中蚂蚁的航向选择、所积累的信息素和避让天气块时启发因子在蚂蚁选择路径中的相对重要性；allowedk={1，2，…n}表示蚂蚁k下一时刻允许选择的栅格，对于已走过的栅格则记录在禁忌表tabuk中；为避免循环搜索陷入局部最优，式中引入参数ωx（x=1、2、3），若某条航线上的信息量过大时，令ωx为一较小值以平衡各条路径上的信息量，当循环达到一定次数时，令ωx为一常数，使蚂蚁找到最优航线。

经过n个时刻，蚁群完成一轮循环后，对各条栅格连通航段进行全局信息素的调整，为加快算法的收敛速度，仅对本次循环中最优更新蚂蚁k所走过的航线进行信息素增强

2.2改进蚁群算法的实现步骤

步骤1：将探测到或预报的气象信息数值化，利用栅格法建立环境模型。

步骤2：初始化蚁群算法搜索路径的参数：循环次数n、最大循环次数N、改航起始点所在网格序号startsn、改航结束点所在网格序号endsn、禁忌表tabu、当前全局最短航程shorterlen。设置蚂蚁数目为m，各相邻栅格（仅3个方向）连通航段上的初始信息素为τij（0）=τ0。

步骤3：设初始栅格为每只蚂蚁的当前栅格gi（i= 0，1…，m-1），同时将m只蚂蚁置于初始栅格上，gi序号记入相应蚂蚁的tabu。

步骤4：根据式（2）和式（3）分别计算从gi到与其相连通栅格的转移概率，并根据概率移动至下一栅格gi’。

步骤5：将gi’序号记入对应的tabu。判断此时是否有蚂蚁到达目标栅格，若有，结束本轮循环，更新shorterlen，取本次循环中最优蚂蚁序号为k。若没有，令gi= gi’，转到步骤4。

步骤6：根据公式（4）、（5）和（6）对各条航线上的信息素浓度进行衰减，并仅对蚂蚁k所走过的改航路径上的信息素进行增强。

步骤7：n=n+1。若n≤N，shorterlen=0，清空每只蚂蚁对应的tabu，转到步骤3。

步骤8：将相邻栅格之间的部分弯曲航段拉直修正，输出全局最优航线及其长度。

3　仿真算例分析

根据前面的数学模型，下面以贵阳—长沙航路为例来说明，当沿航线及其邻近空域受恶劣天气影响时，运用本文所提出的方法规划临时航线，航空器能安全有效地绕过飞行受限区。

贵阳—长沙航线沿途的报告点依次是：贵阳（KW E）—P173—P217—P293—怀化（ZHJ）—P159—老粮仓（LLC）—长沙（CSX）。气象部门通过多普勒气象雷达和气象卫星测得航段P217—P293—怀化（ZHJ）—P159有雷暴，情报部门根据预报确定会受其影响的不同等级的飞行受限区，如图3所示。在P217与P159之间建立栅格环境模型，栅格数量为14×12，L取10 nm。

应用改进后的蚁群算法进行仿真计算。为了验证算法的效果，取不同的参数值进行实验，参数的默认值设为m=100，N=50，α=1，β=1，φ=1，Q=10，ρ=0.9。每次实验只有1个参数被改变，被测试的值为：α∈{0，0.5，1，5}，β∈{0，1，2，3}，φ∈{1，3，5，7}，Q∈{10，100}，ρ∈{0.3，0.5，0.7，0.9}。仿真结果表明当参数设置为表1中的数值时，能迅速规划出一条较优的改航航线，栅格序号为99 - 100 - 101 - 102 - 103 - 90 - 91 - 92 - 93 - 94 - 81 - 68 - 55，如图3虚线所示，同时生成的收敛曲线、各航线平均航程分别如图4、图5所示。

图3　基于改进蚁群算法的改航路径示意图Fig.3 Diverting path diagram based on im p roved ant colony algorithm

表1　实验最优参数设置Tab.1 Experim ental optim al param eter settings

图4　改进蚁群算法收敛曲线Fig.4 Convergence curves of im proved ant colony algorithm

图5　各航线平均航程Fig.5 Average distance of all courses

改进蚁群算法对每次迭代中当前的最优航线进行信息素更新，可提高全局航线的生成速度，这样，可较快收敛较优解。生成的临时航线距离为136.57 nm，较原飞行计划P217至P159航段距离127 nm增加了7.5％，符合改航增加距离在20％范围内的规定。航空器沿新航线通过3个机动转弯就能安全有效地避让危险天气到达改航结束点，较其他多转弯航线，减轻了飞行员与管制员的工作负荷，增加了旅客的舒适度。若将飞行受限区用多边形算法划设[2]，航空器只能从整体恶劣天气的最外缘绕飞，如图3所示，此时改航距离为181.81 nm，比原计划航线增加了54.81 nm。通过对比，本算法规划的改航航线较优。

4　结语

本文针对危险天气下航路不能正常使用的情况，对气象信息栅格化的环境模型提出基于改进蚁群算法的临时航线规划方法。本算法在绕飞过程中，所需转弯次数少，能减轻相关人员的工作负荷；改航航程较短，提高了空域的使用效率及航空运营的经济性。通过对实例进行仿真，得到了令人满意的改航效果，所提出的改航策略具有一定的有效性和可行性。

参考文献：

[1] SRIDHAR B，CHATTERJIG，GRABBE S，et al.Integration of Traffic Flow Management Decisions[C]//AIAA Guidance，Navigation，and ControlConference.Monterey，California，2002：1-9.

[2]李雄，徐肖豪，朱承元，等.基于几何算法的空中交通改航路径规划[J].系统工程，2008，26（8）：37-40.

[3]李雄，徐肖豪，王超，等.基于凸多边形的飞行改航区划设及路径规划研究[C]//中国控制与决策会议.沈阳：东北大学出版社，2008：3083-3088.

[4]宋柯.空中交通流量管理改航策略初步研究[D].南京：南京航空航天大学，2002.

[5]徐肖豪，李成功，赵嶷飞，等.基于人工势场算法的改航路径规划[J].交通运输工程学报，2009，9（6）：64-68.

[6] KROZEL J，W EIDNER T，HUNTER.Terminal AreaGuidance Incorporating Heavy W eather[C]//AIAA Guidance，Navigation and Control Conference.New Orleans，LA，1997：411-421.

[7]李士勇.蚁群算法及其应用[M].哈尔滨：哈尔滨工业大学出版社，2004.

[8]朱庆保，张玉兰.基于栅格法的机器人路径规划蚁群算法[J].机器人，2005，27（2）：132-136.

[9]任春明，张建勋.基于优化蚁群算法的机器人路径规划[J].计算机工程，2008，34（15）：1-3，35.

[10]PANNEQUIN JJ，BAYEN A M，MITCHELL IM，etal.Multiple AircraftDeconflicted Path PlanningwithW eatherAvoidanceConstraints[C] //AIAA Guidance，Navigation and ControlConference，2007.

[11] MUELLER C K，FIDALGO C B，MCCANN D W G，et al.National ConvectiveW eather Forecast Product[C]//8th Conference on Aviation，Range，and AerospaceMeteorology，1999.

[12]RHODA D A，PAW LAK M L.The Thunderstorm Penetration/Deviation Decision in the Terminal Area[C]//American Meteorological Society，8th Conf.on Aviation，Rangeand AerospaceMeteorology，1999：308-312.

（责任编辑：黄月）

Rerouting strategy research based on im proved ant colony algorithm

W ANG Lili，YANG Huidong，ZHOU Juan
（College of Air Traffic Management，CAUC，Tianjin 300300，China）

Abstract：Flight rerouting is an important strategy in the airspace with the limit of heavy weather and flight conflict.To solve rerouting problem，the gridmethod is firstly utilized to build themodel for diverting airspace environment based on numerical weather prediction features in severe weather. Taking air traffic rules and aircraft performance into consideration，a new rerouting path planning method basing on the improved ant colony algorithm is proposed under the limitation of head changing times，turning angels and travelling distance. Finally，the flight path ofGuiyang-Changsha is studied.Simulation results show that the proposed method can search a safe and feasible temporary flight rerouting path between local flow constrained area and others，and can improve the utilization rate of the airspace effectively.

Key words：air traffic planning；rerouting strategy；improved antcolony algorithm；gridmethod

作者简介：王莉莉（1973—），女，陕西兴平人，教授，博士，研究方向为空域规划、空中交通管理.

收稿日期：2014-03-26；修回日期：2014-09-01基金项目：国家自然科学基金项目（61179042）；中央高校基本科研业务费专项（ZXH2012L005）

中图分类号：V355

文献标志码：A

文章编号：1674-5590（2016）01-0015-04