Arrival flights optimal sequencing with multi-path selection based on rolling horizon control
-
摘要:
进场航班排序优化是提高进场航班着落效率、减少航班延误的有效方法。基于此,以最大化着落效率为目标,结合多跑道、多航路选择,考虑实际航路点限制,提出了多路径多跑道一体化进场航班排序优化混合整数规划模型。为解决大规模航班排序计算的实时性问题,提出了多航路点滚动时域控制算法。以广州白云国际机场终端区为实例进行验证,采用实际进场航班数据开展计算实验,在尾流安全间隔上,采用RECAT-CN运行标准,计算结果表明:小规模航班架次时(23架),所提模型最大降落时间比先到先服务方法提前55 s,比未优化时提前271 s;大规模航班架次时(104架),仅靠求解器在3600 s内未找到可行解,所提算法在128.65 s找到解。所提模型和算法有效,可应用于实际航班排序优化。
Abstract:Arrival flight sequencing is an effective strategy to improve landing efficiency and reduce flight delays. On the basis of previous research, this paper aims to minimize the makespan of all flights landing, considers actual multi-waypoint constraints, and proposes a path and runway integrated model, in which runway and path assignment can be achieved simultaneously based on real constraints. In order to solve the model under large-scale conditions in real-time, a multi-way point rolling horizon control algorithm is proposed. In the verification part, we take the Guangzhou Baiyun International Airport terminal area as the background and use the actual arrival data to carry out the calculation experiment. In the wake safety interval, we adopt a more detailed RECAT-CN operating standard. Based on the data from the 23 flights, the computational findings demonstrate that the presented methodology reduces wait times by 271 seconds and 55 seconds when compared to first-come, first-served and natural sequencing, respectively. Using the data of 104 flights to test the solving ability, the computational results show the solving time is 128.65 seconds with the proposed algorithm while no feasible solution is found within 3600 seconds by solver. It will state the proposed model and algorithm works well and could be used in real sequencing.
-
前机 后机 J B C M L J MRS 9.3 11.1 13.0 14.8 B MRS 5.6 7.4 9.3 13.0 C MRS MRS MRS 6.5 11.1 M MRS MRS MRS MRS 9.3 L MRS MRS MRS MRS MRS 表 2 进近航路飞行路线
Table 2. Approach routes of flight path
走廊口 航路编号 进场航路 GYA 1 GYA—AGVOS—GG404—GG401—01 2 GYA—AGVOS—GG404—GG407—GG403—02R IGONO 3 IGONO—GG442—TAN—AGVOS—GG404—GG401—01 4 IGONO—GG442—TAN—AGVOS—GG404—GG407—GG403—02R 5 IGONO—GG442—CON—CEN—GG408—GG407—GG401—01 6 IGONO—GG442—CON—CEN—GG408—GG407—GG403—02R ATAGA 7 ATAGA—GG428—TAN—AGVOS—GG404—GG401—01 8 ATAGA—GG428—TAN—AGVOS—GG404—GG407—GG403—02R 9 ATAGA—GG428—CON—CEN—GG408—GG407—GG401—01 10 ATAGA—GG428—CON—CEN—GG408—GG407—GG403—02R P270 11 P270—SHL—CEN—GG408—GG407—GG401—01 12 P270—SHL—CEN—GG408—GG407—GG403—02R IDUMA 13 IDUMA—SHL—CEN—GG408—GG407—GG401—01 14 IDUMA—SHL—CEN—GG408—GG407—GG403—02R 表 3 模型求解结果对比
Table 3. Comparison of model solution results
航班序号 机型 到走廊口时间/s 走廊口 航班降落时间/s 优化前 FCFS MILP 1 M 0 GYA 955 955 1420 2 M 40 IGONO 1372 1668 1372 3 M 215 IGONO 1547 1738 1772 4 M 249 IGONO 1655 1786 1 930 5 M 349 ATAGA 1 835 1 871 2 026 6 M 374 GYA 1 943 2055 1497 7 M 404 IGONO 1 991 2125 2096 8 M 514 IDUMA 2099 2173 1 978 9 B 549 ATAGA 2147 2243 2319 10 B 564 IGONO 2207 2309 2385 11 M 708 GYA 2256 2370 2144 12 M 719 ATAGA 2364 2418 2205 13 M 858 GYA 2472 2466 2433 14 B 1033 IDUMA 2520 2536 2253 15 M 1038 IGONO 2629 2645 2740 16 M 1068 GYA 2677 2715 2670 17 M 1218 IGONO 2737 2829 2880 18 B 1448 ATAGA 2934 2899 2976 19 M 1512 GYA 3043 2947 2810 20 B 1597 IGONO 3091 2995 3097 21 M 1602 IGONO 3200 3104 3049 22 B 1647 P270 3308 3152 2928 23 B 1762 IGONO 3416 3200 3145 表 4 Gurobi求解器与MWRHC算法结果对比
Table 4. Comparison of algorithm results between Gurobi solver and MWRHC
时段/h 航班
数量目标值/s 计算时间/s Gurobi
求解器MWRHC
算法Gurobi
求解器MWRHC
算法0~0.5 23 3145 3145 51.38 17.95 0~1 41 4917 4917 118.25 27.60 0~1.5 60 6736 6736 383.13 52.31 0~2 77 8559 8559 1697.72 74.20 0~2.5 88 10124 10124 3329.26 77.66 0~3 104 11971 3600 128.65 -
[1] BEASLEY J E, KRISHNAMOORTHY M, SHARAIHA Y M, et al. Scheduling aircraft landings: The static case[J]. Transportation Science, 2000, 34(2): 180-197. doi: 10.1287/trsc.34.2.180.12302 [2] MESGARPOUR M, POTTS C N, BENNELL J A. Models for aircraft landing optimization[C]//Proceedings of the International Conference on Research in Air Transportation. Budapest: ICRAT, 2010: 529-532. [3] HANCERLIOGULLARI G, RABADI G, AL-SALEM A H, et al. Greedy algorithms and metaheuristics for a multiple runway combined arrival-departure aircraft sequencing problem[J]. Journal of Air Transport Management, 2013, 32: 39-48. doi: 10.1016/j.jairtraman.2013.06.001 [4] GHONIEM A, SHERALI H D, BAIK H. Enhanced models for a mixed arrival-departure aircraft sequencing problem[J]. INFORMS Journal on Computing, 2014, 26(3): 514-530. doi: 10.1287/ijoc.2013.0581 [5] FURINI F, KIDD M P, PERSIANI C A, et al. State space reduced dynamic programming for the aircraft sequencing problem with constrained position shifting[C]//Proceedings of the International Symposium on Combinatorial Optimization. Berlin: Springer, 2014: 267-279. [6] WU Y, SUN L G, QU X J. A sequencing model for a team of aircraft landing on the carrier[J]. Aerospace Science and Technology, 2016, 54: 72-87. doi: 10.1016/j.ast.2016.04.007 [7] MUKHERJEE A, HANSEN M. A dynamic rerouting model for air traffic flow management[J]. Transportation Research Part B:Methodological, 2009, 43(1): 159-171. doi: 10.1016/j.trb.2008.05.011 [8] 张启钱, 胡明华, 施赛锋, 等. 多跑道航班起降调度优化算法[J]. 交通运输工程学报, 2012, 12(6): 63-68. doi: 10.3969/j.issn.1671-1637.2012.06.010ZHANG Q Q, HU M H, SHI S F, et al. Optimization algorithm of flight takeoff and landing on multi-runways[J]. Journal of Traffic and Transportation Engineering, 2012, 12(6): 63-68(in Chinese). doi: 10.3969/j.issn.1671-1637.2012.06.010 [9] SAMA M, D’ARIANO A, D’ARIANO P, et al. Optimal aircraft scheduling and routing at a terminal control area during disturbances[J]. Transportation Research Part C:Emerging Technologies, 2014, 47: 61-85. doi: 10.1016/j.trc.2014.08.005 [10] 徐肖豪, 于跃, 黄宝军, 等. 基于ISWO的机场进离场航班优化排序研究[J]. 计算机仿真, 2014, 31(7): 63-67. doi: 10.3969/j.issn.1006-9348.2014.07.015XU X H, YU Y, HUANG B J, et al. Research on arrival and departure sequencing based on ISWO[J]. Computer Simulation, 2014, 31(7): 63-67(in Chinese). doi: 10.3969/j.issn.1006-9348.2014.07.015 [11] DIAO X, CHEN C H. A sequence model for air traffic flow management rerouting problem[J]. Transportation Research Part E: Logistics and Transportation Review, 2018, 110: 15-30. doi: 10.1016/j.tre.2017.12.002 [12] 张兆宁, 刘珂璇. 基于替代航路的进场航班排序优化方法[J]. 数学的实践与认识, 2019, 49(12): 191-198.ZHANG Z N, LIU K X. Arrival sequencing method based on alternative routes[J]. Mathematics in Practice and Theory, 2019, 49(12): 191-198(in Chinese). [13] 郭野晨风, 胡明华, 张颖, 等. 改进的协同航路分配优化模型及算法研究[J]. 交通运输系统工程与信息, 2020, 20(6): 226-232. doi: 10.16097/j.cnki.1009-6744.2020.06.030GUO Y C F, HU M H, ZHANG Y, et al. Improved model and algorithm for optimizing collaborative trajectory options program[J]. Journal of Transportation Systems Engineering and Information Technology, 2020, 20(6): 226-232(in Chinese). doi: 10.16097/j.cnki.1009-6744.2020.06.030 [14] 田文, 杨帆, 尹嘉男, 等. 航路时空资源分配的多目标优化方法[J]. 交通运输工程学报, 2020, 20(6): 218-226. doi: 10.19818/j.cnki.1671-1637.2020.06.019TIAN W, YANG F, YIN J N, et al. Multi-objective optimization method of air route space-time resources allocation[J]. Journal of Traffic and Transportation Engineering, 2020, 20(6): 218-226(in Chinese). doi: 10.19818/j.cnki.1671-1637.2020.06.019 [15] 张军峰, 游录宝, 周铭, 等. 基于点融合系统的多目标进场排序与调度[J]. 北京航空航天大学学报, 2023, 49(1): 66-73.ZHANG J F, YOU L B, ZHOU M, et al. Multi-objective arrival sequencing and scheduling based on point merge system[J]. Journal of Beijing University of Aeronautics and Astronautics, 2023, 49(1): 66-73(in Chinese). [16] 乐美龙, 李星灿, 高金敏. 机场到达时刻数量决策随机模型[J]. 系统工程理论与实践, 2017, 37(11): 2948-2954. doi: 10.12011/1000-6788(2017)11-2948-07LE M L, LI X C, GAO J M. Stochastic model of determining airport arrival slots number[J]. Systems Engineering-Theory & Practice, 2017, 37(11): 2948-2954(in Chinese). doi: 10.12011/1000-6788(2017)11-2948-07 [17] ZHANG Q, LE M L, XU Y. Collaborative delay management towards demand-capacity balancing within user driven prioritisation process[J]. Journal of Air Transport Management, 2021, 91: 102017. doi: 10.1016/j.jairtraman.2020.102017 [18] 王湛, 吴艺. 基于FS-MOPSO的多机场终端区协同航班调度策略[J]. 西南交通大学学报, 2017, 52(1): 179-185. doi: 10.3969/j.issn.0258-2724.2017.01.025WANG Z, WU Y. Collaborative aircrafts scheduling strategy in metroplex terminal area based on FS-MOPSO[J]. Journal of Southwest Jiaotong University, 2017, 52(1): 179-185(in Chinese). doi: 10.3969/j.issn.0258-2724.2017.01.025 [19] 张建同, 杨文娟. 基于优先级的进离港航班排序优化问题研究[J]. 运筹与管理, 2018, 27(6): 115-121.ZHANG J T, YANG W J. The optimization based on priority for a mixed arrival-departure aircraft sequencing problem[J]. Operations Research and Management Science, 2018, 27(6): 115-121(in Chinese). [20] 中国民航网. 航空器尾流重新分类: 突破限制, 提升效率[EB/OL]. (2019-02-28) [2022-03-01]. http://www.caacnews.com.cn/1/3/201902/t20190228_1268076.html.CAAC News. Aircraft wake reclassification: Breaking through limitations and improving efficiency [EB/OL] (2019-02-28) [2023-03-01]. http://www.caacnews.com.cn/1/3/201902/t20190228_1268076.html(in Chinese). [21] HU X B, CHEN W H. Receding horizon control for aircraft arrival sequencing and scheduling[J]. IEEE Transactions on Intelligent Transportation Systems, 2005, 6(2): 189-197. doi: 10.1109/TITS.2005.848365