科学技术与工程

指标	第一种进化策略 (先交叉后变异)	第二种进化策略 (先变异后交叉)
交叉(k₁、k₂)	大	小
变异(k₃、k₄)	小	大

指标

第一种进化策略
(先交叉后变异)

第二种进化策略
(先变异后交叉)

交叉(k₁、k₂)

大

小

变异(k₃、k₄)

小

大

指标	第一种进化策略 (先交叉后变异)	第二种进化策略 (先变异后交叉)
交叉(k₁、k₂)	大	小
变异(k₃、k₄)	小	大

指标

第一种进化策略
(先交叉后变异)

第二种进化策略
(先变异后交叉)

交叉(k₁、k₂)

大

小

变异(k₃、k₄)

小

大

飞机型号	发动机型号	发动机数/ 个	燃油流率/ (kg·s^-1)	对应机型
B737	CFM56-5B 5/3	2	0.092	1
A319	CFM56-5B 7/3	2	0.102	1
A320	V2527-A5	2	0.134	1
A330-302	CF6-80	2	0.201	2
B787	GEnx-2B	2	0.219	2
A330-343	Trent7000	2	0.245	2
A350	XWB-75	2	0.270	3
B777	GE90-115B	2	0.341	3

飞机型号

发动机型号

发动机数/
个

燃油流率/
(kg·s^-1)

对应机型

B737

CFM56-5B 5/3

0.092

A319

CFM56-5B 7/3

0.102

A320

V2527-A5

0.134

A330-302

CF6-80

0.201

B787

GEnx-2B

0.219

A330-343

Trent7000

0.245

A350

XWB-75

0.270

B777

GE90-115B

0.341

飞机型号	发动机型号	发动机数/ 个	燃油流率/ (kg·s^-1)	对应机型
B737	CFM56-5B 5/3	2	0.092	1
A319	CFM56-5B 7/3	2	0.102	1
A320	V2527-A5	2	0.134	1
A330-302	CF6-80	2	0.201	2
B787	GEnx-2B	2	0.219	2
A330-343	Trent7000	2	0.245	2
A350	XWB-75	2	0.270	3
B777	GE90-115B	2	0.341	3

飞机型号

发动机型号

发动机数/
个

燃油流率/
(kg·s^-1)

对应机型

B737

CFM56-5B 5/3

0.092

A319

CFM56-5B 7/3

0.102

A320

V2527-A5

0.134

A330-302

CF6-80

0.201

B787

GEnx-2B

0.219

A330-343

Trent7000

0.245

A350

XWB-75

0.270

B777

GE90-115B

0.341

航班编号	航班代码	出发类型	飞机型号	到达时间	出发时间
1	MU8335	国内	B737	08:20	09:30
2	KE833	国际	A320	09:30	10:40
3	CZ5567	国内	B787	14:20	15:50

航班编号

航班代码

出发类型

飞机型号

到达时间

出发时间

MU8335

国内

B737

08:20

09:30

KE833

国际

A320

09:30

10:40

CZ5567

国内

B787

14:20

15:50

航班编号	航班代码	出发类型	飞机型号	到达时间	出发时间
1	MU8335	国内	B737	08:20	09:30
2	KE833	国际	A320	09:30	10:40
3	CZ5567	国内	B787	14:20	15:50

航班编号

航班代码

出发类型

飞机型号

到达时间

出发时间

MU8335

国内

B737

08:20

09:30

KE833

国际

A320

09:30

10:40

CZ5567

国内

B787

14:20

15:50

旅客信息	航班代码	飞机型号
1	MU3078	B737
2	MF5219	A320
3	CZ5847	A330-343

旅客信息

航班代码

飞机型号

MU3078

B737

MF5219

A320

CZ5847

A330-343

旅客信息	航班代码	飞机型号
1	MU3078	B737
2	MF5219	A320
3	CZ5847	A330-343

旅客信息

航班代码

飞机型号

MU3078

B737

MF5219

A320

CZ5847

A330-343

停机位编号	区域	出发类型	停机位尺寸 (1小型,2中型, 3表示大型)	机位标识 (1表示近机位, 2表示远机位)
1	N	国内出发	3	1
2	S	国内出发	1	1
3	S	国际出发	2	1
…	…	…	…	…
G	远	国内/国际	3	2

停机位编号

区域

出发类型

停机位尺寸
(1小型,2中型,
3表示大型)

机位标识
(1表示近机位,
2表示远机位)

国内出发

国际出发

…

远

国内/国际

停机位编号	区域	出发类型	停机位尺寸 (1小型,2中型, 3表示大型)	机位标识 (1表示近机位, 2表示远机位)
1	N	国内出发	3	1
2	S	国内出发	1	1
3	S	国际出发	2	1
…	…	…	…	…
G	远	国内/国际	3	2

停机位编号

区域

出发类型

停机位尺寸
(1小型,2中型,
3表示大型)

机位标识
(1表示近机位,
2表示远机位)

国内出发

国际出发

…

远

国内/国际

算法	旅客行走距离/ km	碳排放量/ kg	机型匹配指数	远机位航班数	总目标
改进型自适应遗传算法	4 309.4	379 560	65	2	0.215 2
传统遗传算法	11 807.0	363 970	144	15	0.395 0
粒子群算法	6 262.4	395 470	97	4	0.288 0

算法

旅客行走
距离/
km

碳排
放量/
kg

机型匹
配指数

远机位
航班数

总目标

改进型自适应
遗传算法

4 309.4

379 560

0.215 2

传统遗传算法

11 807.0

363 970

144

0.395 0

粒子群算法

6 262.4

395 470

0.288 0

算法	旅客行走距离/ km	碳排放量/ kg	机型匹配指数	远机位航班数	总目标
改进型自适应遗传算法	4 309.4	379 560	65	2	0.215 2
传统遗传算法	11 807.0	363 970	144	15	0.395 0
粒子群算法	6 262.4	395 470	97	4	0.288 0

算法

旅客行走
距离/
km

碳排
放量/
kg

机型匹
配指数

