基于改进 Dijkstra 算法的滑行路径优化

中国民航大学学报 ›› 2022, Vol. 40 ›› Issue (1): 1-6.

• 民用航空 • 下一篇

基于改进 Dijkstra 算法的滑行路径优化

翟文鹏，刘润南，朱承元

（中国民航大学空中交通管理学院，天津 300300）

收稿日期:2021-02-05 修回日期:2021-02-05 接受日期:2020-11-12 出版日期:2022-02-22 发布日期:2022-03-17
作者简介:翟文鹏（1985—），男，天津人，副教授，博士，研究方向为空中交通规划与管理。
基金资助:
国家自然科学基金青年科学基金项目（61603396）

Optimization of taxiway based on improved Dijkstra algorithm

ZHAI Wenpeng, LIU Runnan, ZHU Chengyuan

（College of Air Traffic Management, CAUC, Tianjin 300300, China）

Received:2021-02-05 Revised:2021-02-05 Accepted:2020-11-12 Online:2022-02-22 Published:2022-03-17

摘要/Abstract

摘要： 为了减少大型繁忙机场场面拥堵与航班延误，对处于机场终端区的航班进行预先战术性的滑行路径动态优化。首先，对处于机场终端区的航班划分时间窗口，对航班集合进行分类，使用改进 Dijkstra 算法对需要路径优化的航班进行动态规划。改进 Dijkstra 算法是将整个时间进程分成多个连续滚动的时间片，在每个时间片中，以场面节点的时间当量长度总和最小为优化目标，采用传统 Dijkstra 算法思想，获得每个航班的最优滑行路径解。其次, 在 TAAM（total airspace and airport modeller）仿真软件中利用 Matlab 编程实现算法，并以实际机场为例验证算法正确性。实验结果证明：改进 Dijkstra 算法能有效减少滑行冲突，提高滑行效率，缩短机场航班延误时间。

关键词: 空中交通管制, 机场管制, 改进 Dijkstra 算法, 滑行路径优化, TAAM（total airspace and airport modeller）仿真

Abstract: In order to reduce the congestion and flight delay of large busy airports, the strategic dynamic optimization of flights taxiway in the terminal area of airport is carried out. Firstly, the time windows of the flights in the terminal area of the airport are divided, the flight sets are classified, and the improved Dijkstra algorithm is used to dynamically plan the flights that need path optimization. The improved Dijkstra algorithm divides the whole time process into several continuous rolling time slices. In each time slice, the solution to taxiway optimization of each flight is obtained by using the traditional Dijkstra algorithm with the objective of minimizing the sum of time equivalent length of scene nodes. Secondly, the algorithm is implemented by Matlab in total airspace and airport modeller (TAAM) simulation software, and the correctness of the algorithm is verified by an actual airport. The experimental results show that the improved Dijkstra algorithm can effectively reduce the taxiing conflict, improve the taxiing efficiency and shorten the airport flight delay time.

Key words: air traffic control, airport control, improved Dijkstra algorithm, taxiway path optimization, total airspace and airport modeller(TAAM) simulation

中图分类号:

V355.2

翟文鹏, 刘润南, 朱承元. 基于改进 Dijkstra 算法的滑行路径优化[J]. 中国民航大学学报, 2022, 40(1): 1-6.

ZHAI Wenpeng, LIU Runnan, ZHU Chengyuan. Optimization of taxiway based on improved Dijkstra algorithm [J]. Journal of Civil Aviation University of China, 2022, 40(1): 1-6.

参考文献 12

