发布人：Google Research学生研究员 Kostas Kollias 和 Sreenivas Gollapudi
导航所使用的路径绘制通常依赖于 Dijkstra 算法，该算法是在图中寻找最短路径的基础教科书式解决方案。Dijkstra 算法既简单又简洁 – 算法不会去考虑所有可能的路线（数量呈指数增长），而是反复完善初始解决方案（时间复杂度为多项式时间）。在全球道路网中，每天通过原算法及其实践扩展版本（如 A* 算法）确定车辆路线的次数已达数百万。但是，由于大部分车辆都是燃油驱动的，因此这些算法都不会考虑加油的因素，因为 a) 加油站通常随处可见，只需要绕行一小段路，b) 加油所需的时间通常仅为几分钟，与行程总时间相比，可以忽略不计。
对于电动汽车 (EV) 而言，情况则有些不同。首先，充电桩并不像加油站那样常见，因此这会引起里程焦虑 (range anxiety)，即人们会害怕汽车电量在到达充电桩之前会耗尽。这种担心十分普遍，以至于其已成为电动汽车在全球范围内普及的一大障碍。其次，对电动汽车进行充电更是一项需要决策力的任务，因为充电时间会占行程总时间中很大一部分，且会因充电桩、车辆型号和电池电量而各有不同。此外，充电时间是非线性的，例如，电量从 90% 充到 100% 比从 20% 充到 30% 所花费的时间要长。
在需要充电之前，电动汽车最远可以行驶到标称里程。不同的路线和充电桩会花费不同的时间。而我们的目标是优化总行程时间
近日，我们提出了一种全新的电动汽车路线选择方法，该方法已集成到您电动汽车所内置的最新版本 Google 地图中，我们期待通过将充电桩设计在导航路线中，以缓解里程焦虑。Google 地图将根据电池电量和目的地建议充电桩和相应充电电量，尽可能缩短行程持续时间。为实现这一目标，我们设计了一个高度可扩展的解决方案，用于规划途径充点站的有效路线，从而优化行驶时间和充电时间的总和。
上方图片显示的是燃油车辆从柏林到巴黎的最快路线。中间图片是针对续航为 400 公里（显示的行程时间 - 不包括充电时间）的电动汽车显示的最佳路线，路线中较大的白色圆圈为充电桩。下方图片是针对续航为 200 公里的电动汽车显示的最佳路线
途径充电桩的路线选择
路线选择的一个基本约束条件是充电桩之间的距离不能超过汽车在满电量时可以行驶的距离。因此，路线选择模型的着重点是充电桩图，而不是道路网的路段图，其中每个充电桩为一个节点，各个充电桩之间的每一段路程为一条连线。该算法会将每辆电动汽车的不同特征（如重量、最大电池电量、插座类型等）考虑在内，确定当前电动汽车连线的可行性。路线选择请求输入后，Google 地图电动汽车路线选择功能会使用两个新节点（起点和终点）来增强可行图，并使用多个新的（可行）连线勾勒出从起点到附近充电桩以及从附近的每个充电桩到终点的可能路线。
对于根本不介意充电时间的司机（即总是在每个充电桩为电池充满电的司机），在此图上使用 Dijkstra 算法或 A* 算法确定路线就足以提供最佳的可行解决方案。但是，此类算法不能充分地说明充电时间。针对这一问题，算法会通过多次复制每个充电桩节点来构建新的图。其中一半副本对应着电动汽车带着尚有余电（电量为 x，范围为 0%-100%）的电池进入充电桩。另一半对应着电动汽车带着有部分电量 y（范围仍为 0%-100%）的电池离开充电桩。我们在入口节点（电量为 x）到出口节点（电量为 y）之间添加一条连线（约束条件为 y > x），对应的充电时间为电量从 x 充到 y 的时间。如果充电桩 A 到充电桩 B 的行程消耗了部分 (z) 电池电量，我们在充电桩 A 的每个出口节点到充电桩 B 的相应入口节点之间引入了一条连线（电量为 x-z 之间）。执行此转换后，使用 Dijkstra 或 A* 恢复解决方案。
节点/连线复制示例。在此实例中，算法选择在经过第一个充电桩时不进行充电，在第二个充电桩将电池电量从 20% 充到 80%
图稀疏化
为了有把握地执行以下操作并解决里程焦虑，算法必须精确地计算出充电桩之间每段行程的电池消耗情况。为此，考虑到每种类型的电动汽车的属性，Google 地图会保留在任意两个充电桩之间行驶的道路的特征详细信息（即每段行程的长度、海拔和坡度）。
由于每段行程需要大量信息，因此维护大量连线会非常占用内存。虽然这对电动汽车充电桩稀少的地区不是问题，但世界上仍存在充电桩非常密集的地区（如北欧）。在这些地区，如果为电动汽车可在之间快速行驶的每两个充电桩添加连线，那么可能的连线会增加至数十亿条。
左侧图片说明北欧的充电桩非常密集。不同颜色对应不同的插座类型。右侧图片说明随着充电桩越来越密集，路线选择图的大小也在快速地按比例增大。如果彼此范围内存在多个充电桩，那么所产生的路线选择图是一个完整的图，其中会存储每个连线的详细信息
但是，如此高的密集性表明，行驶在两个相对较远的充电桩之间无疑会经过多个其他充电桩。在此情况中，维护长连线的相关信息是多余的，可以只在图中添加较短的连线 (spanners)，从而生成更稀疏、在计算方面更为可行的图。
Spanner 构造算法是对贪婪几何 spanner 的直接泛化。充电桩之间的行程按最快到最慢排序并按此顺序进行处理。对于点 a 和 b 之间的每段行程，此算法会检查是否将已包含在 spanner 中的较短的子行程段归为直线行程。为此，它会将可使用 spanner 中已存在的子行程段实现的行程时间和电池消耗与相同数量的直线路径 a-b 进行比较。如果发现它们位于微小的误差阈值内，则不会将 a 到 b 的直线行程添加到 spanner，如果不在阈值内则会进行添加。应用此稀疏化算法会产生明显影响，且能够在响应用户路线选择请求时有效地服务于图。
左图是原始道路网（用浅红色表示电动汽车充电桩）。中间的充电桩图标出了充电桩之间所有可行行程的连线。右图的稀疏图维持了相同的距离，但使用的连线要少得多
总结
在这项研究中，我们为远程行驶的电动汽车的路线选择设计了一种可扩展的解决方案，通过利用图稀疏化和全新的标准路线选择算法框架，加入了通往充电桩的路线。我们很高兴能够将这种算法理念和技术传递给 Google 地图用户，我们希望为全球的电动汽车司机提供轻松的路线！
致谢
感谢我们的合作者 Dixie Wang、Xin Wei Chow、Navin Gunatillaka、Stephen Broadfoot、Alex Donaldson 和 Ivan Kuznetsov。
原文：Addressing Range Anxiety with Smart Electric Vehicle Routing
中文：TensorFlow 公众号