• 5
滴滴研究院副院长叶杰平:揭开滴滴人工智能调度系统的真面目
统计 阅读时间大约9分钟(3451字)

2016-12-30 滴滴研究院副院长叶杰平:揭开滴滴人工智能调度系统的真面目

去年滴滴成立了机器学习研究院,之后改名为滴滴研究院。

猎云网注:腾讯大数据峰会暨 KDD China 技术峰会中,滴滴研究院副院长、密歇根大学终身教授叶杰平博士非常全面地解密了机器学习在滴滴中的大规模应用,其中包括:出行目的地预测、路径规划、拼车最优匹配、订单分配、估价、运力调度、评分系统等。AI 科技评论根据现场演讲整理成文,并由叶杰平博士与滴滴 CTO 张博亲自审文。本文转自雷锋网,作者亚峰。

叶杰平:滴滴研究院副院长,美国密歇根大学的终身教授。叶杰平是机器学习领域国际领军人物,其主要从事机器学习、数据挖掘和大数据分析领域的研究,尤其在大规模稀疏模型学习中处于国际领先地位。

屏幕快照 2016-12-30 上午11.58.25

去年滴滴成立了机器学习研究院,之后改名为滴滴研究院。

滴滴研究院做的事情是结合大数据与机器学习,搭建滴滴交通大脑。滴滴交通大脑需要收集每个城市、每一时刻的所有交通出行相关数据,然后做出最优的决策(匹配、导航等),从而提高出行效率。接下来我来分享一下滴滴过去一年在大数据和人工智能方面的探索。

屏幕快照 2016-12-30 上午11.58.17

App 首页中的人工智能

打开滴滴出行 App,首页中就包含很多人工智能:

屏幕快照 2016-12-30 上午11.56.26

 

预测目的地

我们先会精确定位用户的位置,下方是用户所要去的目的地。很多情况下我们能够预测到用户去哪里:因为很多出行是比较有规律的:早上上班、晚上回家。我们利用用户的出行数据从时间和地点中预测用户去的目的地,这是人工智能的一种体现。

估价

我们常见的价格预估背后其实也有着非常复杂的计算过程,涉及到路径规划和时间预估(ETA)。其中从起点到终点的路径规划是非常核心的一部分,找到最佳路径后,我们需要计算出 A 到 B 的距离。随后着手解决行程所需的时间估算:起点到终点需要 20 分钟还是 30 分钟。结合路径和时间,我们给出一个预估价。

拼车

拼车选项也是非常复杂的机器学习问题,我们需要计算用户点击拼车后从起点到终点过程中找到一个拼友的概率。如果概率不大,这名乘客就很可能得一个人从头坐到尾,而滴滴给出的折扣也会低一些,如九折等。如果这条是热门路线,路途中很可能会有其他乘客与你在同一时间去同一个或附近的地方。这种情况下,我们可以打一次力度稍微较大的折扣。

叫车后的人工智能应用

乘客与司机匹配

屏幕快照 2016-12-30 上午11.56.34

 

当用户确认叫车后,滴滴需要做订单匹配,找到最适合接该用户的司机。这一流程也是一系列的机器学习问题。

那么如何权衡订单合不合适,可以有多种办法解决:比如距离和时间上离你最近的司机。当然,权衡订单问题背后也包含个性化搜索,如个别用户可能只喜欢某一类车型、某一种类型的司机。尤其是女性用户在深夜十一二点,可能对车型和司机的要求比较高,这需要进行个性化匹配。

如果用户选择拼车,系统如何找到最适合的一辆车:这辆车有可能是空车,也有可能是载人车,与此同时,算出 A 到 B 的时间。

热力图

这里会遇到一种情况,新司机希望空驶时间越少越好,但往往不知道去哪接单,这时候滴滴会给到一个热力图,告诉司机哪些区域未来的半个小时,有可能有很多订单需求。

滴滴人工智能的核心:订单分配

