基于价格导向的民航运价搜索方案设计

张宏海，彭明田，刘开胜

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

互联网时代，旅客通过航空公司官网和第三方机票销售网站自助购票已成为机票订购主要方式。旅客自助购票过程包括：机票搜索、预订、支付和出票等多个环节。其中运价搜索是最重要的环节，其根据旅客输入的行程请求，自动搜索并生成可用行程，完成航班可利用舱位的查询及对应航班舱位的价格计算。旅客在进行运价搜索时，既希望能搜索到低价航班，又希望有足够丰富的航班选择，满足其差异化的出行需求；另一方面用户对运价搜索系统的处理性能和响应速度要求较高，通常要求系统能在秒级时间内返回旅客需求的合理化排序结果。

在运价搜索系统中，不同旅客行程伴随不同的始发地、目的地和联程点，也使得在运价计算中不同行程的运价元素（FC, fare component）、价格单元（PU,price unit）和运价行程（JR, journey）也不尽相同。因此，基于航班和运价双因素的航班运价排列组合搜索中，数量庞大的全球航班以及航班航段的迥异，使得航班运价组合数量随航段数量的增长呈指数级增长，其解空间极其庞大。

传统处理方法是从满足行程的航班组合开始处理，因此被称为行程导向运价搜索方法，该方法需要先进行航班搜索，其最大难点是搜索空间大。目前全球每年的航班数量超过3 000 万，运价数量约10 亿条。具体到一次运价搜索，以常见的4 个航段往返中转行程为例，假设每个航段的航班数量为N，则4 段往返行程的航班组合数量为N4；假设每个航班有N 个可用舱位，则可用舱位组合的数量也是N4；假设去程和回程各有N 个运价，则运价组合数量为N2，则整个求解空间为N10。对于航段数量超过4 段的复杂行程，由于航班组合数量会随着航段数量的增长呈指数级增长，其解空间会更加庞大。对于NYC 到LON 这样的繁忙航线，其解空间的数量甚至超过了30 亿。

面对庞大的解空间，行程导向传统运价搜索方法很难在用户可接受的响应时间内给出理想结果，且根据航班信息的剪枝操作虽能缩小解空间，但往往无法给出适用于这些航班组合的最低价格。

基于运价的航班搜索，既能满足旅客价低质优的查询需求，同时也可极大提高航班的搜索效率，是民航运价搜索系统亟待实现的技术。国外对此进行了相关研究，以Demarcken 为首的美国研究团队通过并行化方式将运价搜索拆分为多个子搜索，对系统进行优化和改造[1-3]。该方法在一定程度上提升了系统性能，降低了响应时间，但拆分后的子搜索空间依然很大，无法从根本上解决问题。

为了优化不同行程的航班组合，提高航班搜索效率，设计一种运价搜索方案，以价格为导向构造可能的运价组合，在航班信息缺失的情况下先利用经验信息估计运价组合的价格和合理性，最大限度地缩小搜索空间，筛选出运价组合的最优解。该搜索方案在航空客票搜索、旅客需求收集整合、航空客运信息整合共享方面具有极大潜力，将有效提高民航客运服务质量，获得更大的社会、经济效益。

1 方案设计

为解决价格导向的航班搜索问题，采用启发式搜索算法，利用旅行经验数据对潜在行程价格和舒适度进行估计，剔除不合理结果，筛选出满足旅客需求的最终结果。价格导向的民航运价搜索系统包括以下模块：旅行经验信息、运价索引、运价路径选择、运价拆分和运价组合校验。整体框架如图1 所示。

1.1 旅行经验信息模块

图1 系统整体框架图Tab.1 System architecture

