物联网环境下基于图模型寻找最优充电站的方法

赵衍恒, 高洪雨，2，李荣凯，王文明，王 磊，2

(1. 国家电网有限公司技术学院分公司网络大学运管中心，山东济南250002； 2. 山东大学电气工程学院，山东济南250002)

随着我国经济的快速发展，汽车产业增长迅速，由此带来的能源消耗和环境污染问题越来越严重。当前，汽车对石油的消耗总量占所有石油消耗量的60%[1]，新能源汽车将是降低石油消耗、改善环境污染现状的有效方式以及未来汽车行业发展的一个大趋势[2]。新能源汽车主要包括电动汽车、燃料电池汽车等，到2025年，新能源汽车数量可能达到5 000万～8 000万辆[3]。未来电动汽车的充电设施将遍布在住宅小区、停车场、街头或者公共区域，对电动汽车进行常规充电，同时在固定地点配置交流充电桩和直流充电机，为电动汽车进行快速充电服务。

目前，电动汽车充电依然存在明显的问题，如常规充电方式充电时间长[4]，快速充电对电网的冲击明显[5]； 充电站从交流配电网获取电能，增加电网负担，获取电能的方式单一[6-7]。随着电动汽车的普及，未来需要充电的汽车越来越多，容易出现某些热门充电站电动汽车充电等待时间过长的现象，不同充电站的负载严重不平衡问题也会越来越严重，因此，充电调度问题是电动汽车领域的一个研究热点。

一方面，电动汽车充电调度方面的研究集中于电动汽车在寻找充电站的路径规划。黄晶等[8]提出了建立下一目的地导向的电动汽车充电引导策略，实现了充电站设备利用率分布均衡、时间成本最小的目标。严弈遥等[9]基于Dijkstra最短路径算法，提出电动汽车充电路径规划方法，在一定程度上解决了电动汽车充电造成的配电网节点压降过大、线路功率损耗过多问题。Liu等[10]利用充电站电价信息及交通信息，提出一种减少用户行驶时间及充电成本的路径优化模型。杨洪明等[11]基于实时交通信息，构建电动汽车充电路径优化模型，实现了用户出行总成本最小。Wager等[12]对电动汽车在外部因素不同情况下的能耗率进行试验研究，发现电动汽车耗电量会随着路况等因素发生变化。以上研究对本文中提出的定位最优充电站的路径查询提供了解决思路。

另一方面，电动汽车充电研究集中在充电站有序充电调度。蒲勇健[13]通过基于物联网协调有序预约快速充电的背景，证明了一个最大化配对数量的存在性定理。陆坚毅等[14]在实时电价和每个充电任务时间连续的假设下，提出单亲遗传算法混合动态规划两阶段常规充电调度算法，有效地实现了电桩负载均衡和降低电费成本。康振南等[15]提出对电动汽车分层分区调度的方法，实现对电动汽车有序充放电控制，保证了电网经济运行和用户的充电费用最小。曾鸣等[16]根据用户的行驶计划和各充电站的电量需求建立用户与充电站之间的多对一匹配模型，有效地提高了系统总效用和用户满意度。李铭洋[17]、符云辉等[18]提出基于充电站和用户实现双边满意度的算法，改善了用户的出行体验，提高了充电站的收益。以上研究对本文中的定位最优充电站方法中的预约充电提供了解决思路。

基于物联网的电动汽车充电调度问题在本质上涉及到用户侧和电网服务侧2个方面的优化问题，除了实现电网侧的优化外，用户侧的优化也需要实现。随着通信网络的不断发展，电动汽车车载监控系统和信息采集系统逐步形成常规配置，但亟需一种新的方法，在不改变充电站基础设施的前提下，从用户侧需求出发，考虑电动汽车的续航里程、到达充电站的行驶距离和时间、充电前排队等待时间和充电时间作为充电代价，为电动车智能推荐综合目标最优的充电站，并达到各个充电站负载平衡。本文中将对用户侧和电网服务侧2个方面的优化进行研究，实现电动汽车充电业务的多方协同发展。