屏幕快照 2016-12-30 上午11.58.10

 

滴滴研究院目前做的最核心的事情是订单分配。在某个时刻有成千上万的乘客,同时也有成千上万的空闲车辆,我们要完成司机和乘客的最优匹配,权衡标准是匹配度。计算匹配度最简单的方法是用距离进行评估,滴滴在前几年均是用距离进行匹配。但路面距离计算仍存在很多不合理的地方,因为各个路段的状况不同,有些地方特别堵,有些则相反,同样是一公里但行驶所耗时间可能完全不同。这里就急需增加时间这一维度。而计算时间又是一大难题,比预估距离还要难。

所以滴滴实现订单最优匹配需要遵循这两大核心:做出最优路径规划,预估时间。

大规模匹配

计算出某个订单的时间和距离后,会遇到一个问题:由于滴滴数据量特别大,每一个乘客不只是让一个司机去匹配,而是需要跟周围上百个司机匹配。在任何一个时刻,滴滴的匹配量高达千万次以上,在一两秒钟完成上千万次的路径规划,这是一项非常大的挑战。

这项决策与搜索不同,用 Google 搜索出结果后,再过 10 分钟结果依旧与之前相同。而滴滴在匹配时,哪怕滞后两秒钟这个司机就可能过了某个十字路口,使得路径规划状况完全不同。我们现在建立起一个机器学习系统,该系统包含历史数据和实时数据,只要在有滴滴的地方,我们就知道车辆行驶的速度和路况。然后找特征,建立系统,也可用深度学习做路径规划和时间预估。

滴滴研究院最近建立了一套深度学习系统,然后加上路况和其他信息去进行预测,这应该是目前第一个用深度学习来做路径规划和时间预估的系统。简单对比下结果,去年开始用机器学习再到最近的深度学习使误差大概降低了70%左右。

接下来需要做最优匹配,这里有很多不同的方法。滴滴有出租车、快车、专车、豪华车等等多条业务线,滴滴能否把各个业务线打通?比如用户叫了快车,但周围可能没有快车司机来接用户,那有没有可能利用算法去做决策,在这个时刻让专车或出租车司机来接这位用户,该调度方案要做一个全局的最优匹配,充分发挥滴滴优势。

在北京,高峰期大家打车困难可能会认为是由于运力不够导致,但经过分析发现,在高峰期滴滴的运力其实是足够的,主要是因为车辆分布不合理。

屏幕快照 2016-12-30 上午11.58.17

 

为此我们开发了一套系统,把整个地球分割成无数个六边形。每一时刻都在检测每一个六边形,然后在某个六边形里面计算订单数和空车数,计算供需是否平衡。

运力问题解决

司机没有在他应该在地方是我们需要解决的一大问题,如果有一个平台可掌握所有信息,这样使其能做出最优决策、最优调度以及导航决策。解决这个问题的第一种方法就是动态调价。我们也在探索另外两种解决方式:

供需预测、运力调度:如何完成预测,我们先来还原一个场景,比如说某个大会大致在晚上 6 点结束后,很多人会有打车需求,这就是预测的一种体现。此外,我们之前也提到人们出行普遍是有规律的,所以能预测某一时刻、某一区域可能缺多少辆车,这样我们就提前 15 分钟或半小时做调度,把过剩的运力从周围调过去,缓解供需问题。这里牵涉到供需预测,供需预测本质上就是一个时间序列的预测问题。

拼车:如果两个乘客的行程和出行时间类似,就无需两个司机去接,而是把两个订单整合为一个组合订单,用一个司机来接。拼车中涉及到一项非常重要的问题就是用户体验:用户体验体现在两个维度,一是价格便宜,二是在接另外一个人时绕的路程和时间不要太多。我们希望把两个订单整合起来后,这个行程路径是相似的。为此,我们建立了几个机器学习模型估计路径匹配度的高低。

预测乘客体验

