国际航线网络联程路径搜索的KMCSP问题研究

• 作者: 丁晓璐 徐涛 李建伏
• 来源期刊: 西南交通大学学报
• 学科: 经济
• 关键词: 航线 联程路径搜索 KMCSP问题 Yen*算法 A*算法 启发式策略
• 年，卷（期）: 2014,（1）
• 页码范围: 153-159
• 页数: 7页
• 分类号: F561
• 字数: 6051字
• 语种: 中文
• DOI: 10.3969/j.issn.0258-2724.2014.01.024

摘要

为了解决在国际航线网络中查找联程路径时间花费较长的问题,针对国际航线网络联程路径搜索的特点,借助于A*算法的启发式策略,在对Yen算法改进的基础上,提出一种新的解决多约束条件下K条最短路径(K-multiple constrained shortest paths,KMCSP)问题的算法,即约束Yen*算法.在中转次数约束和特定中转点约束条件下,对国际航线网络进行了测试实验,结果表明:与约束Yen算法相比,约束Yen*算法的搜索效率提高了2.98倍,平均运行时间减少了78.3％,算法的搜索规模缩小了86％,且波动范围小.约束Yen*算法适用于多约束条件下快速求解国际航线网络联程路径搜索问题.

作者信息

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