基于贪婪-遗传算法的机场登机口分配策略

doi:10.12305/j.issn.1001-506X.2023.11.22

摘要/Abstract

摘要：

针对枢纽机场新建卫星厅导致中转旅客航班衔接时间延长、换乘失败概率增大的问题, 开展了机场登机口多目标优化分配问题研究。首先, 在顾及航班类型、机体类型和转场时间间隔等约束条件基础上, 建立了航班-登机口多目标优化分配模型。然后, 基于贪婪算法思想, 按照航班“先到先分配”的原则指派登机口, 以生成初始种群, 并利用遗传算法实现机场登机口分配模型求解。最后, 利用实例数据进行了验证, 该方法能够成功为524个航班分配登机口, 占航班总数86.47%, 中转旅客最短流程时间为20 min的比率为20.07%, 其所占比率最大, 实验结果验证了模型和算法的有效性。

关键词: 枢纽机场, 多目标优化, 贪婪算法, 遗传算法

Abstract:

Aiming at the problem that the newly built satellite hall in the hub airport leads to the prolonged connection time of transfer passengers and the increased probability of transfer failure, the research on the multi-objective optimal allocation of airport gates is carried out. Firstly, on the basis of considering the constraints of flight type, aircraft body type and transition time interval, a flight-gate multi-objective optimal allocation model is established. Then, based on the idea of greedy algorithm, the gates are assigned according to the principle of "first come, first allocation" for flights to generate the initial population, and the airport gate allocation model is solved by using the genetic algorithm. Finally, verification experiments are carried out by using the example data, and the results show that the method is able to successfully allocate gates for 524 flights, accounting for 86.47% of the total number of flights, and the ratio of the minimum process time of transit passengers to 20 min is 20.07%, which accounts for the largest proportion. The experimental results verify the effectiveness of the proposed model and algorithm.

Key words: hub airport, multi-objective optimal, greedy algorithm, genetic algorithm

中图分类号:

V351.1

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

Jie HU, Fan BAO, Xiaozhu SHI. Airport gate assignment strategy based on greedy-genetic algorithm[J]. Systems Engineering and Electronics, 2023, 45(11): 3555-3564.

图/表 15

图1

表1

图2

图3

图4

图5

表2

表3

表4

图6

图7

图8

表5

表6

表7

参考文献 31

1	OZLEM K , MERAL A , KEREM A . Exact and heuristic solution approaches for the airport gate assignment problem[J]. Omega, 2021, 103, 102422. doi: 10.1016/j.omega.2021.102422
2	余朝军, 江驹, 徐海燕, 等. 基于改进遗传算法的航班-登机口分配多目标优化[J]. 交通运输工程学报, 2020, 20 (2): 121- 130. doi: 10.19818/j.cnki.1671-1637.2020.02.010
	YU C J , JIANG J , XU H Y , et al. Multi-objective optimization of flight-gate assignment based on improved genetic algorithm[J]. Journal of Traffic and Transportation Engineering, 2020, 20 (2): 121- 130. doi: 10.19818/j.cnki.1671-1637.2020.02.010
3	BRAAKSMA J P , SHORTREED J H . Improving airport gate usage with critical path[J]. Transportation Engineering Journal of ASCE, 1971, 97 (2): 187- 203. doi: 10.1061/TPEJAN.0000147
4	BABIC O , TEODOROVI C D , TOSIC V . Aircraft stand assignment to minimize walking[J]. Journal of Transportation Engineering, 1984, 110 (1): 55- 66. doi: 10.1061/(ASCE)0733-947X(1984)110:1(55)
5	MANGOUBI R S , MATHAISEL D F X . Optimizing gate assignments at airport terminals[J]. Transportation Science, 1985, 19 (2): 173- 188. doi: 10.1287/trsc.19.2.173
6	冯程, 胡明华, 赵征. 一种新的停机位分配优化模型[J]. 交通运输系统工程与信息, 2012, 12 (1): 131- 138. doi: 10.3969/j.issn.1009-6744.2012.01.020
	FENG C , HU M H , ZHAO Z . A new optimization model of airport gate assignment[J]. Journal of Transportation Systems Engineering and Information Technology, 2012, 12 (1): 131- 138. doi: 10.3969/j.issn.1009-6744.2012.01.020
