一种基于双层协同进化的航路网络拓扑设计方法

摘要

本发明提供了一种基于双层协同进化的航路网络拓扑设计方法，将航路网络规划问题归结为航路网络拓扑连接关系优化问题和航路汇聚点位置布局优化问题，建立多目标优化模型；本发明运用计算几何的方法得出满足约束条件的航路网络拓扑结构，再运用多目标优化算法对航路汇聚点位置布局进行优化，对经过航路汇聚点优化后得到的航路网络全拓扑结构，进行非支配排序，提取和输出航路网络全拓扑结构。本发明建立了航路网络拓扑优化模型，采用分层优化的思路，即“分别优化，总体进化”，逐渐趋向最优结果，可以快速地生成经济、安全的航路网络拓扑结构。

说明书

技术领域

本发明涉及一种基于双层协同进化的航路网络拓扑设计方法，属于空中交通管理领域。

背景技术

航路网络是实现空中交通的物理空间，其结构合理性制约着我国民航业及航空运输业的 发展。随着民航运输业的飞速发展，空中交通流量急剧增加，现有的航路网络结构已经无法 适应目前高强度、高密度的运输需求。而目前对航路网络的调整主要局限在局部改进，对全 局航路结构的提升非常有限。因此，有必要科学细致地对全国航路网络进行全局的规划与设 计，以满足航空运输发展的需求。

航路网络设计主要是根据不同机场间交通流分布特征、发展需求，设计合理有效的航路 网络拓扑结构，以保障空中交通运行安全、提高空中交通运行效率、减少航班延误和飞行冲 突，缓解航路拥堵，降低航空公司运行成本，满足航空运输业发展需求。

航路网络设计包括航路网络拓扑连接关系设计和航路汇聚点位置布局。航路汇聚点是指 航路网络中大于两条以上的航路由于飞行流量汇聚而形成的航路定位点；而航路网络拓扑连 接关系即航段，是连接航路汇聚点的通道。航路汇聚点的数量及其空间位置和航路网络拓扑 连接关系共同决定了航路网络的拓扑结构和特性，即，决定了航路网络的运行性能。

航路网络设计本质上是一个优化问题。目前，航路网络设计方法主要分为两种：航路汇 聚点位置优化，即优化航路汇聚点的位置而不改变航段的连接关系；全拓扑优化，即同时优 化航路汇聚点位置和航路网络拓扑连接关系。现有的航路汇聚点位置优化方法主要是法国航 空研究中心全局优化实验室提出的：初始给出一个规则(以经纬网络为脉络)航路网络，通 过逐步移动网络结点位置，利用Floyd-Warshall算法寻找城市对交通流的最短路径，同时利 用模拟退火算法对航路网络进行演进优化，直至找到网络性能较优的设计方案。现有的全拓 扑优化主要是法国航空研究中心提出的：基于初始的直连航线网络，经过网络结点合并和网 络结点移动逐步演化成优化的航路网络；通过计算机图形学的方法量化管制约束和航线经济 性指标，建立结点合并和结点移动的单目标无约束优化模型，利用梯度下降法求解优化模型， 实现了航路网络的全拓扑优化。

航路汇聚点位置与航段连接关系这两个变量既独立又相互联系，即改变盘航路汇聚点位 置需要重新选择合适航路网络拓扑连接关系，而改变航路网络拓扑连接关系对航路汇聚点位 置的选择也有影响。故，只对航路汇聚点位置进行优化无法取得高效、安全的航路网络，反 之亦然。但若同时对航路汇聚点和航路网络连接关系进行优化，变量搜索空间非常大，计算 复杂度非常高，因此也不是最优的航路网络拓扑设计方法。

发明内容

本发明的目的在于克服现有航路网络拓扑优化技术的缺点，提供了一种基于双层协同优 化的航路网络拓扑设计方法。本发明将航路网络设计问题归结为对航路网络拓扑连接关系和 航路汇聚点位置布局优化问题，建立一个更加实用的航路网络拓扑优化模型，并提供了一种 适于求解航路网络拓扑优化模型的双层协同进化方法DT-NSGA2，以可快速求得经济、安全 的航路网络拓扑结构。