旅行经验信息模块用于生成旅行经验信息数据库。系统从ATPCO 公司发布的运价数据和OAG（official airline guide）发布的航班计划数据中计算得到旅行经验数据，包括从运价数据中提取出的价格信息和从航班数据中提取的舒适度信息。旅行经验数据作为运价搜索过程中重要的启发式信息，用于估计运价组合的综合价格，过滤不合理的运价组合。另一方面，经验数据会按照信息的精确度进行有层次的索引和存储。随着搜索的深入，当系统获得的信息越来越完备时，就可利用更完备的信息索引出更精确的旅行经验信息。令O 为始发机场，D 为目的机场，A、B 为中转机场，在运价路径选择中，旅客最初可能只关心O—A—D 和O—B—D 这两条路径哪个更低价，但随着搜索的深入，会更加关注O—A—D 这条路径上，不同舱位等级、不同航空公司和不同运价类型对应的最低运价是多少。在旅行经验数据的更新方面，对于不同精确度的经验数据，当其产生的原始数据发生变化后，会评估经验数据是否仍有效，对于不同精确度的经验数据，以不同频率更新相应的经验数据库；影响程度大的经验数据更新更加频繁。

1.2 运价索引模块

运价索引模块用来建立运价索引以便快速查找运价。面对数以亿计的运价数据，如何快速遍历和查找运价成为系统性能的关键。恰当地建立索引不仅可以快速提取运价数据，还能有效压缩运价的数据规模。系统并不为每一个运价数据建立索引，而是首先将具有相同或部分相同校验规则的运价聚合成元组，并在元组的基础上根据起点终点、航空公司、舱位类型等信息将元组组织为一个具有层次关系的集合，形成运价数据搜索树[4]，如图2 所示。

图2 运价搜索树Tab.2 Airfare search tree

可以看出，运价搜索树中的每个节点都对应一个运价组，而其子节点是具有更多信息的运价组。如上海到北京的运价组节点下，包含不同舱位类型的子节点，而每个舱位类型的子节点下又包含了对应不同航空公司的子节点。系统归纳每一个节点内运价数据的价格信息，并将这些价格信息存储在旅行经验数据库中。通过此种方式组织运价数据，运价搜索就变为按层次逐级深入每一层节点进行搜索的过程，并可根据每个节点的价格和依据旅行经验信息修正后的综合价格对运价路径进行排序和筛选。

1.3 运价路径选择模块

如图3 所示，运价路径选择模块用来生成潜在的低价路径，根据旅客输入的旅行信息提取相应精确度的运价组最低价格。以运价组对应的O 和D 为节点、最低价格为边权构造运价路径图。在图中用最短路径算法搜索满足旅客输入OD 的前N 条最低价格运价路径，并调用旅行经验数据库中的调用经验数据计算路径的综合价格，筛除不合理的运价路径。这是对搜索结果最粗粒度的筛选，系统为每个旅客的查询请求找出至少一条运价路径。

图3 路径选择模块流程图Tab.3 Flowchart of routine selection module

1.4 运价拆分模块

运价拆分模块用于生成IATA（International Air Transport Association）标准的PU 和JR。系统枚举所有可能的价格单元，组合成为不同的运价行程，这样初始的一条运价路径在这里分化成为不同航空公司、不同舱位类型和不同运价类型的运价行程，拆分规则遵守IATA 和ATPCO 要求。

如：假设有O—A—D—B—O 行程，将其拆分为FC（OA），FC（AD），FC（DB），FC（BO），则可能的PU和JR 有

1.5 运价组合校验模块

运价组合校验模块用于产生最终的最优运价组合，也是整个系统最复杂、最核心的模块，其工作流程如图4 所示，整个流程由3 步组成。

图4 运价组合校验模块的流程图Tab.4 Flowchart of airfare combination calibration module

步骤1在明确航空公司、舱位类型等信息后，利用更精确的旅行经验信息估计每一种运价行程的综合价格，按价格对其排序，并剔除不合理的运价行程。系统选择当前综合价格最优的运价行程，如果该行程中包含未展开的运价组则，则展开该运价组，重新组合为新的运价行程，并重复上述过程计算综合价格，排序筛选。直到当前的运价行程全部为元组组成。

步骤2系统根据同一元组中运价对航班的约束要求生成满足要求的航班。

