论文详解：滴滴大数据预测用户目的地，准确率超90% | KDD 2017

本篇文章2615字，读完约7分钟

雷锋。(公开号码:雷锋。《2017 KDD:基于组合优化的出租车订单调度模型》收录了滴滴团队的一篇论文，论文作者是滴滴研究院副院长叶洁萍。雷锋。com将详细解释本文。

论文解释

与在搜索引擎中找到想要的网页相比，在茫茫车流中匹配一辆车带你去目的地要复杂得多。因为网页可以呈现一整天甚至半个月；然而，车辆在高速行驶，乘客和司机的相对位置实时不断变化。匹配过程和方法也非常重要。在给定的区域，有许多乘客和车辆。系统需要全局考虑该区域的需求和供给，以毫秒级的速度进行计算，并实时进行最合理的订单分割，以最大化用户的出行效率和出行体验。

本文介绍了滴滴打车基于组合优化的拆分订单模型。与其他拆分订单模式相比，该模式提高了整体周转率。此外，为了进一步改善用户呼叫汽车时的体验，滴滴还开发了一个目的地预测模型，当用户打开软件时，可以在2毫秒内为用户推荐最可能的目的地。目前，该函数的预测精度已超过90%。

1.拆分订单时优化整体周转率。在早期，出租车软件的订单分配主要集中在每个订单和每个出租车司机之间的关联算法上。当乘客提出一个单一的需求时，系统将尽最大努力匹配调度最近距离的司机，试图使提取时间最短。然而，这些驱动程序是否更适合其他订单往往被忽视。

此前，业界提出了一种基于多智能体架构的新型ntucab，旨在最大限度地减少乘客的等待时间和驾驶距离。在该模型中，每个代理将被视为一个计算单元，它将同时计算和处理n个订单和司机的匹配，但一个订单只能匹配一个出租车司机。如果出租车司机拒绝订单，系统会将订单转发给下一个司机。

然而，这些方法调度时间长，成功率低。对此，滴滴出行提出了一种新的组合优化方法。在这个模型中，一个命令将被广播给几个出租车司机。当多个出租车司机收到同一个订单时，第一个拿到订单的人将得到订单。如果命令未被应答，继续下一轮广播，直到出租车司机应答或乘客取消。该模型的目标是最大化订单周转率，从而保证司机和乘客的旅行体验。实验数据还表明，该模型下出租车的整体成功率比同类模型高4%。

滴滴模型的主要改进之一是使用了“整体”的概念，也就是说，将当前时刻要分配的所有司机和订单组的多对多匹配问题作为一个整体来考虑。以周转率为优化目标，通过将司机和乘客作为一个整体进行分配，提高了乘客订单的整体周转率。

该模型的数学形式为:

其中，max(e)是整个模型的优化目标，即周转率；G(a)≤0是模型必须满足的约束条件，这里可能是一些业务规则，比如一个驱动只能同时分配一个订单；a是模型的解，即如何分配整个订单和整个驱动程序。

假设当前有n个待分配的订单和m个待分配的出租车司机，待分配的全部订单和待分配的司机之间的匹配结果可以定义为m*n的矩阵a _ m*n，其元素a_ij具有以下含义:

其中下标I代表顺序，j代表驱动。考虑到每个出租车司机在同一时间只能广播一个订单，对于每个司机，即每个J，它最多只能广播N个订单中的一个，这反映在矩阵中，即对于每个J列，最多只能出现一个“1”，其余必须全部为“0”。那就是:

2.用物流回归模型计算驾驶员接受概率虽然模型的目标和解决方案已经确定，但仍有一个关键因素需要考虑驾驶员接受订单的意愿。司机接受订单的概率往往取决于很多因素，如订单的价值、行驶距离、方向角、行驶方向等。该信息可以被编码到特征向量x_ij中。

作者使用P_ij来表示驾驶员dj对指令oi的接受概率。关于这种概率的计算，笔者借鉴了计算广告中的点击率预测方法，采用物流回归模型进行计算。

本文利用日志中的数据进行物流回归训练，以驾驶员的接受度为y，以其他特征为向量x，训练得到sigmod函数y = 1/(1+exp(-w*x))中的权重向量w。驾驶员对订单的接受概率与模型相关联，第I个订单的成交概率为:

这样，整个组合优化模型是:

研究人员在北京进行了严格的ab测试，并将该模型与其他两种常用模型进行了比较，以周转率、平均驾驶时间、订单响应时间和取消率等关键业务指标作为核心评价指标。实验结果表明，该模型具有较好的性能，订单总周转率提高了4%。

3.目的地预测:循环正态分布下的概率计算。在寒冷的冬天，用户摇摇晃晃地进入目的地，这不是一个好的体验。如果你能在用户下订单之前，率先为用户推荐最有可能的地点，通常会大大减少用户自己操作软件的时间。

基于滴滴平台的大量历史数据，研究者发现人们的出行往往有一定的规律，用户往往在相似的时间到达相同的目的地；订单位置的分析也有助于准确推荐用户的实时目的地。

基于这一观察，研究人员使用贝叶斯公式建立了用户目标的概率分布模型:

其中，t代表当前时间，d代表日期，(lat，lng)代表纬度和经度，{y1，y2，…，yi，…，yn}代表目的地的可能性，x代表出发地点的时间和纬度和经度。然后剩下的问题是估计出发时间和地点(经度和纬度)的概率分布:

对历史数据的分析表明，用户目的地出发时间的频率直方图往往呈现如下正态分布，因此研究者利用正态分布来估计出发时间t的条件分布，然而，如何估计这种分布的期望值和标准差成为一个需要考虑的问题。

考虑到时间和经纬度的分布是周期性的，均值和方差不能用传统方法估计。因此，研究人员利用循环正态分布，建立了一个优化模型，并通过求解得到了期望均值和方差。

这样，整个算法的流程变成:首先，根据用户的历史订单，依次计算每个目的地对应的订单发出时间的期望值和方差；然后根据当前时间计算每个目的地概率的中间数据；第三步是用贝叶斯框架计算每个目的地的概率；最后，确定阈值，满足阈值的是研究者想要的计算结果:

第一步:根据用户订单历史，估计各目的地订单发出时间集的平均值和方差；

第二步:根据当前时间计算每个目的地的p(t|x_i)和频率p(x _ I)；

步骤3:计算每个目的地的概率p(x_i | t)

步骤4:确定支持度阈值S和概率阈值P，并在第一个屏幕上显示那些满足阈值的。

实验数据表明，该预测模型明显优于基线模型，该模型下的预测准确率为93%，比基线模型高4个百分点。

雷锋网注:

论文下载地址:KDD/KDD 2017/论文/视图/出租车-订单-调度-模型-基于组合优化

相关文章:

作为kdd 2017 DIA的赞助商，滴滴出行现场最值得关注的三大亮点是什么？(带纸质视频)| kdd 2017

雷锋原创文章。严禁擅自转载。详情请参考转载说明。