基于交通状态的离场航班动态协同排序方法

江灏; 刘继新; 董欣放

doi:10.13700/j.bh.1001-5965.2021.0066

基于交通状态的离场航班动态协同排序方法

doi: 10.13700/j.bh.1001-5965.2021.0066

江灏^{1, 2},
刘继新^{1, 2, ,},
董欣放^{1, 2}

1.
南京航空航天大学民航学院, 南京 211106
2.
国家空管飞行流量管理技术重点实验室, 南京 211106

基金项目:

南京航空航天大学研究生创新基地(实验室)开放基金 kfjj20200717

详细信息

通讯作者:
刘继新, E-mail: Larryljx@163.com

中图分类号: V355.2
计量
- 文章访问数: 351
- HTML全文浏览量: 117
- PDF下载量: 28
- 被引次数: 0
出版历程
- 收稿日期: 2021-02-05
- 录用日期: 2021-03-29
- 网络出版日期: 2021-04-16
- 整期出版日期: 2022-10-20

Dynamic collaborative sequencing for departure flights based on traffic state

JIANG Hao^{1, 2},
LIU Jixin^{1, 2
, ,},
DONG Xinfang^{1, 2}

1.
College of Civil Aviation, Nanjing University of Aeronautics and Astronautics, Nanjing 211106, China
2.
National Key Laboratory of Air Traffic Flow Management, Nanjing 211106, China

Funds:

NUAA Graduate Innovation Base (Laboratory) Open Fund kfjj20200717

More Information

Corresponding author: LIU Jixin, E-mail: Larryljx@163.com

摘要

摘要:
为适应协同决策(CDM)需要，考虑空管、航司和机场三方的诉求，对拥挤和非拥挤场景下的离场航班动态协同排序问题进行了系统研究。通过分析离场航班运行特性，利用离场航班的计划撤轮档时间(SOBT)和预计撤轮档时间(EOBT)数据设计了一种离场航班动态排序方法；针对各方构建了离场航班排序的多个优化目标，且为保证排序公平性，提出了航空公司延误公平性评价指标，将非受控离场航班优先级分为3类，对各类非受控离场航班设置其可接受的最大延误时间和最大位置偏移量，创建了基于交通状态的离场航班协同排序模型；采用带精英策略的快速非支配排序遗传算法(NSGA-Ⅱ)寻求离场航班动态协同排序的最优解。仿真结果表明：较先到先服务(FCFS)方法，所提方法在2种场景下各排序时段均增加多种排序方案，离场航班总延误均减少50%以上，且在非拥挤场景下提高了航空公司延误公平性。所提方法可对离场航班进行优化排序，显著减少航班延误，有效提升公平性，契合协同决策理念，可实现三方协同排序。
- 空中交通管理 /
- 离场排序 /
- 协同决策 /
- 航空公司延误公平性 /
- 遗传算法
Abstract:
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.
- air traffic management /
- departure sequencing /
- collaborative decision making /
- airline delay fairness /
- genetic algorithm

HTML全文

图 1 离场航班动态排序方法流程

Figure 1. Flowchart of departure flight dynamic sequencing method

下载: 全尺寸图片幻灯片

图 2 算法流程

Figure 2. Flowchart of algorithm

下载: 全尺寸图片幻灯片

图 3 Pareto最优解(时段1-4)

Figure 3. Pareto optimal solution (time interval 1-4)

下载: 全尺寸图片幻灯片

图 4 种群进化过程中GD和IGD值变化趋势(时段1-4)

Figure 4. Trend of GD and IGD value in process of population evolution (time interval 1-4)

下载: 全尺寸图片幻灯片

图 5 Pareto最优解与先到先服务方法结果(时段1-4)

Figure 5. Pareto optimal and FCFS solution (time interval 1-4)

下载: 全尺寸图片幻灯片

图 6 不同策略下离场航班起飞次序(时段1-4)

Figure 6. Sequences of departure flights using different strategies (time interval 1-4)

下载: 全尺寸图片幻灯片

图 7 筛选后的Pareto最优解(时段1-4)

Figure 7. Selected Pareto optimal solution (time interval 1-4)

下载: 全尺寸图片幻灯片

图 8 Pareto最优解(时段2-2)

Figure 8. Pareto optimal solution (time interval 1-4)

下载: 全尺寸图片幻灯片

图 9 种群进化过程中GD和IGD值变化趋势(时段2-2)

Figure 9. Trend of GD and IGD value in process of population evolution (time interval 2-2)

下载: 全尺寸图片幻灯片

图 10 Pareto最优解与先到先服务方法结果(时段2-2)

Figure 10. Pareto optimal and FCFS solution (time interval 2-2)

下载: 全尺寸图片幻灯片

图 11 不同策略下离场航班起飞次序频数(时段2-2)

Figure 11. Sequence frequency of departure flights using different strategies (time interval 2-2)

下载: 全尺寸图片幻灯片

图 12 筛选后的Pareto最优解(时段2-2)

Figure 12. Selected Pareto optimal solution (time interval 2-2)

下载: 全尺寸图片幻灯片

参考文献(24)

[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).