基于Maklink 图和遗传算法的改航 路径规划方法研究

交通运输系统工程与信息 ›› 2014, Vol. 14 ›› Issue (5): 154-160.

基于Maklink 图和遗传算法的改航路径规划方法研究

王飞^*，王红勇

中国民航大学天津市空管运行规划与安全技术重点实验室，天津300300

收稿日期:2014-01-14 修回日期:2014-02-22 出版日期:2014-10-25 发布日期:2014-12-17
作者简介:王飞（1982-），男，安徽凤阳人，助理研究员，博士.
基金资助:
国家自然科学基金与民航联合资助项目（U1333108）；国家科技支撑计划资助项目(2011BAH24B08)；中央高校基本科研业务费专项基金资助项目(ZXH2011A002，ZXH2012C005)；中国民航大学科研启动基金项目(2011QD01X).

A Re-routing Path Planning Method Based on Maklink Graph and GA Algorithm

WANG Fei,WANG Hong-yong

Tianjin Air Traffic Operation Planning and Safety Technology Laboratory, Civil Aviation University of China，Tianjin 300300, China

Received:2014-01-14 Revised:2014-02-22 Online:2014-10-25 Published:2014-12-17

摘要/Abstract

摘要：

为了保障恶劣天气下的飞行安全，航班需要采取改航策略避开危险区.采用已有的以改航路径最短为目标，以航段最小距离、避开危险区、转弯角度等为约束条件的规划模型，设计了3 阶段方法研究改航路径规划.首先应用Maklink 图和Dijkstra 算法规划一条能够避开危险区的路径，接着应用遗传算法优化路径，最后进行路径调整以满足约束条件.算例仿真结果显示，应用本文方法得到的改航路径长度较短，转弯次数少、转弯角度小，计算效率高.仿真结果说明，应用本文提出的方法获得的改航路径满足目标和约束要求，验证了该方法的可行性和有效性.

关键词: 航空运输, Maklink图, 遗传算法, Dijkstra算法, 改航路径规划, 民航

Abstract:

To ensure flight safety in severe weather, it is necessary to design the optimized route for aircrafts to avoid the dangerous zone. An optimization model is established. Considering several constraints, such as avoiding danger zone, reducing flight segment minimum length, turning angle and turning point number, the model minimizes the total flight path length. After that, a three- stage-method is proposed to solve this model. First, the Maklink graph and the Dijkstra algorithm are used to obtain one flight path to avoid the danger zone. Second, genetic algorithm is applied to optimize the path to obtain the shortest path. Finally, the path is adjusted to satisfy all of the constraints. With the model and method above, several simulation experiments are carried out. Simulation results show that the proposed rerouting path planning method is feasible and effective.

Key words: air transportation, Maklink graph, genetic algorithm, Dijkstra algorithm, rerouting path planning, civil aviation

中图分类号:

V355

王飞，王红勇. 基于Maklink 图和遗传算法的改航路径规划方法研究[J]. 交通运输系统工程与信息, 2014, 14(5): 154-160.

WANG Fei,WANG Hong-yong. A Re-routing Path Planning Method Based on Maklink Graph and GA Algorithm[J]. Journal of Transportation Systems Engineering and Information Technology, 2014, 14(5): 154-160.

导出引用管理器 EndNote|Ris|BibTeX

链接本文: http://www.tseit.org.cn/CN/abstract/abstract18867.shtml

http://www.tseit.org.cn/CN/Y2014/V14/I5/154

参考文献

[1] Dixon M, Weiner G. Automated aircraft routing through weather- impacted airspace[C]// Fifth International Conference on Aviation Weather System. Vienna: VA, 1993: 295-298.

[2] Avijit Mukherjee, Mark Hansen. A dynamic rerouting model for air traffic flow management [J]. ransportation Research Part B. 2009,43(1):159-171.
[3] Krozel J, Penny S, Peter J, et al. Comparison of algorithms for synthesizing weather avoidance routes in transition airspace[R]. AIAA Paper, 2004:1-16.[4] Sameer A, Hussein A, Michael B. Multi-objective ant colony optimization for weather avoidance in a free flight environment[R].The ALAR Technical Report Series,TR-ALAR-2006-0300.
[5] Christine Taylor,Craig Wanke. Generating Operationally- acceptable reroutes using simulated annealing[C]// 10th AIAA Aviation Technology,Integration, and Operations (ATIO) Conference 13 - 15 September 2010, Fort Worth, Texas. 2010：1-22.
[6] 宋柯. 空中交通流量管理改航策略初步研究[D] .南京航空航天大学,2002.[SONG K. The research of rerouting problem in air traffic flow management[D].Nanjing University of Aeronautics and Astronautics,2002.]
[7] 李雄, 徐肖豪, 朱承元，等. 基于几何算法的空中交通改航路径规划[J]. 系统工程, 2008,26(8):37-40.[LI X, XU X H, ZHU C Y，et al. Air traffic reroute planning based on geometry algorithm[J]. Systems Engineering,2008,26(8):37-40.]
[8] 徐肖豪,李成功,赵嶷飞，等. 基于人工势场算法的改航路径规划[J]. 交通运输工程学报,2009,9(6): 64-68.[XU X H, LI C G, ZHAO Y F，et al. Rerouting path planning based on artificial potential field algorithm [J].Journal of Traffic and Transportation Engineering, 2009,9(6): 64-68.]
[9] 王飞, 李成功, 徐肖豪. 基于人工势场—人工鱼群算法的改航路径规划[J], 航空计算技术, 2011,41(2):5-9.[WANG F, LI C G, XU X H. Rerouting path planning based on artificial potential field and artificial fish school algorithm[J]. Aeronautical Computing Technique,2011,41(2):5-9.]
[10] Wang Fei. A new algorithm of flight rerouting path planning in severe weather. American Journal of Engineering and Technology Research, 2011, 11(12):263-266.
[11] 孟令航,徐肖豪,李善梅，等. 不确定强对流天气下动态改航路径规划[J]. 西南交通大学学报, 2012, 47(4):686-691.[MENG L H, XU X H, LI S M，et al. Dynamic reroute planning under uncertain severe convective weather[J]. Journal of Southwest Jiaotong University,2012, 47(4): 686-691.]
[12] 高政. 基于动态空域的自适应改航技术[D].南京航空航天大学, 2009.[GAO Z. Adaptive rerouting technique based on dynamic airspace[D]. Nanjing University of Aeronautics and Astronautics,2009.]
[13] 王兴隆,徐肖豪,冯江然. 基于改进人工势场法的多机改航路径规划[J]. 飞行力学, 2013, 31(4):381-384.[WANG X H, XU X H, FENG J R. Multi- aircraft rerouting path planning based on improved artificial potential field algorithm[J]. Flight Dynamics,2013,31(4):381-384.]
[14] 刘斌, 王涛. 一种高效的平面点集凸包递归算法[J]. 自动化学报, 2012, 38(8):1375-1379.[LIU B, WANG T.An efficient convex hull algorithm for planar point set based on recursive method[J]. ACTA Automatica Sinica,2012, 38(8):1375-1379.]
[15] Habib M K, Asama H. Efficient method to generate collision free paths for autonomous mobile robot based on new free space structuring approach[C]//IEEE/RSJ International Workshop on Intelligent Robots and Systems, Osaka. Japan: IEEE, 1991.