基于蚁群算法的主干航线网络动态规划

谢春生，李少华，戴玉洁

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

空中交通网络是承载航线运输的重要交通设施，是连接机场与机场之间的纽带。随着航空业的快速发展，空域容量日益成为限制民航业发展的瓶颈。传统主干航线通常受地面导航设备限制，一般采用向背台方法设计，而空域限制区开闭、天气影响及空军活动，对航线的影响较大。现有的航线规划方法灵活性差、周期长，延误或取消航班大大降低了空域利用率。绕飞不利天气，会增加飞行油耗、提高运行成本，同时也会导致碳排放量的增加。随着民航新技术的不断发展，尤其是基于性能导航（PBN）技术的出现，信号覆盖范围不再受限，航线的规划空间可包括整个空域。因此，动态航线网络规划是提高空域利用率的有效措施，对提高航线安全性和经济性，推行节能减排的快速实施有重要意义。

主干航线网络规划的本质是路径规划，对于路径规划的研究方法主要分为：①基于概略图的路径规划[1]；②基于栅格的路径规划[2]；③基于类比的路径规划[3]。这些方法主要通过结合不同的启发式算法实现最优的路径规划。主干路径网络规划在煤炭运输[4]、集装箱运输[5]等方面取得丰硕的研究成果，可提供一定的理论基础。

首先，根据限制区、危险区特点，建立障碍区模型，利用图论思想，采用Maklink线对空域进行重新划分；然后，利用蚁群算法，规划出同时满足安全性和经济性的主干航线，根据障碍区的动态开放，提出一种主干航线网络的动态规划方法；最后，以中南管理区部分空域为例，规划出多条主干航线网络，并验证算法的有效性。

1 基于Maklink线的空域模型建立

1.1 障碍区模型

将限制区、危险区、禁区包含的区域定义为障碍区。根据障碍区的开放时间，将障碍区分为静态障碍区和动态障碍区。静态障碍区是指长期处于关闭状态，不允许飞行活动的区域；动态障碍区是指开放时间不固定，在限制时间以外，允许飞行活动的区域。高大障碍物是指地面所有影响飞行安全障碍物的统称。

由于障碍区划设的形状不规则，大多以凸多边形为主，将圆形、凹多边形的障碍区，人为转换为凸多边形，为构建空域模型提供基础。

1.2 Maklink线构造

假设空域C内包含n个障碍区Oi，且均为凸多边形，第i个障碍区表示为Oi={（x1，y1），（x2，y2），…，（xk，yk），…，（xK，yK）}，其中，（xk，yk）是 Oi顶点 Vk的横、纵坐标。整个空域环境可表示为C={O1，O2，…，On}，随着障碍区的变化而动态改变。动态障碍区Maklink线的构造流程，如图1所示。

图1 Maklink线构造流程图Fig.1 Maklink construction procedure

1.3 空域模型建立

主干航线动态规划的解空间是高空空域，研究主干航线规划的首要条件是建立空域图模型。因此，针对主干航线设计问题，结合图论思想建立模型C，如图2 所示。其中，O1，Ok，OK为障碍区，（as1，ae）、（as2，ae）表示起点为as1、as2，终点为ae的初始航线。

图2 空域模型Fig.2 Airspace model

1.4 构造航线初始解

航线初始解是以Maklink线中点为解空间的前提下，采用Dijkstra算法[6]搜索一条可行航线R0，即

其中：as为航线起点；ae为航线终点；ui为Maklink线的中点。

2 独立主干航线规划模型

在三维空间范围内搜索出有效的航路点，工作量大、执行缓慢，较难规划出主干航线网络。因此，将三维航线规划问题简化到二维平面内[7]，将问题转化为最短路径的求解，作为航线规划的目标函数。

2.1 目标函数

航线路径的长短对于主干航线网络水平剖面的经济性有直接影响，将主干航线R投影至二维平面，其中，R={S1，S2，…，Sn}，Si表示航段，对应的航段长度di=|Si|，用pi和pi+1分别表示航段Si的起点和终点。定义投影后总航线距离为

2.2 约束条件

1）航段水平越障

空域内静态障碍区多为无法飞越障碍物，在设计航线时需要绕开此类障碍物，按照规章要求，给出足够的安全裕度z0。假设航段与障碍区的距离为zi，根据凸多边形顶点与航段的相对位置，定义顶点Vk与航段Si的距离如下

2）航线最低安全高度

复杂地形是影响航线规划的主要考虑因素，航段的最低安全高度直接受地面高大障碍物限制，因此，航段需与各高大障碍物之间有一定的垂直安全裕度MOC。假设空域内有m个障碍物，表示为B={b1，b2，…，bm}，其中，bj=（xj，yj，hj）。

