在按钮的水龙头上乘车;它与运输一样简单。但是，优步前端的简单实际上包括复杂的建筑和服务的服务，包括精致的路由和匹配算法，将汽车和人们指向人员。从您打开Uber应用程序的时间从您删除关闭时，我们的路由引擎在工作中很难。

这是优步解决路径问题的历史，以及工程如何使我们从五年前在旧金山的几个优步黑人发展到每天在世界各地提供数百万次服务。

开端:2011 - 2014

当Uber平台在五年前开始运营时，估计的抵达时间（ETA）是我们的第一个功能之一。在打开应用程序时，这是骑车者看到的第一件事。

在优步的早期，我们使用了路由引擎的组合（包括osrm.)生成ETA。(此时我们还没有应用内导航，所以我们只将其用于ETA和地图匹配以显示车辆位置。)

我们称这项服务“Goldeta”，这基本上是一个模型，它坐在路由引擎之上，并使用我们自己的历史优步数据在时间和空间中使用自己的历史优步数据进行调整。该解决方案最终考虑了数十万个优步跳闸，将它们与初始路由引擎ETA进行了比较。戈德纳比使用任何单独的ETA更好地工作。然而，这种方法的一个问题是冷启动问题:当我们在新城市推出时，我们没有足够的数据来告知ETA偏移(对于新城市，正是因为这个原因，我们的ETA比老城市更不准确)。此外，随着我们的成长，我们定期需要添加新功能，但由于必须将其实现到一个开源解决方案(OSRM)中，而这个解决方案并没有从头构建一个调度系统，所以开发速度会变慢。

如何构建自己的路由引擎:入门

金德拉在我们的时间里供应我们的时间，但随着我们的增长更多的城市和服务（如2014年3月推出的Uberrush，我们在2014年春季开始工作的Uberpool），很明显，我们需要献身敬业- 为优步建造的房间路由引擎。所以在2014年，我们开始在我们自己的一体化路线发动机Gurafu上工作。Gurafu的目标？高性能，高度准确的ETA计算，专门用于优步。

在我们发射细节之前，让我们讨论路由引擎中所需的本质。整个道路网络被建模为图形。节点表示十字路口，边缘代表道路段。边缘权重代表感兴趣的指标：通常是道路段距离或贯穿它所需的时间。单向街道，转动限制，转弯成本和速度限制等概念也在图表中进行建模。

当然这不是只要建模现实世界的方法。有些人希望将道路段模拟为节点，并且边缘作为一个路段到另一个路段之间的过渡。与之前提到的基于节点的表示相比，这称为基于边缘的表示。每个代表都有自己的权衡，因此在致力于一个或另一个之前了解您需要的东西是很重要的。

一旦确定了数据结构，就可以使用不同的路由算法来找到路由。一个你可以在家里尝试的简单例子是Dijkstra算法的搜索算法，它已经成为当今大多数现代路由算法的基础。然而，在生产环境中，Dijkstra或任何其他在未处理图之上运行的算法通常都太慢了。

osrm是基于的收缩层次结构．基于收缩层次结构的系统实现了快速性能 - 只需几毫秒即可计算路由 - 通过预处理路由图来计算路由。（Below 100 milliseconds in the 99th percentile response time. We need this because this calculation is done every time before a vehicle is dispatched to a ride request.) But because the preprocessing step is very slow, it’s very difficult to make real-time traffic work. With our data, it takes roughly 12 hours to build the contracted graph using all the roads of the world, meaning we can never take into account up-to-date traffic information.

