航路网络关键节点优化与“三区”避让设计方法

许有臣，朱衍波（民航数据通信有限责任公司，北京 100091）

航路网络关键节点优化与“三区”避让设计方法

许有臣，朱衍波
（民航数据通信有限责任公司，北京 100091）

针对提高空中交通航路网络运行效率的问题，本文提出了航路网络关键节点优化与“三区”避让设计相结合的网络设计方法。首先，给出了航路网络关键节点优化与“三区”避让设计的模型，并利用遗传算法对航路网络设计问题进行了求解；应用分析表明：优化设计后的航路网络相比现行航路网络，在运行成本、非直线系数、连接度、可达性等性能指标上均有大幅改善，从而证明该方法的正确性。

空中交通管理；航路网络；拓扑结构；优化设计；遗传算法

中国现行的航路网络是随着社会、经济、政治、军事的发展而逐步形成的，其形成是一个缓慢而渐进的过程。在此过程中各种因素的不平衡发展和相互制约导致了航路网结构日趋偏离初始的最优化设计。由于以前我国民用航空运输不发达，这种偏离所造成的运输矛盾并不突出。但随着全国民航运输的快速增长与航路需求的多元化发展，全国航路网逐步暴露出其结构性缺陷[1]。目前弥补航路网缺陷采取的是进行局部、小范围的调整方式，无法从根本上解决现行有限的航路网与航空市场日益增长的需求这一矛盾。

本文运用遗传算法等定量化的分析方法，对航路网结构进行重新优化设计，在保障空中飞行安全的同时，合理分配交通流量，从总体上提高航路网的整体容量，实现空域结构的灵活使用，提高空域的整体运行效能，减少航班延误与飞行冲突，缓解航路拥堵现象，降低航空公司运行成本，从而为公共航空运输创造良好的运行环境，满足国民经济和航空事业持续、健康、快速发展的需要。

1 航路网规划关键技术

1.1 关键节点确定技术

1.1.1 问题描述

航路网是由基于航路点组成的网络，对航路网进行优化，实际就是确定航路点的过程。航路点可以分为2种：固定点和移动点。其中，移动点由于其位置不固定，其位置的合适与否将对网络整体性能构成决定性的影响，因此，这种点就成为本研究的关键点。为了方便论述，本节假定航路网中有两个移动节点T1、T2，其他点都是固定点，因此，航路网的优化问题也就可以归结为确定这两个移动点（关键点）的问题。对于此类问题的求解，可以考虑采用遗传算法来进行求解。

1.1.2 基本遗传算法简介

在过去30多年中，人们对模拟自然过程的算法产生了越来越浓厚的兴趣。而计算性能的不断提高不仅对这些算法本身的发展起到了巨大的推动作用，同时也使它们具有越来越重要的实用价值。进化算法是一类基于自然选择和遗传变异等生物演化机制的全局性概率搜索算法，包括遗传算法（GA）、进化规划（EP）、进化策略（ES）3种方法。进化计算是一类模拟生物进化过程与机制求解问题的自组织，自适应人工智能技术。这类技术的核心思想源于这样的基本认识：生物进化过程本身是一个自然的，并行发生的，稳健的优化过程。这一优化过程的目标是对环境的适应性，生物种群通过优胜劣汰及遗传变异来达到进化的目的。依达尔文的自然选择和孟德尔的遗传变异理论，生物进化是通过繁殖、变异、竞争和选择4种基本形式实现的。如何把待解决的问题理解为对某个目标函数的全局优化，则进化计算即是建立在模拟上述生物进化过程基础上的随机搜索优化技术。总的来说，进化计算通过不断迭代逐步改进当前解，直至最后搜索到最优解或者满意解。在进化算法中，采用了模拟生物系统的进化机制，从一组解（群体）出发，以类似自然选择和有性繁殖的方式，在继承原有优良基因的基础上，生成具有良好性能指标的下一代解的群体。

与其他启发式搜索方法（如爬山法，模拟退火法，Monte-Carlo方法）一样，进化算法在形式上也是一种迭代方法。它从选定的初始解出发，通过不断迭代逐步改进当前解，直至最后搜索到最优解或者满意解。在进化算法中，采用了模拟生物系统的进化机制，从一组解（群体）出发，以类似自然选择和有性繁殖的方式，在继承原有优良基因的基础上，生成具有良好性能指标的下一代解的群体。进化计算用于优化问题的一般过程如下：

第一步 随机给定一组初始解；

第二步 评价当前这组解的性能；

第三步 根据评价结果，从当前解中选择一定数量的解作为基因操作的对象；

第四步 对所选的解进行基因操作（杂交/交叉、突变/变异），得到一组新的解；