远机位
航班数

总目标

改进型自适应
遗传算法

4 309.4

379 560

0.215 2

传统遗传算法

11 807.0

363 970

144

0.395 0

粒子群算法

6 262.4

395 470

0.288 0

考虑碳排放的多目标停机位指派优化模型

PDF下载

闫萍 , 刘连治

科学技术与工程 | 论文·航空、航天 2025,25(12): 5229-5239

收起

科学技术与工程 | 论文·航空、航天 2025, 25(12): 5229-5239

考虑碳排放的多目标停机位指派优化模型

全屏

闫萍, 刘连治

作者信息

沈阳航空航天大学经济与管理学院, 沈阳 110136

闫萍(1980—),女,汉族,辽宁沈阳人,博士,副教授。研究方向:航空运营管理。E-mail:0316yanping@126.com。

Multi-Objective Gate Assignment Optimization Model Considering Carbon Emissions

Ping YAN, Lian-zhi LIU

Affiliations

School of Economics and Management, Shenyang Aerospace University, Shenyang 110136, China

出版时间: 2025-04-28 doi: 10.12404/j.issn.1671-1815.2404523

文章导航

摘要

收起

现代机场的停机位指派问题涉及多方利益的协调,包括旅客满意度、机场资源的合理指派以及碳排放量的控制。为解决这一复杂问题,考虑航班类型、飞机机型和停机位可用性等约束条件的基础上,建立一个多目标非线性整数规划模型。其优化目标包括:最小化旅客的步行距离、最大化机型匹配度以及最小化碳排放量。提出一种改进型自适应遗传算法求解指派问题模型。在初始化种群阶段,采用随机、贪婪+扰动多种策略生成多样性更好的初始种群;在算法迭代过程中,自适应调整交叉和变异的概率,并应用先交叉后变异和先变异后交叉两种进化策略,以提高求解效率和全局搜索能力。为了验证算法的有效性,对国内某机场的运营数据进行仿真实验。将改进型自适应遗传算法与传统遗传算法和粒子群算法进行对比,结果显示改进型算法在停机位利用效率、旅客满意度以及碳排放量控制方面均表现出显著优势。此外,通过对改进策略的有效性实验分析,进一步验证所提出算法改进策略的有效性和算法性能的稳定性。所提出的模型和算法为机场停机位管理提供了有力的决策支持,促进了旅客出行满意度的改善、资源的有效利用以及环境的可持续发展。

关键词

航班-停机位指派 / 遗传算法 / 多目标优化 / 贪婪策略

Abstract

收起

The issue of gate assignment at modern airports involves coordinating multiple interests, including passenger satisfaction, efficient allocation of airport resources, and control of carbon emissions. A multi-objective nonlinear integer programming model was developed to solve this complex problem, which considering constraints such as flight type, aircraft model, and gate availability. The optimization objectives of model include minimizing passengers' walking distance, maximizing aircraft-gate matching, and minimizing carbon emissions. An improved adaptive genetic algorithm was proposed to solve the gate assignment problem. In the population initialization phase, a combination of random and greedy-perturbation strategies was employed to generate a more diverse initial population. The probabilities of crossover and mutation were adaptively adjusted during the algorithm's iterations. Both crossover-first and mutation-first evolutionary strategies were applied to enhance solution efficiency and global search ability. To validate the effectiveness of the algorithm, some simulation experiments were conducted using operational data from the domestic airport. The improved adaptive genetic algorithm was compared with traditional genetic algorithms and particle swarm optimization algorithms. Results show that the improved algorithm significantly outperforms the others in terms of gate utilization efficiency, passenger satisfaction, and carbon emission control. Furthermore, the effectiveness of the proposed improvement strategies was confirmed through experimental analysis, demonstrating the stability and performance of the algorithm. The proposed model and algorithm provide robust decision support for gate management, contributing to enhanced passenger satisfaction, efficient resource utilization, and sustainable environmental development.

Key words

flight-gate assignment / genetic algorithm / multi-objective optimization / greedy strategy

引用本文

闫萍, 刘连治. 考虑碳排放的多目标停机位指派优化模型. 科学技术与工程, 2025 , 25 (12) : 5229 -5239 . DOI: 10.12404/j.issn.1671-1815.2404523

Ping YAN, Lian-zhi LIU. Multi-Objective Gate Assignment Optimization Model Considering Carbon Emissions[J]. Science Technology and Engineering, 2025 , 25 (12) : 5229 -5239 . DOI: 10.12404/j.issn.1671-1815.2404523

正文

收起

随着中国经济的快速发展,民航运输业也迎来了前所未有的机遇和挑战。其中旅客人数激增,机场的服务航班量日益增加,现有的机场停机位资源已经很难满足需求,同时还需要考虑到机场运营过程中飞机排放对环境的影响^[1]。因此在现有的机场配置条件下,合理的指派停机位资源,最大化的提高旅客的出行满意度以及减少航班的碳排放量已经成为机场运营需要急迫解决的重要问题。

