谷歌提出新导航算法: 缓解电动汽车“里程焦虑”“充电焦虑”, 助力能源转换革命|充电站_新浪财经

原标题：谷歌提出新导航算法: 缓解电动汽车“里程焦虑”“充电焦虑”, 助力能源转换革命来源：36氪

编者按：本文来自微信公众号“将门创投”（ID:thejiangmen），作者：让创新获得认可，36氪经授权发布。

From:Google Geo Algorithm；编译: T.R

近年来，电动车逐渐得到普及，但电动车的续航问题一直令人焦虑。车企为了缓解这个问题，从大电量长续航和换电两条技术路线推进；同时，大量的基础设施铺设也在进行，充电站密度不断增加。在这种情况下，电动车的续航问题有所改观。

但是，为了获取最优续航方案，人们开电动车出行需要综合考虑续航里程、充电站位置和充电时间等多因素。对于人脑来说，如何获取最优路线？这着实是道有点复杂的思考题。

为了解决这一问题，谷歌的研究人员为新能源时代的汽车导航提出了新的算法，这种算法能综合考虑续航里程、充电时间和行程距离，为用户提供最高效的出行路线建议。

导航算法

目前应用最广泛的导航算法是Dijkstra算法，这是一种用于寻找图上最短距离的基础算法，无需遍历所有可能的路径就能得到结果，是一种简洁优雅的算法。这一算法与其拓展的A*(A-Star)算法，每天在全世界范围内服务着数亿人的出行需求和物流运输。

然而，过去大多数车辆都是利用化石燃料驱动的，可以忽略燃料方面的考虑，这与电动汽车有着很大的不同。一方面，经过一百多年的发展，加油站已经无处不在了；另一方面，加油时间与路途花费时间相比也可忽略不计。

经典的Dijkstra算法

但对于电动汽车来说，出行规划与燃油车的导航有着不一样的约束。目前，虽然发达地区和交通干线上都建立了大量充电站，但就其有限的覆盖范围来看，它们还是与加油站有着较大的差距。

首先，人们的里程焦虑会随着电动车的续航里程减少而不断增加，里程焦虑也因此成了电动车普及过程中的一个主要障碍。

其次，电动汽车的充电时间是非线性的，这意味着从20%到30%的充电时间要比从90%到100%要快。所以充电时间是一个需要决策的过程，需要权衡充电时间与充电电量的关系以获得最优的行程配置。

电动汽车需要在电量耗尽前进行充电，不同的路线和不同的充电站需要花费不同的时间开销。

针对电动汽车的特殊性，谷歌地图团队提出了一种综合考虑充电站和充电时间的电动汽车导航模式，基于电池容量和目标里程规划最优的行程路线，最大化地节省旅途耗时。

从柏林到巴黎的路线图。上图显示了燃油车路线，中图显示了续航400km的电动车路线，下图显示了续航200km的电动车路线。基于充电站的导航

导航过程中的最基础约束是：两个充电站之间的距离不能大于电动车的续航里程。这要求算法模型需要基于充电站构建计算图，而不是依赖道路网来进行计算。在这一图结构中，每个充电站都是一个节点，而充电站之间的路程则构成边。

在实际进行路径规划的时候，需要考虑每一辆电动车的自身特性(包括质量、电池续航水平以及充电头的标准等)。因此，算法需要识别出：连接充电站间的路径对于特定的电动车是否可行。当特定电动车的导航需求发起时，算法将会从充电站节点间找出可行的路径，而不仅仅包含起点到终点的直接路径。

如果不考虑充电时间，利用上述节点和边构成的图可以使用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: 子图结构，在一定误差范围内保留图中最短的路径长度)，从而构建出较为稀疏的、在计算上更为可行的图结构。

研究人员直接使用了贪婪几何算法来构造spanner。充电站间的旅程依照速度从最快到最慢进行排列。对于点a和点b之间的每段行程，该算法检查spanner中是否已包含较小的子行程，如果有则将其归为直接行程。为此，它将使用spanner中已有的子行程来直接与a-b间的路线进行行程时间和电池消耗比较。如果发现它们在很小的误差阈值内，则不会将从a到b的直接行程添加到spanner中，否则就作为新的边添加。

应用这种稀疏算法会产生显著的效果，并且可以在响应用户的导航请求时高效地提供服务。