1 电动汽车充电站策略

在物联网环境下，电动汽车通过自身的通信模块，连接车载导航或者手机等通信设备，通信设备将电动车自身的剩余电量、车速、地理位置等信息发送到数据调度中心，同时数据调度中心访问附近充电站的位置及充电站充电设施的使用情况。电动车作为根节点，各个充电站作为子节点，通过定位电动车自身位置和附近一定范围内充电站的地理位置，将电动汽车与充电站之间的关系抽象为图模型，利用充电调度算法，动态为电动汽车推荐最小充电代价的充电站。图1所示为基于物联网的电动汽车通信方式。

2 充电调度问题模型

充电调度问题由电动汽车模型、充电站模型、路径模型和充电代价模型4个部分构成，本文中使用的主要参数如表1所示。

在电动汽车寻找最优充电代价的充电站过程中，电动汽车作为根节点，一定距离范围内的所有的充电站作为子节点，电动汽车和充电站之间以及各相邻充电站之间连接的路径作为图的边，路径的距离作为边的长度。

CAN—控制器局域网络。图1 基于物联网的电动汽车通信方式

表1 本文中使用的主要参数

图2(a)为电动汽车与充电站布局示意图。图2(a)抽象出来的图模型增加一个虚拟结点u0构成拓扑图G，如图2(b)所示。G是一个带权图，定义G=(C,U,E)，其中C为所有待充电电动汽车的集合，C={c0}，c0作为G的根结点；结点集合U用于表示充电站集合，U={ui|0≤i≤n}，u0为辅助虚拟结束结点，ui(0

2.1 电动汽车模型

定义电动汽车c0自身剩余电量为e0，电池充电功率为p0，行驶速度为v0，可继续行驶里程为s0，电动汽车可继续行驶最长时间为t0，每度电可续航距离为k,

s0=ke0，

t0=s0/v0。

2.2 充电站模型

定义充电站ui的充电桩个数为mi，其中空闲充电桩个数为pi，等待充电的汽车辆数为wi，单桩

(a)电动汽车与充电站布局

c0—待充电电动汽车； u1—u8—搜索范围内的充电站； u0—虚拟结点，辅助构成有向无环图； 线上数字—行驶距离。(b)带权图G模型图2 电动汽车与充电站布局及其带权图G模型

ni=wi/mi，

等待率为ni, 每辆汽车允许最长充电时间为ti。结点ui=(ti,Ωi)，其中Ωi为电动汽车到该充电站可能途经的充电站，Ωi∈U，结点内部数字为充电站编号。当pi大于0时，ni为0。

2.3 路径模型

有向边集合E用于表示从电动汽车到充电站以及充电站之间的路径集合，E={eij|0≤i≤n, 0≤j≤n}，当i为0时，eij表示电动汽车到充电站j的路径；当i不为0时，有向边集合eij的方向表示电动汽车的行驶方向，即电动汽车经过充电站i到充电站j，eij的值表示充电站i直接到达充电站j的距离，图2(b)给出了一个具有8个充电站抽象图，例如充电站1到充电站3的直线距离为8 km，中间不经过其他充电站。

2.4 充电代价模型

充电代价模型分为2个模块：第1个模块是计算电动汽车到任意充电站的最小充电代价；第2个模块是在所有充电站中选择具有最小充电代价的充电站，该充电站即为推荐出的充电站。

电动汽车c0到充电站ui的充电代价定义为qi，包括电动汽车到充电站路上的时间、电动汽车在充电站等待充电时间、电动汽车充电时间。

qi=t0i+niti+ti

式中：t0i为电动汽车c0通过最短路程到达ui的时间；niti为到达充电站i后所需平均等待时间。

t0i通过车速v0和计算电动汽车到充电的最短路径s0i求出，计算公式为

t0i=60s0i/v0。

3 充电调度算法

物联网环境下基于定位预约最优充电站的实现方法，包括将运动中的电动汽车、一定范围内的充电站以及电动汽车到充电站和充电站之间的路径，抽象为充电站拓扑模型带权图G，如图2(b)所示。对带权图G模型使用遍历算法及最短路径算法，对每一辆能到达的充电站的汽车进行充电代价评估，并为电动汽车用户动态推荐并预约代价最小的充电站。基于图模型算法寻找最优充电站的流程如图3所示。

基于图模型算法寻找最优充电站调度算法中提出了计算电动汽车到任意充电站的最小代价的算法GetMixValue，思路如下： 1)计算电动汽车到充电站行驶时间代价； 2)计算电动汽车在充电站等待充电时间代价； 3)计算电动汽车充电时间代价与前2步代价之和。