[1]	陈浩. 机场航空器滑行路径优化技术研究[D]. 南京: 南京航空航天大学, 2015.
[2]	GUPTA P, SUBRAMANIAN H, PANT R. Generation of optimized routes and schedules for surface movement of aircraft on taxiways[C]// 10th AIAA Aviation Technology, Integration, and Operations (ATIO) Conference, September 13 -15, 2010, Fort Worth, Texas. Reston, Vir-ginia: AIAA, 2010.
[3]	姜雨, 王欢, 樊卫国, 等. 场面航空器滑行时空协同优化模型 [J]. 交通运输工程学报, 2019, 19(1): 127-135.
[4]	MAR.N .G. Airport management: taxi planning[J]. Annals of Operations Research, 2006, 143(1): 191-202.
[5]	刘成. 基于遗传算法的航空器地面路径规划研究[D]. 广汉: 中国民用航空飞行学院, 2015.
[6]	杜姗姗. 基于融合蚁群算法的机场地面滑行调度问题研究[D]. 天津: 中国民航大学, 2015.
[7]	MONTOYA J, WOOD Z, RATHINAM S, et al. A mixed integer linear program for solving a multiple route taxi scheduling problem[C]//AIAA Guidance, Navigation, and Control Conference. August 2-5, 2010, Toronto, Ontario, Canada. Reston, Virginia: AIAA, 2010.
[8]	谭国真. 最短路径算法设计、分析、实现和实验评价[R]. 大连: 大连理工大学计算机科学与工程系, 1999.
[9]	冯程, 胡明华, 丛玮. 基于滚动时域算法的航班滑行路径优化模型[J]. 航空计算技术, 2014, 44(4): 80-85.
[10]	陈虹, 申忱, 郭洪艳, 等. 面向动态避障的智能汽车滚动时域路径规划[J]. 中国公路学报, 2019, 32(1): 162-172.
[11]	袁彬, 刘建胜, 钱丹, 等. 一种基于改进 Dijkstra 的物流网络路径优化算法分析[J]. 制造业自动化, 2014, 36(9): 86-88, 105.
[12]	刘建美, 马寿峰, 马帅奇. 基于改进的 Dijkstra 算法的动态最短路计SUAN算方法[J]. 系统工程理论与实践, 2011, 31(6): 1153-1157.

[1]	高伟, 鲁馨桢. 面向航线轮挡时间不确定的 OD 航班时刻优化 [J]. 中国民航大学学报, 2025, 43(4): 84-90.
[2]	姜楠. 新放单管制员值守 EC 席与 PLC 席的管制能力评价 [J]. 中国民航大学学报, 2022, 40(2): 19-23.
[3]	郑丽君, 胡荣, 张军峰, 朱佳琳. 基于废气排放因素的离港航空器滑行路径优化[J]. 中国民航大学学报, 2019, 37(6): 34-38.
[4]	关静, 张精卫. 基于分组的飞行器短期冲突对快速检测算法#br#[J]. 中国民航大学学报, 2019, 37(5): 46-50.
[5]	袁乐平. 空中交通管制员疲劳及工作负荷与失误的关系[J]. 中国民航大学学报, 2018, 36(6): 31-33.
[6]	张兴俭，白鹏. 管制员不良工作状态特征调查研究[J]. 中国民航大学学报, 2018, 36(6): 21-26.
[7]	刘永欣，赵德斌. 基于管制员知识的终端区飞行冲突解决模型[J]. 中国民航大学学报, 2016, 34(3): 6-8,16.
[8]	牟龙芳，白鹏，孟娜，李亚荣. 基于熵权法的管制员素质机测因子赋权研究[J]. 中国民航大学学报, 2015, 33(3): 58-60.
[9]	刘永欣，王含柏. 雷达管制班组协作模型[J]. 中国民航大学学报, 2014, 32(4): 5-8.
[10]	王燕青，吴伟杰. 空中交通管制员不安全行为纠正[J]. 中国民航大学学报, 2013, 31(4): 38-40.
[11]	李楠，李宁，徐肖豪. 基于模糊层次分析法的机场管制模拟机评价[J]. 中国民航大学学报, 2013, 31(3): 10-13.
[12]	赵嶷飞，刘然，王红勇. 基于航线对象的五边进近调配程序模型研究[J]. 中国民航大学学报, 2013, 31(3): 1-5.
[13]	徐肖豪, 王洁宁, 曹文婷. 一种适用于中期冲突探测的概率型算法[J]. 中国民航大学学报, 2013, 31(2): 12-16.

基于改进 Dijkstra 算法的滑行路径优化

Optimization of taxiway based on improved Dijkstra algorithm

可视化

摘要/Abstract

引用本文

使用本文

参考文献 12

相关文章 13

编辑推荐

Metrics

本文评价