基于航路点布局的多目标网络结构优化方法

2019-01-30郑煜坤王瑛李超亓尧李正欣

北京航空航天大学学报 2019年1期

郑煜坤，王瑛，李超，亓尧，李正欣

(1. 空军工程大学研究生院，西安 710051； 2. 空军工程大学装备管理与无人机工程学院，西安 710051)

中国空域呈现碎片化、多元化特征，且部分区域航路网络结构与飞行流量分布的矛盾十分突出[1]。为了规避障碍空域，同时避免因节点失效而导致的网络崩溃，需进行航路网络结构优化。

航路网络结构优化指通过调整航路点及航段的数量和位置以改变原有网络的性质和布局，从而实现优化目标[2]。根据规模大小，航路网络结构优化分为全局性优化和区域性优化[3]。全局性优化针对主干航路进行，其优化过程复杂，改造成本较大；区域性优化则是在已有航路网的基础上，针对一定范围内的支线航路进行，改造成本较小，应用更为广泛。

目前，国内外学者针对区域航路网络的优化模型和算法进行了大量研究。王世锦和公言会[4]根据中国空域实际情况，建立了多目标优化模型，并利用蚁群算法[5]和元胞自动机[6]完成了模型求解。Dunn和Wilkinson[7]针对自然灾害造成的部分航段失效，提出了基于节点重分布的自适应重构策略和永久改航策略。康金霞[8]利用复杂网络建模方法对航路网络抗毁性进行分析，提出了单航路点失效时的改航方法。严伟等[9]以网络经济性与安全性为基础建立多目标优化模型，并采用烟花算法进行求解。然而，传统规划方法采用的目标函数及约束条件较少，规划策略单一，且未能将网络拓扑设计与飞行流量大小相结合，难以满足实际需要。

本文在对两航路、多航路交叉点容量进行细致讨论的基础上，以网络的最小运行费用、最小飞行冲突系数、最小非直线系数和最小航路角度改变量为优化目标，以“三区”约束、容量约束和优化范围约束为限制条件，建立了区域航路网络优化模型。进而提出移动、融合、分解等航路点优化策略和优化步骤，并使用更为精确的NSGA-Ⅲ算法完成模型求解。实现了网络细节与整体性能的统筹规划，有效提升了区域航路网络的安全性、精确性和综合性，弥补了传统规划方法的不足。

1 区域航路网络建立

1.1 组成要素

区域航路网络由航路点和航路构成，且包含了节点连接关系、飞行流量和飞行容量等要素。其中，航路分为境内航路、过境航路和出境航路，它们由多条依次相连的航段组成；航路点分为固定航路点和移动航路点，前者指机场及区域边境点，能够产生和吸收飞行流量，后者指航路交叉点及转向点，能够传递飞行流量[10]。

1.2 表达形式

为了反映区域航路网络特性，对各组成要素进行数学描述，可表示为N(P,D,f,C)，具体含义如下：

1)P(N)={P1,P2，…,Pn,Pn+1,…,Pn+m}为航路点集，前n项为固定航路点，后m项为移动航路点。

2)D(N)为航路连接距离矩阵，可表示为

D(N)=(dij)(n+m)×(n+m)i,j∈[1,m+n]

(1)

(2)

式中：(xi,yi)为Pi坐标；L(Pi,Pj)用来判断航路点Pi与Pj是否相连，若是，值为1，若否，值为0。

3)f(N)为网络流量参数，指单位时间内通过某航段或某航路点的航空器数目，包括航段PiPj的流量fij和航路点Pi的流量fi。

4)C(N)为网络容量参数，包括航段PiPj的容量Cij和航路点Pi的容量Ci。

1.3 容量分析

区域航路网络容量是衡量网络容纳性的参数，分为航段容量和航路点容量。

航段容量指单位时间内航段上某点允许通过的最大飞行架次[11]。令航空器巡航速度为v，最小管制距离为Lmin，可得

(3)

航路点容量指在特定航路结构中的交叉点单位时间内允许通过的最大飞行架次[6]，如图1所示。PA′PO、PB′PO为汇聚航段，POPD′、POPH′为离散航段，α、β、φ、φ为航段夹角。

