基于多因素双向搜索方法的民航行程计算系统

朱家彬，杨永凯，刘 军

（1.中国民航信息网络股份有限公司研发中心，北京 101318；2.民航旅客服务智能化应用技术重点实验室，北京 101318）

中国航信（TravelSky）是国内唯一一家民航计算机订座系统（CRS，computer reservation system）运营商，在其自主研发的早期版本的行程计算系统中，作为核心的联程航班构建模块是采用基于航线网络图的单向搜索方法实现的。当市场上航班数量较少时，该方法基本可以保证行程查询的效率和可用性。但是随着全球民航市场的高速发展，航空公司和商营航班数量急剧增长，这种基于航线网络图单向搜索的联程航班构建方法已经逐渐不能满足旅客和分销商的行程查询需求，其不足主要体现在两个方面。

（1）对于单向搜索算法，无论是单向的K 短路径搜索算法还是宽度（深度）优先搜索算法，扩展两次后结果会以指数级发散，搜索效率相对较低。因此，当航线网络图节点数量大量增加，或出发地—目的地（OD，origin-destination）间涉及多次中转的情况时，系统性能较低、响应时间较长、用户体验度较差。

（2）为了平衡单向搜索算法的性能问题，减少计算量，使用了由直达航线构造的航线网络图进行搜索计算。在航线网络图中，两点之间的连线最多有1 条，表示这两点间存在直达航线，计算时先搜索出中转路径，然后再基于路径构建联程航班。航线网络图虽然可以压缩图的搜索空间，但由于在搜索路径时没有利用航班的具体信息，无法有效应用航班属性对找到的中转路径进行可用性评估，会降低联程航班结果的可用性。

为了解决上述问题，中国航信在对行程计算系统进行改造的实践中，设计了一种多因素双向搜索方法，通过将航线网络图升级为航班网络图，引入航班信息、舱位状态信息、运价信息等数据构建多因素约束，并采用双向搜索算法加速联程航班构建，从而达到了高性能和联程航班结果高可用性的系统目标[1]。

1 系统设计

1.1 总体设计

旅客通过传统代理人、航空公司官网、在线代理人（OTA，online travel agent）及全球分销系统（GDS，global distribution system）等渠道访问行程计算系统，如图1所示。

图1 外部交互关系Fig.1 External interactions

行程计算系统的总体结构包括两部分，即航班查询服务和数据更新服务，如图2所示。

图2 总体设计Fig.2 Overall design

航班查询服务主要为行程的搜索提供查询服务，当有用户查询行程时，航班查询服务器首先解析用户的输入请求，并根据用户输入的O-D 信息、时刻信息等进行行程的搜索计算，并将符合用户查询条件的行程结果集合返回给查询用户；数据更新服务作为与其他系统交互的接口，主要为行程的生成提供基础数据更新服务，包括：从航班控制系统（FLT，flight system）接收直飞航班的信息更新，从航班库存系统（INV，inventory system）接收舱位可利用的状态更新，及从运价计算系统（PRIC，pricing system）接收里程制运价的相关信息。

行程计算系统的总体计算流程主要包括以下4个步骤。

步骤1数据预处理。为提高行程计算过程中联程航班的构建效率，首先进行数据预处理，根据全市场（或特定市场）的商营直飞航班信息构建航班网络图。

步骤2请求输入。用户输入自己的行程需求，包括出发城市（机场）、目的城市（机场）、出发日期等必选项，同时也可以输入偏好条件，包括喜好或厌恶的航空公司、喜好或厌恶的中转机场、最晚起飞时间、中转次数、转机时间等。客户端根据用户输入的选项，生成用户行程请求参数，并发送给航班查询服务器。

步骤3行程搜索。根据用户输入的请求信息，构建多因素约束，应用双向搜索算法进行行程搜索计算。

步骤4结果筛选。对搜索到的行程集合再次进行综合打分，将满足用户需求的较优结果返回给用户。

1.2 航班网络图

航班网络图不同于航线网络图，是基于直达航班进行构建的。通过遍历直达航班信息，根据直达航班的起飞机场、起飞城市、到达机场和到达城市构建航班网络图。航班网络图中的每条边表示1 个直达航班，边与边之间的连接点表示机场。如果两点之间存在1个直达航班，则在两点之间增加1 条边，如果两点之间存在多个直达航班则会存在多条边，如图3所示。

图3 航班网络图Fig.3 Flight network map

航班网络图是多因素双向搜索的基础。由于航班网络图比较庞大，为了保证行程搜索的高效，可以应用邻接矩阵的方式存储航班网络图，同时对航班属性信息进行压缩存储[2-4]。

