基于空闲时间窗和多Agent的A-SMGCS航空器滑行路由规划

唐勇; 胡明华; 黄荣顺; 吴宏刚; 尹嘉男; 徐自励

doi:10.7527/S1000-6893.2014.0119

航空学报 >

2015 , Vol. 36 >Issue 5: 1627 - 1638

DOI: https://doi.org/10.7527/S1000-6893.2014.0119

电子与控制

基于空闲时间窗和多Agent的A-SMGCS航空器滑行路由规划

唐勇 ,
胡明华 ,
黄荣顺 ,
吴宏刚 ,
尹嘉男 ,
徐自励

展开

1. 南京航空航天大学民航学院, 南京 211106;
2. 中国民用航空局第二研究所科研开发中心, 成都 610041

唐勇男, 博士研究生, 工程师。主要研究方向: 场面路由规划, 空管技术, 数据融合, 信息处理。 Tel: 028-82909949 E-mail: tangyong1979@126.com;胡明华男, 教授, 博士生导师。主要研究方向: 国家空域规划、管理与评估, 飞行流量管理, 空中交通管理系统信息化与智能化。 Tel: 025-52112079 E-mail: minghuahu@nuaa.edu.cn

收稿日期: 2014-05-06

修回日期: 2014-06-11

网络出版日期: 2014-06-16

基金资助

国家科技支撑计划 (2011BAH24B06); 国家自然科学基金 (61179060, U1333202, U1233103)

收起

Aircraft taxi routes planning based on free time windows and multi-agent for A-SMGCS

TANG Yong ,
HU Minghua ,
HUANG Rongshun ,
WU Honggang ,
YIN Jia'nan ,
XU Zili

Expand

1. College of Civil Aviation, Nanjing University of Aeronautics and Astronautics, Nanjing 211106, China;
2. Research and Development Center, The Second Research Institute of Civil Aviation Administration of China, Chengdu 610041, China

Received date: 2014-05-06

Revised date: 2014-06-11

Online published: 2014-06-16

Supported by

National Key Technology Research and Development Program of China (2011BAH24B06); National Natural Science Foundation of China (61179060, U1333202, U1233103)

Fold

摘要

先进场面活动引导与控制系统(A-SMGCS)中的航空器滑行路由规划是一个典型NP难题。为解决航空器滑行路由规划的优化性和计算量之间的矛盾,提出一种基于空闲时间窗的路由规划方法,并利用多Agent系统(MAS)进行算法求解。首先,建立滑行资源图以对场面滑行区进行建模。其次,按照航班计划为航空器设置滑行优先级,并按优先级顺序依次规划路由,后规划的路由不破坏已有路由,即利用滑行路段的空闲时间窗进行规划。每次只需为一架航空器规划滑行路由,降低了问题的求解难度;通过搜索空闲时间窗获得路由使场面交通均衡分布,保证了路由规划的整体优化性。分析了空闲时间窗特性,指出空闲时间窗的可达性条件和避免同步资源交换冲突的条件。最后,设计MAS,把建立、维护和搜索空闲时间窗图的复杂集中式求解过程简化为通过路由管理Agent,航空器Agent和资源节点Agent相互协作实现对场面路由规划问题的分布式求解。仿真结果表明,设计的MAS能够快速找到空闲时间窗中的最优解;与固定预选滑行路径算法相比,航空器的平均滑行时间显著减少,最多可以节省19.6%的滑行时间。

关键词： 空闲时间窗; 多Agent系统; 滑行路由规划; 航空器优先级; 先进场面活动引导与控制系统

本文引用格式

唐勇 , 胡明华 , 黄荣顺 , 吴宏刚 , 尹嘉男 , 徐自励 . 基于空闲时间窗和多Agent的A-SMGCS航空器滑行路由规划[J]. 航空学报, 2015 , 36(5) : 1627 -1638 . DOI: 10.7527/S1000-6893.2014.0119

Abstract

Aircraft taxi routes planning for advanced surface movement guidance and control system (A-SMGCS) is a typical NP-Hard problem. To solve the contradiction between taxi routes planning optimization and the great amount of calculation, a taxi routes planning method based on free time windows is proposed and a multi-agent system (MAS) is designed to implement the algorithm. Firstly, a taxi resource graph is established to model airport taxi area. Then, any aircraft is appointed a priority according to flight schedule. Aircraft taxi route is planned sequentially according to the order of aircraft priority. Aircraft can only use free time windows of a taxiway to plan taxi route and the previous planned taxi routes cannot be destroyed. The difficulty of solving aircraft taxi routes planning problem is reduced to that we only need to find a single aircraft taxi route every time. Overall optimization of the taxi route planning is guaranteed because airport surface traffic is balanced through searching free time windows to get taxi routes. Finally, since it is a complex centralized solution process to establish, maintain and search a free time window graph, an MAS is established which makes it simplified through the route management Agent, aircraft Agent and resource node Agent, collaboratively to solve aircraft taxi route planning problem distributively. Simulation results show that the MAS can quickly find the optimal solution of free time windows. Aircraft average taxiing time decreases significantly and up to 19.6% aircraft taxiing time can be saved compared to preselection fixed-path set algorithm.