近年来,中外学者针对停机位指派问题展开了研究。周晓宁等^[2]提出了一种降低机场航空排放的停机位指派优化策略。考虑航空器排放和地面保障设备(ground support equipment,GSE)排放构建了多目标优化模型结果表明建立模型有效降低了有害物质的排放。李云鹏等^[3]主要研究基于属性匹配的停机位指派问题,结合机场的实际运行规则,提出了最小化停机位使用数目的优化目标。Karsu等^[4]研究最小化旅客行走距离和最小化指派至停机坪的航班数量,通过具有强大下界和上界机制的分支和边界算法、波束搜索和滤波波束搜索算法进行求解。Karsu等^[5]提出了一种新的混合整数线性规划公式和数学方法,更加简洁、易于实施和更加有效。王吉豪^[6]考虑最小化旅客的步行距离、最大化近机位航班的数量和最小化航空器的滑行成本3个目标函数,构建了基于公平性的多目标停机位预指派优化模型。余朝军等^[7]考虑了使用登机口的数量,在此基础上建立了使用登机口数量最少和旅客换乘紧张度最小的指派模型。王超等^[8]研究了多跑道运行模式的节油减排方案,引入航空器空中走向约束和航班连接约束。Chao等^[9]考虑不同飞机的油耗、航空公司航站楼位置等多种限制建立了最小化碳排放量和最小化碳排放成本的停机位指派模型。胡杰等^[10]针对新建卫星厅导致的换乘时间过长问题建立了航班-登机口的多目标优化模型,并且将贪婪算法用于初始种群的生成。刘禹汐等^[11]从多方的实际利益出发,建立了多目标优化模型,并根据问题改进可快速非支配遗传算法(non-dominated sorting genetic algorithms,NSGA-Ⅱ)对模型进行求解。Liu等^[12]提出了考虑统一维度鲁棒性和运行效率的新研究目标,并设计两阶段模型采用两种策略的脉冲算法进行求解。She等^[13]考虑机场运行的偏好,设立分数特征,以最大化运营商偏好分数和最小化因航班时刻表改变带来的影响。黄学林等^[14]对军民两用的停机坪进行分析建模,分层赋时着色Petri网模型,提出了一种新的冲突避让机制,保证军民用飞机有效运行。王兴隆等^[15]考虑了天气因素导致的机场除冰作业,综合考虑除冰车和飞行器的联合调度问题。卢飞等^[16]在解决地面拖车保障服务调度问题上建立拖车行驶总路程和航班延误最小化的联合模型,能够在保证机场特种车辆服务质量的前提下降低航班的延误情况。寇伟彬等^[17]针对于机场系统受干扰后的恢复上提出了以场面韧性为核心的优化思想,加快对恶劣天气的干扰适应,保障机场系统的相对稳定。

综上所述,单目标的停机位指派问题能够得到较好的求解方案,但是在实际机位分配过程中需要合理地平衡多方利益。兼顾多目标优化的机位指派研究多集中在改善旅客服务质量、停机位使用效率、机位分配的鲁棒性等方面建立综合优化模型。多目标模型的复杂性增大了优化求解难度,需要不断探索和开发有效的求解算法。并且随着世界环保意识的提升,机场的减排举措也提上了日程,因此从降低碳排放的角度优化机位指派问题,具有重要的现实意义。鉴于此,在考虑航班机型约束、时间约束、安全时间间隔等约束的基础上,建立旅客行走距离最小、最大化机型匹配度以及最小碳排放量的多目标优化模型。针对传统遗传算法随机生成初始种群导致初始解质量较差的问题,设计具有两种贪婪+扰动策略和随机策略3种方式生成初始种群。在遗传操作上采用多种进化策略,使算法种群在迭代过程中自适应调整算法参数。采用中国某机场的实验数据进行仿真实验,与传统遗传算法和粒子群算法进行求解结果比较分析,验证所提改进型自适应遗传算法的有效性和稳定性。

1 问题描述

收起

随着航空业的快速发展,航班在机场的停留过程已成为研究重点。这个过程被划分为不同的阶段,如图1所示,进近、滑行、起飞和爬升4个阶段称为标准起飞着陆循环(landing-takeoff,LTO),这是国际民用航空组织(International Civil Aviation Organization,ICAO)提出的重要概念^[18]。在机场停留的关键时刻是到达时间和出发时间,它们决定了航班在机场的停留时间,并涉及滑行时间、停机位指派以及安全时间等方面的提前安排。在LTO循环中,飞机的滑行阶段耗油量较高,导致碳排放量增加。然而,通过合理的停机位指派,可以减少这一阶段的碳排放量。合理的停机位指派不仅能够优化滑行路径,缩短滑行时间,还可以提升机场的整体运营效率,进而减少环境影响。

在停机位指派的过程中,需要综合考虑多方利益目标,如旅客的出行满意度、航空公司的成本控制以及机场的资源调度等方面。围绕旅客行走距离最小化、机场停机位机型匹配程度最大化以及碳排放量最小化这3个主要目标,展开多目标停机位指派优化研究。当航班指派至近机位时,中转航班旅客满意度和机场的资源利用率会有所提高,而滑行阶段的碳排放量则会增加,同时航班指派至近机位的具体位置不同则会影响中转航班旅客满意度和机场资源利用率;当机位指派至远机位时,滑行阶段的碳排量会降低,但是会降低中转航班旅客的满意度和机场的资源利用率。旨在通过多目标优化方法,在考虑LTO滑行阶段碳排放量的同时,最大化旅客的便利性并最大程度利用机场的停机位资源。不仅有助于提高旅客的出行体验,还有助于促进航空公司和机场在运营成本和资源利用方面的优化,最终实现环境的可持续发展。

2 模型构建

收起

2.1 模型假设

为构建多目标停机位指派模型,做如下假设。

(1)指派过程需要的信息充分假设。在规定的指派时间内,为航班指派停机位的必要数据如旅客人数、航班时刻表、停机位的指派属性等均已知。

(2)旅客行走信息假设。不考虑不同旅客之间的个体差异,即不考虑不同旅客的行走速度以及其他各种因素,如果航班指派至近机位,则旅客行走距离根据停机位的位置具体决定。若航班指派至远机位,则旅客需要乘坐摆渡车等交通工具,因此会对旅客的行走距离产生影响,这里将乘坐摆渡车的时间转化为距离,近似地取3 000 m。

(3)航班起降的机场容量假设。在机场某个工作日内,停机位的数量能够满足所有该时间段内所有的起降航班指派计划,并且其中包含了一个远机位,且远机位的容量为无限大,以简化求解。

(4)安全时间间隔假设。在机场的实际运营中,航班在滑行道和停机位之间滑行需要一定的空间,如果出现两架航班先后滑入同一机位的情况时,就可能会发生事故,因此先后航班滑入需要有充足的时间间隔以确保安全性。为了使问题简化,通常假设安全时间间隔是一定的。

2.2 模型建立

2.2.1 约束条件

假设机场在某一时间段内服务的航班数为F,机场的固定近机位数量为G,i、j分别为第i个航班、第j个机位, ∀i,i₁,i₂∈F,∀j∈G。

