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

AI科技评论按:在KDD 2017中滴滴研究院副院长叶杰平所带的滴滴团队关于出租车组合优化分单模型和目的地预测的论文《A Taxi Order Dispatch Model based On Combinatorial Optimization》被收录。AI 科技评论将对这篇论文进行详细解读。

论文解读

相比于在搜索引擎中找到一个想要的网页,在茫茫车潮中匹配到一辆载你去目的地的车辆会更加复杂。因为网页可以持续呈现一整天,甚至半个月;但车辆是高速移动的,乘客和司机的相对位置一直在实时变动。匹配的过程和方式也极其重要,在一个既定区域,乘客有很多,车辆也有很多,系统需要全局考虑区域内的需求、供给,以毫秒级的速度进行计算,实时地进行最合理的分单,最大化用户的出行效率和出行体验。

这篇论文中介绍在滴滴出租车中使用的基于组合优化的分单模型,该模型相较于别的分单模型,整体成交率得到了提升。此外为了进一步提高用户叫车时的体验,滴滴还开发了一个目的地预测模型,能在用户打开软件时,2毫秒为用户推荐出他最可能前往的地点。目前这一功能的预测准确率已经超过90%。

1、分单时优化整体成交率

早期,出租车打车软件的订单分配主要聚焦在每个订单与每个出租车司机的相关性算法上。当一个乘客发起一单需求,系统会尽量匹配调度最近距离的司机,力图让接驾时间最短。然而此时往往会忽略到这些司机是否更适合其他订单。

此前业界曾提出过一个基于多代理体系结构的新模型NTuCab,它的目的是最小化乘客的等待时间和接驾距离。这一模型会将每个代理视为一个计算单元,它会同时计算处理N个订单和司机的匹配,但一个订单只会匹配一个出租车司机。如果一个出租车司机拒绝该订单,系统才会转发给下一司机。

然而这些方法的调度时间往往偏长,成功率较低。对此,滴滴出行提出了新的组合优化方法。在这个模型中,一个订单会播报给几个出租车司机,当多个出租车司机收到相同的订单时,最先抢单的人会获得订单。如果订单未被应答,则进入下一轮播单,直到它被出租车司机应答或被乘客取消。而模型的目标则是最大化订单成交率,从而确保司机和乘客的出行体验。实验数据也显示,这一模型下打车的全局成功率比同类模型高出了4%。

在滴滴的模型中一个主要的改进是使用“整体”的概念,即会整体考虑当前时刻所有待分配司机和订单群体的多对多的匹配问题。以成交率为优化目标,通过整体分配司机与乘客,提升乘客订单的整体成交率。

模型的数学形式即:

其中,max(E) 为整个模型的优化目标,即成交率;g(a)≤0 为模型必须要满足的约束条件,在这里可能是一些业务规则,比如一个司机同一时刻只能分配一个订单等;a 为模型的解,即如何对整体的订单和整体的司机进行分配。

假设当前有n个待分配订单,m 个待分配出租车司机,那么整体的待分配订单与待分配司机的匹配结果可以定义为一个m*n的矩阵A_m*n,其元素a_ij的含义如下:

其中,下标i代表订单,j代表司机。考虑到每个出租车司机同一时刻只能播送1个订单,那么对每个司机,也就是每个j而言,其至多只能播送n个订单中的一个,表现在矩阵中,就是对每个j的一列,至多只能出现1个“1”,其余必须全部为“0”。即:

2、Logistics Regression模型计算司机接受概率

虽然对模型的目标和求解进行了定义,但这其中,还存在一个关键因素,需要考虑司机对订单的接受意愿。司机接受订单的概率往往取决于诸多因素,如订单的价值、接驾距离、方向夹角、行驶方向等。这些信息可以编码成特征向量x_ij。

作者用p_ij表示司机dj对订单oi的接受概率,关于这个概率的计算,作者借鉴了计算广告学中CTR预估的方法,采用logistics regression模型来进行计算。

作者采用日志中的数据对logistics regression进行训练,以司机是否接受为y,其余特征为向量x,训练得到sigmod函数 y = 1/(1+exp(-w*x)) 中的权重向量w。将司机对订单的接受概率与模型关联起来,第i个订单的成交概率即为:

这样整个组合优化模型即为:

研究人员在北京进行了严格的AB测试,将该模型与另外两种行业普遍运用的模型进行了比较,把成交率、平均接驾时长、订单应答时长、取消率等业务关键指标作为核心评价指标。实验结果显示,该模型有更好的表现效果,订单整体的成交率提高了4%。

