基于改进NSGA-Ⅱ算法的航班战略冲突解脱研究

徐满，胡明华，张颖，江灏; XU Man; HU Minghua; ZHANG Ying; JIANG Hao

2025年6月14日 2:12 星期六

网刊加载中。。。

使用Chrome浏览器效果最佳，继续浏览，你可能不会看到最佳的展示效果，

确定继续浏览么?

复制成功，请在其他浏览器进行阅读

摘要

设计了一种改进的非支配排序遗传算法（Non‑dominated sorting genetic algorithm Ⅱ， NSGA⁃Ⅱ）解决战略阶段轨迹规划大规模优化问题。在经典的NSGA⁃Ⅱ的框架下，采用一种自适应交叉算子与自适应变异算子加快算法的收敛速度并提高解的质量，同时给出衡量Pareto解集优劣的评价指标。大规模四维航迹的引入不可避免地增加了问题的复杂性，本文提出了一种有效的战略冲突解脱模型，旨在最小化潜在的冲突数量和冲突解脱成本。采用中国航路网络繁忙时段1 472架航班进行实例验证，并所提算法与经典的NSGA⁃Ⅱ算法及MOEA/D进行对比。实验结果表明，改进的NSGA⁃Ⅱ算法具有更好的优化效果，能够有效地解决航空器之间的冲突并产生较小的航空器航迹调整量。

关键词

四维航迹; 战略冲突解脱; 自适应遗传算子; 改进NSGA⁃Ⅱ; 多目标优化

随着经济的不断发展，亚太地区将成为航空器客运量增长的主要动力，中国将在2022年成为全球第一大航空运输市场^［

1］。由于空中交通需求的不断增长，当前的空域会变得越来越拥挤，空中交通的拥堵情况越来越严重。

航空器的冲突解脱问题是一个大规模组合优化问题，且由于航空器之间冲突的存在使得航空器之间相互耦合^［

2］。有大量的文献研究航空器在战术及预战术阶段的冲突解脱问题，主要通过调整航空器的起飞时刻、调整航空器的飞行速度、修改航空器的水平航迹和分配高度层等方式解决相应的冲突^{［参考文献 3⁃4}3⁃4］。但是，采用这些方式的短期内的冲突解脱存在一定的缺点，即没有从全局角度考虑航空器的冲突解脱。由于航空器之间的相互关系，短期内的冲突解脱可能会产生“多米诺骨牌”效应，使得冲突解脱一直处于被动，危及空域安全。例如，采用地面等待策略解决冲突时，已经延误了的航空器仍然需要继续等待其他航空器以满足空域的容量要求^{［参考文献 5

百度学术}5］。而战略冲突解脱研究，旨在根据航空器的飞行计划在起飞前相当长一段时间内解决潜在的飞行冲突，是确保航空器安全运行的一项关键技术。目前，战略冲突解脱问题引起了大量的关注。

四维航迹的运用以及基于航迹运行概念的提出被认为是未来空中交通管理的运行基础，在此基础上战略冲突解脱问题得到了进一步的研究。四维航迹将航空器航迹定义为三维空间加上时间，随着运行技术的不断发展，四维航迹可以有效降低航空器运行过程中的不确定性。这就为在一个较长时间范围内解决航空器之间潜在冲突提供了技术支持。

已有大量的文献研究了航空器四维航迹战略冲突解脱问题。冲突解脱由于问题本身的复杂度较高，常采用启发式算法求解，并且在提高算法的求解效率上做了大量的研究。2019年，Dai等^［

6］提出了一种改进的模拟退火算法，将求解过程分成两个阶段：第一阶段用于减少冲突数量；第二阶段用于优化航空器的飞行时间。同时，在冲突解脱时设计了一个均匀高度层策略，引导航空器均匀分布至各个可用高度层，引入滑动时间窗来降低问题复杂度以提高求解效率。但是其将冲突数量与航空器航迹偏移量进行线性组合，解决的仍是单目标优化问题。除此之外，还有大量运用模拟退火算法及其改进算法的研究^{［参考文献 7⁃9}7⁃9］。合作协同进化算法^{［参考文献 10

百度学术}10］在求解航空器冲突解脱问题也拥有良好的性能，合作协同进化算法采用分而治之的思想，将一个大规模组合优化问题分解成若干个子问题，从而降低问题的维数，各个子问题采用特定的进化算法优化得到部分可行解，通过各个小组之间的合作进化获取全局可行解。在合作协同进化算法的框架下，采用遗传算法进行优化可以极大提高算法的优化效率，其研究的仍是单目标优化问题。