(1)

∑ j = 1 G

x_i_,_j=1

(2)(GM_j-FM_i)x_i_,_j≥0

(3)

G D j - F D i

+x_i_,_j≤1

(4)(

t i o u t

t i i n

)x_i_,_j-T_st≥0

(5)(

t i 2 i n

t i 1 o u t

)

y i 2, i 1, j

-ΔT≥0

(6)x_i_,_j,

y i 2, i 1, j

∈{0,1}

式中:x_i_,_j为第i个航班分配至机位j上,当航班i指派至停机位j时的决策变量,x_i_,_j取值为1;GM_j为机场停机位j尺寸,GM_j=1表示停机位尺寸为小型,仅能容纳小型航班;GM_j=2表示停机位尺寸为中型,可容纳中型航班和小型航班;GM_j=3表示停机位尺寸为大型,可以容纳任意型号的航班;FM_i为航班i尺寸,FM_i=1,2,3分别表示小型、中型以及大型航班;GD_j为机场停机位j的出发类型,GD_j=1表示停机位j的出发类型为国内;GD_j=2表示停机位j的出发类型为国际;FD_i为航班i的出发类型,FD_i=1表示航班i的出发类型为国内;FD_i=2表示航班i的出发类型为国际;

t i o u t

为航班i的滑出机位时间;

t i i n

为航班i的滑入机位时间;T_st为停机位的最低保障时间;

t i 2 i n

为航班i₂的滑入机位时间;

t i 1 o u t

为航班i₁的滑出机位时间;DT为同机位相邻航班间的安全时间间隔;当先后航班i₂和i₁指派至同一机位j时

y i 2, i 1, j

=1,否则为0。

式(1)表示唯一性约束,即航班只能指派在一个停机位上;式(2)表示停机位机型约束,即航班不能指派至小于当前航班尺寸的停机位上;式(3)表示航班出发类型约束,即航班分为国内出发和国际出发;式(4)表示最低保障时间约束,即指派至停机位上的航班保障时间不能小于T_st;式(5)表示指派至同一机位的前后航班要满足安全时间间隔。式(6)表示决策变量。

2.2.2 目标函数

从旅客满意度、运营成本以及机场的停机位资源利用率3个方面考虑,设计3个优化目标函数包括:最小化旅客行走距离,最小化航班滑行总碳排放量以及最大化机型匹配率和靠桥率,即保持GM_j=FM_i。

(7)minZ₁=

∑ i = 1 F ∑ j = 1 G

x_i_,_j(

N i i n D j i n

N i o u t D j o u t

)

(8)minZ₂=

∑ i = 1 F ∑ j = 1 G

x_i_,_j

Q i x i, j S j i n + x i, j S j o u t v F R i ρ

(9)minZ₃=

∑ i = 1 F ∑ j = 1 G

x_i_,_j「

G M j - F M i 3

⌉

式中:

N i i n

为航班i到港旅客数量;

D j i n

为到港旅客从停机位j离开步行总距离;

N i o u t

为航班i离港旅客数量;

D j o u t

为离港旅客步行总距离;Q_i为航班i的发动机数量;FR_i为航班i的燃油流率;ρ为碳排放指数,kg/kg,取3.115;

S j i n

为到港航班滑行至机位j的滑行距离;

S j o u t

为离港航班从机位j滑行至跑道的滑行距离;v为滑行速度; 「

G M j - F M i 3

⌉为航班机型匹配程度;「⌉表示向上取整。

式(7)Z₁表示目标函数1为最小化旅客行走距离,式(8)Z₂表示目标函数2为最小化航班滑行总碳排放量,式(9)Z₃表示目标函数3为最大化机型匹配率和靠桥率。为了方便求解,将其变为最小化问题,定义式(9)为机型匹配指数。当航班指派至近机位并且航班机型与停机位尺寸完全匹配时,取值为0;当不完全匹配时,即停机位尺寸大于航班尺寸,则取值为1;当航班指派至远机位时,由于远机位无约束条件限制,国际、国内航班均可指派,这时施加一个惩罚,限制远机位j的GM_j=16。例如,当航班被指派至近机位时,若航班的机型和停机位的机型相同,则取值为0,否则为1;当航班被指派至远机位时,无论航班的机型为1、2、3中的哪一个,最终的取值都为5。

从3个目标函数的定义可知,3个目标函数之间存在制约关系互相影响,当一个目标函数优化时将会导致其他目标函数的劣化,无法同时满足多个目标的优化。因此,对3个目标函数采用归一化方法进行处理。通过最小-最大缩放(min-max scaling),将函数值归一化至[0,1]区间,归纳整理之后的目标函数模型为

(10)minZ=ω₁

Z 1 - Z 1 m i n Z 1 m a x - Z 1 m i n

+ω₂

Z 2 - Z 2 m i n Z 2 m a x - Z 2 m i n

+ω₃

Z 3 - Z 3 m i n Z 3 m a x - Z 3 m i n

式(10)中:Z_i_max和Z_i_min(i=1,2,3)分别为目标函数1、2、3的最大值和最小值。

3 算法设计

收起

遗传算法因其强大的并行处理能力和全局搜索能力,能够在复杂的解空间中找到潜在的最优解。然而,传统遗传算法在求解效率和解的质量方面仍存在一定的局限性。针对这些缺陷,提出一系列改进策略。首先,针对初始解的质量问题,设计随机、贪婪+扰动策略生成初始种群。这种贪婪+扰动的方法在贪婪寻优结果上对其进行扰动操作,避免了生成的个体之间相同的问题,同时又保留了优势特性。其次,针对传统交叉操作容易导致失去种群优势特征和减少多样性的问题,引入自适应交叉操作。类似地,为了解决变异操作设置不当可能导致过度探索或陷入局部最优解的问题,引入自适应变异操作。此外,交叉和变异的先后顺序对算法求解效果也会产生一定的影响,改进算法中采用先交叉后变异和先变异后交叉两种进化策略,以提升算法的性能。在子代种群的选取上,模拟自然界优胜劣汰的选择方式,同时允许少量劣势个体存活,这种方法可以扩大搜索空间,减少陷入局部最优的风险。

