用于导航的地图绘制算法通常依赖于Dijkstra 算法，这是教科书中用于查找图中最短路径的基本解决方案。Dijkstra 算法简单而优雅 - 它不是考虑所有可能的路线（指数），而是迭代地改进初始解决方案，并且在多项式时间内完成。原始算法及其实际扩展（例如A* 算法）每天在全球道路网络上用于规划车辆路线数百万次。然而，由于大多数车辆都是燃气驱动的，这些算法忽略了加油考虑，因为 a) 加油站通常在任何地方都有，只需绕行一小段路，并且 b) 加油所需的时间通常只有几分钟，与总行程时间相比可以忽略不计。
对于电动汽车 (EV) 来说，情况则有所不同。首先，电动汽车充电站并不像加油站那样普遍，这可能导致里程焦虑，即担心汽车在到达充电站之前就耗尽电量。这种担忧非常普遍，因此被认为是广泛采用电动汽车的障碍之一。其次，为电动汽车充电是一项更需要决策的任务，因为充电时间可能占到总行程时间的很大一部分，并且可能因充电站、车型和电池电量的不同而有很大差异。此外，充电时间是非线性的 — 例如，将电池从 90% 充电到 100% 所需的时间比从 20% 充电到 30% 所需的时间更长。
电动汽车在需要充电之前只能行驶一定距离，不同道路和不同站点的时间成本也不同。目标是优化总行程时间。
今天，我们介绍了一种新的电动汽车路线规划方法，该方法集成到您的汽车中，适用于参与计划的电动汽车，通过将充电站集成到导航路线中，可以减少里程焦虑。根据电池电量和目的地，地图将推荐充电站和相应的充电水平，以最大限度地缩短行程总时长。为了实现这一点，我们设计了一种高度可扩展的解决方案，用于推荐通过充电站的高效路线，从而优化驾驶时间和充电时间的总和。
上图显示了燃气汽车从柏林到巴黎的最快路线。中间的图显示了续航里程为 400 公里的电动汽车的最佳路线（显示行驶时间 - 不包括充电时间），其中沿途较大的白色圆圈表示充电站。下图显示了续航里程为 200 公里的电动汽车的最佳路线。
通过充电站进行路由
路线选择的一个基本限制是充电站之间的距离不能大于车辆充满电后可以行驶的距离。因此，路线选择模型强调充电站图，而不是道路网络路段图，其中每个充电站是一个节点，充电站之间的每次行程是一个边。考虑到每辆电动汽车的各种特性（如重量、最大电池电量、插头类型等），该算法确定哪些边对所考虑的电动汽车是可行的，哪些是不可行的。一旦收到路线请求，Maps EV 路线就会在可行图中添加两个新节点（起点和目的地），并添加多个新的（可行）边，这些边概述了从起点到附近充电站以及从每个附近充电站到目的地的潜在行程。
在此图上使用 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%。
图稀疏化
为了在自信地解决里程焦虑的同时执行上述操作，算法必须以良好的精度计算出站点之间每次行程的电池消耗。为此，地图会保留任何两个站点之间行程沿途道路特征的详细信息（例如，行程每段的长度、海拔和坡度），同时考虑到每种电动汽车的特性。
由于每个路段所需的信息量很大，维护大量边可能成为一项内存密集型任务。虽然这对于电动汽车充电站稀疏的地区来说不是问题，但世界上有些地方（如北欧）的充电站密度非常高。在这些地方，为电动汽车可以行驶的每对充电站添加一条边，很快就会增加到数十亿条可能的边。
左图显示了北欧充电站的高密度。不同的颜色对应不同的插头类型。右图说明了为什么随着充电站密度的增加，路由图的大小会迅速增加。当彼此范围内有许多充电站时，诱导路由图是一个完整的图，其中存储了每条边的详细信息。
然而，这种高密度意味着，两个相距较远的车站之间的行程无疑会经过多个其他车站。在这种情况下，维护长边的信息是多余的，因此可以简单地在图中增加较小的边（spanner），从而得到更稀疏、计算更可行的图。
扳手构造算法是贪婪几何扳手 的直接泛化。充电站之间的行程按从最快到最慢的顺序排序，并按该顺序进行处理。对于点a和b之间的每次行程，该算法都会检查扳手中已包含的较小子行程是否包含直接行程。为此，它会将使用扳手中已有的子行程可以实现的行程时间和电池消耗与直接a - b路线的相同数量进行比较。如果发现它们在一个微小的误差阈值内，则不会将从a到b 的直接行程添加到扳手中，否则会添加。应用这种稀疏化算法具有显着的影响，并允许图形有效地响应用户的路由请求。
左侧是原始道路网络（浅红色表示电动汽车站）。中间的站点图包含站点之间所有可行行程的边。右侧的稀疏图使用更少的边来维持距离。
概括
在这项工作中，我们设计了一种可扩展的电动汽车长途路线规划解决方案，通过使用图形稀疏化和标准路线规划算法的新框架，包括访问充电站。我们很高兴将算法思想和技术交到地图用户手中，并期待为全球电动汽车驾驶员提供无压力的路线！
致谢
我们感谢我们的合作者 Dixie Wang、Xin Wei Chow、Navin Gunatillaka、Stephen Broadfoot、Alex Donaldson 和 Ivan Kuznetsov。
评论