若t=0时，前继航班位于PB′PO上的O点，后续航班位于PA′PO上的Y1点，L=|Y1O|，相邻航班间距为F，则存在以下3种情况：

图1 航路点容量示意图Fig.1 Schematic of waypoint capacity

1) 当t∈(0,L/v)时，前继航班运行至G1点，后续航班运行至E1点，有

F={(2v2+2v2cosβ)[t-L/(2v)]2+

(L2/2)(1-cosβ)}1/2

(4)

(5)

2) 当t∈[L/v,+∞)时，前继航班运行至G2点，后续航班运行至E2点，有

F={(2v2+2v2cosφ)[t-L/(2v)]2+

(L2/2)(1-cosφ)}1/2

(6)

(7)

则航路点O能正常运行时，其容量为v/Lmin。

3) 当t∈(-∞,0]时，前继航班运行至G3点，后续航班运行至E3点，有

F={(2v2-2v2cosα)[t-L/(2v)]2+

(L2/2)(1+cosα)}1/2

(8)

(9)

则航路点O能正常运行时，其容量为v/Lmin。

综上所述，当两航路交叉且来流方向固定时，O点的容量取值有6种情况。在实际运行过程中，为保证O点的安全运行，应使其容量取最小值，则有

(10)

(11)

根据上述思路，当多条航路发生交叉时(见图1(b))，可将其划分为若干个两航路交叉的情况进行处理，则交叉点O的容量为

CO=min(CO1,CO2,…,COω)

(12)

(13)

式中：COi(i=1,2,…,ω)和δi(i=1,2,…,ω)分别为第i种两航路交叉情况下对应的点容量和相应航段夹角。

2 区域航路网络结构优化模型

2.1 模型假设

区域航路网络结构复杂，为了模拟实际运行环境，构建网络优化模型，做出以下假设：

1) 网络中的航空器均位于同一高度层，其真航线角为[0,π]或[π,2π]。

2) 航路点之间的连接关系和飞行流量保持不变，“三区”空域不可穿越。

3) 航空器巡航速度为800 km/h，规定的最小雷达管制间隔为20 km，航路点的优化范围为±50 km。

4) 不考虑进近管制区的飞行冲突。

5) 不考虑网络优化过程中的成本。

2.2 特性指标及约束

在区域航路网络优化过程中，需要设定若干特性指标以提升网络经济性、安全性和可行性，促进网络结构优化合理。

1) 运行费用

(14)

式中：T(N)为运行费用；dij为航段PiPj的长度。

2) 飞行冲突系数

(15)

式中：ci(i=1,2,…,m+n)为交叉航路点Pi的飞行冲突系数；αjik为航段PjPi和航段PkPi的夹角。

3) 非直线系数

(16)

Iij=dij/Gij

(17)

4) 航路角度改变量

(18)

式中：Δθij为航路Pi-Pj中相邻航段之间的角度改变量。

为了保证网络优化后满足实际需求，必须制定相应约束对航路走向、航路点分布做出限制。

1) “三区”约束

line(Pi,Pj)∩U(N)=∅

(19)

式中：line(Pi,Pj)为航段PiPj穿越的空域范围；U(N)为网络中的“三区”空域。

2) 容量约束

(20)

式中：λi、λij为裕度因子，表示由于管制员、流量增长等因素带来的影响。可避免航段或航路点陷入失效状态，保持网络的运行能力。

3) 优化范围约束

(21)

2.3 模型建立

区域航路网络的高效运转不仅取决于其结构的安全合理，还取决于飞行流量与网络容量的匹配关系，结合区域航路网络的特性指标及约束条件，建立以下多目标网络优化模型：

(22)

arccos(αjik/2)/(fji+fki)]+M

(23)

(24)

(25)

(26)

式(22)～式(25)分别表示区域航路网络的最小运行费用、最小飞行冲突系数、最小非直线系数和最小航路角度改变量。式(26)表示“三区”约束、容量约束和优化范围约束。式中：c为总飞行冲突系数，表征网络风险水平；M为罚函数，可将部分约束条件转化为目标函数的一部分，表示如下：

