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

谢继文，徐 涛，姜锡珂，李建伏

（1.中国民航大学 计算机科学与技术学院，天津300300；2.中国民航大学 中国民航信息技术科研基地，天津300300；3.民航重庆空管分局 技术保障部，重庆400000）

0 引 言

国际航线运价搜索［1］要解决的问题是在客户容忍的时间内，在时间和费用等条件约束下，寻找出K 条 “最短路径”，本质上是一个扩展的K 条多约束最短路径 （extended K multiple constrained shortest path，EKMCSP）问 题［2］。EKMC－SP问题是在普通K 条多约束最短路径 （K multiple constrained shortest path，KMCSP）问题的基础上，将单弧图模型扩展为多弧图模型后形成［3］。长期以来，普通KMCSP问题 （属NP难问题）受到了广泛的关注和大量的研究，如互联网中保证服务质量的QoS路由问题是最基本的多约束条件下求K 条最短路径问题［4］。求解普通KMCSP问题的算法种类繁多，例如IDA＊ ＿MCSP 算法［5］、SAMCRA 算法［6］、随 机 化 算 法［7］和H ＿MCSP 算 法［8］等，这些算法仅能用来解决K＝1的情形。文献 ［9］提出的以A＊算法为基础的A＊Prune算法，致力于寻找K 条最短路径 （K＝1，2，3…），该算法采用Dijkstra算法做辅助计算，通过不断搜索和剪枝，直到找出满足约束的K 条路径或完成所有路径搜索为止。

针对国际航线运价搜索中庞大的搜索规模和复杂的图模型等问题，本文建立了国际航线运价搜索问题的EKMCSP模型并提出了相应的A＊Level算法。该算法结合国际航线运价搜索问题的特点，采用启发式函数思想和大量剪枝策略来大规模减小搜索空间和提高运算效率。

1 国际航线运价搜索模型

国际航线运价搜索的目的是寻找最能满足用户需求的旅行路径，搜索范围为整个航线网络中所有航班，主要约束条件有时间和运价等［10］。运价FARE 定义为两个城市之间不论有多少航班参与情况下的单程旅行最终花费，其中

式中：b——起飞城市到目的城市之间的航班数量，xi、fi——第i个航班的飞行时间及票价，gq、zq——第q次中转的停留时间及金钱花费。FARE 是所求K 条最短路径排序的依据，当以时间花费为排序的主要依据时，令"＝1，#＝0，$＝1，%＝0；以金钱花费为排序的主要依据时，令"＝0，#＝1，$＝0，%＝1。

国际航线运价搜索的EKMCSP问题与KMCSP问题的差异主要体现在：

（1）图模型不同。KMCSP问题的图模型中节点之间仅有一条单向或双向弧；而在国际航线运价搜索的EKMCSP问题的图模型中，节点之间可以有多条弧，且弧上权值复杂，包括票价，起降时间和航班号等。

（2）辅助算法不同。求解KMCSP 问题的H ＿MCSP算法和A＊Prune算法等均采用Dijkstra算法进行辅助运算；而国际航线运价搜索的EKMCSP问题因其复杂的图模型无法使用Dijkstra算法进行辅助运算。

（3）搜索方式不同。KMCSP问题中，可以进行无序或有序搜索；而在国际航线运价搜索中，无论是以最低票价还是以最短旅行时间为目标，旅客转机次数均是有限的，因此国际航线运价搜索的EKMCSP问题更适合于有限的层次搜索。

1.1 EKMCSP问题的一般描述

令GRA ＝（VR，EG，LI）为一网络图，其中VR 为节点集，VR ＝｛vi｜1≤i≤n｝，n为节点数目；EG 为边集，记eh（vi，vj）为节点vi与vj之间的第h条边，EG ＝｛eijh｜eijh＝eh（vi，vj），vi，vj∈VR｝；LI 为 所 有 边 的 权 值 集 合，记l（eijh）为边eijh的权值，LI＝｛lijh｜lijh＝l（eijh），eijh∈EG｝。假设有起始节点s，目标节点t和约束集CON ＝｛CONi｜i＝1，2，…，R｝，记p（s，t）为s到t的某条可达路径所经边的集合，Y（p（s，t））为p（s，t）在约束CON 下的花费，其中

EKMCSP问题即从起始节点s到目标节点t的所有可达路径中找出K 条最短路径p（s，t）。

