电动汽车智能充电路径规划研究

赵薪智,李盘靖,张　欢,任珈漪,张荣磊

(山东理工大学 计算机科学与技术学院，山东 淄博 255049)



电动汽车智能充电路径规划研究

赵薪智,李盘靖,张欢,任珈漪,张荣磊

(山东理工大学 计算机科学与技术学院，山东 淄博 255049)

针对电动汽车存在的”充电焦虑”问题，建立了智能电动汽车动态网络系统模型，当存在多目标时，在原有路径规划算法的基础上，提出了”Dijkstra算法+最近邻点法”的最优路径规划算法。该算法可对电动汽车的剩余电量进行智能预判，并能实现电动汽车在充电桩的智能充电，有效地缓解了电动汽车“充电焦虑”问题。

智能电动汽车；动态充电路径规划；智能充电桩;充电网络

随着汽车工业的高速发展，全球汽车的保有量不断增加。以燃油发动机为动力的传统汽车带来的环境污染与能源短缺问题日渐凸显，新能源汽车成为未来汽车技术的主要发展方向[1-5]。然而,电动汽车充电时间较长,一般为5～8 h[6]，势必会对充电桩的负荷、充电排队时间造成很大影响。因此，在多个充电桩可选的情况下，存在着在什么时间前往哪个充电桩的路径规划问题。

目前有关电动汽车充电路径规划的研究仍侧重于单一路径规划算法。彭飞等[7]引入基数堆结构减少路径搜索算法的时间复杂度。樊月珍等[8]采用对弧段而不是标点标号，节省了大量存储空间。刘智清等[9]建立了最优路径规划问题的线性规划模型，以期提高运算速度。但这些算法和模型并不能完全应用到实际中，这是因为一般电动汽车存在多个目标遍历，单一的路径规划算法效率相对较低。此外，还忽略了对能耗模型的研究。电动汽车在特定路段的能耗并非基于实时的交通信息估算，而是赋予常量，或者是单方面对电动汽车的能耗进行估算[10-11]。陈勇等[12]通过等速法来计算电动汽车的续驶里程。徐宝贵等[13]分析了影响车载电池工作性能以及汽车续驶里程的因素。陈德兵[14]分析了电动汽车动力电池在不同温度下的充放电情况。纵观目前的研究，大多局限于充电路径规划和续航里程单方面的研究。本文对电动汽车的能耗建模，将该模型作为电动汽车续驶里程估算和路径规划的基础，对实际道路交通条件下的电动汽车进行路径规划，评估电动汽车的节能效果。

1　电动汽车动态网络模型

智能电动汽车动态交通网络模型主要由智能路网模型、智能电动汽车模型和智能充电桩网络模型3部分组成。

1.1智能路网模型

虚拟智能路网是将实际的道路交通网络抽象为有向网络，其中节点表示电动汽车、充电桩位置以及交叉路口，弧段表示道路，弧段权值表示道路距离、所花费时间、所消耗电能。

node=[id,posX,posY,childs]

其中： id为节点编号，表征电动汽车、充电桩所在位置，为实际位置的抽象表示；posx指节点所在实际位置的精度；posy指节点所在实际位置的维度； childs指当前节点的后续子节点。childs采用map类型，即

childs=[node,weight,mold]

其中：node为指向的下一个节点；weight指的是当前节点到下一个节点的权值；mold表示交通权值类型。

当电动汽车在不同工况(启动、加速等6种状态)时，行驶同样的路段，所耗费的电量是不同的。当电动汽车处在加速或减速工况时，耗电量相对增多。因此，当交通状况越拥堵时，电动汽车加速和减速次数也就越多，耗电量也就越多。

本文以淄博市2014年发布的交通状况为例，采用交通拥堵指数动态模拟交通状况。交通拥堵指数是通过获得分布在道路中的动态车辆位置信息，得到不同等级的道路运行速度，进而得到0～10的指数指标值。交通状况拥堵程度越高，该路段所消耗的时间就越多。