3.1 编码方式

基于停机位指派问题的离散特性,采用整数编码的形式。每个染色体由F'个基因组成,其中每个基因代表一个机位号的指派情况。因此,染色体的长度等于航班数量。染色体的结构示例如图2所示,第1个基因位的数字2表示第一个航班指派到编号为2的停机位。

3.2 初始种群的获取

传统遗传算法通常采用随机方式生成初始种群,而随机方式产生初始解有一个缺陷,初始解的质量不佳。为解决随机生成初始解质量不佳的问题,从优化单一目标函数的角度构建贪婪策略,以获取在不同目标优先情景下的多个初始解集。同时,仍然保留了一部分随机生成的初始解。采用这种多策略的方式可以获得更佳的种群多样性和更优秀的初始解质量。初始种群由3个部分构成,3种初始解集生成方式描述如下。

指派策略1 随机生成初始解。

指派策略2 按照航班进港顺序“先到先服务”,以旅客行走距离最小为贪婪目标选择机位指派。

指派策略3 按照航班进港顺序“先到先服务”,以碳排放量最小为贪婪目标选择机位指派。

由于指派策略2和指派策略3在生成初始种群时,容易产生大量相同解,因而添加扰动机制调整贪婪初始解。

扰动原理:对符合当前航班指派条件的机位进行排序,并且随机决定是否交换,交换时随机选择交换其中的不同机位指派优先级,以得到不同的贪婪指派解。扰动原理如图3所示。

贪婪+扰动策略的初始解生成步骤如下。

步骤1 初始化参数。首先将航班按照航班信息中的到达时间进行排序,优先为先到达的航班指派停机位。停机位的开启时间为上一架次航班的离港时间+安全时间间隔。

步骤2 寻找当前到达航班的最优指派机位。对于每个到达航班,寻找其与当前贪婪目标最优的停机位作为指派方案,并且随机决定是否采取次优的停机位作为指派机位,若航班 i占用停机位j,则 x_i_,_j=1,否则 x_i_,_j=0;若某一航班经过多次尝试仍然无法指派到适合的停机位,则将该航班指派至远机位。

步骤3 遍历待指派航班,为所有计划内的航班指派适合的停机位。

初始种群生成流程如图4所示。

3.3 自适应策略

3.3.1 交叉操作

父母本染色体采取成对交叉的方式,即第1个染色体和第2个染色体交叉,第3个染色体和第4个染色体交叉,依次类推。交叉算子采用双点交叉,随机生成两个交叉点χ₁和χ₂,父本与母本之间交换基因片段得到子代染色体。如图5所示。

同时,为了在进化前期能够有较快的进化速度以及在进化后期最大程度地保留优势个体,采用自适应交叉概率,自适应交叉概率的计算步骤如下。

步骤1 计算父本与母本染色体的平均适应度值,计算公式为

(11)f_avg=

f c 1 + f c 2 2

式(11)中:f_c1和f_c2分别为父本与母本染色体。

步骤2 根据平均适应度值确定交叉概率。

(12)P_c=

P c 0 (k 1 + f a v g - f 1), f a v g ≥ f 1 P c 0, f 1 > f a v g > f 2 P c 0 [k 2 - (f 2 - f a v g)], f a v g ≤ f 2

式(12)中:P_c为交叉算子;P_c0为初始交叉概率;k₁和k₂为交叉相关的参数;f₁和f₂为取值在[0,1]内的遗传进化的分层点,f_avg>f₁时表示当前种群处在进化前期,需要较大的交叉概率保证搜索能力;当f₁>f_avg>f₂时表示当前种群处在进化中期,需要保存优势个体的同时平稳地进化,交叉概率平缓;当f_avg<f₂时表示当前种群处在进化后期,需要最大程度的保留优势个体,交叉概率逐渐变小快速收敛。

3.3.2 变异操作

变异操作采用随机变异的方式,根据变异概率决定是否进行变异操作,变异的位置采用随机位置。与交叉算子相同,变异算子也采用自适应变异概率,进化时期的设定也与交叉操作相同,分层点的设定也与交叉操作相同。

(13)P_m=

P m 0 (k 3 + f c - f 1), f c ≥ f 1 P m 0, f 1 > f c > f 2 P m 0 [k 4 - (f 2 - f c)], f c ≤ f 2

式(13)中:P_m为变异算子;P_m0为初始变异概率;k₃和k₄为变异相关的参数。

3.3.3 进化策略

在遗传操作中,交叉操作通过重组现有基因来产生优良的子代个体。然而,如果群体内所有个体都缺少某一特定基因,就无法通过交叉操作获得这一缺失基因。变异操作则模仿生物基因突变,产生原始种群中不存在的新基因;但是,如果种群只产生新基因而不进行基因重组来获取优良个体,优秀个体将不断被破坏,减缓种群的收敛速度^[19]。在整个遗传操作过程中,交叉和变异的先后顺序同样会对种群的进化产生影响。为此,设计了先交叉后变异和先变异后交叉的两种进化策略,以改善种群的全局进化能力。同时,通过自适应调整交叉和变异的概率,使进化过程更加快速和精确。通过调整k的取值可以改变自适应概率的变动幅度,第一种进化策略先交叉后变异,采用较大的交叉概率和较小的变异概率变动;第二种进化策略先变异后交叉,采用较小的交叉概率和较大的变异概率变动,参数k的取值如表1所示。

3.4 改进型自适应遗传算法流程

改进型自适应遗传算法流程如图6所示。算法步骤如下。

步骤1 算法参数初始化。种群大小为N_P,染色体长度为航班数量F,最大遗传代数为M_axgen。

步骤2 根据已知旅客、航班以及机场停机位信息,利用随机、贪婪+扰动策略生成算法初始种群。

步骤3 根据模型的目标函数式(10)计算个体的适应度值,并且记录当前种群的最好染色体解信息。

