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

doi:10.3976/j.issn.1002-4026.20230167

山东科学 ›› 2024, Vol. 37 ›› Issue (2): 104-116.doi: 10.3976/j.issn.1002-4026.20230167

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

刘海滨¹(), 王炬博², 巴博圣², 王瑞昕²^,^*()

1.中国民用航空华北地区空中交通管理局天津分局,天津 300300
2.中国民航大学中欧航空工程师学院,天津 300300

收稿日期:2023-11-08 出版日期:2024-04-20 发布日期:2024-04-09
通信作者: *王瑞昕,讲师,研究方向为应用数学。Tel:13752227285,E-mail:rxwang@cauc.edu.cn
作者简介:刘海滨(1973—),硕士,工程师,研究方向为交通运输。E-mail:13820796935@163.com
基金资助:
中央高校基本科研业务费项目(3122021084);天津市应用基础研究多元投入基金(21JCQNJC00790);国家自然科学基金(72301278)

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

LIU Haibin¹(), WANG Jubo², BA Bosheng², WANG Ruixin²^,^*()

1. Tianjin Sub-bureau of North China Regional Air Traffic Management Bureau,CAAC,Tianjin 300300,China
2. Sino-European Institute of Aviation Engineering,Civil Aviation University of China,Tianjin 300300,China

Received:2023-11-08 Online:2024-04-20 Published:2024-04-09

摘要/Abstract

摘要：

为了提升机场停机坪分配的鲁棒性,针对大型国际机场航班延误常态化对机场运行稳定性的影响,构建了两种整数线性规划模型,并引入爬山算法与大邻域搜索(LNS)元启发式算法进行效能比较。同时,采用Monte Carlo方法对不同目标函数在处理航班冲突时的效果进行评估。测试结果表明LNS算法在提升大型机场停机位分配方案的鲁棒性方面表现卓越,在求解速度和方案质量上均有显著提升。特别是,当以空闲时间的平方作为目标函数时,其效果尤为突出。

关键词: 停机位分配, 固定作业问题, 机场, 组合优化, 大邻域搜索, 线性规划

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

中图分类号:

刘海滨, 王炬博, 巴博圣, 王瑞昕. 基于鲁棒性模拟的停机位分配问题的数值方法比较[J]. 山东科学, 2024, 37(2): 104-116.

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.

图/表 10

表1

模型符号说明"

符号	定义
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的兼容航班集合

表1

图1

图2

表2

图3

图4

图5

图6

图7

图8

参考文献 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)

赞

可视化

摘要/Abstract

引用本文

使用本文

图/表 10

参考文献 15

相关文章 7

Metrics

本文评价

推荐阅读 0

[1]	杨安安, 韩星玉, 田旷, 刘泽远, 明玮. 基于Stacking集成学习的机场线短时客流预测研究[J]. 山东科学, 2024, 37(4): 112-120.
[2]	杨君, 牟建良, 袁小婷, 唐铁桥, 牟宣宇. 基于旅客流量的机场广告位价值评估模型[J]. 山东科学, 2024, 37(3): 103-110.
[3]	张仪果, 屈云超, 尹浩东, 吴建军. 轨道交通封站条件下应急疏散车辆路径优化[J]. 山东科学, 2023, 36(4): 80-88.
[4]	刘杨, 杨得用, 何昕, 孙强. 基于改进群组层次分析法的机场II/III类运行效益影响因素研究[J]. 山东科学, 2023, 36(1): 90-98.
[5]	雷继超, 种小雷, 张世迪, 于庆坤, 龙小勇. 基于重力p-median模型的支线机场物资供应中心选址[J]. 山东科学, 2020, 33(4): 91-100.
[6]	张芳军，郑建风，任华玲. 班轮航线设计与空箱调运研究：箱种代用[J]. 山东科学, 2014, 27(4): 68-74.
[7]	董升伟,贾元华,赵雪静. 基于改进蚁群算法的集装箱装卸顺序优化研究[J]. J4, 2012, 25(5): 92-97.