Key words： free time windows; multi-agent system; taxi routes planning; aircraft priority; A-SMGCS

参考文献

[1] International Civil Aviation Organization. Doc.9830-AN/452 Advanced surface movement guidance and control systems (A-SMGCS) manual[S]. Montreal: ICAO, 2004.
[2] Clare G L, Richards A G. Optimization of taxiway routing and runway scheduling[J]. IEEE Transactions on Intelligent Transportation Systems, 2011, 12(4): 1000-1013.
[3] Zhang X J, Guan X M, Sun D F, et al. The effect of queueing strategy on network traffic[J]. Communications in Theoretical Physics, 2013, 60(4): 496-502.
[4] Guan X M, Zhang X J, Zhu Y B, et al. An efficient routing strategy on spatial scale-free networks[J]. International Journal of Modern Physics C, 2014, 25(7): 1450017-1-1450017-15.
[5] Smeltink J W, Soomer M J, de Waal P R, et al. An optimisation model for airport taxi scheduling[C]//Proceedings of the INFORMS Annual Meeting. Catonsville, MD: INFORMS, 2004: 1-25.
[6] Roling P C, Visser H G. Optimal airport surface traffic planning using mixed-integer linear programming[J]. International Journal of Aerospace Engineering, 2008, 2008: 1-11.
[7] Montoya J, Wood Z, Rathinam S, et al. A mixed integer linear program for solving a multiple route taxi scheduling problem[C]//Proceedings of AIAA Guidance, Navigation, and Control Conference. Reston: AIAA, 2010: 1-18.
[8] Anderson R, Milutinovic D. Optimization of taxiway traversal at congested airports[C]//Proceedings of the 10th AIAA Aviation Technology,Integration and Operations(ATIO) Conference. Reston: AIAA, 2010: 1-11.
[9] Liu C Y, Guo K F. Aircraft taxiing scheduling optimization based on genetic algorithm[C]//Proceedings of 2nd International Conference on Information Engineering and Computer Science. Piscataway, NJ: IEEE Press, 2010: 1-4.
[10] Pesic B, Durand N. Aircraft ground traffic optimization using a genetic algorithm[C]//Proceedings of the Genetic and Evolutionary Computation Conference. New York: GECCO, 2001.
[11] Gotteland J, Durand N, Alliot J M, et al. Aircraft ground traffic optimization[C]//Proceedings of the Genetic and Evolutionary Computation Conference. New York: GECCO, 2001.
[12] Clare G L, Richards A, Sharma S, et al. Iterative optimization of taxiway routing and runway scheduling[C]//Proceedings of the AIAA Guidance Navigation, and Control Conference. Reston: AIAA, 2009.
[13] Gupta P, Subramanian H, Pant R S. Generation of optimized routes and schedules for surface movement of aircraft on taxiways, AIAA-2010-9211[R]. Reston: AIAA, 2010.
[14] Zhu X P, Tang X M, Han S C. EHPN-based modeling of airport taxiway operation control in A-SMGCS[J]. Journal of Traffic and Transportation Engineering, 2010, 10(4): 103-108 (in Chinese). 朱新平, 汤新民, 韩松臣. 基于EHPN的A-SMGCS机场滑行道运行控制建模[J]. 交通运输工程学报, 2010, 10(4): 103-108.
[15] Wang C, Tang X M, An H F. Research on the optimization of aircraft dynamic routes planning for A-SMGCS[J]. Journal of Wuhan University of Technology: Transportation Science & Engineering, 2012, 36(5): 1069-1073 (in Chinese). 王翀, 汤新民, 安宏锋. A-SMGCS航空器动态最优滑行路径规划研究[J]. 武汉理工大学学报: 交通科学与工程版, 2012, 36(5): 1069-1073.
[16] Tang X M, Wang Y T, Han S C. Aircraft dynamic taxiway routes planning for A-SMGCS based on DEDS[J]. Systems Engineering and Electronics, 2010, 32(12):2669-2675 (in Chinese). 汤新民, 王玉婷, 韩松臣. 基于 DEDS的A-SMGCS 航空器动态滑行路径规划研究[J]. 系统工程与电子技术,2010, 32(12): 2669-2675.
[17] Shoham Y, Leyton-Brown K. Multiagent systems: algorithmic, game-theoretic, and logical foundations[M]. Cambridge, UK: Cambridge University Press, 2009.
[18] Borshchev A. The big book of simulation modeling: multimethod modeling with anylogic 6[M]. Chicago: AnyLogic North America Press, 2013: 49-56.

Options

文章导航

模态框（Modal）标题

摘要

本文引用格式

Abstract

参考文献