步骤4 选择操作。采用轮盘赌算法选择染色体,若所有染色体的选择概率相同,则均匀分布随机性选择。

步骤5 第一种进化策略,先交叉后变异。交叉操作采用3.3.1节设计的交叉操作。变异操作采用3.3.2节设计的变异操作生成随机变异点,变异概率自适应变换。

步骤6 第2种进化策略,先变异后交叉。变异操作和交叉操作与第一种进化策略相同。

步骤7 修复个体。交叉和变异之后的个体存在不可行解,需要进行修复操作。修复操作如下:首先遍历航班,判断当前航班机位的指派是否满足约束,满足约束则更新机位空闲时间并进行下一个航班的判断,若不满足则需要对当前航班进行修复。基于贪婪思想对当前航班完成当前的最优指派,将所有机位按照当前航班指派至机位的适应度值由小到大排序,然后依次判断是否满足机位指派约束条件,直至航班能够指派至合适机位,并更新机位空闲时间。

步骤8 种群适应度值排序与选择。由于进化之后的种群个体数量变多,需要筛选一定数量的个体作为下一代进化操作的种群。算法模拟自然选择过程,增加优势个体意外死亡和劣势个体存活的情况。采用前面两种进化策略产生子代种群规模为2N_P,从子代种群中分层选取N_P个染色体进入算法下一次迭代,具体方法为:将子代种群按照适应度值由优到劣进行排序,对于排序后的前N_P个体,选取前70%作为优势个体存活;对于接下来的N_P/2个体,随机选取20%作为次优势个体存活;最后的N_P/2个体,随机选取10%作为劣势个体存活。例如,当N_P取10时,分层选取方式如图7所示。分层选取方式保留一定数量的劣质解,能够增强种群的多样性,选取的各层占总体的比例为7∶2∶1。

步骤9 重复执行步骤3~步骤8 M_axgen次,获得最优停机位指派方案。

4 仿真验证及分析

收起

4.1 仿真验证参数设置

以沈阳桃仙机场的航班数据和旅客信息数据为基础设计仿真实验,验证所提出算法的有效性。其中近机位28个,机场的航班起降共有137架次,旅客共有14 535次变动。航空发动机的燃油流率来自于ICAO数据库。航班发动机、航班、停机位、旅客相关信息示例如表2~表5所示。

为验证所提出改进型自适应遗传算法的性能,将本文算法与传统遗传算法和标准粒子群算法进行对比,以验证算法的整体性能。依据待指派航班计划初始化算法基本参数,传统遗传算法与改进型自适应遗传算法基本参数为:种群规模N_P为100,染色体长度为137,最大迭代次数M_axgen为800,交叉算子P_c0=0.6,变异算子P_m0=0.15。传统遗传算法采取随机策略生成初始种群,改进型自适应遗传算法初始种群中,采用3种指派策略生成染色体数目的比例为4∶3∶3。改进型自适应遗传算法中,进化参数f₁=0.28,f₂=0.24,第1种进化策略中k₁=1.5,k₂=0.8,k₃=1.2,k₄=0.9;第2种进化策略中k₁=1.2,k₂=0.9,k₃=1.5,k₄=0.8。标准粒子群算法的基本参数设置为:种群规模N_P为100,最大迭代次数Maxgen为800,惯性权重为0.9,自我学习因子为0.5,群体学习因子为0.5。目标函数的权重ω₁=ω₂=ω₃=1/3。在Win10系统上使用MATLAB2021b进行仿真求解。

4.2 求解指派方案对比分析

改进型自适应遗传算法求解停机位指派方案如图8所示。由甘特图(图8)可以看出,改进型自适应遗传算法求解的指派方案中,只有29号和122号航班停靠在远机位,停机位资源的整体利用率较高。

依据4.1节的实验参数进行仿真实验,不同算法求解的目标函数值实验结果如表6和图9所示。实验结果表明,传统遗传算法和粒子群算法在进化后期容易陷入局部最优,而改进型自适应遗传算法的全局寻优能力要强于其他两种算法。从解的质量来看,所提出的算法比传统遗传算法优化了45.5%,比粒子群算法优化了25.3%。虽然在碳排放量这一目标上略微高于传统遗传算法,但是在旅客行走距离的目标函数上远优于传统遗传算法,且改善幅度达到63.5%。在机型匹配指数的目标函数方面改善了54.9%。改进型自适应遗传算法与粒子群算法相比,3个目标函数均有所改善,改善幅度分别达到31.2%、4.0%和33.0%。改进型自适应遗传算法的机位指派方案中,指派至远机位的航班数量为2个,指派至近机位的航班机型未匹配数量为55个。传统遗传算法的机位指派结果中,指派至远机位的航班数量为15个,指派至近机位航班机型未匹配数量为69个。粒子群算法的机位指派结果中,指派至远机位的航班数量为4个,指派至近机位的航班机型未匹配数量为77个。由此可知,改进型自适应遗传算法能够有效地提高机场的资源利用率,提高旅客的出行满意度,减少航班滑行时的碳排放量,验证了模型和算法的有效性。从算法求解时间来看,3个算法的求解时间相差不大,均未超过120 s。

4.3 改进策略的有效性分析

为了验证所提出算法改进策略的有效性,对初始种群适应度值进行统计分析,并对自适应策略的有效性和算法结果的稳定性分别进行实验分析,实验结果如图10~图12所示。分析随机策略[图10(a)]与随机、贪婪+扰动策略[图10(b)]生成的初始种群适应度值统计情况可以得出,单纯采用随机方式生成的初始种群,其适应度值在0.45~0.65,数据值过于集中,种群的多样性较差,初始解质量不高;而多策略扰动生成的初始种群,适应度值分布在0.3~0.8,数据分布较为分散,大大提升了种群的多样性,同时得到了更优质的初始解集。因此,随机、贪婪+扰动策略初始种群生成策略较好地改善了种群的多样性并提升了初始解集的质量。

