基于Epsilon约束列生成的机场停机位应急调整

朱少川; 郑磊; 杜文博

doi:10.13700/j.bh.1001-5965.2024.0419

基于Epsilon约束列生成的机场停机位应急调整

doi: 10.13700/j.bh.1001-5965.2024.0419

朱少川^{1, 2},
郑磊^{1, 2},
杜文博^{1, 2, ,}

1.
北京航空航天大学电子信息工程学院，北京 100191
2.
北京航空航天大学空地一体新航行系统技术全国重点实验室，北京 100191

基金项目:

国家自然科学基金(U2333218)

详细信息

通讯作者:
E-mail：wenbodu@buaa.edu.cn

中图分类号: V351
计量
- 文章访问数: 212
- HTML全文浏览量: 85
- PDF下载量: 13
- 被引次数: 0
出版历程
- 收稿日期: 2024-06-12
- 录用日期: 2024-07-12
- 网络出版日期: 2024-08-05
- 整期出版日期: 2026-07-31

An Epsilon constraint-based column generation for airport gate emergency reassignment

ZHU Shaochuan^{1, 2},
ZHENG Lei^{1, 2},
DU Wenbo^{1, 2
, ,}

1.
School of Electronic Information and Engineering，Beihang University，Beijing 100191，China
2.
State Key Laboratory of CNS/ATM，Beihang University，Beijing 100191，China

Funds:

National Natural Science Foundation of China (U2333218)

More Information

Corresponding author: E-mail：wenbodu@buaa.edu.cn

摘要

摘要:
停机位分配方案直接影响航班运行效率和机场服务水平。在实际运行中，场面事故等突发事件常导致局部停机位临时关闭，计划分配方案失效，亟需开展资源受限条件下的停机位应急调整。为此，提出Epsilon约束列生成优化算法，旨在生成兼顾稳定性和效率的调整方案。构建基于集分割的双目标优化模型，最小化计划扰动的同时，最大化调整偏好，保证航班调整的公平性；提出基于Epsilon约束的列生成启发式，快速获取高质量分配方案；基于某国际机场的运行数据设计了数值实验。结果表明：所提方法在受扰航班靠桥率和受扰航班跨区调整比例等指标上均有较好的表现，受扰航班跨区调整比例为52.34%，显著低于其他方法，有效提高了应急场景下机场停机位的调度效率。
- 机场停机位 /
- 资源分配 /
- 应急调整 /
- Epsilon约束法 /
- 列生成
Abstract:
The effectiveness of flight operations and the quality of airport services are directly impacted by airport gate assignment options. In real-world operations, unexpected events such as airfield accidents may lead to the temporary closure of local gates and an infeasible assignment plan. It is urgent to implement gate emergency reassignment under resource constraints. This paper proposes an Epsilon constraint-based column generation optimization algorithm for this problem. In particular, we develop a bi-objective optimization model based on set partitioning with the goal of minimizing assignment plan deviation and increasing solution efficiency. Then, an Epsilon constraint-based column generation optimization algorithm is designed to efficiently obtain high-quality solutions. Numerical experiments are conducted based on real-world operational data from an international airport. The results demonstrate that the proposed method performs well on main metrics such as the bridge boarding rate and flights adjustment efficiency. In particular, the cross-region adjustment proportion of our solution is 52.34%, which is significantly lower than the comparison methods, and effectively improves the airport operational efficiency in emergency scenarios.
- airport gates /
- resource allocation /
- emergency reassignment /
- Epsilon constraint /
- column generation

HTML全文

图 1 局部停机位关闭下的航班调整示意图

Figure 1. Schematic diagram of flight adjustments during partial stand closure

下载: 全尺寸图片幻灯片

图 2 停机位调整偏差示意图

Figure 2. The deviation diagram of gate adjustment

下载: 全尺寸图片幻灯片

图 3 停机位调整偏好示意图

Figure 3. The preference diagram of gate adjustment

下载: 全尺寸图片幻灯片

图 4 本文算法总体求解框架