7	JIANG Y , ZENG L Y , LUO Y X . Multiobjective gate assignment based on passenger walking distance and fairness[J]. Mathematical Problems in Engineering, 2013, 361031.
8	LIU S , CHEN W H , LIU J Y . Robust assignment of airport gates with operational safety constraints[J]. International Journal of Automation and Computing, 2016, 13 (1): 31- 41. doi: 10.1007/s11633-015-0914-x
9	KIM S H , FERON E . Robust gate assignment against gate conflicts[J]. Journal of Air Transportation, 2017, 25 (3): 87- 94. doi: 10.2514/1.D0067
10	YU C H , ZHANG D , LAU H Y . An adaptive large neighborhood search heuristic for solving a robust gate assignment problem[J]. Expert Systems with Applications, 2017, 84, 143- 154. doi: 10.1016/j.eswa.2017.04.050
11	王岩华, 朱金福, 朱博, 等. 繁忙机场机位分配的混合集合规划方法[J]. 武汉理工大学学报(信息与管理工程版), 2015, 37 (4): 427- 431. doi: 10.3963/j.issn.2095-3852.2015.04.009
	WANG Y H , ZHU J F , ZHU B , et al. Method of mixed set programming for gate assignment in busy airports[J]. Journal of Wuhan University of Technology (Information & Management Engineering), 2015, 37 (4): 427- 431. doi: 10.3963/j.issn.2095-3852.2015.04.009
12	TAN C M , HE J L . Robust airport gate assignment based on the analysis of flight arrival time[J]. Mathematical Problems in Engineering, 2021, 6693127.
13	刘君强, 张马兰, 陈鹏超, 等. 基于协同决策的多航站楼停机位实时分配算法[J]. 南京航空航天大学学报, 2015, 47 (1): 71- 76.
	LIU J Q , ZHANG M L , CHEN P C , et al. Real-time gate assignment algorithm of multi-terminal based on collaborative decision making mechanism[J]. Journal of Nanjing University of Aeronautics & Astronautics, 2015, 47 (1): 71- 76.
14	PTERNEA M , HAGHANI A . An aircraft-to-gate reassignment framework for dealing with schedule disruptions[J]. Journal of Air Transport Management, 2019, 78, 116- 132. doi: 10.1016/j.jairtraman.2019.01.005
15	BENLIC U , BURKE E K , WOODWARD J R . Breakout local search for the multi-objective gate allocation problem[J]. Computers and Operations Research, 2017, 78, 80- 93. doi: 10.1016/j.cor.2016.08.010
16	ZHU Y, LIM A, RODRIGUES B. Aircraft and gate scheduling with time windows[C]//Proc. of the IEEE 15th International Conference on Tools with Artificial Intelligence, 2003: 189-193.
17	DENG W , ZHAO H M , YANG X H , et al. Study on an improved adaptive PSO algorithm for solving multi-objective gate assignment[J]. Applied Soft Computing, 2017, 59, 288- 302. doi: 10.1016/j.asoc.2017.06.004
18	ZHANG D , KLABJAN D . Optimization for gate re-assignment[J]. Transportation Research Part B: Methodological, 2017, 95, 260- 284. doi: 10.1016/j.trb.2016.11.006
19	新起点. 航站楼扩增评估-v8最终稿[EB/OL]. [2022-08-30]. https://max.book118.com/html/2018/1219/7122135051001165.shtm.
	New Start. Terminal expansion evaluation-v8 final draft[EB/OL]. [2022-08-30]. https://max.book118.com/html/2018/1219/7122135051001165.shtm.
20	杨朋飞, 李婷, 汝洪武, 等. 机场新增卫星厅对登机口影响的评估方法[J]. 应用数学和力学, 2020, 41 (4): 448- 457.
	YANG P F , LI T , RU H W , et al. An evaluation method for impacts of a new satellite hall on boarding gates[J]. Applied Mathematics and Mechanics, 2020, 41 (4): 448- 457.
21	林闯, 陈莹, 黄霁崴, 等. 服务计算中服务质量的多目标优化模型与求解研究[J]. 计算机学报, 2015, 38 (10): 1907- 1923. doi: 10.11897/SP.J.1016.2015.01907
	LIN C , CHEN Y , HUANG J W , et al. A survey on models and solutions of multi-objective optimization for QoS in services computing[J]. Chinese Journal of Computers, 2015, 38 (10): 1907- 1923. doi: 10.11897/SP.J.1016.2015.01907