从图11可以看出,在算法进化中,改进型自适应遗传算法收敛速度远大于无自适应策略的改进型遗传算法;改进型自适应遗传算法在552代就已经收敛,而无自适应策略的改进型遗传算法在692代收敛,并且改进型自适应遗传算法的求解结果也优于无自适应策略的改进型遗传算法,综上改进型自适应遗传算法的搜索效率和效果均优于无自适应策略的遗传算法,进而验证了自适应策略的有效性和可行性。

图12为独立运行改进型自适应遗传算法30次的实验结果,可以看出,算法求得最终解的值趋于平稳,其中,平均值为0.218 197,方差为0.000 004 7,多次实验数据的方差值很小能够验证算法性能的稳定性,不会产生较大的波动。

5 结论

收起

(1)在构建停机位指派数学模型时,考虑旅客行走距离、碳的排放和机场资源的利用率,即尽可能匹配指派至停机位的机型。在算法设计上,初始化种群部分采用随机、贪婪+扰动相结合方式生成初始解集,从而获得更高质量的初始解,这为后续算法求解提供了更好的全局搜索能力。在遗传操作的进化部分,设计两种的进化策略:较大的交叉概率和较小的变异概率,以及较小的交叉概率和较大的变异概率,以保证算法的全局搜索能力。在子代种群的选择上,采用分层选择机制保留了部分劣势个体,以模拟生物进化中的意外情况,保持种群的多样性。

(2)基于航班数据和机场信息的仿真实验表明,在较大规模优化实例的仿真实验中,与传统遗传算法、粒子群算法相比,所提出的改进型自适应遗传算法具有更快的收敛速度和更好的优化结果,并且表现出良好的算法稳定性,有助于提高机场的高效运营和服务能力。

(3)在后续的研究中,可以结合航班和机场在实际运行中的突发情况考虑实时机位指派问题。例如航班延误和机场保障的突发事件,以构建更加完善的停机位指派模型。

基金

收起

国家自然科学基金(62072085)

参考文献

收起

文献

收起

参考文献引证文献

排序方式：

[1]

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

Rong

, Wang

Deyun

, Feng

Huilin

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

[2]

周晓宁, 王凯, 赵志奇, 等. 基于航空排放的机场停机位分配优化[J]. 科学技术与工程, 2019, 19(30): 362-367.

Zhou

Xiaoning

, Wang

Kai

, Zhao

Zhiqi

, et al. Optimization of airport stand assignment based on aviation emissions[J]. Science Technology and Engineering, 2019, 19(30): 362-367.

[3]

李云鹏, 张则强, 管超, 等. 停机位分配问题的整数规划模型及启发式求解方法[J]. 系统工程, 2020, 38(1): 103-112.

Yunpeng

, Zhang

Zeqiang

, Guan

Chao

, et al. Integer programming model and heuristic solution methods for stand assignment problem[J]. Systems Engineering, 2020, 38(1): 103-112.

[4]

Karsu

, Azizoğlu

, Alanlı

. Exact and heuristic solution approaches for the airport gate assignment problem[J]. Omega, 2021, 103: 102422.

[5]

Karsu

, Solyalı

. A new formulation and an effective matheuristic for the airport gate assignment problem[J]. Computers & Operations Research, 2023, 151: 106073.

[6]

王吉豪. 多目标优化的停机位分配方法研究[D]. 广汉: 中国民用航空飞行学院, 2021.

Wang

Jihao

. Research on Multi-objective optimization methods for stand assignment[D]. Guanghan: Civil Aviation Flight University of China, 2021.

[7]

余朝军, 江驹, 徐海燕, 等. 基于改进遗传算法的航班-登机口分配多目标优化[J]. 交通运输工程学报, 2020, 20(2): 121-130.

Chaojun

, Jiang

, Xu

Haiyan

, et al. Multi-objectiveoptimization of flight-gate assignment based on improved genetic algorithm[J]. Journal of Transportation Engineering, 2020, 20(2): 121-130.

[8]

王超, 任云鸿. 面向节油减排的平行多跑道混合运行机场停机位分配模型[J]. 交通信息与安全, 2021, 39(5): 144-152.

Wang

Chao

, Ren

Yunhong

. Stand assignment model forparallel runway mixed operation airports focusing on fuel-saving and emission reduction[J]. Transportation Information and Safety, 2021, 39(5): 144-152.

[9]

Chao

C C

, Tang

C H

, Hsiao

Y H

. Planned gate and runway assignments considering carbon emissions and costs[J]. International Journal of Sustainable Transportation, 2020, 14(8): 643-655.

[10]

胡杰, 鲍帆, 石潇竹. 基于贪婪-遗传算法的机场登机口分配策略[J]. 系统工程与电子技术, 2023, 45(11): 3555-3564.

Jie

, Bao

Fan

, Shi

Xiaozhu

. Boarding gate assignment strategy at airports based on greedy-genetic algorithm[J]. Systems Engineering and Electronics Technology, 2023, 45(11): 3555-3564.

[11]

刘禹汐, 刘继新, 田文. 基于改进NSGA-Ⅱ的停机位预分配优化[J]. 南京航空航天大学学报, 2023, 55(2): 329-338.

Liu

Yuxi

, Liu

Jixin

, Tian

Wen

. Pre-assignment optimization of aircraft stands based on improved NSGA-II[J]. Journal of Nanjing University of Aeronautics and Astronautics, 2023, 55(2): 329-338.

[12]

Liu

, Xiang

. A branch-and-price algorithm for the airport gate assignment problem considering the trade-off between robustness and efficiency[J]. Transportation Research Part C: Emerging Technologies, 2023, 154: 104232.

[13]

She

, Zhao

, Guo

, et al. A robust strategy to address the airport gate assignment problem considering operators' preferences[J]. Computers & Industrial Engineering, 2022, 168: 108100.

[14]

黄学林, 王观虎, 陈奇奇, 等. 基于Petri网军民共用停机坪运行仿真与分析[J]. 科学技术与工程, 2022, 22(2): 841-849.

Huang

Xuelin

, Wang

Guanhu