(27)

(28)

(29)

其中：σ为罚因子，可取σ=1 000[12]；m′为航路交叉点个数；Ω(PiPj)用来判断航段PiPj是否经过“三区”；Ψ(Pi)用来判断航路点Pi的容量是否符合条件。

3 区域航路网络结构优化模型求解

3.1 优化策略

区域航路网络的具体结构取决于移动航路点的布局[10]。在优化过程中，为满足实际情况，提高区域航路网络的性能，需制定以下优化策略。

1) 构建空域环境

利用栅格法将空域划分为若干个单位长度为l′的栅格以表示初始区域航路网络的基本结构。

2) 增加改航转向点

由于经济发展、历史遗留等客观原因，现有航路布局可能存在缺陷。当航路穿越“三区”时，可采用几何法确定新增改航转向点的初步位置，使飞行器沿“三区”边缘通过[13]。

3) 移动航路点

当交叉点或改航点位置不合理，造成局部节点失效或影响网络整体性能时，可利用NSGA-Ⅲ算法对其布局进行改进，保证区域航路网络正常运转。

4) 融合航路点

当航路交叉点分布密集且飞行流量较小时，空域安全度高，可将一定范围内的多个交叉点融合成单个交叉点，如图2所示，融合后有

图2 航路点融合、分解示意图Fig.2 Schematic diagram of waypoint integration and separation

(30)

5) 分解航路点

当航路交叉点流量较大，出现容流冲突，影响空域安全时，可将单个交叉点分解为多个交叉点，如图2所示，其关系如下：

(31)

3.2 优化步骤

区域航路网络优化需综合考虑网络外在结构的合理性和内在运行的稳定性。因此，必须全面系统地统筹优化策略，设计优化方法。根据区域航路网络的结构特征及运行规律，制定以下优化步骤(见图3)：

步骤1确定初始区域航路网络。

步骤2判断是否满足“三区”约束。

步骤3若不满足，则根据几何法增加改航转向点，连接转向点生成新航路并利用多目标网络优化模型求解航路点最优布局，执行步骤2。

步骤4若满足，则判断是否符合其他约束。

步骤5若不符合，则采取融合、分解航路点策略，进而利用多目标网络优化模型求解航路点最优布局，执行步骤2。

图3 区域航路网络优化步骤Fig.3 Optimization steps of regional air route network

步骤6若符合，取其中最优解集，网络优化完毕。

3.3 NSGA-Ⅲ算法

基于参考点的非支配排序遗传算法，即NSGA-Ⅲ是Kalyanmoy和Himanshu[14]提出的第三代多目标规划算法。该算法在继承NSGA-Ⅱ非支配排序的基础上，利用关联操作求解参考距离的方法代替了原来的拥挤度算子，提高了种群多样性。当目标函数较多时，其规划效果明显优于传统多目标规划方法。

1) 染色体构建

区域航路网络结构取决于移动航路点的分布情况，因此可采用实数编码方式构建染色体，如x11x12…xα1xα2…xk1xk2，k为移动航路点个数，2k为染色体长度，xα1、xα2分别为航路点Pα的横、纵坐标。

2) 操作算子

为了改进算法性能，提高运算效率，NSGA-Ⅲ算法在采取选择、变异、交叉3种传统操作算子的同时，引入删除算子，其表述如下：

① 选择算子。计算复合种群所有个体的目标函数值并根据结果进行快速非支配排序，当序号为N′的个体位于第l层时，采取关联操作计算第l层个体到其对应参考线的垂直距离，根据距离筛选符合条件的个体进入子代种群。

② 变异算子。采用基本变异方式，先确定变异个体及位置，进而由变异概率确定是否变异及变异后个体值。

③ 交叉算子。采取模拟二进制交叉算子，先确定交叉个体及位置，进而由交叉概率判断是否发生交叉。

④ 删除算子。对航路点坐标超出规划范围的染色体执行删除操作，重新生成染色体。

3) 算法步骤