1.2智能电动汽车模型

智能电动汽车模型需要实现的功能有SOC(剩余电量)的预警、自动寻路、寻找最近充电桩、充电等。因此，电动汽车模型为：

cars=[id,speed,SOC,waitTime,chargeTime,

pathTime,costElec,costLen,costTime,

pos,goal,mold,path,pathInfo,trace,sf,gl]

其中：id为电动汽车编号；speed为电动汽车行驶速度；SOC为剩余电量；waitTime表示当电动汽车已经到达充电桩到充电前的等待时间，当开始充电时，waitTime=0；chargeTime表示充电时间，当chargeTime=0时，电动汽车离开充电桩；pathTime表示到达充电桩路上所耗费时间，当pathTime=0时，表示已经到达充电桩；costElec，costLen和costTime分别表示从初始状态到达目的地总共耗费的电能、总共走过距离、总共花费的时间(包括电动汽车充电时间)；pos为所在位置，即节点node编号；goal表示所要前往位置，当电动汽车需要充电时，此时目的地为充电桩位置，否则目的地为最后终点；mold为优化方式；path记录到达每个节点最短路径权值；pathInfo记录到达每个节点的最短路径；trace记录车走过的节点；sf为安全系数，确保SOC在安全电量内；gl为到达最近充电桩的预估值。

1.3智能充电桩网络模型

智能充电桩网络能使智能电动汽车根据实时的充电桩信息做出智能充电决策，因此智能充电桩网络模型为

elecs=[id,pos,sequene,count,totalTime,

capacity]

其中：id表示充电桩编号；pos表示所在节点位置；sequene表示当前充电队列；count表示当前充电的电动汽车数量；totalTime 表示当前充电所需要总时间；capacity表示充电桩车辆容纳数。

1.4模型间的交互联系

智能路网将实际的交通网抽象为有向图网络，为电动汽车提供了位置信息，同时还提供了各路段的权值信息。智能充电桩向智能电动汽车提供当前充电桩位置、当前队列以及所需充电的时间等。智能电动汽车根据优化目标来做出选择。智能电动汽车的速度、SOC等均与智能路网路段权值有关，同时智能电动汽车的排队时间、充电时间、SOC的变化量等与智能充电桩的状态信息也是密不可分的。

2　电动汽车充电路径规划

在建立电动汽车动态网络模型的基础上，提出一种最优的充电路径规划方法，即当电动汽车有多目标需要遍历时，采用基于”Dijkestra算法+最近邻点法”的静态最优路径规划方法，但是由于各路段上的交通状态是动态波动的，难以得到准确的可行驶时间随时间变化的关系式。将时间离散化，即在单位时间内交通状况是稳定的。基于交通路况的动态路径规划可以认为在多个离散的时间点上做出静态的路径规划，也就减少了路径规划次数。同时，当有突发情况发生时，例如有其他电动汽车改变行驶状态、改变行驶路径时，可做出新的路径规划，增大了路径规划的准确率。

首先进行初始化。然后在间隔时间段内初始时刻或有事件发生时进行阶段性分析。对电动汽车的SOC进行智能预警分析。当电动汽车不在充电桩充电时，返回阶段性分析；当电动汽车在充电桩充电时，无需进行阶段性分析；当电动汽车充满电时，回到动态交通中，此时返回阶段性分析。

动态路径规划流程主要由初始化阶段、智能充电桩竞争关系分析、SOC智能预警控制分析以及阶段性分析4部分组成，如图1所示。

图1　动态路径规划流程

2.1初始化阶段

在初始化阶段中， 初始化虚拟场景中的电动汽车、充电桩、路网、时间器等部分，并根据电动汽车的多目的地做出第1次优化。采用Dijkstra算法为基础算法，即各目标点之间使用Dijkstra算法，确保目标之间的路径为最短路径。由于电动汽车一般有多个目的地，因此采用最近邻点法，使电动汽车确定一条遍历所有目标点的最短路径。