1.3 多因素双向搜索方法

在行程搜索环节，主要应用的搜索算法是双向宽度优先搜索算法。该算法首先解决了单向搜索算法搜索效率低的问题，同时，在搜索中应用多因素约束的综合排序打分策略也可以大大提升结果的可用性。

给定航班网络图G、出发地O 和目的地D，请求返回的行程数量为N。整个搜索方法的流程如图4所示。

图4 多因素双向搜索方法流程图Fig.4 The flowchart of multi-factor bidirectional search

该方法的主要步骤可以概括如下。

1）扩展

根据用户输入的出发地O 和目的地D 从航班网络图的两端进行扩展，即分别以出发地和目的地为初始节点在航班网络图上进行边的搜索，找到以出发地为初始节点的所有航班经过的路径集合Li，以及以目的地为初始节点的所有航班经过的路径集合Ri，Li和Ri中存储历史路径的航班信息和机场信息。逐级扩展后将会得到分别以出发地和目的地为初始节点的两个行程集合L={Li}和R={Ri}。

2）剪枝

所谓剪枝即删除行程集合L 和R 中较差的行程点，目的是减少不必要的扩展，从而提高搜索效率，剪枝后生成行程集合L′和R′。剪枝时需要删除不合理的中转点，减少下次扩展时的搜索空间。剪枝过程要尽量避免降低结果的丰富度。剪枝过程发生在每次扩展后，需要对两个方向生成的行程分别进行剪枝，如果一个方向生成的行程已经很差则可以删除。剪枝过程即多因素约束过程，实践中可考虑下列几个因素。

（a）距离

当扩展点的里程超过里程制运价中关于中转里程的限制时则删除该点。为了得到更优的行程结果，对于里程的限制也可以借鉴经验数据，例如可以通过限制绕飞率对中转里程进行限制，实践中绕飞率一般不超过2.5。

（b）中转次数

主要对行程超过一定中转次数的点进行删减。中转次数的限制可以根据经验数据进行设置，例如一个完整行程的中转次数一般不会超过5 次。如果两地之间存在直飞航班，则多次中转的联程航班权重较低。

（c）时间

中转机场的最短衔接时间（MCT，minimum connecting time）限制，低于该时长将无法在相应机场实现中转。另外也可以对旅行总时间设置限制要求。

（d）运价规则

在里程制运价规则中对旅行方向进行了规定，只有满足旅行方向的扩展点才被保留。另外运价规则还对航班的属性进行了限制，例如可以限制整个行程的航班不允许存在航班经停。

（e）其他

包括航空联盟限制等，不再赘述。

3）交集

将两个方向的行程集合L′和R′的扩展点取交集，如果存在交集则可以组成完整的行程P={Pi}（Pi存储了完整的行程路径信息）。

4）检查

对已经得到的行程P 进行检查，检查的目的是对完整行程进行可用性的再度评估及取舍，保证结果集合的多样性和便捷性，同时关注价格，检查后生成行程集合P′。首先可以根据需要保留极端最优行程，如价格最低、旅行时间最短、所有直飞航班等；其次对所有行程进行综合打分，计算行程的分值并按照分值由高到低存储，删除综合打分低的行程。典型的打分项包括：对舱位可利用状态打分（CAV Score，cabin availability score）、对行程的总旅行时间打分（TFT Score，total flight time score）、对行程的中转次数打分（Connection Score）、对行程中航空公司之间的关系打分（Alliance Score）等，汇总后获得总分值。

5）判断是否需要进一步扩展

如果已经搜索到的行程数量还没有达到返回结果的数量限制，即|P′|

1.4 方法模型

多因素双向搜索方法描述可以简化为如下数学模型。

航班网络图抽象为有向图G=，其中：V={v1，v2，…，vn}为节点集，n 为网络图中节点的个数；E={e1，e2，…，em}为边集，m 为网络图中边的条数。

正向搜索：指定O=v1为搜索起点，宽度遍历其作为出度点的边，然后再以得到的边集查找对应的入度点，这样就得到路径集L1={v1e1v2，v1e2v2，v1e3v3，…}，然后以路径集中各路径终点为起点重复以上步骤，并在查找过程中删除有重复点的路径，得到路径集L2={v1e1v2e4v4，v1e2v2e4v4，v1e3v3e5v4，…}。重复以上步骤A 次，可以得到路径集合L={L1，L2，…，LA}。反向搜索：指定D=vn为搜索起点，进行反向遍历，最终得到路径集合R={R1，R2，…，RA}。基于O、D 两个端点，同时分别执行正向搜索和反向搜索，可得到路径集L 和R，设定VL∈L 为L 的路径终点集合，VR∈R 为R 的路径终点集合，如果VL∩VR≠ ，则可以获得完整行程P。