Figure 4. Overall solution framework of the proposed algorithm

下载: 全尺寸图片幻灯片

图 5 3种方法的平均性能对比

Figure 5. Comparison of the average performance of three methods

下载: 全尺寸图片幻灯片

图 6 停机位关闭占比与受扰航班跨区调整比例的关系

Figure 6. Relationship between the proportion of closed gates and cross-region adjustment proportion of disturbed flight

下载: 全尺寸图片幻灯片

图 7 停机位关闭占比与正常航班延误比例的关系

Figure 7. Relationship between the proportion of closed gates and the rate of delayed flights

下载: 全尺寸图片幻灯片

图 8 不同参数ε下的方案性能

Figure 8. Solution performance in different ε parameters

下载: 全尺寸图片幻灯片

表 1 不同案例规模下的方案性能对比

Table 1. Comparison of solution performance in different case sizes

案例 (关闭停机位数量，受扰航班数量)	正常航班机位变更比例/%			受扰航班靠桥率/%			受扰航班跨区调整比例/%			eSEM计算时间/s
案例 (关闭停机位数量，受扰航班数量)	SM	SUM	eSEM	SM	SUM	eSEM	SM	SUM	eSEM	eSEM计算时间/s
C1(1,3)	0	0.99	0.50	0	100.00	100.00	100.00	66.67	66.67	19.3
C2(3,9)	0	2.55	0.51	0	100.00	100.00	100.00	66.67	77.78	21.6
C3(5,16)	0	4.23	2.12	0	100.00	100.00	100.00	81.25	50.00	23.6
C4(7,23)	0	5.49	2.75	13.04	100.00	100.00	100.00	95.65	60.87	27.7
C5(9,30)	0	6.29	4.00	16.67	96.67	100.00	100.00	86.67	50.00	23.4
C6(11,39)	0	7.23	4.82	17.95	89.74	97.44	92.31	82.05	46.15	32.2
C7(13,43)	0	10.49	7.41	18.60	93.02	95.35	95.35	83.72	44.19	26.3
C8(15,49)	0	9.62	8.33	10.20	81.63	93.88	100.00	87.76	53.06	26.8
C9(17,56)	0	9.40	10.07	21.43	73.21	87.50	98.21	85.71	41.07	36.3
C10(19,65)	0	14.29	12.14	18.46	75.38	86.15	92.31	81.54	36.92	35.8
C11(25,82)	0	13.01	13.01	10.98	57.32	70.73	97.56	82.93	46.34	38.5
C12(30,100)	0	14.29	10.48	11.00	49.00	57.00	97.00	87.00	55.00	37.1
注：加粗数字表示最优值。

下载: 导出CSV

参考文献(22)

