基于鲁棒性模拟的停机位分配问题的数值方法比较

doi:10.3976/j.issn.1002-4026.20230167

Abstract

Abstract:

Frequent delays of flights at large international airports can affect their smooth operation, hence, the airport apron allocation problem needs to be robustly optimized. In this study, we proposed two integer linear-programing models for solving this problem and used two algorithms for performance comparison: the hill-climbing and large-neighborhood search (LNS) metaheuristic algorithms. In addition, we used the Monte Carlo method to evaluate the effectiveness of different objective functions in dealing with flight conflicts. The final test results show that the LNS algorithm not only improves the robustness of the gate allocation scheme for large airports but also excels in speed and quality, especially, when the square of idle time is used as the objective function.

Key words: gate allocation, fixed job problem, airport, combinatorial optimization, large-neighborhood search, linear programing

CLC Number:

LIU Haibin, WANG Jubo, BA Bosheng, WANG Ruixin. A numerical comparison of methods for solving the gate allocation problem based on robustness simulation[J].Shandong Science, 2024, 37(2): 104-116.

Figures/Tables 10

Table 1

Description of model symbols"

符号	定义
n	需要分配的航班数量
m	可用停机位数量
F={f₁,…,f_n}	n个航班的集合
$f s i$ ,f_i∈F	航班f_i占用停机位的开始时间
$f e i$ ,f_i∈F	航班f_i占用停机位的结束时间
G_i⊆G	可分配给航班f_i的兼容停机位集合
G={g₁,…,g_m}	m个停机位的集合
$g s i$ ,g_i∈G	停机位i占用开始时间。本文考虑所有停机位都在同一时间g^s开放
$g e i$ ,g_i∈G	停机位i占用结束时间。本文考虑所有停机位都在同一时间g^e关闭
F_k⊆F	可分配到停机位g_k的兼容航班集合

Table 1

Fig.1

Fig.2

Table 2

Fig.3

Fig.4

Fig.5

Fig.6

Fig.7

Fig.8

References 15

[1]	GUPTA U I, LEE D T, LEUNG J Y T. Efficient algorithms for interval graphs and circular-arc graphs[J]. Networks, 1982, 12(4): 459-467. DOI: 10.1002/net.3230120410.
[2]	HUJTER M, TUZA Z. Precoloring extension. IV. general bounds and list colorings[EB/OL]. [2023-11-01]. http://arxiv.org/abs/2104.01007.pdf.
[3]	BOLAT A. Assigning arriving flights at an airport to the available gates[J]. Journal of the Operational Research Society, 1999, 50(1): 23-34. DOI: 10.1057/palgrave.jors.2600655.
[4]	BOLAT A. Models and a genetic algorithm for static aircraft-gate assignment problem[J]. Journal of the Operational Research Society, 2001, 52(10): 1107-1120. DOI: 10.1057/palgrave.jors.2601190.
[5]	WANG R X, ALLIGNOL C, BARNIER N, et al. Departure management with robust gate allocation[C]// ATM 2019, 13th USA/Europe Air Traffic Management Research and Development Seminar. Vienna,Austra:ATM, 2019: hal-02090426.
[6]	WANG R X, ALLIGNOL C, BARNIER N, et al. A new multi-commodity flow model to optimize the robustness of the gate allocation problem[J]. Transportation Research Part C: Emerging Technologies, 2022, 136: 103491. DOI: 10.1016/j.trc.2021.103491.
[7]	JAEHN F. Solving the flight gate assignment problem using dynamic programming[J]. Zeitschrift Für Betriebswirtschaft, 2010, 80(10): 1027-1039. DOI: 10.1007/s11573-010-0396-9.
[8]	BI J, WANG F J, DING C, et al. The airport gate assignment problem: a branch-and-price approach for improving utilization of jetways[J]. Computers & Industrial Engineering, 2022, 164: 107878. DOI: 10.1016/j.cie.2021.107878.
[9]	JIANG Y, HU Z T, LIU Z Y, et al. Optimization of multi-objective airport gate assignment problem: considering fairness between airlines[J]. Transportmetrica B: Transport Dynamics, 2023, 11(1): 196-210. DOI: 10.1080/21680566.2022.2056542.
[10]	DING H, LIM A, RODRIGUES B, et al. The over-constrained airport gate assignment problem[J]. Computers & Operations Research, 2005, 32(7): 1867-1880. DOI: 10.1016/j.cor.2003.12.003.
[11]	YU C H, ZHANG D, LAU H Y K. 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.
[12]	CASTAING J, MUKHERJEE I, COHN A, et al. Reducing airport gate blockage in passenger aviation[J]. Computers and Operations Research, 2016, 65(C): 189-199. DOI: 10.1016/j.cor.2014.02.011.
[13]	SÖLVELING G. Stochastic programming methods for scheduling of airport runway operations under uncertainty[M]. Georgia Institute of Technology, 2012.
[14]	PÉREZ-RODRÍGUEZ J V, PÉREZ-SÁNCHEZ J M, GÓMEZ-DÉNIZ E. Modelling the asymmetric probabilistic delay of aircraft arrival[J]. Journal of Air Transport Management, 2017, 62: 90-98. DOI: 10.1016/j.jairtraman.2017.03.001.
[15]	BENLIC U, BURKE E K, WOODWARD J R. Breakout local search for the multi-objective gate allocation problem[J]. Computers & Operations Research, 2017, 78: 80-93. DOI: 10.1016/j.cor.2016.08.010.

航站楼	航班数	停机位数	平均航班数	占用率
2A	46.9	17	2.8	27.7%
2B	15.3	10	1.5	17.4%
2C	21.2	14	1.5	16.5%
2D	83.4	18	4.6	36.3%
2E	101.6	23	4.4	49.4%
2F	184.2	27	6.8	63.4%
2J	71.5	20	3.6	32.3%
2M	12.6	10	1.3	17.1%
2Q	52.0	17	3.1	27.2%
2R	11.3	12	0.9	14.3%

A numerical comparison of methods for solving the gate allocation problem based on robustness simulation

RichHTML

PDF (PC)

Like

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 10

References 15

Related Articles 3

Metrics

Comments

Recommended 0

[1]	LIU Yang, YANG Deyong, HE Xin, SUN Qiang. Research on factors influencing airport Category II/III operation benefit based on improved group analytic hierarchy process [J]. Shandong Science, 2023, 36(1): 90-98.
[2]	LEI Ji-chao, CHONG Xiao-lei, ZHANG Shi-di, YU Qing-kun, LONG Xiao-yong. Location of regional airport supply center based on gravity p-median model [J]. Shandong Science, 2020, 33(4): 91-100.
[3]	DONG Sheng-Wei, JIA Yuan-Hua, ZHAO Xue-Jing. Research on improved Ant Colony Algorithm based optimization of container handling sequence problem [J]. J4, 2012, 25(5): 92-97.