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

K-Multiple Constrained Shortest Paths Problem for Connecting Path Search in International Flight Path Network

作　　者：徐涛[1,2] 丁晓璐[1,2] 李建伏[1] 

机构地区：[1]中国民航大学计算机科学与技术学院,天津300300 [2]中国民航信息技术科研基地,天津300300

出　　处：《西南交通大学学报》2014年第1期153-159,共7页Journal of Southwest Jiaotong University

基　　金：中国民用航空局科技项目(MHRD201007);中央高校基本科研业务费用中国民航大学专项基金资助项目(ZXH2011B003)

摘　　要：为了解决在国际航线网络中查找联程路径时间花费较长的问题,针对国际航线网络联程路径搜索的特点,借助于A*算法的启发式策略,在对Yen算法改进的基础上,提出一种新的解决多约束条件下K条最短路径(K-multiple constrained shortest paths,KMCSP)问题的算法,即约束Yen*算法.在中转次数约束和特定中转点约束条件下,对国际航线网络进行了测试实验,结果表明:与约束Yen算法相比,约束Yen*算法的搜索效率提高了2.98倍,平均运行时间减少了78.3%,算法的搜索规模缩小了86%,且波动范围小.约束Yen*算法适用于多约束条件下快速求解国际航线网络联程路径搜索问题.In order to solve the problem that the connecting path search method takes long time in international flight path network, according to the features of the connecting path search in the network, a constrained Yen ＊ algorithm, which adopts the heuristic strategy of A ＊ algorithm and is based on the Yen algorithm, is proposed to solve the K-multiple constrained shortest paths （KMCSP） problem. The proposed algorithm is tested in the international flight path network under the constraints of transfer times and a given transferring node. The results show that compared with the constrained Yen algorithm, the constrained Yen ＊ algorithm improves the searching efficiency by 2.98 times, reduces the average running time by 78.3% , and decrease the search space by 86% with a small fluctuation range. Therefore, the constrained Yen＊ algorithm can be used to quickly solve the multiple constrained connecting path problem in international flight path network.

关 键 词：航线 联程路径搜索 KMCSP问题 Yen＊算法 A＊算法 启发式策略 

分 类 号：F561[经济管理—产业经济]