Citation: | JIANG Hao, LIU Jixin, DONG Xinfanget al. Dynamic collaborative sequencing for departure flights based on traffic state[J]. Journal of Beijing University of Aeronautics and Astronautics, 2022, 48(10): 2048-2060. doi: 10.13700/j.bh.1001-5965.2021.0066(in Chinese) |
To meet the needs for collaborative decision making (CDM), the dynamic collaborative sequencing of departure flights in both crowded and uncrowded scenarios was systematically studied with the demands of air traffic control units, airlines and airports being taken into consideration. With a deep analysis of the operation characteristics of departure flights, a dynamic sequencing method was designed based on scheduled off-block time (SOBT) and estimated off-block time (EOBT) data of the departure flights. Several optimization objectives of departure flight sequencing were set for each of the parties. Meanwhile, an evaluating indicator of airline delay fairness was proposed to ensure the sequencing fairness, the priority of uncontrolled departure flights was divided into three categories, the maximum acceptable delay time and maximum position offset were set for all categories of uncontrolled departure flights, and thus the collaborative sequencing model for departure flights based on traffic state was established. Further, a fast non-dominant sorting genetic algorithm with elite strategy (NSGA-Ⅱ) was designed to find the optimal solution to dynamic collaborative sequencing for departure flights. Simulation results show that, compared with first come first served (FCFS) method, the proposed method adds a variety of sequencing schemes in each sequencing stage in both scenarios, the total delay of departure flights is reduced by more than 50%, and the airline delay fairness is improved in uncrowded scenarios. The proposed method can optimize the sequencing of departure flights, significantly reduce flight delays, effectively improve fairness, and fit in with the concept of collaborative decision making, thus realizing tripartite collaborative sequencing.
[1] |
ATKIN J A D, BURKE E K, GREENWOOD J S, et al. Hybrid metaheuristics to aid runway scheduling at London heathrow airport[J]. Transportation Science, 2007, 41(1): 90-106. doi: 10.1287/trsc.1060.0163
|
[2] |
刘继新, 江灏, 董欣放, 等. 基于空中交通密度的进场航班动态协同排序方法[J]. 航空学报, 2020, 41(7): 323717. https://www.cnki.com.cn/Article/CJFDTOTAL-HKXB202007025.htm
LIU J X, JIANG H, DONG X F, et al. Dynamic collaborative sequencing method for arrival flights based on air traffic density[J]. Acta Aeronautica et Astronautica Sinica, 2020, 41(7): 323717(in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-HKXB202007025.htm
|
[3] |
ATKIN J A D, BURKE E K, GREENWOOD J S, et al. A metaheuristic approach to aircraft departure scheduling at London Heathrow airport[C]//HICKMAN M, MIRCHANDANI P, VOB S. Computer-aided systems in public transport. Berlin: Springer, 2008, 600: 235-252.
|
[4] |
ATKIN J A D, BURKE E K, GREENWOOD J S, et al. On-line decision support for take-off runway scheduling with uncertain taxi times at London Heathrow airport[J]. Journal of Scheduling, 2008, 11(5): 323-346. doi: 10.1007/s10951-008-0065-9
|
[5] |
BALAKRISHNAN H, CHANDRAN B G. Efficient and equitable departure scheduling in real-time: New approaches to old problems[C]//Proceedings of 7th USA/Europe Air Traffic Management Research and Development Seminar, 2007: 243-252.
|
[6] |
BALAKRISHNAN H, CHANDRAN B G. Algorithms for sche-duling runway operations under constrained position shifting[J]. Operations Research, 2010, 58(6): 1650-1665. doi: 10.1287/opre.1100.0869
|
[7] |
RATHINAM S, WOOD Z, SRIDHAR B, et al. A generalized dynamic programming approach for a departure scheduling pro-blem[C]//AIAA Guidance, Navigation, and Control Conference. Reston: AIAA, 2009: 6306-6317.
|
[8] |
MONTOYA J, RATHINAM S, WOOD Z. Multiobjective departure runway scheduling using dynamic programming[J]. IEEE Transactions on Intelligent Transportation Systems, 2014, 15(1): 399-413. doi: 10.1109/TITS.2013.2283256
|
[9] |
GUPTA G, MALIK W, JUNG Y. A mixed integer linear program for airport departure scheduling[C]//9th AIAA Aviation Technology, Integration, and Operations Conference(ATIO). Reston: AIAA, 2009: 6933.
|
[10] |
SU W B, PARK J, CLARKE J P. Modified mixed integer linear program for airport departure scheduling[C]//AIAA Gui-dance, Navigation, and Control Conference. Reston: AIAA, 2013: 4885.
|
[11] |
LIU M, SUN Z H, ZHANG X N, et al. A two-stage no-wait hybrid flow-shop model for the flight departure scheduling in a multi-airport system[C]//2017 IEEE 14th International Conference on Networking, Sensing and Control. Piscataway: IEEE Press, 2017: 495-500.
|
[12] |
SÖLVELING G, CLARKE J P. Scheduling of airport runway operations using stochastic branch and bound methods[J]. Transportation Research Part C: Emerging Technologies, 2014, 45: 119-137. doi: 10.1016/j.trc.2014.02.021
|
[13] |
王菲, 张军峰, 葛腾腾, 等. 基于分支定界的离场航空器动态排序[J]. 南京航空航天大学学报, 2015, 47(4): 547-552. https://www.cnki.com.cn/Article/CJFDTOTAL-NJHK201504011.htm
WANG F, ZHANG J F, GE T T, et al. Dynamic departure sequencing based on branch and bound algorithm[J]. Journal of Nanjing University of Aeronautics & Astronautics, 2015, 47(4): 547-552(in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-NJHK201504011.htm
|
[14] |
尹嘉男, 胡明华, 张洪海, 等. 独立离场模式下多跑道时空资源优化调度方法[J]. 航空学报, 2015, 36(5): 1574-1584. https://www.cnki.com.cn/Article/CJFDTOTAL-HKXB201505021.htm
YIN J N, HU M H, ZHANG H H, et al. Optimized method for multi-runway spatio-temporal resource scheduling in the mode of independent departures[J]. Acta Aeronautica et Astronautica Sinica, 2015, 36(5): 1574-1584(in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-HKXB201505021.htm
|
[15] |
ZHANG H F, HU M H. Optimization method for departure flight scheduling problem based on genetic algorithm[J]. Transactions of Nanjing University of Aeronautics and Astronautics, 2015, 32(4): 477-484. doi: 10.3969/j.issn.1005-1120.2015.04.016
|
[16] |
ZHONG H, GUAN W, ZHANG W Y, et al. A bi-objective integer programming model for partly-restricted flight departure scheduling[J]. PLoS One, 2018, 13(5): e0196146. doi: 10.1371/journal.pone.0196146
|
[17] |
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
|
[18] |
FAIRBROTHER J, ZOGRAFOS K G, GLAZEBROOK K D. A slot-scheduling mechanism at congested airports that incorporates efficiency, fairness, and airline preferences[J]. Transportation Science, 2020, 54(1): 115-138. doi: 10.1287/trsc.2019.0926
|
[19] |
DEAR R G, SHERIF Y S. An algorithm for computer assisted sequencing and scheduling of terminal area operations[J]. Transportation Research Part A: General, 1991, 25(2-3): 129-139. https://www.sciencedirect.com/science/article/pii/019126079190132A
|
[20] |
马园园, 胡明华, 张洪海, 等. 多机场终端区进场航班协同排序方法[J]. 航空学报, 2015, 36(7): 2279-2290. https://www.cnki.com.cn/Article/CJFDTOTAL-HKXB201507020.htm
MA Y Y, HU M H, ZHANG H H, et al. Optimized method for collaborative arrival sequencing and scheduling in metroplex terminal area[J]. Acta Aeronautica et Astronautica Sinica, 2015, 36(7): 2279-2290(in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-HKXB201507020.htm
|
[21] |
徐肖豪, 李善梅. 空中交通拥挤的识别与预测方法研究[J]. 航空学报, 2015, 36(8): 2753-2763. https://www.cnki.com.cn/Article/CJFDTOTAL-HKXB201508023.htm
XU X H, LI S M. Identification and prediction of air traffic congestion[J]. Acta Aeronautica et Astronautica Sinica, 2015, 36(8): 2753-2763(in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-HKXB201508023.htm
|
[22] |
MALIK W, JUNG Y C. Exact and heuristic algorithms for runway scheduling[C]//16th AIAA Aviation Technology, Integration, and Operations Conference (ATIO). Reston: AIAA, 2016: 4072.
|
[23] |
DEB K, PRATAP A, AGARWAL S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-Ⅱ[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197.
|
[24] |
郑金华, 邹娟. 多目标进化优化[M]. 北京: 科学出版社, 2017: 164-165, 176.
ZHENG J H, ZOU J. Multi-objective evolutionary optimization[M]. Beijing: Science Press, 2017: 164-165, 176(in Chinese).
|