这就是为什么经常需要一些预处理和调整来加快查询速度。(最近文献中这类算法的例子包括公路等级，alt-almorithm， 和可定制的路线规划。）

以下是我们从2014年开始尝试创建自己的路由引擎时所做的尝试:

1.使收缩层次结构动态

在我们的路由图中，随着新的流量信息进入，我们需要能够动态更新这些图形边缘权重。如我们所提到的，我们使用了osrm，它使用收缩层次结构作为其路由算法。收缩层次结构的一个缺点是更新边缘权重时，需要为整个图形重新运行预处理步骤，这可能需要几个小时的大图，例如覆盖整个地球的一个。这使得收缩层次结构不适合实时流量更新。

通过动态更新，收缩层次结构的预处理步骤可以显著加快，在动态更新中，节点的顺序保持不变，只更新由于流量而改变的边。这大大减少了预计算。使用这种方法，即使10%的路段改变了交通速度，也只需要10分钟就可以动态更新世界图表。然而，对于交通更新来说，10分钟仍然是一个很大的延迟，最终被考虑为eta。所以，这条路最终是一条死胡同。

碎片

我们还可以将图形分解为地理区域，又名分叉。分片速度加快构建合同图形所需的时间。但是，这需要对我们的基础架构进行相当多的工程，并将在每个区域的服务器的集群大小中引入瓶颈。如果一个区域在高峰时段期间收到过多的请求，则其他服务器无法共享负载。我们希望充分利用我们拥有的有限的服务器，因此我们也没有实现此解决方案。

3.A *算法

为了实时更新和小规模，我们尝试了a *搜索算法．At a high level, A* is Dijkstra’s search algorithm with heuristics, so A* prioritizes whichever nodes are most likely to find a route from A to B. This means we can update the edge weights of the graph in real-time to account for traffic conditions without needing to do any precomputation. And since most routes we need to calculate are for short trips (the en route time from drivers to riders), A* works well in those situations.

但是我们知道A*是一个临时的解决方案，因为对于长路径它真的很慢:A*响应与所遍历的节点深度成几何级数增长。(例如，从要塞到旧金山的教会区(Mission District)的一条路线的响应时间大约是120毫秒，比收缩层次要长好几倍。)

甚至A*与地标，它利用三角不等式和几个预计算技巧，不会增加*遍历的时间足以使其成为可行的解决方案。

对于长途旅行，A*根本没有足够快的响应时间，所以我们最终使用了一个收缩图，它一开始没有动态边权值。

2015年及以后

我们需要两个世界的最佳：我们需要预兆才能使其快速使得能够快速更新边缘权重，以支持实时流量。我们的解决方案通过仅针对整个图形的一小部分重新运行预处理步骤，有效地处理实时流量更新。由于我们的解决方案将图形分成相对彼此相对独立的小小区的层，因此在需要时并行地运行预处理步骤以使其更快。（点击这里了解更多！）

要了解我们在推动新的路由引擎之前所做的改进，我们跟踪了Gurafu和Goldeta之间的实时ETA准确性，一旦我们的第一个Gurafu版本已准备好进行测试：

2015年4月，我们全球推出了新的路由引擎，使我们能够拥有更准确的ETA预测系统。新系统基于Gurafu，我们的新路由引擎和Flux，优步的第一历史交通系统，基于我们从合作伙伴手机收集的GPS数据。我们主要用于拾取的内部ETA系统，但我们还一直在跟踪ETA准确性，以满足全旅游长度eta。

为了测量ETA的准确性，我们建立了一个工具来吸收我们的Kafka.实时登录以检索到达的实际时间（ATA），并将其与ETA进行比较。此外，我们的团队成员可以直接从应用程序报告ETA错误。测量路径质量有时需要对案例的视觉检查，因此我们还建立了丰富的Web工具，以便可视化，检查和比较来自不同型号和提供商的路线。

这些理智检查表明我们在去年我们走了很长的路要走。

超高效的路线规划和高精度的ETA是至关重要的。我们使用现代路由算法构建一个精心优化的系统，能够处理每秒数十万个ETA请求，单位数字毫秒响应时间。我们所有的新服务，例如Uberpool和Ubereats都以此系统开头。

这个旅程尚未结束。准确性和效率的重要性和效率，以确定到某个地方的最佳方式，以及当我们扩展和改善Uberpool等产品时，将继续上升。我们将打电话更加可靠和智能。如果这听起来像是对您感兴趣的挑战，我们就会喜欢你加入我们．