1.2 国际航线运价搜索的EKMCSP模型

国际航线运价搜索问题的EKMCSP模型可以直观地反映航线网络的特点。图1是一个简单航线网络的EKMCSP模型图示例，其中A、B、C、D、E、F 代表6个城市，节点间的每条弧代表执行该航段的一个航班。记MCT ＿TIME为中转过程中降落航班和起飞航班之间的最小连接时间，BCT＿TIME 表示中转过程中降落航班和起飞航班之间所允许的最大连接时间，TR 表示可容忍的最大花费，约束条件通常包括：①抵达航班的降落时间与换乘航班的起飞时间之差要大于MCT＿TIME，且小于BCT＿TIME；②已搜索路径的花费和小于TR；③转机次数。

针对起始节点到目标节点的可达路径搜索以树形层次顺序进行。在图1 中，设起始节点为C，目标节点为B，MCT＿TIME为30分钟，BCT＿TIME 为120分钟，转机次数不超过3次，以C到B的直达航班最高票价作为TR。若任意节点u和d之间存在多弧的情况，则将边eh（u，d）依次记为udh（h＝1，2，…）。于是，从C 到B 的可达路径有｛CB1｝，｛CA1，AB1｝，｛CA2，AB1｝，｛CF1，FD1，DB1｝，｛CF2，FD2，DE1，EB2｝等。其中｛CA2，AB1｝不满足约束条件①，｛CF1，FD1，DB1｝不 满 足 约 束 条 件②，｛CF2，FD2，DE1，EB2｝不满足约束条件③。因此在该模型下，运价搜索的结果按照金钱花费多少排序为｛CA1，AB1｝，｛CB1｝。

2 基于EKMCSP模型的搜索算法

国际航线运价搜索的EKMCSP模型中，节点之间存在一条或多条弧，而KMCSP 算法只能解决节点间单弧连接的模型，如A＊Prune算法和约束剪枝算法［11］等。为此针对国际航线运价搜索问题的EKMCSP模型，以A＊算法为基础，借鉴A＊Prune算法的路径搜索方式，从初始节点开始搜索，在扩展下一个节点时，不再使用Dijkstra算法进行辅助运算，而是采用路径价值评估函数的运算结果作为启发信息。根据这些信息对存储的路径集按价值高低进行排序，优先扩展价值较高的路径。并且在搜索过程中加入有限层搜索的思想，通过不断的扩展，将生成的新的路径存储在价值优先队列中，利用时间和费用等方面的约束条件对搜索空间进行剪枝，从而形成多约束条件下有限层搜索的A＊算法，简称A＊Level算法。

图1 某航线网络的EKMCSP模型

2.1 关键步骤

2.1.1 数据预处理

对航班属性等相关数据进行整理并建立相应的数据结构。该数据结构以offairport（起飞机场）为主要标识建立数据块，数据块中包含offairport（起飞机场），offcity （起飞城市），inairport（降落机场），incity （降落城市），offtime（起飞时间），intime （降落时间），cost（运价），dep＿longi（起飞机场经度），dep＿lati（起飞机场纬度），arr＿longi（降落机场经度），arr＿lati（降落机场纬度），ct（航班 所 属 国 家），fltno （航 班 号），onlynumber （唯 一 标识）等信息。所有数据块以邻接链表形式存储，并辅助以onlynumber进行定位。

以图1中的某航线网络为例，所形成的数据结构如图2所示。

图2 数据结构

2.1.2 路径价值评估函数

记任意节点u的地理坐标为（ulongi，ulati），其中ulongi和ulati分别代表节点u的经度和纬度。

设任意节点u和d之间的距离为DISud，则

设起始节点s到目标节点t经过节点w，SW（p（s，w））为p（s，w）的路径和，则

设路径p（s，w）的价值为VAL（p（s，w）），则

路径价值评估函数中，综合考虑了机场地理坐标信息和运价花费等因素，VAL（p（s，w））的值越小，则表示路径p（s，w）的价值越高。

2.2 算法描述

A＊Level算法的输入有起飞机场、目的机场、起飞时间和搜索层次等。输出为起飞机场到目的机场的K 条可达路径。A＊Level算法的完整描述如下：

步骤1 数据预处理。对航班数据进行整理，并存入特定的数据结构中。

