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

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

为提升国际航线运价搜索效率,建立一个国际航线运价搜索的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.