科学技术与工程

符号	符号意义
${x}_{k}^{(i,j)}$	航空器k是否从节点i滑行至节点j,若是则为1,否则为0
t_jk	航空器k到达节点j的时刻
t_ok	航空器k的开始滑行时刻
${t}_{jk}^{\mathrm{w}}$	航空器k在j点的等待时间
c_j	航空器k在路径上的等待时间所产生的CO₂之和
${z}_{{k}_{1},{k}_{2}}^{i}$	航空器k₁、k₂在i点的顺序决策变量,代表k₁先于k₂到达i点,若是则为1,否则为0
${y}_{{k}_{1},{k}_{2}}^{(i,j)}$	航空器k₁、k₂在(i,j)边的顺序决策变量,代表k₁先于k₂到达(i,j)边,若是则为1,否则为0
${t}_{k}^{\mathrm{d}\mathrm{e}\mathrm{l}\mathrm{a}\mathrm{y}}$	离场航空器k的在起点推出等待的时间

符号	符号意义
${x}_{k}^{(i,j)}$	航空器k是否从节点i滑行至节点j,若是则为1,否则为0
t_jk	航空器k到达节点j的时刻
t_ok	航空器k的开始滑行时刻
${t}_{jk}^{\mathrm{w}}$	航空器k在j点的等待时间
c_j	航空器k在路径上的等待时间所产生的CO₂之和
${z}_{{k}_{1},{k}_{2}}^{i}$	航空器k₁、k₂在i点的顺序决策变量,代表k₁先于k₂到达i点,若是则为1,否则为0
${y}_{{k}_{1},{k}_{2}}^{(i,j)}$	航空器k₁、k₂在(i,j)边的顺序决策变量,代表k₁先于k₂到达(i,j)边,若是则为1,否则为0
${t}_{k}^{\mathrm{d}\mathrm{e}\mathrm{l}\mathrm{a}\mathrm{y}}$	离场航空器k的在起点推出等待的时间

符号	符号意义
${t}_{\_\mathrm{w}}$	离场航空器允许在预计离场时间后进行推出的时间范围
t_s	航空器之间的安全时间间隔
k	航空器编号
$\mathrm{E}\mathrm{T}\mathrm{O}{\mathrm{P}}_{k}$	航空器k的预计进离场时间
t^(i,j)、c^(i,j)	航空器从i到达j所需的时间和CO₂排放量
v₁、v₂	航空器在直线上和弯道上的速度
n_k	航空器k的发动机数量
F_k	航空器k在不同滑行阶段时每台发动机的燃油流量
EI	公布的航空器的废气的排放指数^[18]
V	顶点集合
E	边集合
s_k	航空器k的起点
e_k	航空器k的终点
M	一个足够大的正整数
m	航空器总数量

符号	符号意义
${t}_{\_\mathrm{w}}$	离场航空器允许在预计离场时间后进行推出的时间范围
t_s	航空器之间的安全时间间隔
k	航空器编号
$\mathrm{E}\mathrm{T}\mathrm{O}{\mathrm{P}}_{k}$	航空器k的预计进离场时间
t^(i,j)、c^(i,j)	航空器从i到达j所需的时间和CO₂排放量
v₁、v₂	航空器在直线上和弯道上的速度
n_k	航空器k的发动机数量
F_k	航空器k在不同滑行阶段时每台发动机的燃油流量
EI	公布的航空器的废气的排放指数^[18]
V	顶点集合
E	边集合
s_k	航空器k的起点
e_k	航空器k的终点
M	一个足够大的正整数
m	航空器总数量

序号	航班号	停机位	降落时间/推出时间/s	进/离港
1	G54202	P1	0	进港
2	CA2866	P2	85	离港
3	H01209	P2	120	进港
4	EU1849	P2	250	离港
5	CA4070	P2	264	进港
6	G52893	P2	315	离港
7	HU7639	P3	360	进港
8	H01706	P1	405	离港
9	8L9525	P1	480	进港
10	PN6295	P1	635	离港
11	NS8077	P2	681	进港
12	MU9543	P2	778	离港
13	GS6477	P1	800	进港
14	GY7151	P1	945	离港

序号	航班号	停机位	降落时间/推出时间/s	进/离港
1	G54202	P1	0	进港
2	CA2866	P2	85	离港
3	H01209	P2	120	进港
4	EU1849	P2	250	离港
5	CA4070	P2	264	进港
6	G52893	P2	315	离港
7	HU7639	P3	360	进港
8	H01706	P1	405	离港
9	8L9525	P1	480	进港
10	PN6295	P1	635	离港
11	NS8077	P2	681	进港
12	MU9543	P2	778	离港
13	GS6477	P1	800	进港
14	GY7151	P1	945	离港

帕累托解	航空器总滑行时间/ s	CO₂ 排放量/ kg	直线滑行时间/ s	弯道滑行时间/ s	等待时间/ s	延误时间/ s
1	3 676.04	2 621.17	2 760.52	884.52	0	31
2	3 684.98	2 614.82	2 774.38	839.16	40.44	31
3	3 709.57	2 610.79	2 781.40	816.48	58.69	53

帕累托解	航空器总滑行时间/ s	CO₂ 排放量/ kg	直线滑行时间/ s	弯道滑行时间/ s	等待时间/ s	延误时间/ s
1	3 676.04	2 621.17	2 760.52	884.52	0	31
2	3 684.98	2 614.82	2 774.38	839.16	40.44	31
3	3 709.57	2 610.79	2 781.40	816.48	58.69	53

不同对比参数	NSGA-II算法	基于Gurobi算法的混合整数规划
解的质量gap/%	1.083	0
求解时间/s	102.2	2 060.9

不同对比参数	NSGA-II算法	基于Gurobi算法的混合整数规划
解的质量gap/%	1.083	0
求解时间/s	102.2	2 060.9

实验组	航空器数量/ 架	NSGA-II算法求解时间/ s	NSGA-II算法解的质量 gap/%	基于Gurobi算法的混合整数规划求解时间/s
1	2	3.8	0	3.0
2	4	11.2	0.001	8.1
3	6	32.6	0.241	15.7
4	8	43.3	0.425	28.4
5	10	61.4	0.611	74.3
6	12	87.7	0.835	120.2
7	14	102.2	1.083	2 060.9
8	16	123.9	1.252	3 318.4
9	18	151.6	1.410	14 633.8

