%0 Journal Article %A 丁晓璐 %A 胡欣 %A 李建伏 %A 徐涛 %T 国际航线网络中K条最短路径算法改进与仿真 %D 2014 %R 10.11772/j.issn.1001-9081.2014.04.1192 %J 计算机应用 %P 1192-1195 %V 34 %N 4 %X

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

%U http://www.joca.cn/CN/10.11772/j.issn.1001-9081.2014.04.1192