22	XU L , ZHANG C , XIAO F , et al. A robust approach to airport gate assignment with a solution-dependent uncertainty budget[J]. Transportation Research Part B, 2017, 105, 458- 478. doi: 10.1016/j.trb.2017.09.013
23	徐克虎, 孔德鹏, 黄大山, 等. 智能计算方法及其应用[M]. 北京: 国防工业出版社, 2019.
	XU K H , KONG D P , HUANG D S , et al. Intelligent computing method and its application[M]. Beijing: National Defense Industry Press, 2019.
24	YAN S Y , TANG C H , HOU Y Z . Airport gate reassignments considering deterministic and stochastic flight departure/arrival times[J]. Journal of Advanced Transportation, 2011, 45 (4): 304- 320. doi: 10.1002/atr.141
25	PTERNEA M , HAGHANI A . Mathematical models for flight-to-gate reassignment with passenger flows: state-of-the-art comparative analysis, formulation improvement, and a new multidimensional assignment model[J]. Computers & Industrial Engineering, 2018, 123, 103- 118.
26	李云鹏, 张则强, 管超, 等. 停机位分配问题的整数规划模型及启发式求解方法[J]. 系统工程, 2020, 38 (1): 103- 112.
	LI Y P , ZHANG Z Q , GUAN C , et al. Integer programming model and heuristic method for gate assignment problem[J]. Systems Engineering, 2020, 38 (1): 103- 112.
27	蒋洪讯, 马仁义. 面向靠桥率及道口冲突率的航班-机位指派问题优化模型及其启发式算法研究[J]. 系统科学与数学, 2021, 41 (1): 75- 98.
	JIANG H X , MA R Y . Rates of closed-bridge and crossing-collision oriented optimization model on aircraft-gate assignment and its heuristics[J]. Journal of Systems Science and Mathematical Sciences, 2021, 41 (1): 75- 98.
28	GHAZOUANI H, HAMMAMI M, KORBAA O. Solving airport gate assignment problem using genetic algorithms approach[C]//Proc. of the IEEE 4th International Conference on Advanced Logistics and Transport, 2015: 175-180.
29	RUDOLPB G . Convergence analysis of canonical genetic algorithms[J]. IEEE Trans.on Neural Networks, 1994, 5 (1): 96- 101. doi: 10.1109/72.265964
30	SRINIVAS M , PATNAIK L M . Adaptive probabilities of crossover and mutation in genetic algorithms[J]. IEEE Trans.on Systems, Man and Cybernetics, 1994, 24 (4): 656- 667. doi: 10.1109/21.286385
31	董兵, 吴郑源, 赖桂瑾, 等. 具有卫星厅的机场航站楼登机口分配研究[J]. 科学技术与工程, 2020, 20 (18): 7545- 7551.
	DONG B , WU Z Y , LAI G J , et al. Research on gate allocation of airport terminal with satellite hall[J]. Science Technology and Engineering, 2020, 20 (18): 7545- 7551.

转场编号	到达航班	出发航班	到达类型	出发类型	机体类别	到达时间	出发时间
PK173	GN0541	GN0480	D	D	N	2018/1/19 22:00	2018/1/20 6:40
PK174	NV6405	NV3280	D	D	N	2018/1/19 22:00	2018/1/20 9:55
PK175	GN0489	GN0282	D	D	N	2018/1/19 22:05	2018/1/20 7:30

旅客编号	乘客数	到达航班	到达日期	出发航班	出发日期
T3123	2	NV6737	2018/1/20	NV880	2018/1/21
T3124	2	NV6737	2018/1/20	NV880	2018/1/21
T3125	1	NV6737	2018/1/20	NV880	2018/1/21

登机口	终端厅	区域	到达类型	出发类型	机体类别
T9	T	North	D, I	D	N
T10	T	Center	D	D	N

算法模型	成功分配航班数量/架次	宽体机分配成功率/%	窄体机分配成功率/%
先到先分配	478	74.59	78.04
贪婪算法	502	81.24	85.13
禁忌搜索算法	510	100.00	81.10
贪婪-遗传算法	524	83.67	87.01

算法模型	登机口使用数量/个	T登机口平均使用率/%	S登机口平均使用率/%
先到先分配	69	64.76	46.72
贪婪算法	69	63.56	49.18
禁忌搜索算法	64	57.40	61.00
贪婪-遗传算法	67	61.09	56.22