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

摘要：

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

关键词：国际航线网络、最短路径算法、K条最短路径问题、Yen算法、启发式策略

所属期刊栏目：34

分类号：TP301(计算技术、计算机技术)

资助基金：中国民用航空局科技项目MHRD201101;2013年度中国民航大学预研重大项目3122013P003

在线出版日期：2014-05-04（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：1192-1195