第五步 返回到第二步，对该组新的解进行评价；若当前解满足要求或进化过程达到一定次数，计算结束，否则转到第三步继续进行。

遗传算法属于进化算法的一种。可以把难解的问题看成是对潜在解空间的一种搜索，对“最好”解的搜索及优化过程。对于小空间，经典的穷举法已经足够，而对于大空间就可以考虑使用遗传算法等。

遗传算法借用了遗传学和生物学中的一些名词。一个群体中的个体称为串或染色体，一个染色体的个体称为单倍体。染色体的基本单位是基因，每个基因控制一个或几个遗传特征。某一特征的基因位于染色体的特定位置称为位（locus）。每个基因型（可看作单个染色体）代表一个问题在特定染色体意义下的潜在解，一个发生在染色体群上的进化对应一个潜在解空间的搜索。

给定一个优化任务，首先要将其转化为可解的整体优化问题。整体优化问题的定义为：给定非空集合S作为搜索空间，f为目标函数，任务（fx）是在S中找到至少一个使得目标函数最大化的点。函数值f*= （fx*）+∞称为一个整体极大值，当且仅当∀x∈S，（fx）≤（fx*）时，x*∈S成为一个整体极大解。要有参数空间以及评价函数，遗传算法以编码空间代替原始的参数空间，以适应度函数作为评价依据。针对不同的问题适应度有不同的含义，因此其适应函数也不同。在编码群体的基础上进行算子操作进行搜索。可以看出，遗传算法必须包含以下5个要素：对问题潜在解的遗传表达；产生潜在解初始群体的方法；扮演环境作用的、用“适应值”评价解的优劣的评价函数；改变后代构成的各种遗传算子；各种控制参数：群体规模、应用遗传算子的概率等。

1.1.3 基于单目标约束的关键节点优化模型

关键节点优化问题可以抽象为单目标约束优化问题，目标函数为航空运行成本，约束是关键节点的可搜索空间[2-7]。在既定机队型号和规模的前提下，航空运行成本可以间接表征为航路网络运行成本，亦即总的飞行里程数（飞行流量X航段长度）进行表示。模型具体表达式如下所示。

目标函数

其中fi、fj为单位时间上航路i、j上的飞机流量；m为与关键节点T1相关的航段数目；n为与关键节点T2相关的航段数目；Xi、Yi为与关键节点T1相关的航段端点位置横纵坐标；Xj、Yj为与关键节点T2相关的航段端点位置横纵坐标；XT1、YT1对应关键节点T1的位置横纵坐标（直角坐标系下）；XT2、YT2对应关键节点T2的位置坐标（直角坐标系下）；给定非空集合ST1、ST2作为关键点T1、T2的可搜索空间。

上述表达式（1）中，目标函数中前一部分表示与关键节点T1相关的航段（共m段）的运行成本总和，后一部分表述与关键节点T2相关的航段（共n段）的运行成本总合；两者加和最小化，即要求关键节点的选择位置，满足运行成本最小。约束条件包括两关键节点的位置取值范围。

1.1.4 基于基本GA算法的单目标优化模型求解

针对此单目标约束优化模型，求解方法有很多，本章采用的遗传算法具有隐式并行性和全局搜索性两大主要特点，作为强有力且应用广泛的随机搜索和优化方法，遗传算法可能是当今影响最广泛的进化计算方法之一。

遗传算法实现过程中的关键要素通常包括决策变量的编解码方法、适应值函数的选取、遗传算子等，本求解过程中，关键节点优化模型的GA算法实现的关键因素具体如下：

1）决策变量的编码，此处决策变量为T1，T2的位置信息，即（Xi，Yi，Xj，Xj），本文采用浮点型编码，即编码值代表决策变量的实际取值。

2）适应值函数是与目标函数相关的评价函数，此处目标函数始终为正，因此直接以目标函数为适应值函数。

3）遗传变异算子包括选择算子，交叉算子和变异算子。选择算子作用在于从当前代群体中选择出一些较优个体，将其复制至下一代群体中，本模型中选择为比例选择算子，个体被选中并遗传到下一代的概率与该个体的适应度大小成比例。交叉算子采用单点交叉算子；变异算子采用基本位变异算子。

4）进化终止条件采用进化代数为200代；种群个体数目取每代个体50个。

通过上述设置，处理，实现关键节点模型的GA算法求解，即可得到T1，T2对应优化方案下的决策变量值。

1.2“三区”避让技术

1.2.1 问题描述

在航路网络规划过程中，需要考虑一定的空域限制。这些空域限制是指“三区”，即禁飞区、限制区、危险区。本文所涉及的航路主干网络设计不考虑不同时间段的具体航路，只是从宏观、全局进行航路网络设计，因此针对“三区”，本文以禁飞区看待，即在“三区”内，飞机无法穿越、无法布设航路网络。“三区”避让优化设计问题的目标在于，使得所设计的航路满足飞机交通流量需求的同时保证航路主干网络最优，并且满足“三区”（禁飞区、限制区、危险区）限制要求，即航路不能穿过三区。

