分享嘉宾：诗安 阿里飞猪

编辑整理：张振

出品平台：DataFunTalk

导读： 当用户打算从A地到达B地时，有时没有直达方案或者不符合预期，这就需要拼接召回技术。面对海量航班、多商家票源，我们基于带约束的路由算法和机器学习算法，兼顾用户偏好和召回方案的合理性，提升拼接召回效率。本次将分享飞猪近一年的技术探索，希望为交通、旅行行业的算法同学带来启发。

01 背景与挑战

1. 拼接召回 IN 机票搜索

首先是背景与挑战，我们今天讲的是拼接召回，它的主要落地场景是飞猪的机票搜索，大家可以从飞猪APP首页的机票、淘宝搜机票，或者支付宝机票火车票小程序，进入到飞猪机票搜索，搜索首页如右图所示。进入到机票搜索之后，当用户发起一次机票搜索时，就和其他传统的搜索一样，机票搜索其实也是一个召回加排序的经典流程。但是在机票搜索里面，不管是在召回阶段，还是在排序阶段，和一般的电商都有比较大的差别。

2. 机票搜索

在召回阶段大概可以分为三种类型，单机票召回、拼接机票召回、拼接跨类目召回。我们举个例子，用户搜索威海到大阪直飞，有两种情况都属于单机票的召回，一是召回一个航线SC2439，来自山东航空旗舰店，它就是一个单机票的召回；二是从威海飞到首尔，再从首尔飞到大阪，虽然它是一个连程，但是机票的商家会把这两程给打包起来，两程的票都是来自于ABC机票专营店，它是来自一个商家的，这个时候商家已经把它拼起来了。所以我们在召回的时候，不管是去召回一个S2439，还是去召回一个OZ124-OZ356，一个商家把两程拼起来的，对我们来讲都是一样的。我们把这种一个商家提供的票都统称为单机票的召回。然后第二个就是拼接机票的召回，有点类似于单机票召回的第二种情况，只是没有商家帮忙打包，这个时候就要我们平台有拼接机票的能力，把不同商家的两张票拼在一起提供出来。这就是我们今天重点要讲的拼接机票的召回。

我们可以看到这个例子，比如说先从威海到首尔是来自一个商家的，再从首尔到大阪是来自一个另外一个商家的，然后把这两张票拼起来提供给用户，这种就是拼接机票召回。第三种是拼接跨类目的召回。举个例子，比如用户同样是搜索威海到大阪，我们提供的不是拼起来的两张机票，而是一张高铁票，从威海到青岛，再加一张青岛出发到大阪的机票，这种不同交通工具的比如火车票加机票的组合，就属于跨类目的拼接召回。到了排序阶段，有三种排序，分别是直飞排序、中转排序和临近排序。这里面直飞排序排得是单机票召回的第一种情况；中转排序，是把单机票召回的两程票和拼接机票召回合在一起排序；临近排序排得是跨类目的召回，为什么叫临近排序呢，因为机票拼火车票，通常火车段比较短，机票段比较长，所以在火车票那边来看的话，它的出发地和目的地相对于整个行程来讲是临近的，所以我们把它称作邻近的排序。以上三类排序完成后，还有一个混合排序，最后到了展示层的时候展示出来。展示出来的时候，有一个点是我们看到中间框起来那几个组合特价，这个标区别了单机票召回的第二种和拼接机票召回，我们今天重点讲的就是拼接机票的召回，它是一个比较深入行业的问题。

3. 拼接召回的挑战

拼接机票的召回是一个比较深入行业的问题。深入进去有不少的挑战，首先是业务场景的多且杂。刚刚我们举的例子只是一个单程搜索的例子，就是用户简简单单地搜了一个从A到B。实际上，飞猪提供了单程、往返、多程等多种搜索能力，然后每一种又分别有多种的召回方式，不同的搜索类型乘以不同的召回方式，合起来其实是比较复杂的。

第二个挑战是什么？其实买过机票的人应该都知道，我们看上一个机票，假如现在不买，可能过几分钟价格就变了，因为机票的价格它确实是实时变动的，所以在召回的全阶段我们没有办法每一步都拿到一个绝对准确的价格。然而价格对于机票来说，它绝对是一个非常重要的特征，它是很多用户买机票时最关键的决策因素，所以价格的变动是我们面临的巨大挑战。

第三个挑战是复杂的业务逻辑。国家、机场、商家，各个维度都会有自己的一些规则，比如你在有些地方中转，国家可能需要单独办签证，这样对于用户的中转比较麻烦，再比如说有些商家他们对拼接有特殊的要求，部分商家只允许和自己提供的行程进行拼接，部分商家不能和自己提供的行程进行拼接，有些商家只能和部分商家提供的行程进行拼接，这些业务逻辑穿插进来，也会影响我们拼接的结果。

4. 拼接召回的期望目标