步骤2 初始化。设已找到的路径数k＝0，并确定TR的值。如果起始节点s和目标节点t之间有直达航班，则以该航班的最高运价为TR；否则从起始节点s开始做两层搜索，在形成的所有路径中以花费最多的路径的运价为TR。从起始节点s开始做一次扩展，形成的所有满足约束的路径放入队列AL＿QUEUE中。

步骤3 队列排序。对AL＿QUEUE 中所有路径按其价值从大到小排序。

步骤4 路径扩展。AL＿QUEUE 队首的路径出队，设该路径的尾节点为lnode，扩展节点lnode的后继节点生成若干条新的路径。

步骤5 剪枝。遍历扩展生成的所有新的路径，对产生回路或者不满足约束条件①、②的路径进行剪枝。

步骤6 有限层搜索。只在有限层进行路径扩展，超过限定的层次则进行剪枝。

步骤7 判断。如果路径的尾节点即为目标节点，则k＝k＋1。

步骤8 扩充路径队列。将扩展后没有产生回路，且满足约束条件①、②、③的路径加入队列AL＿QUEUE。

步骤9 重复步骤3～步骤8，直到k＝K （目标最短路径数）或队列AL＿QUEUE为空。

3 实验结果及分析

实验所采用数据集包含网上采集及其它途径获得的航班数据，共有12716个国际航班的相关数据。每条航班数据包含offairport，offcity，inairport，incity，offtime，intime，cost，dep＿longi，dep＿lati，arr＿longi，arr＿lati，ct，fltno，onlynumber等字段。设MCT＿TIME 为30 分钟，BCT＿TIME 为180 分钟。实验机器配置：Intel

CoreTM2Duo CPU E4600 2.40GHz，内存2.00GB，操作系统：Microsoft Windows XP Professional 2002Service Pack 3，数据库：Oracle 9i，编程：Java＋Myelipse＋struts。为验证基于EKMCSP 模型的A＊Level算法的性能，共设计了3个实验来进行验证。

实验一：设查询得到的路径数为K 且为K 条最短路径，或得到的路径数小于K 且均为最短路径，则查询成功；否则查询失败。多组实验的综合正确率ACC 为

式中：a——进行实验的组数，mi（1≤i≤a）表示第i组实验进行的实验次数，ci——第i组实验中搜索结果正确的次数。对12716条航班数据进行处理，如果城市间存在多个航班，则只保留一个航班，即将节点间多弧连接的国际航线运价搜索的EKMCSP 模型简化为节点间单弧连接的KMCSP模型。分别对A＊Level算法和约束剪枝算法进行5组实验，其中每组实验5次，每次输入不同的起飞机场，目的机场，起飞时间和票价类型等。通过实验后发现，整体上A＊Level算法搜索的正确率和时间效率均高于约束剪枝算法。图3和表1给出了进行5组实验的搜索结果。

图3 约束剪枝算法和A＊Level算法的耗时对比

表1 约束剪枝算法和A＊Level算法的效果对比

实验二：实验处理的数据对象为12716 个国际航班的相关数据，如果城市间存在多个航班，则保留多个航班，即保持节点间多弧连接的国际航线运价搜索的EKMCSP模型。实验输入为：PEK （北京，出发城市），CDG （巴黎，目的城市），2011－01－08 （出发日期），成人 （购票类型）。分别设置4，5和6这3种搜索层次，进行3次实验。通过实验后发现，对传统KMCSP 算法无能为力的国际航线运价搜索的EKMCSP 问题，A＊Level算法可以得到比较满意的结果。在600ms以内，输出与搜索层次相对应的最短路径集，以及每条最短路径相应的总时间花费和总金钱花费 （见表2）。

表2 A＊Level算法的输出结果

实验三：实验处理的数据对象为12716 个国际航班的相关数据，如果城市间存在多个航班，则保留多个航班，即保持节点间多弧连接的国际航线运价搜索的EKMCSP模型。表3给出了进行3组实验的搜索结果，其中每组实验10次，每次输入不同的起飞机场，目的机场，起飞时间和票价类型等。

表3 A＊Level算法的正确率验证

根据式 （4），可得本次实验的综合正确率为93.3%。由此可得，A＊Level算法具有较高的正确率。通过3组实验，证明了A＊Level算法既可以处理节点间存在单弧的模型，也可以处理节点间存在多弧的模型，并具有较优的正确率和时间效率。

4 结束语