该算法使用的是贪心算法，先把充电站U分成S和T共2个组，定义S为已求出最低充电代价的充电站的集合，T=U-S为尚未确定最低充电代价的充电站集合。

将T中结点按最小充电代价递增的次序加入到S中，c0到T中充电站uk的最小充电代价，是c0到uk的直接路径上的充电代价或是从c0路经S中其他充电站到uk的充电代价之和。

求最小充电代价步骤如下：初始时令S={c0},T={其余结点}；若存在电动汽车直接到达充电站ui，即存在〈c0,ui〉[8]有值，则T中结点对应的最小代价值为〈c0,ui〉边上的行驶距离代价与充电站ui内的充电时间代价之和(下文统称充电代价之和)；若不存在〈c0,ui〉，则设置为无穷大值[10]。

DAG—有向无环图。图3 基于图模型算法寻找最优充电站的流程

从T中选取一个充电代价之和为最小的充电站w，加入S，对T中结点的代价值进行修改。若加进w作为中间结点(因为电动汽车不在w充电，只是路过，所以不计算在w的充电代价)，从c0到ui的充电代价比不加w的充电代价要小，则修改此代价值(上面2个并列for循环，使用最小充电代价值更新)。

重复上述步骤，直到S中包含所有结点，即S=U为止。

为电动汽车用户动态推荐并预约代价最小的充电站，是将计算出的每一个充电站的充电代价Value进行性能排序，得到qi最小值的充电站即为推荐预约充电站。获取c0到uk最小充电代价算法伪代码如下。

int GetMixValue (intc0, intuk)

{//计算c0到uk间最小充电代价，并返回充电路径初始化S={c0}；

d[s]=0;//其余d值为正无穷大，d值为充电代价

while(NOTukinS)

{

for(所有不在

//取出不在S中的最小的d[i]

S中且与i相邻的点j)

if(d[j]>d[i]+cost[i][j] )

d[j]=d[i]+cost[i][j]+cost[j];

S=S+{i};

//把i点添加到集合中

}

returnd[uk];

}

int SearchMostSuitableFillingStation(DAGG)

{//寻找最合适充电站，遍历每个充电站结点，计算电动汽车到该访问结点的最小充电代价，并在所有充电站中选出最小代价充电站。

SqQueueq;

//存储图G的结点

QElemTypep;

//临时队列元素q

int Station ID;

//最小充电代价的充电站ID

int Value;

//保存最小充电代价的充电站

If(!q)

//如果队列不为空，则继续执行

{

InitQueue(&q);

EnQueue(&q,T);

while(!QueueEmpty(q))//对所有充电站进行

遍历

{

//充电站之间的充电代价

De Queue(&q,&p);

Value=GetMixValue(c0,p);

if(p->lchild!=NULL)

EnQueue(&q,p->lchild);

if(p->rchild!=NULL)

EnQueue(&q,p->rchild);

}

}

}

StationID=GetMixCostStation();

//返回最小充电代

价的充电站

4 算法分析

4.1 算法实例