步骤3在获得航班信息后，系统根据航班信息校验元组中的运价规则，依据ATPCO 标准，自下而上分为3 层次校验，即FC 层、PU 层和JR 层，直到得到通过全部校验且价格最优的运价组合。如果该运价组合的价格高于已知的运价行程价格，则从已知价格最低的运价行程开始继续处理，展开该运价行程中的运价组，生成新的运价行程，评估价格，排序筛选，校验规则等。直到不再有运价行程价格低于已知的运价组合，系统将得到的运价组合结果返回给用户。

目前国际民航业运价数据大约有10 亿条，因此如何索引和筛选运价数据是运价搜索面对的重要挑战之一。确定一个运价（fare）是否可用，需要知道一系列信息：fare（OD，Dep/Arr date，cabin，OW/RT，PU，JR，FC，carrier，tariff，routing，rule，...）。如fare（OD）可以索引到一组运价，而fare（OD，Dep/Arr date）则是fare（OD）的一个子集，依此类推，系统知道的信息越完备，可索引到的运价数量越少，价格越确定，则需要校验的规则也越少。这也是为什么传统的航班搜索要首先生成航班组合，因为有了航班组合才能获得确定运价的完备信息，从而校验某个运价是否可用于这个航班组合。但这种方式的缺点也十分明显，确定完备的信息后，运价的搜索范围被限制在非常小的区域内，很容易错过潜在的低价结果。

从上文对运价数据的描述，可发现运价数据很适合用一个搜索树来描述，各个信息对应树的各级。系统知道的信息越多相当于可以定位到越深的分支上。而搜索过程正是获得信息由少到多的过程，相当于逐级打开搜索树的过程。因此在本方案中系统以搜索树的形式存储和建立运价的多级索引，并且计算各级分支中运价的最低价格和索引一起存储。在搜索过程中，随着已知信息的增加，系统逐级打开搜索树，并根据最低价格进行“剪枝”，筛选出价格较低的分支，沿着这些分支继续深入搜索[5-6]。

具体到技术方案实现上，对于步骤1，整个搜索排序过程大量采用了列生成（Column）算法，基于打分和校验规则高效地在海量解空间中找到下一个最优解。通常而言，运价搜索需要创建所有的组合，对这些组合进行打分排序，然后依次选择最优解，但此种方法效率较低，对于运价搜索系统来说，无法满足性能要求。通过列生成算法，对每个备选的元组按照一定规则进行打分并将其放入对应的Column 中，然后按需产生下一个最优解，且该最优解必须满足特定的校验规则。同时，为提高效率，每产生一个最优解，都会判断后续备选方案是否还有继续处理的必要，如果后续备选方案预估价格已经较高，则无需继续处理。

对于步骤2，在针对每个元组生成可用航班的过程中，为进一步提升系统效率，化解业务复杂度，结合运价业务创新性地采用双向A*启发式算法，并利用有向图策略，将全局网络简化为局部网络压缩解空间[7-9]。经测试，以4 条典型航线和一次中转的求解空间为例，采用双向A*算法后，其求解空间是采用单向A*算法的6%到8%，大幅压缩了求解空间，从而提升了系统响应速度，如表1 所示。

表1 两种算法的结果集对比Fig.1 Comparison between two algorithms

对于步骤3，在运价数据的校验过程中，可以发现运价数据之间会共用一些规则，这意味着系统可以把具有相同规则的运价数据聚合成组。系统将此类运价组作为运价搜索树最底层的叶节点。系统以该层为分界线，把在其之上的信息称为筛选信息，把其之下的信息称为校验信息。原因很简单，在这之上系统利用信息分支来筛选运价，而其之下则是根据信息校验运价是否可用。至此，系统完成了对运价数据的重新组织和索引，数据以搜索树的方式存储。搜索过程中，系统逐层打开各处运价组，进行组合和筛选[10]。

此外，前述系统利用运价索引的最低价格来估计潜在行程的最终价格，但如果系统仅以价格为考虑因素进行搜索，可能给出不合理或者舒适度很差的结果。例如旅客查询北京到上海的航班，系统可能给出经迪拜中转的联程结果或经成都再经武汉两次中转的结果。因此在具体实现上，系统要把舒适度和价格综合起来考虑，可以把舒适度以一定比例转换后加入到价格中，生成一个综合价格，以此来修正系统对质优价廉结果的估计，则综合价格为