在实际运行过程中，空中交通管制员往往会在冲突数量和航空器航迹调整量之间寻求一个很好的平衡，将冲突解脱问题建模为多目标优化问题更加符合实际。Su等^［

11］于2017年采用多目标文化基因算法求解冲突解脱问题。算法采用经典非支配排序遗传算法（Non⁃dominated sorting genetic algorithm Ⅱ，NSGA⁃Ⅱ）进行全局搜索获取可行解，同时结合局部搜索算法加强对当前最优解的搜索，获得更优可行解，但是算法的复杂度较高。多目标合作协同进化算法^{［参考文献 12

百度学术}12］同样被应用于冲突解脱问题，在协同进化算法的框架下，采用基于分解的多目标进化算法（Multi⁃objective evolutionary algorithm based on decomposition，MOEA/D）^{［参考文献 13

百度学术}13］进行各个小组的内部优化。虽然采用了合作协同进化算法的框架，但是算法的求解效率较低。

针对以上问题，本文采用一种改进的NSGA⁃Ⅱ算法研究航空器冲突解脱中的多目标优化问题，通过对算法内部遗传算子的设计，提高算法优化效率，同时控制算法的复杂度。在解决航空器之间潜在冲突的同时考虑与航空器航迹调整量所引起的航迹调整成本。本文采用调整航空器起飞时刻和分配高度层的方式在战略阶段解决航空器之间的潜在冲突，冲突成本来自航班冲突解脱后的飞行计划与初始飞行计划之间的偏差。主要创新之处在于，本文为染色体中的基因赋予相应的局部适应度，设计了一种自适应交叉算子与变异算子，结合NSGA⁃Ⅱ框架进行全局优化。

1 问题建模

1.1　冲突探测模型

本文研究巡航状态下的航空器冲突解脱问题，因此假设航迹起终点为爬升和下降顶点。假设空域中有 $n$ 架航空器， $F = (f_{1}, f_{2}, f_{3}, \dots, f_{n})$ 按照航班计划沿着特定的航路飞行，航空器处于巡航状态，按照固定的高度层以恒定的速度运行。航空器的安全间隔在垂直方向上为 $N_{v}$ ，水平方向为 $N_{h}$ ，当航空器在空域中飞行时，它们的航迹相互影响。假设航班严格地按照计划航线飞行，那么潜在的冲突会发生在两条航路的交叉点附近，如图1所示。当两架航空器的保护区发生重叠时，则认为两架航空器存在潜在冲突，这种情况并不意味着两架航空器一定会冲突，但是在运行过程中是需要避免出现的。当航空器 $f_{i}$ 和航空器 $f_{j}$ 的水平距离小于 $N_{h}$ 且垂直距离小于 $N_{v}$ 时， ${‖P_{f_{i}} (t) - P_{f_{j}} (t)‖}_{2} < N_{h}, |L_{f_{i}} (t) - L_{f_{j}} (t)| < N_{v}$ ，则认为航空器 $f_{i}$ 和航空器 $f_{j}$ 发生冲突。式中： $P_{f_{i}} (t)$ 表示在 $t$ 时刻航班 $f_{i}$ 的水平位置， $L_{f_{i}} (t)$ 表示在 $t$ 时刻航班 $f_{i}$ 的飞行高度。冲突探测可以通过标称法探测^［

14］，不考虑不确定性因素的影响。

图1 航空器冲突图

Fig.1 Aircraft conflict

为了表示航空器之间的冲突关系，本文定义了一个矩阵 $C$ 来表示航空器之间是否有冲突，即

C = (\begin{matrix} C_{11} & \dots & C_{1 n} \\ ⋮ & ⋮ & ⋮ \\ C_{n 1} & \dots & C_{n n} \end{matrix})

（1）

式中