航线的水平保护区是以航段Si的投影航迹si为中心航线，绘制的宽度为W，长度为|si|的矩形区域[8]。判断障碍物bj是否在保护区内，如果在，则将障碍物bj置于该保护区障碍物集合N中。因此，航线最低安全高度需满足如下条件

其中，hM=hmax{N}+MOC，hmax{N}为该保护区中障碍物的最大垂直距离。

3）航段转弯角度

受飞机性能及飞行员操纵限制，飞机机头的偏转角度θ应满足如下条件

综上所述，建立独立主干航线模型如下

3 蚁群算法的动态规划

蚁群算法是用于解决复杂规划问题的全新启发式算法[9]，航路点的水平搜索规则可实现水平方向的经济性最优。假设x只蚂蚁从起点as爬行至终点ae，在到达航路点pi时构造下一航路点步骤如下。

1）水平剖面将Maklink线均分，水平离散度为a，因此，可表示为 l1，l2，…，la。

2）li表示为下一个以概率phozi进行选择的水平方向节点。phozi的计算如下

目前，国内外针对空域主干航线网络规划问题的研究尚不成熟。结合国内公交网络设计方法，采用“逐条布线，规划成网”的方法进行航线网络的动态规划。根据网络设计要求，在众多可行备选线路集中逐条布设，逐渐迭加成网，该方法简单、可操作性较强。

由于空域中存在的动态障碍区开放时间不固定，而障碍区的动态变化对整个主干航线网络的规划有很大影响。因此，航线网络的布局需要根据障碍区的变化及时调整，从而实现空域容量最大化。采用图论思想将空域划分，根据动态障碍区的变化，可通过重新调整Maklink线的布局将空域重新划设，进而利用蚁群算法重新进行航线网络规划。

4 实例分析

以中南地区部分空域为例，验证主干航线网络规划方法。考虑 4 个危险障碍物分别为 b1、b2、b3、b4；8个高大障碍区分别为O116、O117、O118、O119、O120、O121、O122、O127。其中，O127为凹多边形，将其转化为凸多边形。表1给出待优化的起点及终点，其中，航线起点均为空域内导航台或报告点。

表1 待优化主干航线起点与终点Tab.1 Starting point and final point of trunk route to be optimized

4.1 独立主干航线规划

以航线H61为例，首先根据1.2节构造Maklink线，将空域划分为若干区域，然后构造航线初始解，如图3虚线所示。

图3 主干航线H61规划Fig.3 Trunk route H61 planning

假设障碍区安全距离z0=5 km，障碍物超障裕度MOC=600 m，航线保护区宽度W=25 km。选取水平离散度a=10，蚂蚁数量x=30，迭代次数t=500，信息素重要程度因子α=6，节点启发值β=1.1。采用蚁群算法优化初始水平航迹，如图3所示。划设航线安全保护区，确定b4为影响安全的关键障碍物，海拔高度为2 680 m，根据式（5）确定航线最低安全高度3 280 m。表2给出航线H61优化前后结果比较。

表2 航线H61优化结果Tab.2 Optimized Route H61

从表2可看出：优化后的航线距离d较优化前缩短了58.6 km，经济性得到很大提高；优化后的机头偏转角度θ变化幅度在前4段都较之前有所减小，更利于飞行员操作。同时采用以Maklink线中点为基点，两侧内缩25 km的算法，保证了与障碍区之间的安全间隔，同时满足水平安全间隔和转弯角度要求。

4.2 主干航线网络动态规划

利用独立主干航线的规划方法，分别优化A151和H79航线，图4给出了主干航线规划图。障碍物b2是A151航线关键障碍物，由式（5）确定航线最低安全高度为2 652 m。根据国内航空资料汇编（NAIP）可知，O117为动态障碍区，每日 08：00～24：00 关闭。因此，需重新规划航线网络，如图5所示。O117对航线A151有影响，从表3中可看出，关闭障碍区O117后，优化后的航线距离比之前减少12 km。同时，优化后的机头偏转角度θ继续保持在0°～90°之间，满足飞机性能及安全性的要求。

表3 A151优化结果Tab.3 Optimized Route A151

5 结语

随着碳交易的日益推进，对节能减排的迫切需求，主干航线网络设计在保证空中交通运输安全的同时，兼顾效率及效益。首先建立障碍区模型，采用Maklink线将空域重新划分；然后，利用蚁群算法规划出同时满足安全性和经济性的主干航线；根据障碍区的动态开放状态，提出一种空域内主干航线网络的动态规划方法，最终实现整个空域的主干航线网络动态规划。

图4 主干航线网络规划图Fig.4 Trunk ronte network planning

图5 主干航线网络动态规划图Fig.5 The result of trunk network dynamic planning