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

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

Abstract

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

CLC Number:

V351.1

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.

Figures/Tables 15

Fig.1

Table 1

Fig.2

Fig.3

Fig.4

Fig.5

Table 2

Table 3

Table 4

Fig.6

Fig.7

Fig.8

Table 5

Table 6

Table 7

References 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

Airport gate assignment strategy based on greedy-genetic algorithm

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 15

References 31

Related Articles 15

Recommended Articles

Metrics

Comments

出行状态		国内出发		国际出发
出行状态		T	S	T	S
国内到达	T	15	20	35	40
国内到达	S	20	15	40	35
国际到达	T	35	40	20	30
国际到达	S	40	45	30	20

算法模型	总体最短流程时间
先到先分配	75 170
贪婪算法	69 755
禁忌搜索算法	64 735
贪婪-遗传算法	63 156

[1]	Yong DENG, Feng YAO, Lining XING, Lei HE. Inter-satellite data transmission method in satellite network based on hybrid evolutionary algorithm [J]. Systems Engineering and Electronics, 2023, 45(9): 2931-2940.
[2]	Weining MA, Qiwei HU, Wenbin CAO, Xisheng JIA. Equipment selective maintenance decision optimization considering maintenance task assignment [J]. Systems Engineering and Electronics, 2023, 45(6): 1902-1910.
[3]	Kexin BI, Minggong WU, Xiangxi WEN, Wenbin ZHANG, Wenda YANG. Conflict resolution strategy based on flight conflict network and genetic algorithm [J]. Systems Engineering and Electronics, 2023, 45(5): 1429-1440.
[4]	Xiaofeng LYU, Dongze YANG, Ling MA. Optimal design of modular ammunition scheduling scheme for carrier-based aircraft [J]. Systems Engineering and Electronics, 2023, 45(2): 465-471.
[5]	Lu ZHUANG, Zhong LU, Haijing SONG, Jia ZHOU. An optimization method for development assurance level assignment of airborne system [J]. Systems Engineering and Electronics, 2022, 44(8): 2688-2698.
[6]	Tiansu LUO, Lingfeng ZHAO, Yunwen FENG, Xiaofeng XUE, Cheng LU. Super large-scale satellite constellation multi-level backup strategy based on METRIC theory [J]. Systems Engineering and Electronics, 2022, 44(7): 2181-2190.
[7]	Bo LI, Jiahao ZHOU, Minmin LIU, Pinchao ZHU. Feature selection for welding defect assessment based on improved NSGA3 [J]. Systems Engineering and Electronics, 2022, 44(7): 2211-2218.
[8]	Haobo FENG, Qiao HU, Zhenyi ZHAO. AUV swarm path planning based on elite family genetic algorithm [J]. Systems Engineering and Electronics, 2022, 44(7): 2251-2262.
[9]	Shaolong YANG, Jin HUANG, Xianbo XIANG, Weichao LI. Optimization of USV area coverage path planning based on confidence ellipsoid [J]. Systems Engineering and Electronics, 2022, 44(7): 2263-2269.
[10]	Yunwen FENG, Junyu CHEN, Cheng LU. Research on civil aircraft spare parts multi-region support network model [J]. Systems Engineering and Electronics, 2022, 44(5): 1553-1561.
[11]	Peng JIN, Xiaoxi TANG. Multi-satellite emergency task scheduling with merging mechanism [J]. Systems Engineering and Electronics, 2022, 44(4): 1270-1281.
[12]	Jianwei SUN, Chao WANG, Qingzhan SHI, Wenbo REN, Zekun YAO, Naichang YUAN. Intelligent optimization of phase-modulation waveform based on genetic algorithm [J]. Systems Engineering and Electronics, 2022, 44(3): 722-729.
[13]	Naiyang XUE, Dan DING, Hongmin WANG, Buhua LIU. Multi-type TT&C resource scheduling method based on improved genetic algorithm [J]. Systems Engineering and Electronics, 2021, 43(9): 2535-2543.
[14]	Luda ZHAO, Bin WANG, Wei ZENG. Three-level programming model of electronic countermeasures force requirements in offensive combat [J]. Systems Engineering and Electronics, 2021, 43(6): 1564-1571.
[15]	Li WANG, Ziqi LIU. Fault diagnosis of analog circuit for WPA-IGA-BP neural network [J]. Systems Engineering and Electronics, 2021, 43(4): 1133-1143.