基于上述描述，“三区”避让问题转化为以下几个问题：空域的规划建模，即以一定方法描述“三区”以外的可用空域；“优化”航路主干网络的数学描述，即优化航路主干网络的数学建模，“优化”航路主干网络通常通过多个网络性能指标定义，因此该数学模型为多目标约束优化模型；优化航路主干网络模型的求解算法，该算法需要对多目标问题具有良好适应性与求解效率。针对以上问题，下文给出具体描述。

“三区”避让的目的是满足空域可用性要求，同时保证航路主干网络的性能。航路主干网优化模型的目标函数通过网络性能指标体现，因此目标函数与网络优化指标密不可分。

1）航路网络性能参数优化指标概念

衡量网络优化的指标包括：网络运行成本、网络连接度、网络冲突系数、网络非直线系数、网络可达性指标及航路利用率指标等。

2）航路主干网络的多目标优化模型

a.优化航路主干网络定义

优化网络的指标包括网络运行成本、冲突指标等，在诸多指标中，网络运行成本及网络运行安全性是最重要的衡量指标，此处以网络运行成本及网络运行安全性指标作为目标函数，量化航路主干优化网络；而其他性能参数指标可以作为航路网络布局方案的评价指标，以便与现状进行对比分析。

b.航路主干网络的多目标优化模型

一层航路主干网络用有向图G（N，L，C）表示，其中网络节点集合为N（xi）（包括固定城市节点和中间节点），L（li）为所有的有向边构成的集合，C表示航路网过渡网络各边通行能力的集合。变量定义为：fi为网络边/航段的流量；Li为网络边的长度；ci为网络边/航段的容量；Nc为网络中间节点集合；P={p1（x，y），p2（x，y），…，pk（x，y）}为网络节点位置坐标集合；V为航路飞机平均速度；X为雷达管制下侧向间隔标准；αij为边ij夹角；Pi为满足“三区”限制，在航路布设过程中产生的中间节点。

目标函数

约束条件

该多目标约束优化模型是以航路主干网络安全性与成本效益为目标函数、以“三区”限制表示为约束。目标函数中Pc为航路主干网络的潜在冲突系数，反映网络安全性指标；Q为航路主干网络运行成本指标，以飞行总里程表征；约束条件反映在航路路径选择必须在链接图规划建模中的“三区”链接线上，以满足三区避让要求。

1.2.2 基于NSGA2的多目标优化模型求解

多目标问题求解方法很多，针对上述多目标约束优化模型，采用NSGA2算法。这是一种基于Paroet最优概念的遗传算法，是众多的多目标优化遗传算法之中体现Golbderg思想最直接的方法[8-10]。求解流程如图1所示。

图1 NSGA2算法流程图Fig.1 NSGA2 flow chart

以上NSGA2算法过程为：针对“三区”避让优化模型的可行解集，并进行种群编码及初始化操作，对该代种群进行遗传变异产生子代种群，合并父代与子代种群，进行非支配排序，并根据拥挤度进行选择，对所选择的个体进行交叉变异操作，依次循环，直至终止条件，解码输出求得解集。针对本模型，实现的关键因素如下。

1）模型决策变量编码及种群初始化

在带有三区的航路主干网络规划空间建模基础上，对模型决策变量进行编码，模型的决策变量为需求城市对间的路径，起点至终点的路径为P0P1P2…PnPn+1，其中P0表示起点，Pn+1表示终点，要得到的最优路径是对Pi（i=1，2，…，n）的位置在三区链接线上进行调整，从而得到航路在规划空间上满足网络最优准则的布局网络[11]。

Pi点在三区顶点Pi1，Pi2所组成的链接线上移动，则其具体位置可通过Pi1，Pi2（分别对应三区的顶点位置信息）进行表达，表达如式（4）所示。对于每个城市需求对间的路径都如此处理，共同构成模型的决策变量，构成航路主干网络布局的一个可行解编码，然后通过随机数对种群进行初始化。

2）交叉变异算子

该模型对决策变量的编码是浮点型编码，即实值编码，因此交叉算子选择实值编码遗传算法的SBX （simulated binary crossover）交叉，变异算子选择多项式变异[12-13]。具体实现流程如下：

SBX：该交叉算子是仿真二进制交叉，为

式中：p1k，p2k表示选择的父代个体；c1k，c2k表示子代个体；βk为具有一定概率分布的随机数，其分布可以通过随机数u∈（0，1）按照下述公式产生