其中：P 为原始价格；p1～pn为影响排序的舒适度因素，包括总经停时间、总旅行时间和中转次数等；w1～wn为p1～pn对应的权重系数；K 为调节系数，不同场景下调节系数取值不同。例如相对散客，商务旅客对舒适度的要求更高，因此调节系数会较高。

以海南航空公司布鲁塞尔到北京的航线为例，出发日期为2109 年10 月10 日，抽取系统返回的5 个典型航班，搜索结果如表2 所示。

可以看出，按照综合价格排序的结果明显更加合理，例如直达航班HU492 的综合价格更低，会优先显示给旅客，而两次中转的联程航班HU 8506 HU7992 HU497，虽然价格最低，但由于飞行时间过长，导致其综合价格过高，所以会排在后面。

综上所述，在运价搜索过程中，旅行经验信息是系统用来估计结果优劣的重要启发式信息。系统通过估计运价的最低价格搜索潜在的低运价路径，又利用对舒适度的估计筛选不合理的运价路径，并通过综合价格修正系统的估计。

表2 航班搜索结果排序示例Fig.2 Flight sorting example

2 实例验证

2.1 数据采集与实验环境

数据分析表明，系统的主要查询请求为国内始发的国际航线，其中95%为单程和往返程。因此，验证数据集选择400 条国内始发国际的热门航线，行程类型为单程和往返程，请求类型为多航空公司，1 名成人乘客，旅行日期范围为2019 年8 月至2020 年7 月。

为验证基于价格方案的运价搜索性能，在工程上进行了编码实现和实践验证，采用C++语言编写程序，在Linux Redhat v6.5 系统上运行，主机采用X86 服务器，16 核CPU，内存512G，硬盘2.9T SSD。

2.2 实验评价指标

目前基于价格的运价搜索系统已在生产环境部署，用于为航空公司和代理人网站提供运价搜索服务。

在测试指标的选择上，需要从多个指标综合衡量。通过客户调研和数据分析，不同旅客对航班的关注点不同：散客对于价格敏感，希望系统能够返回更低的价格；商务旅客对于价格不敏感，希望系统能够返回更加丰富的结果，满足其出行需求。此外，所有旅客都希望系统能够快速返回搜索结果。因此，在工程验证上，选取以下3 个关键指标，作为判断方案优劣的因素：①响应时间（s），一个运价搜索请求返回结果的响应时间；②结果丰富度，一个运价搜索请求返回结果的数量；③低价命中率（%），一个运价搜索请求返回结果最低价格的概率。

实验采用上述数据集，依次对基于价格的运价搜索方法（Price-based）和基于行程的运价搜索方法（Travel-based）进行测试，结果如表3 所示。

可以看出，从“响应时间”指标来看，Price-based方法的单程请求响应时间为1.12 s，仅为Travel-based方法的28.41%；且往返程请求响应时间为2.31 s，仅为Travel-based 方法的32.26%；从“结果丰富度”指标来看，Price-based 方法平均结果数为491，Travel-based方法为199，是传统基于行程导向方法的2.46 倍；从“低价命中率”指标来看，Price-based 方法的低价命中率为83.7%，比传统方法提高了38.16%。通过验证结果可以看到，相比基于行程的运价搜索方法，基于价格的运价搜索方法在平均结果数量大幅增加的情况下，响应时间有效缩短，低价命中率也明显提升，证明其成效显著。

表3 不同方法不同指标的结果对比Tab.3 Comparison between different algorithms and indices

3 结语

基于价格的启发式运价搜索方法，利用旅行经验数据对潜在行程价格和舒适度进行估计，筛选出满足旅客需求的最终结果，解决了有限时间内对海量数据空间求运价最优解的难题，为民航运价搜索的快速响应和高效率执行提供了有效的解决方案。该算法的推广将有效提高民航客运服务质量，促进行业社会和经济效益的提升。