基于扩展KMCSP的国际航线运价搜索模型及算法  

Model and algorithm of searching for air fares in international airlines based on extended KMCSP

作　　者：谢继文[1,2] 徐涛[1,2] 姜锡珂 李建伏[1,2] 

机构地区：[1]中国民航大学计算机科学与技术学院,天津300300 [2]中国民航大学中国民航信息技术科研基地,天津300300 [3]民航重庆空管分局技术保障部,重庆400000

出　　处：《计算机工程与设计》2015年第8期2103-2107,2166,共6页Computer Engineering and Design

基　　金：中国民用航空局科技基金项目(MHRD201101);2013年度中国民航大学预研重大基金项目(3122013P003);中央高校基本科研业务费专项基金项目(ZXH2011B003)

摘　　要：为提升国际航线运价搜索效率,建立一个国际航线运价搜索的EKMCSP模型,该模型基于K条多约束最短路径(KMCSP)问题并进行扩展。国际航线运价搜索的各种因素被表示为EKMCSP模型中的变量、约束和目标;针对建立的国际航线运价搜索EKMCSP模型提出A*Level算法,结合国际航线运价搜索的特点,采用有限层搜索的思想,提高搜索效率并减小搜索规模。大量实验结果表明,该算法可实现国际航线运价搜索的EKMCSP问题的快速求解,且解集具有较高的正确率。To improve the efficiency of searching for best air fares in international airlines, the extended K multiple constrained shortest path （EKMCSP） model of searching for best air fares in international airlines was established, in which the previous K multiple constrained shortest path （KMCSP） model was extended and all kinds of factors in searching model were represented clearly as variables, constraints and objectives. A ＊ Level algorithm based on EKMCSP model of searching for best airfares in in- ternational airlines was presented. Furthermore, a technique of searching with limited levels was combined with the A ＊ Level al- gorithm to improve the speed of searching and reduce the scales of searching. Experimental results show that the solution to EK- MCSP problem about searching for best air fares in international airlines can be obtained fast using the proposed algorithm, and the solution set has higher accuracy.

关 键 词：国际航线 运价搜索 多约束 K条最短路径 A＊Level算法 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]