本发明提供的基于双层协同进化的航路网络拓扑设计方法，为航路网络规划问题建立多 目标优化数学模型，具体是：

设航路网络的节点集合为V(N)，包括m个机场节点子集和n个汇聚 点子集V(N)＝A(N)∪U(N)；对任意节点$\overrightarrow{v_i}\in V\left(N\right),$有$\overrightarrow{v_i}=(x_i,y_i),$x_i和y_i为节点的位置坐标，当i≤m时，当m＜i≤m+n时，

目标函数包括两个：

(1)最小化航路网络的运行成本TAC，表示如下：

$\min \mathrm{TAC}=\min \underset{i=1}{\overset{m+n}{\Sigma }}\underset{j=1}{\overset{m+n}{\Sigma }}{f}_{\mathrm{ij}}·d_{\mathrm{ij}}$

其中，min表示最小化，f_ij表示从节点i到节点j航段上的流量值，d_ij表示两个相连节点 i和节点j之间的直线距离，当节点i到节点j不相连时d_ij＝∞；

(2)最小化航路汇聚点的飞行冲突系数TFCC，表示如下：

$\min \mathrm{TFCC}=\min \underset{i=m+1}{\overset{m+n}{\Sigma }}\underset{s=m+1}{\overset{m+n}{\Sigma }}\underset{t=s+1}{\overset{m+n}{\Sigma }}\frac{2f_{\mathrm{si}}{f}_{\mathrm{ti}}}{X}·\mathrm{ST}·{\cos }^{-1}\left(\frac{{\alpha }_{\mathrm{st}}^i}{2}\right)$

其中，X为飞机巡航时速，f_si表示从节点s飞入汇聚点i航段的流量值，f_ti表示从节点t 飞入汇聚点i航段的流量值；ST为雷达管制下的侧向间隔标准；为从节点s飞入汇聚点i 的航段和从节点t飞入汇聚点i的航段之间的夹角。

约束条件为：汇聚点的位置处于有限空间范围内；航路网络中任意两条航段之间不能有 交叉；航路网络中的航段不能跨越国境线。

通过对建立的多目标优化数学模型求解，获取优化后的汇聚点的位置。

本发明求解所建立的多目标优化数学模型，具体包括如下步骤：

步骤1，初始化网络数据，包括机场节点位置和航路汇聚点位置，设定迭代代数g的初 始值为0；

步骤2，设计航路网络拓扑连接关系优化模块，根据机场节点和航路汇聚点位置生成航 段，并进行航段越境和航段删除处理，得出满足约束条件的航路网络拓扑结构；通过步骤2， 根据M组航路汇聚点位置输出M组航路网络拓扑结构；

步骤3，设计航路汇聚点位置布局优化模块，利用多目标优化算法对航路汇聚点位置布 局进行优化；对M组航路网络拓扑结构分别通过步骤3优化，最终得到优化的M·PopSize组 航路网络拓扑结构；其中PopSize为多目标优化算法中设置的种群规模；

步骤4，设计了接口模块，对经过航路汇聚点优化后得到的M·PopSize组航路网络拓扑 结构，依据目标函数值进行非支配排序，并提取排序的前M组航路网络拓扑结构，输出航路 网络拓扑结构对应的M组航路汇聚点位置；

判断是否需要继续进行优化，若是，继续转步骤2执行，若否，输出步骤4最终得到的 M组航路网络拓扑结构。

本发明提供的航路网络拓扑设计方法，与现有技术相比的优点在于：

(1)将航路网络规划问题归结为航路网络拓扑连接关系优化问题和航路汇聚点位置布局 的优化问题，建立了航路网络拓扑优化模型，采用分层优化的思路，即“分别优化，总体进 化”，逐渐趋向最优结果；

(2)求解航路网络拓扑优化模型的双层协同进化方法DT-NSAG2中，包括航路网络拓扑 连接关系优化模块、航路汇聚点位置布局优化模块和接口模块；各模块分别采用计算几何 (Delaunay三角剖分)的方法和多目标优化算法(NSGA2)对上层航路网络拓扑连接关系优 化模块和下层航路汇聚点位置布局优化模块进行实例化，并设计合理的接口模块，提高了运 行效率；本发明可以快速地生成经济、安全的航路网络拓扑结构。