实验组	航空器数量/ 架	NSGA-II算法求解时间/ s	NSGA-II算法解的质量 gap/%	基于Gurobi算法的混合整数规划求解时间/s
1	2	3.8	0	3.0
2	4	11.2	0.001	8.1
3	6	32.6	0.241	15.7
4	8	43.3	0.425	28.4
5	10	61.4	0.611	74.3
6	12	87.7	0.835	120.2
7	14	102.2	1.083	2 060.9
8	16	123.9	1.252	3 318.4
9	18	151.6	1.410	14 633.8

基于改进NSGA-II算法的航空器滑行路径多目标优化

PDF下载

钟庆伟 ¹ , 唐浩铭 ¹ , 庾映雪 ¹^,^* , 张永祥 ² , 姚俊杰 ¹ , 潘明思语 ¹

科学技术与工程 | 论文·航空、航天 2025,25(20): 8737-8744

收起

科学技术与工程 | 论文·航空、航天 2025, 25(20): 8737-8744

基于改进NSGA-II算法的航空器滑行路径多目标优化

全屏

钟庆伟¹, 唐浩铭¹, 庾映雪¹^,^*, 张永祥², 姚俊杰¹, 潘明思语¹

作者信息

¹ 中国民用航空飞行学院空中交通管理学院, 广汉 618307

² 西南交通大学交通运输与物流学院, 成都 610031

钟庆伟(1991—),男,汉族,四川什邡人,博士,副教授。研究方向:交通运输组织优化。E-mail:qingweizhong@cafuc.edu.cn。

通讯作者:

^* 庾映雪(1997—),女,汉族,广东东莞人,硕士研究生。研究方向:交通运输组织优化。E-mail:yuyingxue@cafuc.edu.cn。

Multi-objective Optimization of Aircraft Taxiing Paths Based on Improved NSGA-II Algorithm

Qing-wei ZHONG¹, Hao-ming TANG¹, Ying-xue YU¹^,^*, Yong-xiang ZHANG², Jun-jie YAO¹, Ming-si-yu PAN¹

Affiliations

¹ Department of Air Traffic Management, Civil Aviation Flight University of China, Guanghan 618307, China

² Department of Transportation and Logistics, Southwest Jiaotong University, Chengdu 610031, China

出版时间: 2025-07-18 doi: 10.12404/j.issn.1671-1815.2405546

文章导航

摘要

收起

随着全球航空业的快速发展,机场场面航空器滑行管理难度增加,如何在保障安全和提升效率的同时减少对环境的影响变得尤为重要。针对该问题,以预防滑行路径冲突为基础约束条件,以滑行时间最短和二氧化碳(carbon dioxide,CO₂)排放量最小为优化目标建立混合整数线性优化模型,并设计非支配排序遗传算法 II(non-dominated sorting genetic algorithm II, NSGA-II)进行动态求解。最后,以中国某枢纽机场为算例背景,借助Python语言实现NSGA-II算法,并与商业优化求解器Gurobi进行对比。计算结果表明:航空器数量为14架次时,与优化前相比,总滑行时间减少约17.46%,CO₂排放量降低约18.35%;NSGA-II算法得到的可行解与Gurobi所求最优解间的距离为1.083%,但NSGA-II的求解时间相对减少95.0%。同时,通过多个算例测试表明,NSGA-II算法在处理大规模多目标路径优化问题时具有显著优势。所提出的优化方案可有效提升机场场面运营效率并减少CO₂排放。

关键词

滑行路径优化 / 多目标优化 / 非支配排序遗传算法(NSGA-II) / 数学求解器 / 动态优化 / CO₂排放

Abstract

收起

With the rapid development of the global aviation industry, airport ground operations management is increasingly challenging. Ensuring safety, improving efficiency, and reducing environmental impacts constitute critical tasks. To address this, a mixed-integer linear programming model incorporating taxiway conflict prevention was developed. This model aimed to minimize taxi time and CO₂ emissions through dynamic optimization with the non-dominated sorting genetic algorithm II (NSGA-II). Implementation was conducted in Python for a major Chinese hub airport, with results compared against the commercial optimizer Gurobi. Computational findings reveal a 17.46% reduction in total taxi time and an 18.35% decrease in CO₂ emissions across 14 aircraft. The NSGA-II solution is found to be within 1.083% of Gurobi’s optimal solution, while a 95.0% faster computation time is achieved. The capability of NSGA-II in handling large-scale multi-objective taxi path optimization problems is demonstrated. Operational efficiency is enhanced, and CO₂ emissions are significantly reduced by the proposed approach.

Key words

taxi path optimization / multi-objective optimization / non-dominated sorting genetic algorithm II(NSGA-II) / math solvers / dynamic optimization / CO₂ emissions

引用本文

钟庆伟, 唐浩铭, 庾映雪, 张永祥, 姚俊杰, 潘明思语. 基于改进NSGA-II算法的航空器滑行路径多目标优化. 科学技术与工程, 2025 , 25 (20) : 8737 -8744 . DOI: 10.12404/j.issn.1671-1815.2405546

Qing-wei ZHONG, Hao-ming TANG, Ying-xue YU, Yong-xiang ZHANG, Jun-jie YAO, Ming-si-yu PAN. Multi-objective Optimization of Aircraft Taxiing Paths Based on Improved NSGA-II Algorithm[J]. Science Technology and Engineering, 2025 , 25 (20) : 8737 -8744 . DOI: 10.12404/j.issn.1671-1815.2405546

正文

收起

在航空科技和全球化的双重推动下,民航业成为中国现代化进程的领头羊。随着全球脱碳进程的加速,同时遵循着“航班再加密,往来更便利”政策导向,使得各机场不仅要应对航班密度增加,还要面临航班效率与低碳发展的双重挑战。在此背景下,如何在低碳目标下优化航空器的滑行路径将是疏通机场场面交通的关键^[1-3]。

