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

doi:10.7527/S1000-6893.2014.0119

ACTA AERONAUTICAET ASTRONAUTICA SINICA >

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

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

Electronics and Control

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

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

Cite this article

TANG Yong , HU Minghua , HUANG Rongshun , WU Honggang , YIN Jia'nan , XU Zili . Aircraft taxi routes planning based on free time windows and multi-agent for A-SMGCS[J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2015 , 36(5) : 1627 -1638 . DOI: 10.7527/S1000-6893.2014.0119

References

[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

Outlines

模态框（Modal）标题

Abstract

Cite this article

References