, Chen

Qiqi

, et al. Simulation and analysis of the operation of military-civilian shared aprons based on Petri nets[J]. Science Technology and Engineering, 2022, 22(2): 841-849.

[15]

王兴隆, 丁俊峰. 机场飞行区航空器与除冰车协同优化调度方法[J]. 科学技术与工程, 2023, 23(10): 4440-4447.

Wang

Xinglong

, Ding

Junfeng

. Collaborative optimization scheduling method for aircraft and deicing vehicles in airport movement areas[J]. Science Technology and Engineering, 2023, 23(10): 4440-4447.

[16]

卢飞, 宋佳佳. 基于非支配排序的机场特种车辆调度[J]. 科学技术与工程, 2024, 24(21): 9152-9159.

Fei

, Song

Jiajia

, Airport special vehicle scheduling based on non-dominated sorting[J]. Science Technology and Engineering, 2024, 24(21): 9152-9159.

[17]

寇伟彬, 于凯任, 王佳玉, 等. 韧性导向的机场航空器滑行路径及停机位联合优化[J/OL]. (2024-02-07)[2024-10-02]. https://doi.org/10.13700/j.bh.1001-5965.2023.0801.

Kou

Weibin

, Yu

Kairen

, Wang

Jiayu

, et al. Resilience-oriented joint optimization of aircraft taxiing paths and parking positions at airports[J/OL]. (2024-02-07)[2024-10-02]. https://doi.org/10.13700/j.bh.1001-5965.2023.0801.

[18]

尤倩, 李洪枚, 伯鑫, 等. 中国民用航空机场大气污染物及碳排放清单[J]. 中国环境科学, 2022, 42(10): 4517-4524.

You

Qian

, Li

Hongmei

, Bo

Xin

, et al. Inventory of atmospheric pollutants and carbon emissions at Chinese civil aviation airports[J]. China Environmental Science, 2022, 42(10): 4517-4524.

[19]

潘家文, 钱谦, 伏云发, 等. 模糊自适应并行遗传算法在函数优化中的应用[J]. 小型微型计算机系统, 2021, 42(11): 2313-2322.

Pan

Jiawen

, Qian

Qian

, Fu

Yunfa

, et al. Application of fuzzy adaptive parallel genetic algorithm in function optimization[J]. Journal of Small and Miniature Computers, 2021, 42(11): 2313-2322.

2025年第25卷第12期

PDF下载

408

161

引用本文

BibTeX

文章信息

doi: 10.12404/j.issn.1671-1815.2404523

接收时间：2024-06-17
首发时间：2025-07-09
出版时间：2025-04-28

补充材料

相关文章

文章信息

作者

出版历史

收稿日期：2024-06-17
修回日期：2025-02-12

基金

国家自然科学基金(62072085)

作者信息

沈阳航空航天大学经济与管理学院, 沈阳 110136

参考文献

分享链接

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

分享至

全文二维码

扫描看全文

引用本文

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

指标	第一种进化策略 (先交叉后变异)	第二种进化策略 (先变异后交叉)
交叉(k₁、k₂)	大	小
变异(k₃、k₄)	小	大

指标

第一种进化策略
(先交叉后变异)

第二种进化策略
(先变异后交叉)

交叉(k₁、k₂)

大

小

变异(k₃、k₄)

小

大

飞机型号	发动机型号	发动机数/ 个	燃油流率/ (kg·s^-1)	对应机型
B737	CFM56-5B 5/3	2	0.092	1
A319	CFM56-5B 7/3	2	0.102	1
A320	V2527-A5	2	0.134	1
A330-302	CF6-80	2	0.201	2
B787	GEnx-2B	2	0.219	2
A330-343	Trent7000	2	0.245	2
A350	XWB-75	2	0.270	3
B777	GE90-115B	2	0.341	3

飞机型号

发动机型号

发动机数/
个

燃油流率/
(kg·s^-1)

对应机型

B737

CFM56-5B 5/3

0.092

A319

CFM56-5B 7/3

0.102

A320

V2527-A5

0.134

A330-302

CF6-80

0.201

B787

GEnx-2B

0.219

A330-343

Trent7000

0.245

A350

XWB-75

0.270

B777

GE90-115B

0.341

航班编号	航班代码	出发类型	飞机型号	到达时间	出发时间
1	MU8335	国内	B737	08:20	09:30
2	KE833	国际	A320	09:30	10:40
3	CZ5567	国内	B787	14:20	15:50

航班编号

航班代码

出发类型

飞机型号

到达时间

出发时间

MU8335

国内

B737

08:20

09:30

KE833

国际

A320

09:30

10:40

CZ5567

国内

B787

14:20

15:50

旅客信息	航班代码	飞机型号
1	MU3078	B737
2	MF5219	A320
3	CZ5847	A330-343

旅客信息

航班代码

飞机型号

MU3078

B737

MF5219

A320

CZ5847

A330-343

停机位编号	区域	出发类型	停机位尺寸 (1小型,2中型, 3表示大型)	机位标识 (1表示近机位, 2表示远机位)
1	N	国内出发	3	1
2	S	国内出发	1	1
3	S	国际出发	2	1
…	…	…	…	…
G	远	国内/国际	3	2

停机位编号

区域

出发类型

停机位尺寸
(1小型,2中型,
3表示大型)

机位标识
(1表示近机位,
2表示远机位)

国内出发

国际出发

…

远

国内/国际

算法	旅客行走距离/ km	碳排放量/ kg	机型匹配指数	远机位航班数	总目标
改进型自适应遗传算法	4 309.4	379 560	65	2	0.215 2
传统遗传算法	11 807.0	363 970	144	15	0.395 0
粒子群算法	6 262.4	395 470	97	4	0.288 0

算法

旅客行走
距离/
km

碳排
放量/
kg

机型匹
配指数

远机位
航班数

总目标

改进型自适应
遗传算法

4 309.4

379 560

0.215 2

传统遗传算法

11 807.0

363 970

144

0.395 0

粒子群算法

6 262.4

395 470

0.288 0