多因素约束条件：在双向搜索过程中，每步均通过多因素约束进行剪枝，以控制发散。

1）距离约束条件

针对O、D，查询其里程制运价中总里程限制，设为M，则约束条件如下

式中：g=〈Vg，Eg〉表示搜索过程中产生的1 条路径；de表示路径中边e 的里程。

绕飞率约束一般限制为2.5，则

式中Zg表示路径g 的两个端点间的商营直飞里程。

2）中转次数约束条件

中转次数一般不超过5 次，即

Hg-2≤2.5 ∀g∈L∪R∪P

式中Hg表示路径g 上所有节点的数量。

3）时间约束条件

设定te和tv表示路径g 上e 边的飞行时长和两个衔接边在v 点上的衔接时长，Cv表示v 点的MCT 时间限制，T 表示O、D 间总旅行时长限制，则

此外还可以根据运价规则、航空联盟等设置约束条件，以尽快达到剪枝的目的[8-10]。

在上述约束条件的基础上，针对完整行程集合P，确定打分规则进行评分筛选，则路径g 的评分公式如下

式中：Sg为路径g 的总分数；sq为路径g 的第q 项分数；Q 为评分项。

2 工程验证

基于上述设计方案，在工程上进行了编码实现和比较验证，主要验证基于航线网络图的单向搜索方法与基于航班网络图的多因素双向搜索方法在搜索性能和结果可用性方面的差异。具体的开发环境和部署环境如表1所示。

表1 工程实践的应用环境Tab.1 IT environment of practice

首先应用性能测试工具LoadRunner 模拟用户并发查询场景，分别对单向搜索方法与多因素双向搜索方法进行搜索性能的比较。

根据CRS 系统的实际请求随机选取多组国内、国际航线作为输入集合，配置查询5 条路径的联程航班结果进行30 min 压力测试，限制最大中转次数不超过5 次，航班最大衔接时间不超过24 h。测试中启动10台查询服务器，并发用户数为50。

测试一采用单向搜索方法。根据市场航线数据构建国内航线网络图（167 个节点，2 460 条边）及国际航线网络图（3 538 个节点，45 838 条边）。单向搜索模式下，随机选取200 对不同的国内O-D，查询5 条联程路径结果的平均响应时间为0.122 s，随机选取1 000对不同的国际O-D，查询5 条联程路径结果的平均响应时间为9.878 s。

测试二采用多因素双向搜索方法。根据市场航班数据构建国内航班网络图（167 个节点，12 300 条边）和国际航班网络图（3 538 个节点，225 300 条边）。多因素双向搜索模式下，随机选取200 对不同的国内OD，查询5 条联程路径结果的平均响应时间为0.187 s，随机选取1 000 对不同的国际O-D，查询5 条联程路径结果的平均响应时间为0.212 s。

测试一、二的性能对比结果如表2所示（测试用时为30 min）。

表2 单双向搜索结果对比Tab.2 Comparison of one-way and bidirectional search results

测试结果表明：当网络图的节点数量较多时，单向搜索响应时间的增长比较明显，而双向搜索响应时间的增长是可控的。

在上述搜索性能比较的基础上，对搜索过程中产生的联程航班结果按照系统综合评分方法进行可用性评分比较。随机选取了1 000 个测试结果进行可用性综合评分（评分项包括CAV Score、TFT Score、Connection Score、Alliance Score，每项满分为1，总分满分为4）对比分析，评分分布如表3所示。结果表明：多因素双向搜索方法的联程航班结果在可用性方面的综合评分远优于单向搜索方法[11-12]。

表3 结果评分分布Tab.3 Distribution of results total score

3 结语

综上所述，通过双向搜索与多因素约束相结合的方式，将航线网络图扩展为航班网络图，设计了一种民航行程计算系统。

虽然多因素双向搜索方法在流程上和工程实现上比单向搜索方法要复杂一些，航班网络图的复杂程度也远大于航线网络图，增加了行程计算系统建设的难度。但是多因素双向搜索方法保证了搜索性能和结果的可用性，从而完美解决了单向搜索方法在面临搜索空间变大后所产生的搜索效率低下和结果可用性不高的问题。此外，本方案在工程实践中也具有较大应用价值。