[1]	Daş G S, Gzara F, Stützle T. A review on airport gate assignment problems: single versus multi objective approaches[J]. Omega, 2020, 92: 102146.
[2]	Cai X Y, Sun W X, Misir M, et al. A bi-objective constrained robust gate assignment problem: formulation, instances and algorithm[J]. IEEE Transactions on Cybernetics, 2021, 51(9): 4488-4500.
[3]	Du W B, Zhu S C, Tong L, et al. Robust gate assignment to minimise aircraft conflicts[J]. Transportmetrica B: Transport Dynamics, 2023, 11(1): 2185497.
[4]	寇伟彬, 于凯任, 王佳玉, 等. 韧性导向的机场航空器滑行路径及停机位分配联合优化[J]. 北京航空航天大学学报, 2026, 52(2): 426-435. Kou W B, Yu K R, Wang J Y, et al. Resilience-oriented joint optimization of aircraft taxiing route and apron assignment in airport[J]. Journal of Beijing University of Aeronautics and Astronautics, 2026, 52(2): 426-435(in Chinese).
[5]	Reid C. Catering vehicle smashes into lufthansa airbus A321 leaving parts stuck in fuselage[EB/OL]. (2024-01-14)[2024-06-05]. https://simpleflying.com/lufthansa-airbus-a321-catering-truck-collision.
[6]	张颖, 黎晓英, 尹嘉男, 等. 基于概率滑行时间的航空器离场推出柔性控制[J]. 航空学报, 2023, 44(10): 327452. Zhang Y, Li X Y, Yin J N, et al. Flexible control of aircraft departure pushback time based on probabilistic taxiing time[J]. Acta Aeronautica et Astronautica Sinica, 2023, 44(10): 327452(in Chinese).
[7]	Tang C H, Yan S Y, Hou Y Z. A gate reassignment framework for real time flight delays[J]. 4OR, 2010, 8(3): 299-318.
[8]	Maharjan B, Matis T I. An optimization model for gate reassignment in response to flight delays[J]. Journal of Air Transport Management, 2011, 17(4): 256-261.
[9]	Zhang D, Klabjan D. Optimization for gate re-assignment[J]. Transportation Research Part B: Methodological, 2017, 95: 260-284.
[10]	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.
[11]	Skorupski J, Żarów P. Dynamic management of aircraft stand allocation[J]. Journal of Air Transport Management, 2021, 90: 101964.
[12]	姜雨, 胡志韬, 童楚, 等. 面向航班延误的停机位实时指派优化模型[J]. 交通运输系统工程与信息, 2020, 20(5): 185-190. Jiang Y, Hu Z T, Tong C, et al. An optimization model for gate re-assignment under flight delays[J]. Journal of Transportation Systems Engineering and Information Technology, 2020, 20(5): 185-190(in Chinese).
[13]	Yu C H, Zhang D, Lau H Y K H. A heuristic approach for solving an integrated gate reassignment and taxi scheduling problem[J]. Journal of Air Transport Management, 2017, 62(C): 189-196.
[14]	Yan S Y, Chen C Y, Tang C H. Airport gate reassignment following temporary airport closures[J]. Transportmetrica, 2009, 5(1): 25-41.
[15]	Tang C H. A gate reassignment model for the Taiwan Taoyuan Airport under temporary gate shortages and stochastic flight delays[J]. IEEE Transactions on Systems, Man, and Cybernetics-Part A: Systems and Humans, 2011, 41(4): 637-650.
[16]	乐美龙, 檀财茂. 非正常运行下机场停机位实时分配模型[J]. 工业工程, 2014, 17(1): 12-16. Le M L, Tan C M. Research on the airport gate real-time allocation model in considering irregular operations[J]. Industrial Engineering Journal, 2014, 17(1): 12-16(in Chinese).
[17]	Poyraz D D, Azizoğlu M. An airport gate reassignment problem with gate closures[J]. Journal of Air Transport Management, 2024, 115: 102529.
[18]	Mavrotas G. Effective implementation of the ε-constraint method in multi-objective mathematical programming problems[J]. Applied Mathematics and Computation, 2009, 213(2): 455-465.
[19]	Desaulniers G, Desrosiers J, Solomon M M. Column generation[M]. Berlin: Springer, 2005.
[20]	Xiao F, Guo S Q, Huang L, et al. Integrated aircraft tail assignment and cargo routing problem with through cargo consideration[J]. Transportation Research Part B: Methodological, 2022, 162: 328-351.
[21]	Breugem T, Van Rossum B T C, Dollevoet T, et al. A column generation approach for the integrated crew re-planning problem[J]. Omega, 2022, 107: 102555.
[22]	中国民用航空局. 运输机场机坪运行管理规则: 民航规[2022]20号 (AP-140-CA-2022-07) [EB/OL]. (2022-06-15)[2024-06-05]. http://www.caac.gov.cn/XXGK/XXGK/GFXWJ/202207/t20220704_213952.html. Civil Aviation Administration of China. Administrative rules for apron operation and management of transport airports: CAAC regulations[2022] No. 20 (AP-140-CA-2022-07)[EB/OL]. (2022-06-15)[2024-06-05]. http://www.caac.gov.cn/XXGK/XXGK/GFXWJ/202207/t20220704_213952.html.