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

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中，否则就作为新的边添加。

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

左图是道路网格(充电站表示为浅红色)；中间图表示连接充电站间的所有可行路线；右图则表示更为稀疏的图连接。

这一大规模的导航解决方案 可以有效解决长距离的电动汽车旅行问题 ，利用图的稀疏性和新颖的路径规划算法 可以实现行程时间最小化、大幅缓解电动汽车用户的里程焦虑。

相信未来类似的导航算法将不断促进电动汽车的普及，完成人类历史上最庞大的能源转换革命。

ref：

https://arxiv.org/pdf/1909.03152v2.pdf

https://ai.googleblog.com/2021/01/addressing-range-anxiety-with-smart.html

https://drive-green.co.uk/2018/10/09/range-anxiety-should-i-be-anxious/

https://wattev2buy.com/ev-select-determine-ideal-plugin-electric-vehicle/

关于我“门”

▼

将门 是一家 以专注于 发掘、加速及投资技术驱动型创业公司 的新型 创投机构 ，旗下涵盖 将门创新服务 、 将门技术社群 以及 将门创投基金 。

将门成立于2015年底，创始团队由微软创投在中国的创始团队原班人马构建而成，曾为微软优选和深度孵化了126家创新的技术型创业公司。

如果您是技术领域的初创企业，不仅想获得投资，还希望获得一系列持续性、有价值的投后服务， 欢迎发送或者推荐项目给我“门”: 

[email protected]

    

点击右上角，把文章分享到朋友圈