3、预测目的地:循环正态分布下的概率计算

在寒风凛冽的冬天,让用户哆哆嗦嗦地输入目的地,这个体验并不算好。如果能够在用户发出订单前,率先为用户推荐他最可能前往的地点,往往可以大幅减少他自行操作软件时间。

基于滴滴平台海量的历史数据,研究人员发现,人们的出行往往存在一定的规律,用户往往倾向在类似的时间到达相同的目的地;而对订单的位置进行分析,也有助于精准推荐用户的实时目的地。

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

其中,T代表当前时间,D表示日期,(lat, lng)表示经纬度,{y1,y2,…,yi,…,yn}表示目的地的可能性,X表示出发地的时间和经纬度。那么剩下的问题是估计出发时间和地点 (经度和纬度)的概率分布:

而历史数据分析显示,用户目的地的出发时刻的频率直方图往往呈现如下正态分布,于是研究人员采用正态分布对出发时刻T的条件分布进行估计。但如何估计这个分布的期望和标准差,这就成为一个需要思考的问题。

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

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

Step1:根据用户订单历史,估计每个目的地的发单时刻集合的平均值和方差; Step2:根据当前时间,计算每个目的地的P(T|X_i)和频率P(X_i); Setp3:计算每个目的地的概率P(X_i | T ) Step4:确定支持度阈值s和概率阈值p,对满足阈值的予以首屏展示。

实验数据显示,这一预测模型明显优于基线模型,这一模型下的预估准确率达93%,较基线模型高出了4个百分点。

论文地址:http://www.kdd.org/kdd2017/papers/view/a-taxi-order-dispatch-model-based-on-combinatorial-optimization

原文发布于微信公众号 - AI科技评论(aitechtalk)

原文发表时间:2017-08-15

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏TEG云端专业号的专栏

全国知识图谱与语义计算大会 - 实体发现与链接比赛总结

一 背景 互联网大数据时代中,随着机器语义理解需求的日益增长,知识图谱,即各类实体、概念及其之间的语义关系,日益成为大数据时代知识表示的主要形态之一,并在学术界...

5777
来自专栏QQ大数据团队的专栏

一种海量社交短文本的热点话题发现方法

直接从海量文本中生成语法正确、意思明确的话题,是一件不容易的事情。本文主要介绍在话题生成上运用的一个较为简单高效的方法。

5513
来自专栏人工智能头条

【微信分享】李滔:搜狐基于Spark的新闻和广告推荐实战

1302
来自专栏新智元

华中科大骆清铭:开启“脑空间信息计划”,连接脑科学与类脑人工智能

【新智元导读】华中科技大学(苏州)脑空间信息技术研究院启动在即,旨在使工业级高分辨率脑图成为神经科学的标准工具。这一项目由华中科技大学生物医学成像研究者骆清铭领...

3636
来自专栏达观数据

技术干货 | “想你所想”之个性化推荐:实践与优化

在当今 DT 时代,每天都在产生着海量的数据,移动互联网的兴起更是让我们体验到获取信息是如此的简单和方便。 同时,更多的选择也带来更多的困扰,面对层出不穷的信...

3735
来自专栏机器之心

专栏 | 滴滴KDD2017论文:基于组合优化的出租车分单模型

机器之心专栏 机器之心编辑部 数据挖掘顶会 KDD 2017 已经开幕,国内有众多来自产业界的论文被 KDD 2017 接收。本文是对滴滴 KDD 2017 论...

3288
来自专栏专知

亚马逊NAACL新论文:如何教Alexa语音助手快速理解新语言

1082
来自专栏新智元

【抗击谷歌】亚马逊微软发布深度学习库,让训练神经网络像开发APP一样简单

【新智元导读】AWS和微软共同宣布了推出一个新的深度学习库Gluon。Gluon允许所有技能水平的开发者设计原型、创建和训练深度学习模型,部署在云端、终端设备或...

3568
来自专栏专知

自动驾驶的“大脑” ——控制工程篇(一)

自动驾驶的“大脑”——控制工程篇(一) 中国人工智能系列白皮书 -智能驾驶2017 中国人工智能系列白皮书 --智能交通2017(附报告pdf下载) 一文带你看...

3487
来自专栏华章科技

预测雾霾,大数据能帮什么忙?

10月份以来,北京已经发出三次空气重污染黄色预警,一次蓝色预警。说好的秋高气爽、说好的北京最美季节,为何如此短暂?

952

扫码关注云+社区