行程结束后,我们也需要去预测乘客的体验是好是坏。由于历史订单中有些乘客会进行投诉,比如说拼车匹配欠佳、绕路。而有些用户则会给出好评。我们从大量历史数据学习出来哪些特征是导致乘客抱怨的原因,哪些特征会导致好评。

拼车最核心的一点是定价,里面用的也是机器学习优化算法。核心想法非常简单,如果乘客发了拼车单,我们会预测这个乘客起点到终点系统为它找到拼友的概率大不大,匹配度如何?如果预测出他很大概率自己一个人会从头到尾走到底的话,折扣相对就会更低,反之则会高一些。

除此之外,我们也做了很多图像方面的工作。比如驾照图像检测,识别证件号码等,让司机的很多手续无需要到滴滴办公室即可解决。

评分系统

屏幕快照 2016-12-30 上午11.58.25

我们可以把滴滴看做是一种搜索引擎,即乘客搜索司机。与百度搜索信息不同,在百度搜索结束后,就没有其他后续问题。但乘客在滴滴中搜索好司机后,滴滴需要保证安全和出行体验。于是我们在近期引入一套机器学习系统,预测司机的服务质量和服务态度,衡量服务好还是坏需要通过分析大量乘客的打分、评语数据。

以往 滴滴和 Uber 都采用星级打分制,后来我们发现该功能并不完美。现实情况是用户要么不打分,要么给较高的五分或四分,使得星级评分功能不够有效。

这本质上是用户习惯问题,为了让评分系统更加全面,平台把乘客留下的所有痕迹都整合起来,然后给出一个分数评判。比如乘客打出星级后,又进行文字评价态度很差、绕路等,针对乘客给出的两个维度信息,我们再根据轨迹等多项数据,然后给出综合的分数。分数越高,滴滴也会保证司机的收入越高,推动司机主动提高服务质量。

这里存在另外一个问题,就是乘客恶意给司机写差评。针对这一情况我们建立了一个判责机器学习系统,该模型能够判差评的背后是司机的责任,还是乘客的责任。如果责任不在司机,我们就不会降低它的分数。判责系统上线后滴滴平台司机满意度有了显著提高。

系统可视化

最后我们提一下非常重要的系统可视化性,这套系统能够看到历史订单行程中发生了什么事情,如哪些区域是我们比较感兴趣的、成交率高的,订单多的。其次是区域变化情况,如早高峰时订单量涨了,晚高峰订单量跌了,应答率可能在早晚高峰非常低,平时可能非常高,我们可以迅速知道每个区域、每个时刻的情况。

上述为区域,我们也可以有一个城市的维度,比如这个城市大概有多少订单?大概有多少司机?乘客发出订单需求成交率大概有多少?我们也能掌握过去和现在的情况,司机实时看到热区所处的位置,引导司机沿着热区去走,减少空驶时间、提高平台效率。

除此之外,我们也能实时看到跨城情况,尤其是春节之前等节假日,因为有很多人会拼车回家。为此,我们也会找到一些比较特殊的区域,单独去分析它发生了什么事。

可视化系统也能让大家看到全城各个时刻供需不平衡情况:哪些区域供大于求,哪些区域求大于供,哪些区域供需平衡,以及现在和过去发生了什么事。针对这些现象,我们需找到应答率低、成交率低的原因。

1、猎云网原创文章未经授权转载必究,如需转载请联系官方微信号进行授权。
2、转载时须在文章头部明确注明出处、保留官方微信、作者和原文超链接。如转自猎云网(微信号:lieyunjingxuan
)字样。
3、猎云网报道中所涉及的融资金额均由创业公司提供,仅供参考,猎云网不对真实性背书。
4、联系猎云,请加微信号:jinjilei
相关阅读
推荐阅读
{{item.author_display_name}}
{{item.author_display_name}}
{{item.author_user_occu}}
{{item.author_user_sign}}
×