2.2阶段性分析

为了增大动态路径规划的准确率并且减少重复路径规划的执行次数，设定间隔的离散时间点和事件集。间隔的离散时间点是将时间离散化，假定在单位时间段内的交通状况不会发生变化，在每个时间段初做出分析。事件集为存储与动态路径规划有关的一系列事件集，包括各类的突发状况、电动汽车状态的改变等。

当time%inte==0||eventGroup.has(e)(系统时间在间隔时间段的初始时刻或事件集中有事件发生)时，场景会发生变化，需要重新进行路径规划。当事件结束时，清除事件。阶段性分析流程见图2。

图2　阶段性分析流程

2.3SOC智能预警控制分析

当电动汽车的SOC

图3　SOC智能预警控制流程

2.4智能充电

当cars0需要去充电桩充电时，分别计算cars0的pathTime，waitTime，chargeTime。当pathTime=0时，说明电动汽车已经在充电桩队列中，充电桩的队列数加1，将car推入sequene末尾处，并且totalTime+=car.chargeTime；当waitTime=0时，电动汽车已经开始充电；当chargeTime=0时，电动汽车已经充满电，准备离开充电桩，此时将sequence移除car，同时队列数减1。智能充电流程见图4。

图4　智能充电流程

3　仿真分析

以百度地图为基础，在淄博市城区范围内对电动汽车智能最优充电路径规划进行仿真分析。采用节点表示充电桩、电动汽车等相对位置，建立了包含1 800个节点、10个充电桩以及50辆电动汽车的模型。仿真系统界面如图5所示。

图5　仿真系统界面

3.1充电桩智能充电仿真分析

假定主车(cars0)要去9号充电桩充电，到达充电桩时间为20 min，9号充电桩位置是1050。此时在充电桩有2辆车(分别为cars1和cars2)在充电，cars3，cars4，cars5在去9号充电桩充电的路上，各电动汽车的初始状态如表1所示。假定每走1单位路程耗费1单位电量,每分钟充1单位电量，充满电后电动汽车离开。9号充电桩状态变化如表2所示。

表1　电动汽车初始状态

表2　充电桩状态变化

3.2电动汽车多目标路径规划仿真

电动汽车所在位置为node532，需要去往5个目的地，分别为：dest1，dest2，dest3，dest4，dest5(node432，node333，node233，node1132，node121)。同时，假定在电动汽车电量<50时自动寻找最优充电桩充电。仿真结果如表3所示。

3.3电动汽车路径规划实时性分析

当电动汽车路径规划时，需要对路径规划的实时性进行分析，能否及时给出路径规划方案。主要分为2种情况:① 当有突发状况发生时无需重新计算，可从原有的存储的最短路径重新取出从当前位置到第1个目标节点的最短路径。② 当电动汽车电量不足时需找到一个最近充电桩，使得当前位置到达充电桩的距离与充电桩到达下一个充电桩距离之和最短，即需计算2段最短距离，因此需要保证其准确性，缩小充电桩搜索范围并及时做出路径规划。

表3　路径规划对比

现对电动汽车电量不足情况进行实时性分析。对当前范围内100个节点进行搜索，对充电桩个数进行分析，结果如表4所示。

表4充电桩个数与搜索速度关系

充电桩个数搜索速度/s1<12<1314252641015

当充电桩数量较少时运行时间很短；当充电桩数量较多时运行时间虽相对较长，但仍在可接受范围之内。

4　结束语

本文在建立多目标电动汽车智能充电路径规划模型上进行如下改进：

1) 将时间离散化，并且添加了事件集，优化了电动汽车动态路径规划。

2) 对SOC做出智能预警，缓解了电动汽车的“充电焦虑”问题。

3) 在原有算法的基础上提出了”最近邻点法+Dijkstra算法”，大大优化了电动汽车的路径规划。同时根据实时的交通信息，动态模拟了电动汽车的智能充电过程。