目前，国内外对于普通KMCSP问题的应用研究很多，但是针对国际航线运价搜索的EKMCSP问题研究尚少。基于EKMCSP模型的A＊Level算法首先在搜索前进行数据预处理，利用时间、费用等约束条件对搜索空间进行剪枝，并根据民航运输的特点，采用了有限层搜索的思想。另外，结合机场地理坐标信息和运价花费等因素设计了路径价值评估函数，以此提高搜索效率。经过验证，A＊Level算法可以实现国际航线运价搜索的EKMCSP 问题的快速求解，搜索正确率也较高。现实中的全球航线网络异常复杂，航班数量增加迅速，随之产生的搜索规模也异常庞大。如何设计更加科学合理的约束条件和更高效率的路径价值评估函数是下一步研究的重点。

［1］HU Xin，XU Tao，DING Xiaolu，et al.Improvement and simulation of K－shortest－paths algorithm in international flight route network ［J］.Journal of Computer Applications，2014，34 （4）：1192－1195 （in Chinese）. ［胡 欣，徐 涛，丁 晓 璐，等.国际航线网络中K 条最短路径算法改进与仿真 ［J］.计算机应用，2014，34 （4）：1192－1195.］

［2］WANG Zhijian，HAN Weiyi，LI Yijun.Shortest path problem with multiple shortest paths［J］.Journal of Harbin Institute of Technology，2010，42 （9）：1428－1431 （in Chinese）.［王志坚，韩伟一，李一军.具有多条最短路径的最短路问题［J］.哈尔滨工业大学学报，2010，42 （9）：1428－1431.］

［3］WANG Haimei，ZHOU Xianzhong.Improved shortest path algorithm for restricted searching area［J］.Journal of Nanjing University of Science and Technology （Natural Science），2009，33 （5）：638－642 （in Chinese）.［王海梅，周献中.一种限制搜索区域的最短路径改进算法 ［J］.南京理工大学学报（自然科学版），2009，33 （5）：638－642.］

［4］WAN Zhiping，LV Zhimin.A kind of adaptive species optimization of wireless Mesh network Qos routing algorithm ［J］.Journal of Shandong University（Natural Science），2013，48（9）：10－16 （in Chinese）. ［万智萍，吕志民.一种自适应物种寻优的无线Mesh网络Qos路由算法 ［J］.山东大学学报（理学版），2013，48 （9）：10－16.］

［5］MA Yueyong，WANG Haimei，LIAO Jianjun.Comparative study of multi－constrained optimal path algorithms ［J］.Journal of Nanjing University of Science and Technology，2011，35（6）：749－754 （in Chinese）. ［马跃勇，王海梅，廖建军.多约束最优路径算法比较研究 ［J］.南京理工大学学报，2011，35 （6）：749－754.］

［6］Zhang Z，Zhao J.Multi－constraint－pru－ning：An algorithm for finding K shortest paths subject to multiple constraints［C］／／Proceedings of APCC，2008：1－5.

［7］ZOU Yonggui，WEI Lai.Optimal path algorithm with multconstrained condition ［J］.Computer Applications，2008，28（5）：1101－1104 （in Chinese）.［邹永贵，魏来.带多约束条件的最优路径选择算法研究 ［J］.计算机应用，2008，28 （5）：1101－1104.］

［8］NING S.K constrained shortest path problem ［J］.IEEE Transactions on Automation Science and Engineering，2010，7（1）：15－23.

［9］IIT S V，PANDIT A K.A＊prune modified algorithm in video compression ［J］.Ubiquitous Computing and Communication Journal，2008，3 （5）：49－52.

［10］XU Tao，DING Xiaolu，LI Jianfu.Review on K shortest paths algorithms ［J］.Computer Engineering and Design，2013，34 （11）：3900－3906 （in Chinese）. ［徐涛，丁晓璐，李建伏.K 最短路径算法综述 ［J］.计算机工程与设计，2013，34 （11）：3900－3906.］

［11］XU Tao，DING Xiaolu，LI Jianfu.K－multiple constrained shortest paths problem for connecting path search in international flight path network ［J］.Journal of Southwest Jiaotong University，2014，49 （1）：153－159（in Chinese）. ［徐涛，丁晓璐，李建伏.国际航线网络联程路径搜索的KMCSP问题研究 ［J］.西南交通大学学报，2014，49 （1）：153－159.］