中外众多学者致力于通过各类优化方法来解决这一问题。潘卫军等^[4]提出基于冲突热点的地面滑行路径优化模型。Evertse等^[5]通过定时滑行路线减少排放。姜雨等^[6]采用双层规划方法,提升滑行调度效率并降低成本。何庶等^[7]利用改进的遗传算法优化侧向跑道机场的滑行路径。Sun等^[8]提出联合优化框架,使用了非支配排序遗传算法 II(non-dominated sorting genetic algorithm II, NSGA-II)和Dijkstra算法解决了最短滑行时间和登机口匹配的优化问题,优化了滑行效率并杜绝了冲突。Wang等^[9]提出一种离线规划和在线跟踪结合的框架实现协同滑行规划和跟踪。张兆宁等^[10]提出基于路径检测的动态滑行路径优化模型并采用蚁群算法求解。孙若飞等^[11]结合遗传算法和Yen算法优化滑行速度,减少尾气排放。Benmessaoud等^[12]通过动态计算最短路径的方法成功改善通勤时间,减少燃料消耗、污染物排放。Qiang等^[13]利用混合整数线性规划解决如何优化电动出租车到电池更换站的路径选择问题,从而提高电动出租车的运营效益和减少环境影响。吴闯洋等^[14]采用多目标涟漪扩散算法优化进离港航班的滑行路径。程小慷等^[15]使用改进的粒子群算法,基于成本和排放量最小化策略优化滑行路径。Zhong等^[16]采用群体划分策略和动态椭圆保护区模型优化低空无人机路径,减少航空器燃油消耗,提升避障效率。Chen等^[17]采用双层模型对航空器路径进行优化,避免了冲突,减少了航空器排放量和燃油消耗。2015—2024年,全球学者采用多种优化算法来提升机场地面滑行路径的效率。这些研究针对增强时间效率、减少滑行距离、避免冲突、降低油耗等关键需求,通过发展创新的优化模型和算法,显著提高了机场运行效率并对滑行成本进行控制。

上述研究提供了路径优化的参考,但仍存在以下不足:①大多数研究的优化目标考虑减小滑行时间^[4,13,17],减少延误时间^[7-8,11],降低燃油消耗^[12,16-17]等,但针对减少航空器滑行时产生的二氧化碳(carbon dioxide,CO₂)^[5,11]的研究仍然较少;②目前研究主要面向静态环境^[11,14]下的路径优化问题;③许多研究针对多目标问题时,通常采用两个目标的线性权重组合^[16]进行求解,但这种方法往往忽略了目标之间的复杂关系和相互影响。鉴于此,考虑建立目标为CO₂排放量和总滑行时间的多目标优化模型,并设计NSGA-II算法获取帕累托解集。同时引入动态优化,允许实时更新和调整路径以应对突发冲突。

1 问题描述

收起

在航空器滑行过程中,存在3种主要的冲突情形:超越冲突[图1(a)]、对头冲突[图1(b)]以及交叉冲突[图1(c)]。一旦冲突发生,至少需要对其中一架航空器执行冲突管理措施。具体策略包括在节点处等待或更改滑行路径以避免冲突。在航空器冲突解脱的研究中,传统上采用先到先服务(first come first service, FCFS)原则来处理航空器间的冲突。然而,当航空器数量呈幂级数增加,如从10架增至15架甚至更多,航空器的实时路径规划复杂度显著提高。因此,亟须开发更为高效的方法来优化航空器的滑行路径,同时考虑到缩短滑行时间和减少CO₂排放的需求,以确保航空安全。

2 数学模型

收起

2.1 问题假设

假设1:航空器在直线和弯道滑行时以不同的速度匀速滑行。

假设2:将机场停机位转化为3个停机区。

假设3:不考虑天气等其他因素的影响。

2.2 航空器路径多目标优化模型

2.2.1 符号说明

对航空器路径多目标优化模型所使用决策变量和其余参数的符号进行定义和说明分别如表1和表2所示。

2.2.2 目标函数

本文模型目标函数共由2个部分组成:以航空器的最短总滑行时间以及最少CO₂排放作为目标函数。目标函数为

(1)

$\begin{array}{l}\mathrm{m}\mathrm{i}\mathrm{n}{Z}_{1}=\stackrel{m}{\sum _{k=1}}\stackrel{V}{\sum _{i=1}}\stackrel{V}{\sum _{j=1}}{x}_{k}^{(i,j)}{t}^{(i,j)}+\stackrel{m}{\sum _{k=1}}\stackrel{V}{\sum _{j=1}}{{t}^{\mathrm{w}}}_{jk}+\\ \stackrel{m}{\sum _{k=1}}{t}_{k}^{\mathrm{d}\mathrm{e}\mathrm{l}\mathrm{a}\mathrm{y}}\end{array}$

(2)

$\mathrm{m}\mathrm{i}\mathrm{n}{Z}_{2}=\stackrel{m}{\sum _{k=1}}\stackrel{V}{\sum _{i=1}}\stackrel{V}{\sum _{j=1}}{x}_{k}^{(i,j)}{c}^{(i,j)}+{c}_{j}$

式中:$\stackrel{m}{\sum _{k=1}}\stackrel{V}{\sum _{i=1}}\stackrel{V}{\sum _{j=1}}{x}_{k}^{(i,j)}{t}^{(i,j)}$为航空器k所经过路径所需的时间之和;$\stackrel{m}{\sum _{k=1}}\stackrel{V}{\sum _{j=1}}{{t}^{\mathrm{w}}}_{jk}$为航空器k在路径上的等待时间之和;$\stackrel{m}{\sum _{k=1}}{t}_{k}^{\mathrm{d}\mathrm{e}\mathrm{l}\mathrm{a}\mathrm{y}}$为航空器k在起点推出等待时间之和;$\stackrel{m}{\sum _{k=1}}\stackrel{V}{\sum _{i=1}}\stackrel{V}{\sum _{j=1}}{x}_{k}^{(i,j)}{c}^{(i,j)}$为航空器k所经过路径所产生的CO₂之和,其中滑行时间和等待时间的CO₂产生量可分别通过式(3)、式(4)计算。

