炼数成金 门户 科学探索 算法 查看内容

解密Uber数据科学团队路径选择算法的优化之路

2016-6-16 16:48| 发布者: 炼数成金_小数| 查看: 27048| 评论: 0|原作者: THI NGUYEN|来自: 数学中国

摘要: 一键用车现在已经烂大街,但是Uber简单的界面下又隐藏着怎样复杂的后端架构和服务呢?这些复杂的路径规划和订单匹配算法又是如何让车找到人,将人送到目的地的呢?现在让我们揭开UberApp这神秘的面纱。当五年以前Ube ...

工具 算法 模型 基础 服务器

概述
一键用车现在已经烂大街,但是Uber简单的界面下又隐藏着怎样复杂的后端架构和服务呢?这些复杂的路径规划和订单匹配算法又是如何让车找到人,将人送到目的地的呢?现在让我们揭开UberApp这神秘的面纱。

当五年以前Uber平台刚刚开始运营的时候,到达时间估算(ETA)是我们推出的第一个特性。这是乘客对我们的第一印象。
2012年早些时候,应用内显示的 ETA

在Uber早期,我们用了一系列路径引擎的组合(包括OSRM)来做ETA。(我们刚开始并没有应用内的导航功能,因此我们只能用它来做ETA并且匹配所显示的车辆位置。

我们已经用黄金ETA很久了,但是随着我们在更多城市和服务上的扩展(比如在2014年3月开启的 UberRUSH 服务以及 我们在2014年春天开启的 UberPOOL 服务),我们需要为Uber打造一个自己的路径引擎的需求已经变得非常迫切了。因此,在2014年,我们开始着手打造我们自己的全套路径引擎,我们称之为 Gurafu。Gurafu的目标是为Uber量身定制一个高性能、高精度的ETA计算工具。

在我们具体实施之前,让我讨论一下我们需要一个路径引擎的必要性。这整个的路网就像一个图结构(运筹学中图论的概念)。节点表示十字路口,边表示道路。这个边的权重表示一个有趣的度量:这段距离或时间路线经常被人经过。其他一些像单行道,转弯限制、转弯成本以及速度限制等概念都在这个图结构模型被考虑到了。

当然,这不是通往真实世界的模型。有些人也把道路作为节点,而两个路段的转换作为边。相对于之前提到的基于点的表达式这就是所谓的基于边的表达式。每种表达式都有自己的权衡,因此在确定使用哪种模型之前明白我们需要什么就变得非常重要了。

一旦你的数据结构确定了,你就可以使用不同的路径规划算法来寻优。举一个简单的例子,你可以尝试的最基础的Dijkstra搜索算法,这种方法是今天大多数搜索算法的基石。但是在生产环境下,Dijkstra或者其他一些算法常常没法处理太大规模的图结构,它总是显得速度太慢了。

OSRM 是基于收缩的层次结构的。系统基于收缩层次结构来提升性能,通过预处理路线的图结构只用毫秒级的时间就完成整个路径的计算。下面99%的响应都是在100毫秒内完成的。因为在每次车辆收到用车请求的时候我们都需要计算所以我们非常需要这个功能。但是,因为这个预处理步骤是十分缓慢的,想要做实时的交通处理是非常困难的。而我我们的数据会用全世界的道路花12个小时来构建这个收缩图结构。这意味着我们很难去更新这个交通流量的信息。

这是就是为什么一些预处理和变换常常需要加速查询。(这类算法的最近例子包括了高速公路层次算法、ALT算法以及自定义路径规划算法)

这里是从2014年开始尝试构建自己的路径引擎所做的工作:

1. 采用动态的收缩层次算法
在我们的路径图结构中,随着新交通信息涌入,我们需要能够动态更新这些图结构的边权重。就像我们提到的,我们所用的 OSRM 是用 收缩层次来做路径寻优算法的。收缩层次的一个缺点就在与当边权重更新,预处理过程需要用整个图结构重新再跑一边,当我们跑稍微大一点的图结构就需要好几个小时,更不要说全世界了。所以这个收缩层次算法对于实时的交通变化并不适合,我们需要一个增量算法。

收缩层次的预处理步骤可以通过动态更新来快速实现,这种情况下大多数节点的排序将保留,而只是更新需要更新的节点,这样我们就可以大大减少预处理的计算量了。

2. 分片
我们也用一种叫作分片的方式,将整个图结构分解成几个小的地理区域,分而治之。分片加速了我们构建图结构的时间。但是,这里需要在我们的基础设施上为此做一些工作,并且在每个地区的服务器集群大小上总是会遇到瓶颈。如果一个地区在高峰期一下子有太多的请求,那么其他服务就不能共享加载这种分片的资源了。我们想要利用我们有限的服务器资源,因此我们也并没有采用这种解决方案。

3. A星算法
对于小范围的实时更新,我们尝试使用A星搜索算法。在更高的层面上,A星是Dijkstra搜索算法的启发式实现,因此A星优先找到从A到B之间的一条可能的最优路径。这意味着我们可以实时更新图结构的边权重,而且在不需要做任何预处理的条件下计算交通流量的情况。既然大多数航线我们需要计算是短途旅行(从司机乘客途中时间),那么A *在这种情况下其实非常有效的。

不过我们知道A星算法是一个权宜之计,因为它对于比较长的路线规划显得非常的慢:A星的响应速度与深度遍历的节点是相关的,以几何增长。(例如,从普雷西迪奥到旧金山地区教会区的路线计算时间是120毫秒,这相比收缩层次算法花费了数倍的时间)。

即使A星算法利用地标、三角不等式和几个预先估计技巧,不会增加A星遍历的时间,足以使它成为一个可行的解决方案。

但是对于长途旅行来说,A星还是不能够快速响应,因此我们又回到了使用静态收缩图结构的老路。

化蛹成蝶:2015之后
我们既需要使用预处理来加速计算,又想要快速更新边权重来支持实时交通。我们的解决方案仅仅通过重新刷新整个图结构的一部分就可以完成预处理过程,有效解决了实时交通更新的问题。因为我们的解决方案将图像划分为层相对独立的小模块,通过并行执行预处理,让我们能够在必要时让这个过程加速计算。

在我们的第一个Gurafu版本已经准备好测试之后,为了知道我们我们之前推出的新路径引擎的效果,我们打算在2015年1月分别纪录了Gurafu和黄金ETA的实时ETA准确度。
2015年1月份我们制作了一个内部的仪表盘来显示ETA准确性:Gurafu(紫色)相比黄金ETA(绿色和红色)每次预测ETA都更加精准。注意到往往在交通通勤的高峰期(周三晚上和周四早上)Gurafu的表现在这时候一骑绝尘。这里,我们显示的三藩市,但是这个模式在我们所有的其他城市也是如此。

2015年4月,我们在全球范围内推出了一个全新的更较精确的ETA预测的路线引擎系统。新系统是基于我们新的路线引擎Gurafu。另外,基于我们从司机端收集的GPS数据,我们还推出了 Uber的第一个历史交通系统,我们称之为 Flux。
我们使用独有的ETA系统主要是为了获取乘客,但我们也在整个行程中记录每次ETA预测的准确性。为了衡量ETA的准确性,我们用从Kafka日志获取的实时检索实际到达时间(ATA)对比我们的ETA并以此构建了一个工具。
Goldeta 对比 Gurafu: 通过超过十万次的行程采样,系统计算预计到达时间(ETA)与实际到达时间(ATA)的差距。新的ETA系统Gurafu的误差分布更尖更高,这意味着新系统比旧系统在预测是更加稳定(方差更小)。纵轴是行程估计错误的数量。这意味着只有在很少概率会有小错误发生。

这些健康检查显示去年我们已经走过了漫长的道路。

这个优化之旅还没有结束。随着我们扩展和改进像UberPOOL这样的产品,根据地点和时间的上下文确定最优路线还将使得服务准确性和效率进一步提升。

译者: Harry Zhu

欢迎加入本站公开兴趣群
商业智能与数据分析群
兴趣范围包括各种让数据产生价值的办法,实际应用案例分享与讨论,分析工具,ETL工具,数据仓库,数据挖掘工具,报表系统等全方位知识
QQ群:81035754

鲜花

握手

雷人

路过

鸡蛋

最新评论

热门频道

  • 大数据
  • 商业智能
  • 量化投资
  • 科学探索
  • 创业

即将开课

 

GMT+8, 2017-10-20 22:22 , Processed in 0.156228 second(s), 24 queries .