以图2所示的充电站为实例，将其抽象为有向无环图(DAG)，如图4所示。在电动汽车搜索范围内共有8个充电站，即u1—u8，在DAG图中，c0为电动汽车，u0作为虚拟结束节点，每2个充电站之间路径上的数据为2个充电站之间的行驶时间，每个充电站节点括号内的数据为在此充电站等待充电及充电时间之和。如果电动汽车c0到充电站u1充电，最短行驶时间为5 min，充电等待及充电时间为125 min，总的充电代价为130 min；如果c0到u2充电，最短路径中间途径u1，则行驶时间为12 min，充电等待及充电时间130 min，总的充电代价则为142 min。

c0—待充电电动汽车； u1—u8—搜索范围内的充电站；u0—虚拟结点，辅助构成有向无环图； 线上数字—行驶距离； 括号内数字—等待时间与充电时间之和。图4 充电站抽象带权有向无环图

查找最优充电站的算法为对电动汽车搜索范围内的所有充电站进行遍历，计算电动汽车到每个充电站的最小充电代价，然后在所有充电代价中，选择充电代价最小的充电站作为推荐充电站。表2所示为图4中DAG的邻接矩阵表示。如果2个充电站之间有路径直接相连，则〈ui,uj〉的值为2个充电站之间的行驶时间，若2个充电站之间没有路径直接相连，则〈ui,uj〉的值为无穷大[12]。〈ui,ui〉的值为电动汽车在充电站的等待时间和充电时间之和。

表3所示为使用基于图模型算法寻找最优充电站的计算过程和结果。第1列为DAG图中代表充电站的各个节点，第2列数据为充电汽车使用最短路径算法计算的到达充电站的最短时间，第3列数据为行驶路径，第4列为充电汽车在充电站需要等&待和充电的时间，最后一列数据为电动汽车如果在该充电站充电所需要的充电时间代价。由表中的计算结果可知，充电站到u1有最短的行驶路径，但是到u4具有最小的充电代价，且行驶路径为u1→u2→u4。

表2 抽象带权有向无环图的邻接矩阵表示

表3 基于图算法的计算过程和结果

4.2 复杂度分析

设定待充电电动汽车搜索范围内的所有充电站数量为n,查找最优充电站的算法的时间复杂度则为O(n2)。

查找最优充电站的算法首先对所有充点站进行队列遍历，时间复杂度为O(n)，然后嵌套使用电动汽车到充电站最小充电代价的算法，最终得出计算最优充电站的时间复杂度为O(n2)。

4.3 仿真效果分析

本文中分别设计电动汽车搜索范围内的充电站个数为30、45、60进行仿真模拟。本算法基于物联网环境，可即时获得电动汽车搜索范围内的充电站的到达时间和充电等待时间，实验环境对每座充电站的到达时间和充电等待时间采用蒙特卡罗法生成，到达充电站的时间为5～50 min，充电等待时间为40～160 min。将查找最优充电站算法和最近充电站算法以及最短等待时间的充电代价进行对比，结果如图5所示。

(a)充电站个数为30

(b)充电站个数为45

(c)充电站个数为60图5 充电站个数不同时的总充电代价对比

从图5中可以看出： 当充电站个数为30时，最优充电站所花费的充电代价最小，为最短等待时间的充电代价算法的85.5%，为最近充电站算法的67%； 当充电站个数为45时，最优充电站所花费的充电代价为最短等待时间的充电代价算法的75.9%，为最近充电站算法的38.2%； 当充电站个数为60时，最优充电站所花费的充电代价为最短等待时间的充电代价算法的78%，为最近充电站算法的61.3%。由此可以得出结论，物联网环境下基于图模型的寻找最优充电站算法能以最小的充电代价推荐充电站，最大程度地节省用户充电代价。

5 结语

通过物联网环境下基于图模型算法寻找最优充电站的方法，从用户侧需求出发，为电动汽车用户推荐定位预约充电的最省时充电站，同时也达到平衡各个充电站负载的作用。下一步，该算法将在原有思路的基础上，将充电功率、充电计费和充电时间结合，对寻找充电站算法进行优化，以达到进一步服务用户和平衡充电站负载的目标。