(3)

${c}^{(i,j)}={n}_{k}{F}_{k}\mathrm{E}\mathrm{I}{t}^{(i,j)}$

(4)

${c}_{j}=\stackrel{V}{\sum _{j=1}}\stackrel{m}{\sum _{k=1}}{n}_{k}{F}_{k}\mathrm{E}\mathrm{I}{{t}^{\mathrm{w}}}_{jk}$

2.2.3 约束条件

航空器路径多目标优化模型需要满足下面一系列约束。

(1)流平衡约束。为确保生成航空器从起点到终点的路径,对于每架航空器k除起点终点外的每个节点i,满足:

(5)

$\sum _{(i,j)\in E}{x}_{k}^{(i,j)}-\sum _{(j,i)\in E}{x}_{k}^{(j,i)}=0$

对于每架航空器k,起点s_k满足:

(6)

$\left\{\begin{array}{l}\sum _{({s}_{k},j)\in E}{x}_{k}^{({s}_{k},j)}=1\\ \sum _{(j,{s}_{k})\in E}{x}_{k}^{(j,{s}_{k})}=0\end{array}\right.$

对于每架航空器k,终点e_k满足:

(7)

$\left\{\begin{array}{l}\sum _{({e}_{k},j)\in E}{x}_{k}^{({e}_{k},j)}=0\\ \sum _{(j,{e}_{k})\in E}{x}_{k}^{(j,{e}_{k})}=1\end{array}\right.$

(2)出发时间约束。对于每架航空器k,其出发时间t_ok的设定依据航空器是进场还是离场航空器而定。

对于进场航空器k,其预定到达时间$\mathrm{E}\mathrm{T}\mathrm{O}{\mathrm{P}}_{k}$将直接作为其出发时间,即

(8)

${t}_{\mathrm{o}k}=\mathrm{E}\mathrm{T}\mathrm{O}{\mathrm{P}}_{k}$

对于离场航空器k,其出发时间被设定在一个长度为${t}_{\_\mathrm{w}}$的时间窗口内,即

(9)

$\left\{\begin{array}{l}\mathrm{E}\mathrm{T}\mathrm{O}{\mathrm{P}}_{k}\le {t}_{\mathrm{o}k}\\ {t}_{\mathrm{o}k}\le \mathrm{E}\mathrm{T}\mathrm{O}{\mathrm{P}}_{k}+{t}_{\_\mathrm{w}}\end{array}\right.$

对于航空器推出等待时间,被设定在一个长度为${t}_{\_\mathrm{w}}$的时间窗口内:

(10)

$\left\{\begin{array}{l}{t}_{k}^{\mathrm{d}\mathrm{e}\mathrm{l}\mathrm{a}\mathrm{y}}=={t}_{\mathrm{o}k}-\mathrm{E}\mathrm{T}\mathrm{O}{\mathrm{P}}_{k}\\ {t}_{\_\mathrm{w}}\ge {t}_{k}^{\mathrm{d}\mathrm{e}\mathrm{l}\mathrm{a}\mathrm{y}}\ge 0\end{array}\right.$

(3)时间连续性约束。为确保航空器的路径到达点时间的连续性,对于每条边(i,j)和航空器k做出约束:

(11)

$\left\{\begin{array}{l}{t}_{jk}\le {t}_{ik}+{t}^{(i,j)}+{w}_{jk}+M[1-{x}_{k}^{(i,j)}]\\ {t}_{jk}\ge {t}_{ik}+{t}^{(i,j)}+{w}_{jk}-M[1-{x}_{k}^{(i,j)}]\end{array}\right.$

(4)交叉冲突、追尾冲突避免约束。为防止航空器之间发生交叉冲突以及追尾冲突,现对于每个节点i以及每对航空器${k}_{1},{k}_{2}({k}_{1}\ne {k}_{2})$做出约束:

(12)

$\left\{\begin{array}{l}{t}_{i{k}_{1}}+{t}_{\mathrm{s}}\le {t}_{i{k}_{2}}+M(1-{z}_{{k}_{1},{k}_{2}}^{i})\\ {t}_{i{k}_{2}}+{t}_{\mathrm{s}}\le {t}_{i{k}_{1}}+M{z}_{{k}_{1},{k}_{2}}^{i}\end{array}\right.$

(5)对头冲突避免约束。为防止航空器之间发生对头冲突,现对于每条边(i,j)以及每对航空器${k}_{1}、{k}_{2}({k}_{1}\ne {k}_{2})$做出约束:

(13)

$\left\{\begin{array}{l}{t}_{i{k}_{1}}+{t}^{(i,j)}\le {t}_{j{k}_{2}}+M[1-{y}_{{k}_{1},{k}_{2}}^{(i,j)}]+M[1-\\ {x}_{k1}^{(i,j)}]+M[1-{x}_{k2}^{(j,i)}]\\ {t}_{j{k}_{2}}+{t}^{(i,j)}\le {t}_{i{k}_{1}}+M{y}_{k1,k2}^{(i,j)}+M[1-{x}_{k2}^{(j,i)}]+\\ M[1-{x}_{k1}^{(i,j)}]\end{array}\right.$

综上,式(1)~式(13)构成了航空器路径多目标优化模型生成混合整数线性规划模型。

3 算法设计

收起

3.1 算法原理

航空器路径优化问题涉及大量变量和约束,属于NP困难问题。伴随着问题规模的增加,求解时间呈指数增加,传统的精确算法难以在合理时间内得到有效结果。相比之下,启发式算法具备强大的全局搜索能力,能够快速提供近似解。因此,本研究采用启发式算法来解决航空器路径规划问题。

对于多目标优化问题,各优化目标之间往往相互矛盾,难以同时达到所有目标的最优。故而,通常不存在唯一的全局最优解,而是存在一组最优解的集合。为同时考虑多目标,选择NSGA-II算法对模型进行优化。

3.2 算法流程

所设计的NSGA-II算法多目标优化的流程如下。

步骤1 染色体编码。采用混合编码策略,每个染色体代表一种可行的航空器滑行方案。每个基因由两部分构成:一是航空器从起点到终点的路径;二是路径上每个节点的预计到达时间,该时间基于离场时间及节点间的时间权重计算得出。染色体基因编码示例如图2所示。

步骤2 初始化种群。设定合适的种群规模,利用回溯算法随机生成初始滑行路径,并随机生成航空器的初始离场时间,每个个体对应一种规划方案。

步骤3 适应度评估。在NSGA-II算法中,个体适应度包含非支配层数和个体的拥挤度。利用NSGA-II算法的快速非支配排序方法对种群进行分层,确定种群个体的非支配层数,使优良个体更加接近帕累托前沿。拥挤度以目标空间上的每一点与同层相邻两点之间的局部拥挤距离来计算,可以保持个体的多样性。

步骤4 选择。采用精英选择策略,优先选择较高前沿层中的个体,同一前沿层中优先选择拥挤度较低的个体。

步骤5 交叉。采用多点交叉策略,即随机选择两个不同的交叉点,并交换两点间的基因片段,以生成两个新的后代。交叉操作基于对应序号的染色体部分进行交换,因此交叉后不会出现基因重复的问题,交叉部分为路径部分,具体示例如图3所示,假设交叉点为2和5。

步骤6 变异。对每个染色体进行变异判断,若变异,则该染色体的每个基因随机选择一个点生成至终点的变异路径。变异操作基于Dijkstra算法,并引入随机因子,该因子通过权重乘以一定比例和一个随机数得出。该操作不一定直接选出最小权重路径,但能逐步接近最小权重路径。

步骤7 优化离场时间。探寻更优的离场时间组合。此步骤能避免过早陷入局部最优解,并丰富解的多样性。

步骤8 选择下一代种群。合并交叉前和变异后的种群,并根据选择操作得到下一代种群。

步骤9 重复迭代。重复执行步骤4~步骤8,直到满足终止条件。

步骤10 算法结束。满足终止条件,输出帕累托解集。

NSGA-Ⅱ算法具体流程如图4所示。

同时,使用Gurobi线性求解器对该模型进行精确求解,得到可靠下界,计算结果用于后续实验。

4 算例分析

收起

4.1 参数设定

以4E级民用国际机场,中国西南地区重要的航空枢纽贵阳龙洞堡机场为研究背景,依据发布的机场图绘制该机场网络模型如图5所示。可以看出,由162个节点,237条边组成,将龙洞堡机场的停机位简化为3个停机区。

设定航空器在不同滑行情况下的推力等级:直线滑行时为7%,转弯滑行时为8%,停止等待时为3%^[5,19]。选用龙洞堡机场常见机型波音737的代表发动机CFM56-7B26型号进行实例仿真。利用国际民用航空组织(International Civil Aviation Organization, ICAO)排放数据库中的参数^[20],并通过线性插值计算不同推力等级情况下的燃油流量。NSGA-II的参数设置如下:种群规模为60,最大迭代次数为50,交叉百分比0.7,变异百分比取0.2。

随机选用2024年5月某日龙洞堡机场真实航班进行仿真实验。在实际情况下,由于管制员控制停机位和推出时间,各航班间一般不会发生冲突,因此将原30 min内的航班计划合理编排以模拟机场繁忙的情况。考虑滑行时最大直线滑行速度为50 km/h,最大转弯速度为15 km/h^[21],出于安全考虑,将航空器滑行抽象为匀速滑行,故将直线速度和弯道速度分别设为40 km/h和10 km/h,航班信息如表3所示。所有算例均在配置为Windows 10~64 bits,Intel Core i9-13900HX 4.70 GHz CPU, 16 GB RAM的个人笔记本电脑上运行求解。

4.2 计算结果分析

4.2.1 多目标优化以及帕累托解集分析

帕累托前沿是多目标优化问题中,描述无法再改进一个目标而不损害其他目标的最优解集合。对仿真算例内序号为1~14的航班进行仿真优化,可得帕累托前沿如图6所示。将帕累托前沿上的3个非支配解作表分析,分析结果如表4、图7所示。两个目标的优化过程分析结果如图8、图9所示。图10展示不同帕累托解中某航空器的可视化滑行路径。

如表4、图7所示,不同的目标会产生不同的滑行决策,其中CO₂排放更低的帕累托解通常在弯道的滑行时间会更少,等待时间也会相对较少。而滑行时间更少的帕累托解往往航班的延误时间更短。结合上述分析,所得帕累托解集可以为管制员提供一定的决策辅助:航空器在滑行的过程中,若管制员趋向于降低总滑行时间,并考虑航空器的延误时间更少,则需要选择帕累托解1,比帕累托解3省时33.53 s;若管制员倾向于减少航空器滑行CO₂排放量,同时也考虑航空器在滑行时的等待时间更少,则应该选择帕累托解3,比帕累托解1少排放10.38 kg CO₂。如果管制员需要在两个目标之间找到平衡解,可以选择帕累托解2。如图8所示,航空器总滑行时间从4 453.45 s优化到3 676.04 s,总共优化了17.46%。如图9所示,航空器的CO₂排放量从3 198.36 kg减少到2 610.79 kg,整体减少了18.35%。可见NSGA-II算法在多目标优化方面的有效性。

4.2.2 算法对比分析

为了验证不同算法的优劣性,对Gurobi线性求解和NSGA-II算法在仿真中的时间和解的质量进行了列表分析。利用Gurobi线性求解对两个目标分别进行计算以获得可靠的下界,并基于此下界计算NSGA-II算法的启发解与下界之间的距离,得到两解间的“gap”值,并且数据为相同背景下的10次仿真的结果所取平均值。结果如表5所示,启发解与下界间的距离为1.083%。NSGA-II的求解时间比Gurobi快95.0%。

对不同架次数航空器进行仿真实验,发现不同算法在仿真时间和求解质量上存在差异,结果见4.2.3节。

4.2.3 基于不同航空器数量的算法对比分析

通过对2~18架次航空器的仿真实验,对比分析两种算法的求解时间和求解质量。分析结果如表6所示。图11展示了两种算法的求解时间随航空器数量增加的变化趋势。

如表6所示,当航空器架次较少时,精确算法和启发式算法的求解时间相差不大。例如,航空器数量为2架时,NSGA-II算法求解时间为3.8 s,基于Gurobi算法的混合整数规划求解时间为3.0 s,两者仅相差0.8 s。然而在航空器架次数增加的过程中,虽然两个算法的求解时间都在增加,但增加速度不同。当航空器架次增加到14架时,NSGA-II算法求解时间为102.2 s,基于Gurobi算法的混合整数规划的求解时间为2 060.9 s,两者相差1 958.7 s。当航空器架次数为18架时,基于Gurobi算法的混合整数规划的求解时间为14 633.8 s,而NSGA-II算法的求解时间仅为151.6 s,两个算法的求解时间差异为14 210.6 s。可见随着航空器架次的增加,两个算法求解时间的增长不成比例。

在大规模的优化问题中,涉及大量整数变量,求解可能会出现内存不足的情况,解决方法为通过求解松弛问题(即放松整数约束的模型)以获得一个初始下界a。对所研究问题进行大规模测试,当航空器数量增至24架时,使用Gurobi算法求解将出现内存不足的问题,无法获得最优解,使用NSGA-II算法求解则能够得到启发解,求解时间为243.5 s,与初始下界a之间的距离为3.7%。这一结果验证了NSGA-II算法在处理大规模问题时的有效性。

5 结论

收起

在全球航空业迅速发展的过程中,机场场面航空器滑行管理面临更多挑战。考虑航空器滑行路径多目标优化问题,即最小化滑行中产生的CO₂排放量和滑行时间。此外,还比较了商业求解器和设计的启发式算法,即通过不同航空器数量的仿真算例,同时使用两种算法进行求解,并对比二者解的质量和求解时间。得出以下结论。

(1)航空器滑行路径多目标优化模型能够生成既提高滑行时间效率又减少环境影响的路径方案。

(2)NSGA-II算法能快速求得可行解,但其解的质量略低于最优解。相比之下,商业求解器Gurobi算法虽然能够保证获得模型的最优解,但求解时间较长,且解的多样性不足,难以满足实际需求。

(3)当航空器数量逐渐增加,NSGA-II的求解效率在合理范围内变化。Gurobi算法在航空器数量较少(12架次以内)时求解效率也在合理范围内变化,但当航空器数量达到14~18架时,求解效率急剧下降。当航空器数量增加到24架时,使用Gurobi算法无法获得最优解。因此,当航空器数量较少时,可以根据需求选择不同的算法,但当航空器数量较多时,NSGA-II算法是更优选择。

未来的研究可以重点改进NSGA-II算法的性能以应对更大规模复杂冲突场景下的滑行路径规划问题。此外,研究的方法还可以扩展应用于低空空域管理、智能交通系统、机器人路径规划等领域。

基金

收起

国家自然科学基金(72201268)
国家自然科学基金(U2333209)
中央高校基本科研业务费专项(24CAFUC03048)
大学生创新创业训练计划(202410624020)
民航飞行技术与飞行安全重点实验室开放基金(F2024KF07C)
中国民用航空飞行学院研究生科研创新基金项目(25CAFUC10032)

参考文献

收起

文献

收起

参考文献引证文献

排序方式：

[1]

胡荣, 王德芸, 冯慧琳, 等. 碳达峰视角下的机场航空器碳排放预测[J]. 交通运输系统工程与信息, 2021, 21(6): 257-263.

Rong

, Wang

Deyun

, Feng

Huilin

, et al. Forecasting aircraft carbon emissions at airports from a peak carbon perspective[J]. Journal of Transportation Systems Engineering and Information Technology, 2021, 21(6): 257-263.

[2]

张晓濛, 贾志勇, 陈渤, 等. “双碳”背景下可持续航空煤油的研究现状与展望[J]. 现代化工, 2024, 44(5): 1-6.

Zhang

Xiaomeng

, Jia

Zhiyong

, Chen

, et al. Research status and prospects of sustainable aviation kerosene under the “dual carbon” background[J]. Modern Chemical Industry, 2024, 44(5): 1-6.

[3]

袁志逸, 李振宇, 康利平, 等. 中国交通部门低碳排放措施和路径研究综述[J]. 气候变化研究进展, 2021, 17(1): 27-35.

Yuan

Zhiyi

, Li

Zhenyu

, Kang

Liping

, et al. Review of low-carbon emission measures and pathways in the Chinese transportation sector[J]. Climate Change Research Progress, 2021, 17(1): 27-35.

[4]

潘卫军, 王玄, 夏正洪, 等. 航空器热点区域的滑行避让方法[J]. 计算机工程与设计, 2015, 36(12): 3324-3327, 3384.

Pan

Weijun

, Wang

Xuan

, Xia

Zhenghong

, et al. Taxiing avoidance method for hot zones of aircraft[J]. Computer Engineering and Design, 2015, 36(12): 3324-3327, 3384.

[5]

Evertse

, Visser

H G

. Real-time airport surface movement planning: minimizing aircraft emissions[J]. Transportation Research Part C: Emerging Technologies, 2017, 79: 224-241.

[6]

姜雨, 王欢, 樊卫国, 等. 场面航空器滑行时空协同优化模型[J]. 交通运输工程学报, 2019, 19(1): 127-135.

Jiang

, Wang

Huan

, Fan

Weiguo

, et al. Spatio-temporal cooperative optimization model for aircraft taxiing on the ground[J]. Journal of Traffic and Transportation Engineering, 2019, 19(1): 127-135.

[7]

何庶, 卢朝阳, 王颜颜, 等. 侧向跑道机场滑行路径优化[J]. 科学技术与工程, 2021, 21(20): 8695-8701.

Shu

, Lu

Chaoyang

, Wang

Yanyan

, et al. Taxiway path optimization at airports with lateral runways[J]. Science Technology and Engineering, 2021, 21(20): 8695-8701.

[8]

Sun

, Li

, Niu

, et al. Research on joint ground movement optimization based on bilevel programming[J]. Aerospace, 2022, 9(9): 502.

[9]

Wang

, Peng

, Liu

, et al. Optimal control based coordinated taxiing path planning and tracking for multiple carrier aircraft on flight deck[J]. Defence Technology, 2022, 18(2): 238-248.

[10]

张兆宁, 孙英然. 基于路径检测的航空器动态滑行路径优化模型[J]. 计算机仿真, 2022, 39(11): 53-59.

Zhang

Zhaoning

, Sun

Yingran

. Dynamic taxiway path optimization model based on path detection[J]. Computer Simulation, 2022, 39(11): 53-59.

[11]

孙若飞, 李杰, 万莉莉, 等. 基于速度分配的航空器绿色滑行优化[J]. 科学技术与工程, 2022, 22(16): 6752-6758.

Sun

Ruofei

, Li

Jie

, Wan

Lili

, et al. Aircraft green taxiing optimization based on speed allocation[J]. Science Technology and Engineering, 2022, 22(16): 6752-6758.

[12]

Benmessaoud

, Cherrat

, Ezziyyani

. Real-time self-adaptive traffic management system for optimal vehicular navigation in modern cities[J]. Computers, 2023, 12(4): DOI: 10.3390/computers12040080.

[13]

Qiang

, Hu

, Tang

, et al. Research on optimization strategy of battery swapping for electric taxis[J]. Energies, 2023, 16(5): 2296-2307.

[14]

吴闯洋, 胡小兵, 马霁. 基于涟漪扩散算法的航空器滑行路径优化[J]. 计算机仿真, 2023, 40(12): 87-92.

Chuangyang

, Hu

Xiaobin

, Ma

. Taxiway path optimization for aircraft based on ripple spreading algorithm[J]. Computer Simulation, 2023, 40(12): 87-92.

[15]

程小慷, 曹誉丹, 崔宇婕. 基于改进PSO的离港航班绿色滑行路径优化[J]. 航空计算技术, 2023, 53(3): 25-29.

Cheng

Xiaokang

, Cao

Yudan

, Cui

Yujie

. Green taxiway path optimization for departing flights based on improved PSO[J]. Aeronautical Computing Technique, 2023, 53(3): 25-29.

[16]

Zhong

, Yu

, Zhang

, et al. Swarm division-based aircraft velocity obstacle optimization considering low-carbon emissions[J]. Sustainability, 2024, 16(5): 1855.

[17]

Chen

, Quan

, Yu

. Aircraft taxi path optimization considering environmental impacts based on a bilevelspatial-temporal optimization model[J]. Energies, 2024, 17(11): 2692.

[18]

黄梦圆, 胡荣, 张军峰, 等. 基于快速存取记录器数据的飞机废气排放计算与分析[J]. 科学技术与工程, 2020, 20(32): 13502-13507.

Huang

Mengyuan

, Hu

Rong

, Zhang

Junfeng

, et al. Calculation and analysis of aircraft emissions based on quick access recorder data[J]. Science Technology and Engineering, 2020, 20(32): 13502-13507.

[19]

Chen

, Weiszer

, Stewart

. Optimal speed profile generation for airport ground movement with consideration of emissions[C]// IEEE 18th International Conference on Intelligent Transportation Systems. Canary Islands: IEEE, 2015: 1797-1802.

[20]

International Civil Aviation Organization. ICAO aircraft engine emissionsdatabank: Doc-9646[R]. Montreal: International Civil Aviation Organization, 2015.

[21]

Xia

, Pan

, Kang

, et al. Research on the terminal aircraft separations based on the history surveillance data[J]. Applied Mechanics and Materials, 2014, 496-500: 2899-2903.

2025年第25卷第20期

PDF下载

引用本文

BibTeX

文章信息

doi: 10.12404/j.issn.1671-1815.2405546

接收时间：2024-07-23
首发时间：2026-05-13
出版时间：2025-07-18

补充材料

相关文章

文章信息

作者

出版历史

收稿日期：2024-07-23
修回日期：2025-04-12

基金

国家自然科学基金(72201268)

国家自然科学基金(U2333209)

中央高校基本科研业务费专项(24CAFUC03048)

大学生创新创业训练计划(202410624020)

民航飞行技术与飞行安全重点实验室开放基金(F2024KF07C)

中国民用航空飞行学院研究生科研创新基金项目(25CAFUC10032)

作者信息

¹ 中国民用航空飞行学院空中交通管理学院, 广汉 618307

² 西南交通大学交通运输与物流学院, 成都 610031

通讯作者:

^* 庾映雪(1997—),女,汉族,广东东莞人,硕士研究生。研究方向:交通运输组织优化。E-mail:yuyingxue@cafuc.edu.cn。

参考文献

分享链接

https://castjournals.cast.org.cn/joweb/kxjsygc/CN/10.12404/j.issn.1671-1815.2405546

分享至

全文二维码

扫描看全文

引用本文

BibTeX

本文的引用情况

2种不同金属材料的力学参数

科 Family	属数 Number of genus	种数 Number of species	占总种数比例 Percentage of total species (%)	属 Genus	种数 Number of species	占总种数比例 Percentage of total species (%)
鹅膏菌科Amanitaceae	2	11	5.26	鹅膏菌属 Amanita	10	4.78
小菇科 Mycenaceae	2	12	5.74	丝盖伞属 Inocybe	5	2.39
多孔菌科 Polyporaceae	8	14	6.70	蜡蘑属 Laccaria	5	2.39
红菇科 Russulaceae	3	23	11.00	小皮伞属 Marasmius	6	2.87
				小菇属 Mycena	11	5.26
				光柄菇属 Pluteus	5	2.39
				红菇属 Russula	17	8.13
				栓菌属 Trametes	5	2.39

关闭全屏

BibTeX
EndNote
RefWorks
TxT

符号	符号意义
${x}_{k}^{(i,j)}$	航空器k是否从节点i滑行至节点j,若是则为1,否则为0
t_jk	航空器k到达节点j的时刻
t_ok	航空器k的开始滑行时刻
${t}_{jk}^{\mathrm{w}}$	航空器k在j点的等待时间
c_j	航空器k在路径上的等待时间所产生的CO₂之和
${z}_{{k}_{1},{k}_{2}}^{i}$	航空器k₁、k₂在i点的顺序决策变量,代表k₁先于k₂到达i点,若是则为1,否则为0
${y}_{{k}_{1},{k}_{2}}^{(i,j)}$	航空器k₁、k₂在(i,j)边的顺序决策变量,代表k₁先于k₂到达(i,j)边,若是则为1,否则为0
${t}_{k}^{\mathrm{d}\mathrm{e}\mathrm{l}\mathrm{a}\mathrm{y}}$	离场航空器k的在起点推出等待的时间

符号

符号意义

${x}_{k}^{(i,j)}$

航空器k是否从节点i滑行至节点j,若是则为1,否则为0

t_jk

航空器k到达节点j的时刻

t_ok

航空器k的开始滑行时刻

${t}_{jk}^{\mathrm{w}}$

航空器k在j点的等待时间

c_j

航空器k在路径上的等待时间所产生的CO₂之和

${z}_{{k}_{1},{k}_{2}}^{i}$

航空器k₁、k₂在i点的顺序决策变量,代表k₁先于k₂到达i点,若是则为1,否则为0

${y}_{{k}_{1},{k}_{2}}^{(i,j)}$

航空器k₁、k₂在(i,j)边的顺序决策变量,代表k₁先于k₂到达(i,j)边,若是则为1,否则为0

${t}_{k}^{\mathrm{d}\mathrm{e}\mathrm{l}\mathrm{a}\mathrm{y}}$

离场航空器k的在起点推出等待的时间

符号	符号意义
${t}_{\_\mathrm{w}}$	离场航空器允许在预计离场时间后进行推出的时间范围
t_s	航空器之间的安全时间间隔
k	航空器编号
$\mathrm{E}\mathrm{T}\mathrm{O}{\mathrm{P}}_{k}$	航空器k的预计进离场时间
t^(i,j)、c^(i,j)	航空器从i到达j所需的时间和CO₂排放量
v₁、v₂	航空器在直线上和弯道上的速度
n_k	航空器k的发动机数量
F_k	航空器k在不同滑行阶段时每台发动机的燃油流量
EI	公布的航空器的废气的排放指数^[18]
V	顶点集合
E	边集合
s_k	航空器k的起点
e_k	航空器k的终点
M	一个足够大的正整数
m	航空器总数量

符号

符号意义

${t}_{\_\mathrm{w}}$

离场航空器允许在预计离场时间后进行推出的时间范围

t_s

航空器之间的安全时间间隔

航空器编号

$\mathrm{E}\mathrm{T}\mathrm{O}{\mathrm{P}}_{k}$

航空器k的预计进离场时间

t^(i,j)、c^(i,j)

航空器从i到达j所需的时间和CO₂排放量

v₁、v₂

航空器在直线上和弯道上的速度

n_k

航空器k的发动机数量

F_k

航空器k在不同滑行阶段时每台发动机的燃油流量

公布的航空器的废气的排放指数^[18]

顶点集合

边集合

s_k

航空器k的起点

e_k

航空器k的终点

一个足够大的正整数

航空器总数量

序号	航班号	停机位	降落时间/推出时间/s	进/离港
1	G54202	P1	0	进港
2	CA2866	P2	85	离港
3	H01209	P2	120	进港
4	EU1849	P2	250	离港
5	CA4070	P2	264	进港
6	G52893	P2	315	离港
7	HU7639	P3	360	进港
8	H01706	P1	405	离港
9	8L9525	P1	480	进港
10	PN6295	P1	635	离港
11	NS8077	P2	681	进港
12	MU9543	P2	778	离港
13	GS6477	P1	800	进港
14	GY7151	P1	945	离港

序号

航班号

停机位

降落时间/推出时间/s

进/离港

G54202

进港

CA2866

离港

H01209

120

进港

EU1849

250

离港

CA4070

264

进港

G52893

315

离港

HU7639

360

进港

H01706

405

离港

8L9525

480

进港

PN6295

635

离港

NS8077

681

进港

MU9543

778

离港

GS6477

800

进港

GY7151

945

离港

帕累托解	航空器总滑行时间/ s	CO₂ 排放量/ kg	直线滑行时间/ s	弯道滑行时间/ s	等待时间/ s	延误时间/ s
1	3 676.04	2 621.17	2 760.52	884.52	0	31
2	3 684.98	2 614.82	2 774.38	839.16	40.44	31
3	3 709.57	2 610.79	2 781.40	816.48	58.69	53

帕累
托解

航空器总
滑行时间/
s

CO₂
排放量/
kg

直线滑
行时间/
s

弯道滑
行时间/
s

等待
时间/
s

延误
时间/
s

3 676.04

2 621.17

2 760.52

884.52

3 684.98

2 614.82

2 774.38

839.16

40.44

3 709.57

2 610.79

2 781.40

816.48

58.69

不同对比参数	NSGA-II算法	基于Gurobi算法的混合整数规划
解的质量gap/%	1.083	0
求解时间/s	102.2	2 060.9

不同对比参数

NSGA-II算法

基于Gurobi算法的混合整数规划

解的质量gap/%

1.083

求解时间/s

102.2

2 060.9

实验组	航空器数量/ 架	NSGA-II算法求解时间/ s	NSGA-II算法解的质量 gap/%	基于Gurobi算法的混合整数规划求解时间/s
1	2	3.8	0	3.0
2	4	11.2	0.001	8.1
3	6	32.6	0.241	15.7
4	8	43.3	0.425	28.4
5	10	61.4	0.611	74.3
6	12	87.7	0.835	120.2
7	14	102.2	1.083	2 060.9
8	16	123.9	1.252	3 318.4
9	18	151.6	1.410	14 633.8

实验组

航空器
数量/
架

NSGA-II算法
求解时间/
s

NSGA-II算法
解的质量
gap/%

基于Gurobi算法
的混合整数规
划求解时间/s

3.8

3.0

11.2

0.001

8.1

32.6

0.241

15.7

43.3

0.425

28.4

61.4

0.611

74.3

87.7

0.835

120.2

102.2

1.083

2 060.9

123.9

1.252

3 318.4

151.6

1.410

14 633.8