附图说明

图1为本发明实施例所用的航路网络示意图；

图2为本发明基于双层协同进化的航路网络拓扑设计方法实施例的流程图；

图3为本发明基于双层协同进化的航路网络拓扑设计方法实施例中上层优化模块操作流 程图；

图4为本发明基于双层协同进化的航路网络拓扑设计方法实施例中区域划分示意图；

图5为本发明基于双层协同进化的航路网络拓扑设计方法实施例中下层优化模块操作流 程图；

图6为本发明基于双层协同进化的航路网络拓扑设计方法实施例中接口模块关系示意图；

具体实施方式

下面将结合附图和实施例对本发明作进一步的详细说明。

图1为本发明实施例所用的航路网络示意图。航路网络的基本组成要素是航路网络节点 和航路网络拓扑连接关系(航段)。从图论的观点来看，航路网络就是由点和线组成的有向加 权图，其中点包括机场节点和航路汇聚点，线包括从机场与汇聚点之间或汇聚点与汇聚点之 间的航段，航段的方向取决于飞行流量方向，权值为飞行流量数值。其中，机场节点作为航 路网络中飞行流量的产生点和吸收点，空间位置固定不变；航路汇聚点是飞行流量的传输点， 既不产生流量也不吸收流量，数量指定，空间位置可设计。图1所示，三角形节点表示机场， 如节点a₁,a₂,a₃,a₄；圆形节点表示航路汇聚点，如节点u₁,u₂，而<a₁,u₁>,<a₂,u₁>,<a₁,u₂>,<a₂,u₂>, <a₃,u₁>,＜a₄,u₁＞,＜u₁,u₂＞则表示航段。

本发明中将存在航班飞行需求的每对机场节点的连接称之为一条航线，航线上的航班飞 行路径可由航路网络中的多条关联航路段连接得到，如航线＜a₁,a₂＞的航班飞行可经由 ＜a₁,u₂＞、＜u₂,a₂＞这2条航路段。因此，流量分配的实质是航段的选择。

实际的航路网络是三维网络，但本发明中研究的重点是高空航路，不考虑不同高度层间 的飞行爬升或下降，因此将航路网络将视为二维平面网络。

本发明中航路网络规划问题可描述为：给定m个机场节点的空间位置及其飞行流量需求， 指定航路汇聚点的个数n，求解各个航路汇聚点的空间位置及其连接关系，使得航路网络具 有运行成本最小和冲突最小等特性。

本发明将航路网络规划问题归结为航路网络拓扑连接关系优化问题和航路汇聚点位置布 局优化问题，建立多目标优化数学模型，目标函数为最小化航路网络的运行成本和最小化航 路汇聚点的飞行冲突系数，约束条件为航路汇聚点有限的可移动空间位置、航段之间不能交 叉且不能出现越境航段；输入参数集合包括机场节点位置信息、航路汇聚点初始位置信息、 机场对之间的流量等。

在本发明对航路网络拓扑建模中，首先对航路网络的节点进行定义，具体如下：

航路网络的节点集合V(N)，其中包括机场节点子集和汇聚点子集 V(N)＝A(N)∪U(N)；对任意$\overrightarrow{v_i}\in V\left(N\right),$有$\overrightarrow{v_i}=(x_i,y_i);$且当i≤m 时，当m＜i≤m+n时，则航路网络节点二维坐标组成的节点位置矩阵P(N) 为：

$P\left(N\right)={\left(\begin{array}{cccc}{x}_1& x_2& ...& x_{m+n}\\ y_1& y_2& ...& y_{m+n}\end{array}\right)}^T$

本发明中优化目标主要包括航路网络的运行成本和航路汇聚点的飞行冲突系数，即目标 函数为：

(1)最小化航路网络的运行成本(Total Airline Cost，以下简称TAC)