NSGA-Ⅲ算法的基本步骤与传统遗传算法相似[15]，但在选择机制上有所创新，如图4所示。

其中，选择操作的具体步骤可描述如下：

步骤1非支配排序。将种群个体按照非支配规则分为m层，其中前l层个体记为Πl，数目为|Πl|，且|Πl|>N′。前l-1层个体记为Πl-1，数目为|Πl-1|，且|Πl-1|

步骤3归一化目标函数。计算理想点和极值点，转换目标函数，最终完成归一化操作。

步骤4关联操作。连接参考点和原点构成参考线，计算所有个体到与之最近的参考线的距离，将个体与对应参考点进行关联。

4 实例分析

以北京飞行情报区二连浩特P11、土木尔台P12和锡林浩特P19组成的区域航路网络为例进行结构优化仿真，令航空器的真航线角范围为[0,π]，栅格边长l′为23.58 km，其示意图如图5所示。其中，空心圆代表边境点和机场，实心圆代表航路交叉点，ZTi为“三区”，箭头指向表示流量运行方向。航段容量为40 架次/h，令λi=λij=0.75，图5所示的区域航路网络的相关数据见表1和表2[16-17]。

图5 初始区域航路网络Fig.5 Initial regional air route network

航路点汇聚航段交叉角航路点流量/(架次·h-1)航路点容量/(架次·h-1)P13∠P11P13P1211.420.96P14∠P13P14P1212.532.31P15∠P12P15P1412.938.03P16∠P15P16P1816.634.77P17∠P16P17P614.927.04P18∠P9P18P1414.926.92

表2 航段信息

由表1和表2可知，航路交叉点均符合容量约束，但航段P12P15和航段P17P19穿越“三区”，需要增加部分改航点，则经过初步规划后的区域航路网络如图6所示。

图6中，区域航路网络的总运行费用为5.424×103，飞行冲突系数为1.151，非直线系数为1.248，角度改变量为215.9°。根据区域航路网络优化步骤，分别采用NSGA-Ⅲ算法、NSGA-Ⅱ算法和粒子群算法对图6中移动航路点的布局进行优化。设置种群大小为100，进化代数为800，变异率为0.1，杂交率为0.15，可得如图7所示的优化结果。

图7中，(a)～(d)为利用NSGA-Ⅲ算法得到的区域航路网络；(e)、(f)为利用NSGA-Ⅱ算法和粒子群算法得到的区域航路网络，各网络具体特征值如表3所示。

表3中，⑦为初步规划后的网络，⑧为初始区域航路网络。通过对比可知，各优化网络的运行费用、非直线系数和角度改变量相比于初始网络均有所增加，但是这些网络的飞行冲突系数下降显著，同时实现了对障碍区域的规避，从而使得空域安全性得以提高。其中，网络③、④的运行费用、非直线系数和角度改变量较优，其改进效果较佳；网络①、②的各项指标较为均衡，改进效果良好；网络⑤、⑥的飞行冲突系数较小，但是其多项指标排名靠后，整体性能一般。为突出差异，对各优化网络指标与网络⑦指标的比值进行分析，如图8所示。

不难看出，优化网络②～④的综合性能优于优化网络⑤、⑥，其中优化网络④的改进效果最佳。相比于初步规划后的网络，优化网络④的运行费用减少了0.11%，飞行冲突系数减少了15.6%，非直线系数减少了0.16%，仅角度改变量略有增加；相比于初始网络，优化网络④符合全部约束条件，同时其飞行冲突系数减少了10.8%，运行费用与非直线系数略有增加，仅角度改变量变化较大。

图6 初步规划结果Fig.6 Preliminary planning result

图7 区域航路网络优化结果示意图Fig.7 Schematic of regional air route network optimization results

网络序号运行费用飞行冲突系数非直线系数角度改变量/(°)①5.409×1031.0921.244266.5②5.425×1030.9541.251268.1③5.413×1030.9721.245238.7④5.418×1030.9711.246216.5⑤5.437×1030.9691.257282.3⑥5.495×1030.8791.276330.2⑦5.424×1031.1511.248215.9⑧5.405×1031.0891.22763.34