召回的期望目标有以下几点：一个是搜索有结果，当用户搜一个很冷门的出发地目的地，很有可能没有办法召回一些直飞的票，而且因为它冷门，商家也不会去主动拼接。在这种情况下，我们期望能够通过平台的跨商家拼接为用户找到合适的票；二是我们希望可以找到优质票，比如说价格更便宜的，或者是出行的时间更合适的票；三是给用户更多选择，我们通过多交通方式拼接的方式，希望能够让用户看到更多的可能性，是不是可能坐火车去临近的城市性价比更高？时间更合适？这种都为用户提供更多可能。

我们最终的一个目标还是期望用户综合的体验会比较好，能够在飞猪找到适合自己的交通方案，比如说在疫情期间，因为各航司都大幅度减少了航班，这个时候直飞航班减少了，然后拼接召回在这个阶段发挥了很重要的作用。

02 算法实践

1. 以单程一次中转为例

接下来我们讲下算法的实践。还是以比较简单的单程的一次中转为例来梳理一下这个问题，用户搜索了出发到达，A到B，理论上所有的通航城市都是候选的中转城市。当确定中转城市后，比如说我们已经选定了最上面City1，然后出发城市经由City1再到重点，又有大量的航班，而且在每一个航班的维度，还是会有很多商家供票。这个问题的解空间是千万级的，直接去求解。其实可以，但是耗时很久，因为取价是一个比较复杂的操作，所以我们对问题进行了拆解。

2. 问题解法

机票的拼接是一个比较复杂的操作，而且有时间的限制，所以我们在实际上去解这个问题的时候，把这个问题进行了一步步的拆解。具体来看的话，我们把它拆成了四步，第一个是构建城市的联通图，第二个是中转点的初选，第三个是中转点的精选，最后一个是航班的组合。所谓的中转点其实就是中转城市，我们接下来看一下，每一步我们具体如何实现。

首先是构建城市的联通图，在这个阶段我们其实是利用航班的计划，还有历史城市的成交数据，构建了一张所有通航城市的联通图，然后利用图引擎快速的检索出发地到目的地的一个子图，然后如图所示初选中转点，这里以机票最重要的价格信息来筛选，基于我们的离线大规模的机票缓存的低价库，然后以中转点之间的最低价作为它的权重，以价选点。然后就是中转点粗排到精排的阶段，我们引入了地理位置之外的更丰富的多元特征来挑选少量top的中转城市，减少后续系统的压力。这一步主要是一个排序问题。最后一步就是航班组合的选择，这一步其实也是一个排序的问题，但是我们这一步就已经先拿到了准实时的比较准确的价格，主要难点是要在性能要求极高的情况下做最后一边排序，最后选出航班的组合，我们可以看到在中转点精选和航班组合选择这两个阶段，我们把问题变成了两个排序问题。

3. 中转点精选

在中转点的精选阶段，我们选用了用户的静态特征，和航班的组合特征，以及中转点维度的一些统计特征，还有用户的偏好特征，另外还有一些行业的特征，我们把它们合在一起，然后用了一个比较简单的NN模型打分，直接去选top，作为我们top的中转城市。这就是我们本次搜索的中转点的选择。

4. 航班组合选择

在航班组合的选择阶段，它虽然也是个排序问题，但是区别在于这一步是一边取价格，一边计算分数。我们最开始也说了，机票的价格是多变的，这一步其实对于性能要求比较高，而且我们还有一个难点，就是我们只拿价格算的话缺少一个全局的辅助信息。因此我们在这里的做法是：一是在特征上，离线统计模拟全局的信息，二是选用了LR的模型，一个非常简单的模型，它可以让我们把权重直接写到内存里面，会过一段时间自动去更新一下，因为是LR模型，所以也很好解释。

上面的图给大家展示一下，我们最关键的两个决策因素：价格和时长。首先是价格，不同的目的地、不同的出发日期，它的价格差距很大，比如说从北京飞到上海，或者是飞到伦敦，他们价格就不在一个量级上，而且平日飞、节假日飞，价格差距也会很大。因此我们在使用价格这个特征的时候就不会去用它的绝对值。最好能有一个全局的信息，有一个上下文的信息，然而刚才说过了，因为一边取价一遍打分，全局的信息拿不到。所以在这个情况下，我们使用了T-1天的价格，比如昨天同出发地目的地下的最低价的比值来表达价格，我们可以看出价格越高，用户越不愿意买，而且如果当日价格高于昨日最低价的两倍时，用户就不太会买了。这我们的认知也是比较一致的。再者是时长，和价格一样，它也有不同行程之间时长差距很大的问题。比如说可能上海飞北京两个小时，飞到伦敦十几个小时，它的差别是很大的，但在这一步的时候，是在中转点选择之后的，我们在选定了特定中转点的时候，飞行时长基本上比较一致了。所以可以用中转时长来给代替总时长，而中转时长不太会有因为不同的航段差距大的问题，所以这里我们用了中转等待时长的绝对值。我们可以看到，用户比较倾向于等待两个小时左右，低于和高于两小时的时候，权重就会下降。这样其实也比较符合常识，低于两个小时，用户可能会担心来不及换乘，如果等太久的话，是对时间的一个浪费。除了这两个特征，我们还精选了一些反馈类的特征，还有表征出行便利性的一些特征，还有一些行业特色的一些特征，这些