PM：多项式变异算子如下

式中：pk表示选择的父代个体，其父代基因值上下限分别为pku、pkl，ck表示子代个体，δk是由下述多项式分布公式产生的较小变量

式中：γk是（0，1）间随机数；ηm是变异分布概率。

3）进化终止条件

进化终止条件可根据需求及算法结果人为选择，此处选择进化次数为200次最为终止条件。

2 实际应用分析

基于以上方法，笔者所在项目组协助中国民航局空中交通管理局完成了面向2030年的航路网络规划方案的制定（根据2010年冬春季班机时刻表数据对骨干航路网络规划方案进行流量分配，城市对航线取规划网络中的最短路径）。为有效量化骨干航路网络规划方案的优劣性，建立了综合反映航路网络技术性能、经济效益及环境效益的航路网络规划方案评价指标体系。基于该指标体系的评估结果如表1所示。相比现行骨干航路网，规划航路网的网络连接度提高了20.4%，周运行成本下降了5.19%，非直线系数下降了5.32%，冲突系数下降了10.34%，航路利用率（繁忙程度）下降了6.7%，航班可达性提高了1.26%。这些指标说明规划航路网络的总体性能提升比较显著，符合总体目标要求。

表1 规划航路网络主要性能指标评估结果Tab.1 Assessment of designed air route network′s key performance metrics

3 结语

本文在对全国航路网规划的问题进行理论抽象的基础上，提出了“关键节点”优化设计与“三区”避让优化设计相结合的网络设计方法；构建了基于基本GA的关键节点优化模型和基于NSGA2的多目标优化模型，并给出模型求解方法。经过对规划航路网络的主要性能指标进行全面评估表明：网络连接度、冲突系数、非直线系数等均有较大幅度提升；本文所述的航路网络优化算法能够提高航路网络的整体利用效率，降低网络复杂度，提高空域利用的灵活性。

[1]民航数据公司.我国航路网络规划计划研究报告[R].北京:中国民航总局空管局，2007.

[2] SMITH M J.Existence uniqueness and stability of traffic equilibria[J]. Transportation Research，1979，13B（4）:295-303.

[3]ZHANG XIE，LIU BO，ZHANG JUN，et al.Optimization of Sequencing for Arrival Aircraft Based on Approach Routes[C].The 10th International IEEE Conference on Intelligent Transportation Systems，2007:3-5.

[4]SIDDIQUEE M W.MATHEMATICAL AIDS in Air Route Network Design[C].IEEE Conference on Decision and Control including the 12th Symposium on Adaptive Processes，1973:651-654.

[5] KARIM MEHADHEBI.A methodology for the Design of a Route Network[J].ATM Seminar 2000，2000:30-34.

[6]THOMAS RIVIÈRE.Redesign of the European Route Network for Sector-Less[C].23rd Digital Avionics Systems Conference，2004:32-35.

[7] RIVIÈRE T，BRISSET P.Shortest Path in Planar Graph and Air Route network[R].JFPC，2005:23-25.

[8]关志华.非支配排序遗传算法（NSGA）算子分析[J].管理工程学报，2004，12（1）:2-3.

[9]蒋腾旭.智能优化算法概述[J].人工智能及识别技术，2007:2-3.

[10]袁亚湘.非线性优化计算方法[M].北京：科学出版社，2008:26-30.

[11]WATTS D J，STROGATZ S H.Collective dynamics of‘small-world’networks[J].Nature，1998:440-442.

[12]周 明，孙树栋.遗传算法原理及应用[M].北京:国防工业出版社，2005:128-136.

[13]苟先太，金炜东.有约束优化中遗传算法的应用 [J].西南交通大学学报，1997，32（4）:15-23.

（责任编辑：黄 月）

Methodology of key network nodes optimization and re-stricted airspace avoiding

XU You-chen，ZHU Yan-bo
（Aviation Data Communication Corp oration，Beijing 100191，China）

To solve the problem of improving the air route network （ARN）efficiencies，this paper proposes a methodology of key network nodes optimization and the restricted airspace avoiding.Firstly，the model of key network nodes optimization and the re-stricted airspace avoiding is established.Then，genetic algorithm（GA）is used to solve this model.Finally，practical applications analysis shows that the optimized ARN is better than current ARN on the performance metrics such as the operating cost，the non linear indicator，the connectivity，the reachability，etc.It is proved that the optimization method is efficient and correct by the actual cases.

air traffic management；air route network；topological structure；optimization design；genetic algorithm（GA）

V355.1；X951

A

1674－5590（2013）01－0041－05

2012-05-04；

2012-08-20

国家科技支撑计划项目（2011BAH24B08）

许有臣（1975—），辽宁大连人，工程师，硕士，研究方向为空域管理与航行情报.