[1]欧雯要,叶瑞克,鲍健强.电动汽车(V2G技术)的节能减碳价值研究[J].未来与发展,2012(5):36-40.

[2]KIM H,LEE J,PARK G,et al.An efficient scheduling scheme on charging stations for smart transportation [M].Berlin Heidelberg:Springer,2010:274-278.

[3]KIM B,JO J,KIM J,et al.Optimal route search in car navigation systems by multi-objective genetic algorithms [J].International Journal of Information Systems for Logistics and Management,2009,4(2):9-18.

[4]MARIYASAGAYAM M N,KOBAYASHI Y.Electric vehicle route assistance using forecast on charging station [C]//Lisbon,Portugal:Proceedings of 3th International Conference on Smart Grids,Green Communications and IT Energy-aware Technologies.2013:134-142.

[5]KOBAYASHI Y,KIYAMA N,AOSHIMA H,et al.A route search method for electric vehicles in consideration of range and locations of charging stations [C]//Baden-Baden,Germany:Proceedings of 2011 IEEE Intelligent Vehicles Symposium (FV).[S.l.]:IEEE,2011:920-925.

[6]SEDANO J,CHIRA C,VILLAR J R,et al.An intelligent route management system for electric vehicle charging[J].Integrated Computer-Aided Engineering,2013,20(4):321-333.

[7]彭飞,柳重堪,张其善.车辆定位与导航系统中的快速路径规划算法[J].北京航空航天大学学报,2002,28(1):70-73.

[8]樊月珍,江发潮,毛恩荣.车辆行驶最优路径优化算法设计[J]计算机工程与设计,2007,28(23):5758-5761.

[9]刘智请,李春贵.城市交通最优路径规划仿真研究[J].计算机仿真,2011,28(7):349-352.

[10]田佳榮,张昌华.一种电动汽车用GPS导航系统的设计[J].电子测试,2011(1):54-57.

[11]KRAUSE K R,GAULT T A,PEBBLES P H,et al.Charge notification method for extended range electric vehicles[P].American patents,2012-1-19.

[12]陈勇,孙逢春.电动汽车续驶里程及其影响因素的研究[J].北京理工大学学报,2009,21(5)：529-582.

[13]徐贵宝,王震坡.电动汽车续驶里程能量计算和影响因素分析[J].车辆与动力技术,2008(2):53-56,61.

[14]陈德兵,叶磊.低温对纯电动汽车续驶离成的影响分析[J].客车技术与研究,2012(2):49-51,57.

(责任编辑刘舸)

Research on Intelligent Path Planning Charging for Electric Vehicle

ZHAO Xin-zhi, LI Pan-jing, ZHANG Huan, REN Jia-yi, ZHANG Rong-lei

(College of Computer Science and Technology,Shandong University of Technology, Zibo 255049, China)

Intelligent electric vehicle dynamic network system model was established for solving the “battery charging anxiety” problem of electromobile, and when multiple targets exist, the optimal path planning algorithm of “Dijkstra algorithm plus the nearest neighbor point method” was put forward based on the original path planning algorithm. The intelligent pre-sentence of remaining power of electric vehicles was made, and the intelligent charging of electric vehicles in the charging pile was achieved, which effectively eases the electric car charging anxiety problem.

intelligent electric vehicle; dynamic charging path planning; intelligent charging pile; charging network

2016-05-12

赵薪智(1992—)，男，主要从事软件工程研究，E-mail:530143256@163.com。

format：ZHAO Xin-zhi, LI Pan-jing, ZHANG Huan, et al.Research on Intelligent Path Planning Charging for Electric Vehicle[J].Journal of Chongqing University of Technology(Natural Science)，2016(10):34-39.

10.3969/j.issn.1674-8425(z).2016.10.005

TP301

A

1674-8425(2016)10-0034-06

引用格式：赵薪智,李盘靖,张欢,等.电动汽车智能充电路径规划研究[J].重庆理工大学学报(自然科学)，2016(10):34-39.