从 A 点到 B 点的预计旅行时间称为预计到达时间（ETA）：
Uber 在 4 种情况下计算 ETA：
- 眼球：当乘客在应用程序中输入目的地时
- 调度：在最短等待时间内找到接送乘客的车辆
- 取车：查找接送乘客所需的时间
- 途中：实时更新到达目的地的时间
一次旅行通常需要约 1000 次 ETA 请求。
然而，计算 ETA 是一个难题。因为出发地和目的地之间的距离不是一条直线。
相反，它由复杂的街道网络和高速公路组成。
Uber 聪明的工程师们用简单的想法解决了这个难题。
1.路由算法
他们将物理地图表示为图形。
每个道路交叉口都是一个节点。
而每个路段则被模拟为有向边。
因此，计算 ETA 就成了在有向加权图中寻找最短路径。
Dijkstra 算法是在图中寻找最短路径的著名算法。
但 Dijkstra 算法的时间复杂度为 O(n logn)。n 是图中道路交叉点或节点的数量。
仅旧金山湾区就有 50 万个道路交叉口。因此，Dijkstra 算法在 Uber 的规模上是不够的。
于是，他们对图形进行了分割。然后在每个分区中预先计算出最佳路径。
因此，与图分区的边界交互就足以找到最佳路径。
想象一下，一个稠密的图形映射成一个圆。
必须遍历圆中的每一个节点，才能找到两点之间的最佳路径。
因此，时间复杂度就是圆的面积：π * r^2
而分区和预计算会使效率更高。
只需与圆边界上的节点交互，就能找到最佳路径。
因此，时间复杂度就是圆的周长：2 * pi * r
换句话说，在旧金山湾区找到最佳路径的时间复杂度将从 500 Thousand 减少到 700 Thousand。
2.交通信息
要找到两点之间的最快路径，必须考虑路段上的交通情况。
交通情况取决于一天中的时间、天气和道路上的车辆数量。
他们使用交通信息来填充图的边权重。因为这样能使 ETA 更准确。
此外，他们还将汇总的历史速度信息与实时速度信息相结合。因为额外的遍历数据会使交通信息更加准确。
3.地图匹配
GPS 信号会变得嘈杂和稀疏，尤其是当车辆进入隧道时。
此外，多径效应也会使 GPS 信号变差。当建筑物反射 GPS 信号时，就会产生多径效应。
GPS 信号不佳会降低 ETA 的准确性。
因此，他们会进行地图匹配，以找到最佳的 ETA。
地图匹配通过将原始 GPS 信号映射到实际路段来实现。
他们使用卡尔曼滤波器进行地图匹配。它能获取 GPS 信号，并将其与路段进行匹配。
把卡尔曼滤波器想象成一个能正确猜测事物位置的人。在猜测过程中，新信息和旧信息都会被考虑在内。
此外，他们还使用维特比算法 Viterbi algorithm 来找到最可能的路段。这是一种动态编程方法。
把维特比算法想象成一个人，即使有些单词拼写错误，也能找出正确的故事。他们通过查看附近的单词并修正错误，从而使故事更加合理。
如果实际行程时间高于预计到达时间，乘客很可能会避免今后的行程。
此外，Uber 每天完成的出行次数超过 1800 万次。
因此，就 Uber 的规模而言，一个糟糕的 ETA 可能会给他们带来数十亿美元的损失。
目前的方法允许他们将请求扩展到每秒 50 万个。