$\min \mathrm{TAC}=\min \underset{i=1}{\overset{m+n}{\Sigma }}\underset{j=1}{\overset{m+n}{\Sigma }}{f}_{\mathrm{ij}}·d_{\mathrm{ij}}---\left(1\right)$

其中，f_ij表示从节点i到节点j航段上的流量值，可通过Floyd-Warshall算法进行航路网 络流量分配后得到；d_ij表示两个相连节点i和节点j之间的直线距离，当节点i到节点j不相 连时d_ij＝∞。

(2)最小化航路汇聚点的飞行冲突系数(Total Flight Conflict Coefficient，以下简称 TFCC)

$\min \mathrm{TFCC}=\min \underset{i=m+1}{\overset{m+n}{\Sigma }}\underset{s=m+1}{\overset{m+n}{\Sigma }}\underset{t=s+1}{\overset{m+n}{\Sigma }}\frac{2f_{\mathrm{si}}{f}_{\mathrm{ti}}}{X}·\mathrm{ST}·{\cos }^{-1}\left(\frac{{\alpha }_{\mathrm{st}}^i}{2}\right)---\left(2\right)$

其中，f_si、f_ti分别表示从节点s飞入汇聚点i的航段和从节点t飞入汇聚点i的航段的流 量值(单位为架次/小时)；X为飞机巡航时速(单位为公里/小时)；ST为雷达管制下的侧向 间隔标准(单位为公里)；为从节点s飞入汇聚点i的航段和从节点t飞入汇聚点i的航段 间的夹角。

本发明中所建立的模型还需要满足以下约束条件：

(1)汇聚点的位置处于有限空间范围内，即：i∈{1,…,n}； 其中，和分别是是汇聚点i寻优位置的上、下界。

(2)航路网络中任意两条航段之间不能有交叉，即：i,j,k,t∈{1,…,n}且i≠j； 其中，和分别表示以节点i,j和k,t为顶点的两条航段。

(3)航路网络中的航段不能跨越国境线，即：i,j∈{1,…,n}且i≠j；其中， U表示地图全集，A表示中国国境集合，表示以节点i,j为顶点的航段。

第一类约束仅仅是对变量定义域的约束，因而只需将搜索限制在约束的范围内即可；第 二类约束条件的数目巨大，为了得到满足约束条件的解，本发明将在航路网络拓扑连接关系 优化模块中引入相应算法以降低运算量，提高算法效率，具体算法见上层优化模块；第三类 约束定义和判别都较为简单，但为了进一步提高该类约束的处理速度，本发明综合考虑地图 集合的概念与计算机的离散处理方式提出了一种近似的处理方式，极大的降低了运算量，具 体的处理方式在航路汇聚点位置布局优化模块中予以详细介绍。

图2为本发明基于双层协同进化的航路网络拓扑设计方法实施例的流程图，具体包括如 下步骤：

步骤101，初始化网络数据，包括机场节点位置、航路汇聚点位置数据，设定迭代代数 (Generation，以下简称g)g＝0；

步骤102，生成已知位置的机场节点和航路汇聚点的连接关系，即进行航路网络拓扑连 接关系优化。通过步骤102，根据一簇M组航路汇聚点位置坐标数据输出一簇M组航路网络 全拓扑结构数据。

本步骤设计了航路网络拓扑连接关系优化模块，即上层优化模块，该模块的功能可以根 据如图3实施例中所示的步骤来实现：

步骤201，根据机场节点和航路汇聚点坐标数据，采用Delaunay三角剖分算法生成航段 连接关系；

Delaunay三角剖分是计算几何中区域划分的一种重要方法，考虑到其与网络拓扑连接关 系优化的相似性，故本发明将Delaunay三角剖分引入到上层优化模块中来。

考虑到Delaunay三角剖分的定义与性质可知，采用Delaunay三角剖分算法生成的航段 连接关系中不会出现航段交叉，故利用Delaunay三角剖分算法可以成功的满足第二类约束条 件，避免了航段交叉约束处理。

步骤202，根据边境线数据，采用区域划分策略对生成的航段连接关系进行航段越境约 束处理；