C_{i j} = \{\begin{matrix} 1 & 如果 F_{i} 和 F_{j} 有冲 突, i \neq j \\ 0 & 其他 \end{matrix}

i, j = 1,2, \dots, n

（2）

1.2　数学优化模型

航路网络范围内的战略冲突解脱问题可以描述为：给定一个航路网络范围，对于航路网络中的每一架航空器进行四维航迹规划，在较低的航空器冲突解脱成本下尽可能减少航空器之间的冲突数量。在进行冲突解脱的过程中，应满足空域容量限制、航空器机动性能限制等。航空器 $f$ 的航迹由一组四维航迹采样点组成，即有

\begin{array}{l} t r a j e c t o r y^{f} = \\ \{(S_{1}^{f}, l_{1}^{f}, t_{1}^{f}), \dots, (S_{m}^{f}, l_{m}^{f}, t_{m}^{f}), \dots, (S_{|m_{f}|}^{f}, l_{|m_{f}|}^{f}, t_{|m_{f}|}^{f})\} \end{array}

式中： $S_{m}^{f}$ 表示第 $m$ 个采样点水平位置， $l_{m}^{f}$ 表示第 $m$ 个采样点飞行高度， $t_{m}^{f}$ 为第 $m$ 个采样点过点时间。

1.2.1　决策变量

本文引入如下 $0 ⁃ 1$ 变量作为决策变量

x_{e, l, t}^{f} = \{\begin{matrix} 1 & \begin{array}{l} 航班 f 在时 间 t 内以 \\ 高度 层 l 经过 航段 e \end{array} \\ 0 & 其他 \end{matrix}

1.2.2　目标函数

为保证航空器运行的安全性，必须尽可能地减少航空器之间的潜在冲突，由式（1）中的矩阵 $C$ 可得航班之间的冲突关系。那么，航班 $f_{i}$ 的冲突数量可以由式（3）计算。

Φ_{i} = \sum_{j = 1}^{n} C_{i j}

（3）

每一个冲突都被一对冲突航班重复计算两次，所以航班间的冲突数量为

Φ_{t o t a l} = \sum_{i = 1}^{n} Φ_{i} / 2 = \sum_{i = 1}^{n} \sum_{j = 1}^{n} C_{i j} / 2

（4）

为了减少航空器间的冲突数量，目标1可定义为 $O b j_{1} = C S = m i n (\sum_{i = 1}^{n} \sum_{j = 1}^{n} C_{i j} / 2)$ 。其中CS表示航空器间的冲突数量。

在求解过程中，为了尽可能避免与其他航班之间的潜在冲突，可能对航班的初始航迹做出重大修改，从而导致大量偏移其初始航班计划。但是，这样的方式可能会产生额外的成本。因此，冲突解脱还应从经济角度进行评估，即航班应尽可能小地偏离初始计划，目标2重点关注最小化航迹调整成本（Total trajectory amendment cost，TTAC）。本文采用调整航空器起飞时刻以及高度层分配解决航空器之间的潜在冲突，TTAC由地面延误成本（ $C o s t_{G H}$ ）和高度层分配成本（ $C o s t_{F L}$ ）构成，那么目标2可由式（5）计算。

O b j_{2} = T T A C = λ^{G H} \times C o s t_{G H} + λ^{F L} \times C o s t_{F L}

（5）

式中： $λ_{G H}$ 为地面延误成本系数； $λ_{F L}$ 为高度层分配成本系数。由于地面延误成本与高度层分配成本单位不同，无法直接相加，因此需要进行归一化处理，即将每个航班的地面延误和高度调整量除以最大允许值。

（1）地面延误成本

航空器实际离场时间与初始飞行计划中离场时间之差为航空器的地面延误，即

C o s t_{G H} = \sum_{f \in F, l \in L, t \in T} (t - t_{o r i g}) (x_{o r i g, l, t}^{f} - x_{o r i g, l, t - 1}^{f})

（6）

式中： $F$ 为航班集合， $L$ 为航空器 $f$ 可用高度层集合， $T$ 为时隙集合， $t_{o r i g}$ 为航空器计划离场时间， $x_{o r i g}^{f}$ 表示航空器初始航段。

（2）高度层分配成本

航空器冲突解脱后为其分配的高度层与初始飞行计划中高度层之差为航空器的高度调整量，即

C o s t_{F L} = \sum_{f \in F, l \in L, t \in T} |l - l_{o r i g}| (x_{o r i g, l, t}^{f} - x_{o r i g, l, t - 1}^{f})

（7）

式中 $l_{o r i g}$ 为航空器计划飞行高度层。

1.2.3　约束条件

考虑到安全性、公平性和航空器的性能，轨迹中的每个元素应尽可能接近其计划值。模型的约束集如下所示

x_{e, l, t}^{f} - x_{e, l, t - 1}^{f} \geq 0

（8）

(t - t_{o r i g}) (x_{o r i g, l, t}^{f} - x_{o r i g, l, t - 1}^{f}) \leq T_{G H}^{f}

（9）

|(l - l_{o r i g}) (x_{o r i g, l, t}^{f} - x_{o r i g, l, t - 1}^{f})| \leq N_{F L}^{f}

（10）

$\forall f \in F, e \in E, l \in L, t \in T$ 均应满足上述约束， $E$ 是航段集合。其中，约束（8）保证航空器沿着单一可行航线飞行；约束（9）保证航空器的地面延误不超出最大允许延误， $T_{G H}^{f}$ 表示单个航空器最大允许延误；约束（10）保证航空器的飞行高度层只能在允许的高度层内， $N_{F L}^{f}$ 为最大高度调整量。

2 多目标优化算法设计

2.1　改进的NSGA⁃Ⅱ算法

多目标优化可以定义为寻找满足约束条件的决策变量向量，并同时优化多个目标函数的问题，目标函数之间往往是对立的。NSGA⁃Ⅱ根据目标函数特点，对可行解进行非支配排序，最终得到Pareto前沿。与经典的NSGA⁃Ⅱ算法及MOEA/D相比，本文采用的算法根据问题特点设计了自适应交叉算子与变异算子^［

15］加快进化过程。

2.1.1　初始化种群

本文采用调整航空器起飞时刻与高度层分配两种方式解决航空器间的潜在冲突，在生成初始种群时，根据当前航班计划中各个航班冲突数量，采用轮盘赌随机选择一条航迹，冲突数量越多，航迹被选中的概率越大。以概率形式随机修改起飞时刻与飞行高度层，独立运行N次，生成初始种群，具体过程如图2所示。

图2 种群初始化流程图

Fig.2 Flow chart of population initialization

2.1.2　选择

本文采用锦标赛选择法。从父代种群中随机选择两个父代，首先比较两个父代的非支配序，优先选择非支配序较低的父代个体；若父代的非支配序相同，则比较父代个体的拥挤距离，优先选择拥挤距离较大的父代个体。

2.1.3　交叉

本文采用的自适应交叉算子，在进行交叉操作时，对于选择的父代个体，比较父代个体相同位置基因的适应度，即在两个不同的航班计划中比较同一架航班在该计划下的冲突解脱成本。个体中每架航班的局部适应度由式（11）计算。

f i t n e s s_{i} = \frac{1 - \frac{T T A C_{i}}{T T A C_{m a x}}}{1 + C S_{i}}

（11）

式中： $C S_{i}$ 为航班 $i$ 的冲突数量， $T T A C_{i}$ 为航班 $i$ 的航迹调整成本， $T T A C_{m a x}$ 为冲突解脱允许的最大航迹调整成本。

在种群中选择两个亲本 $A$ 和 $B$ ，比较两个亲本相同位置的基因适应度。如果 $f i t n e s s_{i}^{A} < f i t n e s s_{i}^{B}$ ，那么生成的两个子代同时继承父代 $B$ 该位置的基因；如果 $f i t n e s s_{i}^{A} > f i t n e s s_{i}^{B}$ ，那么生成的两个子代同时继承父代 $A$ 该位置的基因；如果 $f i t n e s s_{i}^{A} = f i t n e s s_{i}^{B}$ ，那么由式（12）确定。

\begin{matrix} A_{C i} = f l o o r (k A_{i} + (1 - k) B_{i}) \\ B_{C i} = f l o o r (k B_{i} + (1 - k) A_{i}) \end{matrix}

（12）

式中：A_C和B_C分别为线性重组生成的两个子代， $f l o o r$ 表示向下取整， $k$ 为线形重组系数，交叉概率为 $P_{c}$ 。自适应交叉算子如图3所示。

图3 自适应交叉算子

Fig.3 Adaptive crossover operator

2.1.4　变异

较高的局部适应度意味着该航班的飞行计划产生较少的冲突和较低的飞行成本，所以当染色体某个位置基因适应度值小于 $ε$ 时，才发生变异，其发生变异的概率为 $P_{m}$ 。自适应变异算子如图4所示。

图4 自适应变异算子

Fig.4 Adaptive mutation operator

2.2　多目标优化解的评价

如何评价冲突解脱优化解集的优劣，在使航班尽可能小地偏离初始飞行计划的情况下得到较少冲突数量的航班计划是一个值得深究的问题。本文拟从Pareto最优解的收敛性和多样性两个方面进行评估，采用以下4个指标^［

16］来评估本文提出的算法。

2.2.1　覆盖率

覆盖率（C⁃Metric， CM）是衡量Pareto前沿的收敛性的指标，即

\begin{array}{l} C_{C M} (P F_{U}, P F_{V}) = \\ \frac{|v \in P F_{V}| \exists u \in P F_{U} : u d o m i n a t e s v\}|}{|P F_{V}|} \end{array}

（13）

式中PF_U、PF_V分别为两组Pareto最优解集。分子表示解集V中被U中至少一个解支配的解的数目，分母表示解集V中所有解的个数。若 $C_{C M} (P F_{U}, P F_{V}) = 1$ ，说明解集V完全被解集U支配，即解集V收敛性比解集U差。

2.2.2　空间分布

空间分布（Spacing， SP）是衡量Pareto前沿的广泛程度的指标，即

C_{S P} (P F) = \sqrt[]{\frac{\sum_{p = 1}^{|P F|} {(\bar{u} - u_{p})}^{2}}{| P F | - 1}}

（14）

式中： $u_{p}$ 表示各个解到其他解的最小欧氏距离； $\bar{u}$ 为均值。 $C_{S P} (P F)$ 值越小，说明空间分布越均匀。

2.2.3　超体积

超体积（Hyper volume， HV）是衡量Pareto前沿收敛性和多样性的综合指标，即

C_{H V} (P F) = δ (\sum_{p = 1}^{|P F|} V_{p})

（15）

式中： $δ$ 代表 $L e b e s g u e$ 测度，用来衡量体积； $V_{p}$ 表示第 $p$ 个点与参考点围成区域的超体积。超体积值越大，表示解集的效果越好。

2.2.4　平均理想距离

平均理想距离（Mean ideal distance， MID）是衡量Pareto前沿和理想点间距离的指标，即

C_{M I D} (P F) = \frac{\sum_{p = 1}^{|P F|} \sqrt[]{\sum_{t = 1}^{2} {(\frac{f_{p}^{t}}{m a x (f_{p}^{t}) - m i n (f_{p}^{t})})}^{2}}}{| P F |}

（16）

式中 $f_{p}^{t}$ 表示第p个非支配解的第t个目标值。本文研究双目标优化问题，因为求解最小化问题，所以理想点可设置为坐标原点。

3 仿真验证

3.1　运行场景

本文重点研究巡航阶段冲突解脱问题，数据采用2019年6月8日9：00至12：00中国航路网络中1 472架航班进行仿真验证，在MATLAB R2019a平台上运行，航班飞过的航路点如图5所示，涉及2 136个航路点和186个起降机场。本文对每条航迹采用等时间间隔采样生成相应的航迹采样点，采样间隔为15 s，利用墨卡托投影将航迹采样点从经纬度坐标转化为 $(x, y)$ 坐标。允许的单个航班最大延误 $T_{G H}^{f}$ 为60 min，航班离场时隙为1 min；单个航班飞行高度最大调整量 $N_{F L}^{f}$ 为1 200 m，遵循“东单西双”的原则，允许的飞行高度范围为8 900 m至11 600 m，以300 m的间隔划分高度层。采用网格法探测航空器之间的潜在冲突，网格在水平方向上大小为 $N_{h}$ ，在垂直方向上为 $N_{v}$ ，时间维度的网格大小与采样时间间隔相等。本文采用的改进NSGA⁃Ⅱ算法各项参数如表1所示，其中，种群规模与进化代数等参数均通过多次对比实验得到的最优结果确定。

图5 航路点图

Fig.5 Distribution of waypoints

表1 算法参数设置

Table 1 Parameter settings of algorithms

符号	参数名	数值
$λ_{G H}$	地面延误系数	0.5
$λ_{F L}$	高度层分配系数	0.5
$k$	线性重组系数	0.5
$ε$	期望适应度值	0.5
$P o p u l a t i o n$	种群规模	100
$G e n e r a t i o n$	进化代数	300
$P_{c}$	交叉概率	0.9
$P_{m}$	变异概率	0.1

3.2　结果分析

3.2.1　算法性能评价

本文将改进的NSGA⁃Ⅱ算法与经典NSGA⁃Ⅱ算法以及MOEA/D进行对比验证算法的有效性，同时利用多目标优化解的指标进行评价，具体结果如表2所示。启发式算法的优化效果具有随机性，因此，表2中的结果均基于15次独立重复试验得到。

表2 算法性能对比

Table 2 Performance comparison between algorithms

算法	指标
算法	CM	SP	HV	MID
经典NSGA⁃Ⅱ	0	0.832	0.022	1.634
MOEA/D	0	0.654	0.030	1.629
改进NSGA⁃Ⅱ	1	0.620	0.036	1.627

由表2可知，改进的NSGA⁃Ⅱ算法在各项性能上均优于经典的NSGA⁃Ⅱ算法及MOEA/D。覆盖率指标，改进的NSGA⁃Ⅱ算法得到的Pareto前沿完全支配另外两种算法。改进的NSGA⁃Ⅱ算法的Pareto最优解相对于经典算法及MOEA/D而言，解集更占有支配地位（CM），解集的分布更均匀（SP），解集的收敛性更好（HV），解得质量也更高（MID）。

算法的收敛性和多样性可由反转世代距离（Inverted generational distance， IGD）反映，本文将15次独立运行得到的Pareto最优解集 $P^{*}$ 作为参考集，计算参考点到最近的解的距离的平均值。IGD值越小，说明算法综合性越好，即

I G D (P, P^{*}) = \frac{\sum_{x \in P^{*}} \underset{y \in P}{m i n} d i s (x, y)}{|P^{*}|}

（17）

IGD值与进化代数的关系如图6所示，由于IGD值在前100代平稳，所以图中只选取了前100代的结果并做归一化处理，以使变化趋势更加明显。

图6 IGD变化趋势

Fig.6 IGD changing trend

由图6可知，在当前参数条件下，3种算法均可收敛。在3种算法中，采用了自适应遗传算子的改进NSGA⁃Ⅱ算法收敛速度最快。表3给出了3种算法在达到收敛代数和达到最大进化代数时的运行时间。对比MOEA/D算法、经典NSGA⁃Ⅱ算法与改进的NSGA⁃Ⅱ算法，本文所提算法在运算速度上提高了约8%。

表3 算法运行时间对比

Table 3 Running time comparison between algorithms

算法	时间
算法	收敛时间/s	总运行时间/s
经典NSGA⁃Ⅱ	2 756.7	4 024.2
MOEA/D	3 045.6	3 856.4
改进NSGA⁃Ⅱ	2 525.8	3 688.1

3.2.2　算法优化结果

图7是3种算法的优化结果对比图。由图可知，改进的NSGA⁃Ⅱ算法不仅在冲突解脱的效果上优于两种算法（Obj₁），而且产生的航迹偏移量（Obj₂）也更小。在最终的Pareto最优解集中，本文的改进算法目标1最优时可以将冲突数量减少至272，而经典的算法冲突数量则多达422，MOEA/D冲突数量最小也为324个，这反映了在引入改进了的交叉算子和变异算子后算法在冲突解脱方面的优异性能。目标2则反映出改进后的NSGA⁃Ⅱ算法，在解决冲突的时候产生的航迹调整量更少，使航空器在冲突解脱时产生更小的调整成本，符合航空公司的利益。

图7 Pareto前沿对比图

Fig.7 Comparison chart of Pareto front

4 结　　论

本文主要研究了冲突解脱中的多目标优化问题。针对问题的特点，本文将航空器冲突解脱建模为以冲突数量和航空器航迹调整量为目标的双目标优化问题。针对所求解的冲突解脱问题的特点，采用了一种改进的NSGA⁃Ⅱ算法，设计了自适应交叉算子与变异算子，旨在提高算法搜索最优解的效率。与经典的NSGA⁃Ⅱ算法以及MOEA/D相比，改进了的算法具有冲突解脱的有效性和求解的高效性，不仅可以同时兼顾航迹调整成本解决大量冲突，而且能更快收敛，有很强的参考价值。

下一步的工作主要集中对更复杂冲突解脱方式的建模以及进一步提高算法的效率上：冲突解脱方式除了考虑起飞时间和高度层优化分配，还可以考虑航迹的水平调整以及高度层的分航段优化；算法在求解大规模航班时缺乏时效性，可能需要大量的计算时间。采用更加多样化的冲突方式和将算法与局部搜索算法相结合以提高搜索效率预期将有助于提高算法的效率。

参考文献

NOLAN M S. Fundamentals of air traffic control［M］. 5th ed. Stanford， USA： Cengage Learning， 2011. [百度学术]

DURAND N， ALLIGNOL C， BARNIER N. A ground holding model for aircraft deconfliction［C］//Proceedings of Digital Avionics Systems Conference. ［S.l］： IEEE， 2014. [百度学术]

ARCHIBALD J K， HILL J C， JEPSEN N A， et al. A satisficing approach to aircraft conflict resolution［J］. IEEE Transactions on Systems Man & Cybernetics Part C， 2008， 38（4）： 510-521. [百度学术]

VIVONA R， KARR D， ROSCOE D. Pattern-based genetic algorithm for airborne conflict resolution［C］//Proceedings of AIAA Guidance， Navigation， and Control Conference and Exhibit. Keystone， Colorado， USA： AIAA， 2006. [百度学术]

DHIEF I， DOUGUI N H， DELAHAYE D， et al. Strategic planning of aircraft trajectories in North Atlantic oceanic airspace based on flocking behaviour［C］//Proceedings of Evolutionary Computation. ［S.l.］： IEEE， 2016. [百度学术]

DAI W， ZHANG J， DELAHAYE D， et al. A heuristic algorithm for aircraft 4D trajectory optimization based on bezier curve［C］//Proceedings of the 13th USA/Europe Air Traffic Management Research and Development Seminar. ［S.l.］： ATM， 2019. [百度学术]

CHAIMATANAN S， DELAHAYE D， MONGEAU M. A hybrid metaheuristic optimization algorithm for strategic planning of 4D aircraft trajectories at the continental scale［J］. IEEE Computational Intelligence Magazine， 2014， 9（4）： 46-61. [百度学术]

COURCHELLE V， DELAHAYE D， GONZÁLEZ-ARRIBAS D， et al. Simulated annealing for dtrategic traffic deconfliction by subliminal speed control under wind uncertainties［C］//Proceedings of the 7th SESAR Innovation Days. ［S.l.］： SESAR， 2017. [百度学术]

COURCHELLE V， SOLER M， GONZALEZ-ARRIBAS D， et al. A simulated annealing approach to 3D strategic aircraft deconfliction based on en-route speed changes under wind and temperature uncertainties［J］. Transportation Research， 2019， 103： 194-210. [百度学术]

GUAN X， ZHANG X， WEI J， et al. A strategic conflict avoidance approach based on cooperative coevolutionary with the dynamic grouping strategy［J］. International Journal of Systems Science， 2016， 47（9）： 1995-2008. [百度学术]

SU Y， CAI K Q. A multi-objective multi-memetic algorithm for network-wide conflict-free 4D flight trajectories planning［J］. Chinese Journal of Aeronautics， 2017， 30（3）： 1161-1173. [百度学术]

GUAN X， ZHANG X， LV R， et al. A large-scale multi-objective flights conflict avoidance approach supporting 4D trajectory operation［J］. Science China Information Sciences， 2017， 60（11）： 1-13. [百度学术]

ZHANG Q， LI H. MOEA/D： A multi-objective evolutionary algorithm based on decomposition［J］. IEEE Transactions on Evolutionary Computation， 2007， 11（6）： 712-731. [百度学术]

WANG Y， LI B， LAI X. Variance priority based cooperative co-evolution differential evolution for large scale global optimization［C］//Proceedings of 2009 IEEE Congress on Evolutionary Computation. Norway： IEEE， 2009. [百度学术]

DURAND N， ALLIOT J M， NOAILLES J. Automatic aircraft conflict resolution using genetic algorithms［C］//Proceedings of the 1996 ACM Symposium on Applied Computing. ［S.l.］： ACM， 1996： 289-298. [百度学术]

ZANDIEH M， KHATAMI A R， RAHMATI S H A. Flexible job shop scheduling under condition-based maintenance： Improved version of imperialist competitive algorithm［J］. Applied Soft Computing， 2017， 58： 449-464. [百度学术]

请使用 Firefox、Chrome、IE10、IE11、360极速模式、搜狗极速模式、QQ极速模式等浏览器，其他浏览器不建议使用!

基于改进NSGA⁃Ⅱ算法的航班战略冲突解脱研究 PDF

摘要

关键词

1 问题建模

1.1 冲突探测模型

1.2 数学优化模型

2 多目标优化算法设计

2.1 改进的NSGA⁃Ⅱ算法

2.2 多目标优化解的评价