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

• 作者: 丁晓璐 徐涛 李建伏 胡欣
• 来源期刊: 计算机应用
• 学科: 工学
• 关键词: 国际航线网络 最短路径算法 K条最短路径问题 Yen算法 启发式策略
• 年，卷（期）: 2014,（4）
• 所属期刊栏目: 行业与领域应用
• 页码范围: 1192-1195
• 页数: 4页
• 分类号: TP301
• 字数: 5175字
• 语种: 中文
• DOI: 10.11772/j.issn.1001-9081.2014.04.1192

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李建伏	中国民航大学计算机科学与技术学院	17	139	6.0	11.0
2	丁晓璐	中国民航大学计算机科学与技术学院	1	11	1.0	1.0