由于边境线数据由上千个离散点构成，若逐一比较每条航段和边境点数据，则会带来非 常大的运算量，故本发明采用划分空域的方式来降低计算复杂度。

图4为本发明区域划分示意图。图中所示为一种简单的区域划分策略，将我国空域划分 成了20个规则区域，所有的航路节点都位于这些区域当中。

故本步骤中航段越境约束处理流程为：建立邻接矩阵S来存储各区域之间的连接关系， 若s_p,q＝1则表示区域p和区域q可以存在相连的航段，否则不能存在；标记每个航路汇聚点 所在区域的编号，以及航路段与区域相交点所在的区域编号；搜索所有的航段，根据邻接矩 阵删除越境航段。

本步骤中航段越境约束处理算法复杂度为O(n)，不仅可以很好地解决航段越境约束处理 问题，还极大地满足算法计算时间复杂度的要求。

步骤203，根据航路汇聚点初始位置和机场对之间的流量，应用Floyd-Warshall方法进行 流量分配；

步骤204，根据航路汇聚点冲突系数进行航路网络拓扑连接关系的优化；

通过对每个航路汇聚点的冲突系数和航段夹角的统计，过大的夹角很剧烈的放大冲突系 数，故要减少冲突系数，需要对其进一步的优化。

在上层优化模块中，存在航段交叉约束条件，而直接移动航路点或者增加航段都将不满 足约束条件，故本步骤采用最简单但也非常有效的策略，即删除航段来进行优化。若直接将 夹角过大的航段删除，势必会造成航路网络的连通性下降，甚至会产生孤立点，故在本步骤 中进行航段删除策略必遵循以下设定，即在降低航段冲突系数的情况下不对网络造成破坏性 影响。

本步骤中对航段进行删除具体包括以下步骤：计算每个航路汇聚点的冲突系数；选择冲 突系数大于设定阈值A的若干个航路汇聚点，并统计过所选择的这些航路汇聚点的所有航段 及其对应的夹角；排序所统计的这些航段被发现的次数；删除其中夹角大于设定阈值B的航 段对中出现次数最多的航段；返回航路网络全拓扑结构数据。其中阈值A和B根据用户需要 来设定，可根据多次试验比较效果来得到。

步骤103，采用改进的快速非支配排序的多目标遗传算法(NSGA2)分别优化M组航路 汇聚点位置，使得到的M·PopSize组航路网络全拓扑结构满足经济和安全性要求；

本步骤中航路汇聚点位置布局优化问题本质上是一个连续域寻优级的目标优化问题，具 体可以描述为：给定机场的空间位置和机场间的初始流量需求，指定航路汇聚点个数和航路 节点间的连接关系，求解各个航路汇聚点的空间位置，以满足航路网络运行成本最小、安全 性最佳的目标。

本步骤设计了航路汇聚点位置布局优化模块，即下层优化模块，利用多目标优化算法对 航路汇聚点位置布局进行优化，具体可通过如图5实施例所示的步骤实现：

步骤301，编码，航路汇聚点位置布局优化问题的决策变量是航路汇聚点的位置变量， 故将每个个体编码为一个包含所有航路汇聚点二维位置信息的向量(x₁,y₁,...x_n,y_n)；

步骤302，生成规模为PopSize的初始种群，导入航路网络拓扑结构数据，并将其作为种 群个体初始化，即一个个体代表一个航路网络；

对于一组航路汇聚点位置，将其内的x和y坐标在设定的浮动区间内随机采样，每采样 一次得到一个个体，共生成规模为PopSize的种群。

步骤303，基于Floyd-Warshall最短路径方法进行流量分配，对每个个体，根据公式(1) 和(2)计算航路网络的运行成本和航路汇聚点的飞行冲突系数值，并计算适应度值；

步骤304，通过交叉、变异等遗传算法操作产生并新一代个体；

步骤305，根据约束条件进行约束处理，判断新的个体是否满足约束条件(1)，即判断 航路汇聚点位置移动范围是否在寻优位置的上、下界之内，对于不满足约束条件的个体按照 如下策略进行约束处理：

