• 行业与领域应用 •

### 国际航线网络中K条最短路径算法改进与仿真

1. 1. 中国民航大学 中国民航信息技术科研基地,天津 300300;
2. 中国民航大学 计算机科学与技术学院,天津 300300
• 收稿日期:2013-10-09 修回日期:2013-12-09 出版日期:2014-04-01 发布日期:2014-04-29
• 通讯作者: 胡欣
• 作者简介:胡欣(1984-),女,江西鄱阳人,实习研究员,硕士,主要研究方向:交通信息工程及控制;
徐涛(1962-),男,重庆人,教授, CCF会员,主要研究方向:民航信息系统、智能信息处理;
丁晓璐(1988-),女,河南濮阳人,硕士研究生,主要研究方向:民航信息系统;
李建伏(1979-),女,河北沧州人,讲师,博士,主要研究方向:民航信息系统、人工智能。
• 基金资助:

中国民用航空局科技项目;2013年度中国民航大学预研重大项目

### Improvement and simulation of K-shortest-paths algorithm in international flight route network

HU Xin1,XU Tao1,2,DING Xialu2,LI Jianfu2

1. 1. Information Technology Research Base, Civil Aviation University of China, Tianjin 300300, China
2. College of Computer Science and Technology, Civil Aviation University of China, Tianjin 300300, China
• Received:2013-10-09 Revised:2013-12-09 Online:2014-04-01 Published:2014-04-29
• Contact: HU Xin

K条最短路径(KSP)问题是国际航线网络实际路径优化问题。通过对航线网络特征与K条最短路径算法的分析，研究了解决KSP问题的典型Yen算法。针对Yen算法求解候选路径占用大量运算时间的问题，提出一种改进Yen算法。改进Yen算法通过借助A*算法的启发式策略，减少了产生候选航线路径的时间，从而提高了算法的搜索效率并减小了算法搜索的规模。通过对国际航线网络实例的仿真，实验结果表明改进Yen算法能够快速求解国际航线网络中的KSP问题;同时，与Yen算法相比，运算效率提升了75.19%以上，能够为航线路径优化提供决策支持。

Abstract:

K-Shortest-Paths (KSP) problem is the optimization issue in international flight route network. With the analysis on the international flight route network and KSP algorithm, the typical Yen algorithm solve KSP problem was investigated. To resolve the problem that Yen algorithm occupied much time in solving the candidate paths, an improved Yen algorithm was proposed. The improved Yen algorithm was set up by using the heuristic strategy of A* algorithm, which reduced the time to generate candidate paths, thereby, the search efficiency was improved and the search scale was reduced. The simulation results of international flight route network example show that the improved Yen algorithm can quickly solve KSP problem in international flight route network. Compared with the Yen algorithm, the efficiency of the proposed algorithm is increased by 75.19%, so it can provide decision support for international flight route optimization.