$x_i=\left(\begin{array}{cc}{x}_{\min }^i,& x_i<x_{\min }^i\\ x_{\max }^i,& x_i>x_{\max }^i\end{array}\right),y_i=\left(\begin{array}{cc}{y}_{\min }^i,& {y_i<y}_{\min }^i\\ y_{\max }^i,& y_i>y_{\max }^i\end{array}\right)$

步骤306，生成新种群，计算子种群中每个个体的目标函数值和适应度值，并对子种群 与其父种群的并集中的所有个体，根据目标函数值进行非支配排序，最后选择出排在前 PopSize的个体构成新种群；

步骤307，判断是否满足终止条件，如果满足终止条件则输出种群中的非支配解和相应 的目标函数值，进入步骤104；否则令g＝g+1，并进入步骤303。终止条件一般设定为当前 达到了最大迭代次数，用户也可根据需要来设定。

步骤104，进行航路网络拓扑结构数据处理即接口模块的实例化。本步骤可以具体包括 如下步骤：对经过航路汇聚点优化后得到的M·PopSize组航路网络全拓扑结构数据进行非支 配排序；根据非支配排序的结果整合并提取适应度值大的前M组航路网络全拓扑结构，输出 航路网络全拓扑结构对应的M组航路汇聚点位置；判断是否满足终止条件，如果满足终止条 件则输出步骤104最终得到的航路网络全拓扑结构，结束循环；否则，继续进行优化，剔除 M组全拓扑结构数据中的航路网络拓扑连接关系信息，提取出航路汇聚点信息，并进入步骤 102。

本步骤中设计了接口模块，接口模块主要具有以下功能：数据格式标准化，对收到的数 据进行格式处理，使之满足接收模块的输入要求；数据整合和分发，管理上层优化模块和下 层优化模块间数据流；监控当前算法参数，判断算法是否结束；数据初始化和输出负责算法 的对外通信。以上功能在本步骤中都有具体体现，其中，数据整合与分发为接口模块的核心 功能。

综上可知，数据完成一个有效循环需经过如图6本发明接口模块关系示意图所示的步骤： 步骤102－接口1－存储空间1－接口3－步骤103－接口4－存储空间3－非支配排序－存储 空间1－数据整合提取－存储空间2－步骤102。步骤102中通过航路网络拓扑连接关系优化 模块提供M组航路汇聚点位置及对应的航路网络拓扑结构，并通过接口1将M组航路网络 拓扑结构存储在接口模块的存储空间1中。然后接口模块通过接口3将M组航路网络拓扑结 构发送给航路汇聚点位置布局优化模块。航路汇聚点位置布局优化模块进行优化，通过接口 4输出G组航路网络拓扑结构并存储在接口模块的存储空间3中，此处的G为M·PopSize。 计算G组航路网络拓扑结构的目标函数值并进行非支配排序，选出M组航路网络拓扑结构放 在存储空间1中，然后对所选取的航路网络拓扑结构进行整合提取处理，并剔除M组全拓扑 结构数据中的航路网络拓扑连接关系信息，提取出航路汇聚点信息，输入接口2，供上层模 块优化。

本实施例提供了一种基于双层协同进化的航路网络拓扑设计方法，将航路网络规划问题 归结为航路网络拓扑连接关系优化问题和航路汇聚点位置布局优化问题，建立了更加实用的 数学建模，提出了基于双层协同进化的航路网络全拓扑优化的模块化设计思路，并对每个模 块的接口和功能进行了规定，建立了新的问题求解DT-NSGA2算法。应用计算几何的方法对 上层模块进行了实例化，并设计了相应的约束处理方法和改进策略；应用多目标优化算法进 行了了下层模块的实例化；最后将上下层模块和接口模块组合成适用于求解航路网络全拓扑 优化的DT-NSGA2算法，可以快速地生成经济、安全的航路网络拓扑结构。

最后应说明的是：以上实施例仅用以说明本发明的技术方案，而非对其限制；尽管参照 前述实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前 述实施例所记载的技术方案进行修改，或者对其中部分技术特征进行等同替换；而这些修改 或者替换，并不使相应技术方案的本质脱离本发明实施例技术方案的精神和范围。