CAIXUN 财讯
－81－
□ 华北电力大学 熊媛媛 刘吉成 / 文 在全球能源互联网的环境下电动汽车作为缓解能源和环境压力的不二选择引起了众人关注，因而充电站规划的科学性和合理性也越来越重要。充电站的选址问题是涉及环境、能源、电网规划等领域的综合性、系统性的问题。本文使用了图与网络分析的最短路算法对充电站选址规划问题进行分析并通过实例验证了该算法的可行性和科学性，为充电站选址规划提供了一种新的方法和思路。
电动汽车技术网电动汽车 充电站选址 最短路算法
Dijkstra 算法
推动能源系统的清洁化、低碳化和
智能化转型，是应对全球气候变化，减
少环境污染的重要途径。2016年3月召
开的全球能源互联网大会标志着全球能
源互联网合作组织正式成立。在全球能
源互联网的环境下电动汽车作为缓解能
源危机和环境压力的不二选择引起了越
来越多人的关注，世界各国投入了大量
的人力、物力、财力研发新型电动汽车。
我国政府从发展汽车产业的战略高度出
发制定了一系列政策极大的促进了我国
汽车行业的发展。
我国电动汽车充电站发展现状
随着电动汽车客户体的日益扩大，
如何选择充电站为电动汽车充电成为现
在亟待解决的问题。作为电动汽车的重要
配套设施，充电站规划研究的不足严重制
约着我国电动汽车行业的发展。因此，寻
求科学、适用的充电站规划评价方法已成
为众学者和研究机构研究的重要课题。
Wagner Sebastian 和Götzinger
Markus 等（2013）基于兴趣点法对智能
城市充电站的优化选址问题进行了研
究 ；刘柏良，黄学良等（2015）建立了
充电站与分布式电源定容选址模型；贾
龙，胡泽春等（2015）研究了电动汽车
在高速路网中的充电需求分布。研究发
现充电站的选址问题是包含环境、能源、
电网规划等领域的综合性问题。下面我
们使用最短路算法对充电站选址规划问
题进行分析。
最短路算法
最短路径问题旨在寻图中节点之
间的最短路径，目前最好的算法是适用
于无负权最短路问题的Dijkstra 算法。在
寻求过程中，记录下每点对应的标号。
该标号表示从起点到该点的最短路的权（称为P 标号），或表示从起点到该点的最短路的权的上界（称为T 标号）。直到终点得到P 标号时，算法结束。 Dijkstra 算法的计算步骤如下所示：（1）给起点νs 标上永久性标号P （νs ）＝0，其余各点标临时性标号T （νj ）＝＋∞；（2）若νi 为刚得到P 标号的点，若νj 为T 标号，且弧（νi ，νj ）属于D （或[νi ，νj ]属于D ），对νj 的T 标号进行如下的更改：T （νj ）＝min{T （νj ），P （νi ）+ωij }；（3）比较所有具有T 标号的点，把最小者改完P 标号，即P （νi ）＝min{T （νi ）| νi 为T 标号点}；（4）判断是否全部点均为P 标号点。若是，则算法终止；否则用νi 代νi 转回第二步。 实例验证 现有一辆电动汽车要从起点ν1到达终点ν7，途中有四个电动汽车充电站ν2，ν3，ν4，ν5，途中每条路径上的权重代表该节点到下一节点的综合花费值，该值是包含建设费用、运行费用、对环境造成的影响、对当地电网的冲击、线路负荷率、地质水文条件、对城市规划等因素的综合评价值。现在需要确定如何选择路径才能使得总花费最小，也即转换为求解起点到终点的最短路径问题。
图1 充电站路径规划图 求解过程如下所示： （1）给ν1以P 标号，P （ν1）＝0，其余所有点标号T ，T （νi ）＝＋∞ （2）边[ ν1，ν2 ][ ν
1，ν3 ][ ν1，ν4 ]属于初始点构成的集合G ，且ν2，ν3，ν4为T 标号，所以修改这三个点的标号，过程如下： T （ν2）＝min{T （ν2），P （ν1）＋ω12}＝min （＋∞，0＋26）＝26 T （ν3）＝min{T （ν3），P （ν1）＋ω13}＝min （＋∞，0＋12）＝12 T （ν4）＝min{T （ν4），P （ν1）＋ω14}＝min （＋∞，0＋28）＝28 比较所有T 标号，可以看到T （ν3）最小，所以令P （ν3）＝T （ν3）＝12 （3）ν3为刚得到P 编号的点，ν3对应的边为[ ν3，ν2 ][ ν3，ν4 ][ ν3，ν6 ]，下面计算各端点对应的T 值，过程如下： T （ν2）＝min{T （ν2），P （ν3）＋ω32}＝min （26，12＋30）＝26 T （ν4）＝min{T （ν4），P （ν3）＋ω34}＝min （28，12＋12）＝24 T （ν6）＝min{T （ν6），P （ν3）＋ω36}＝min （＋∞，12＋36）＝48 比较所有T 标号，可以看到T （ν4）最小，所以令P （ν4）＝T （ν4）＝24。以此类推，直至所有的T 标号都变为P 标号时算法结束。最终结果为T （ν7）＝min{ T （ν7），P （ν6）＋ω67}＝min （76，47＋30）＝76。将ν7对应的T 标号变为P 标号，可得P （ν7）＝76，算法结束。同时可以得到我们所需要的最短路径图如图2所示： 图2 最短路径结果图 从图2中可以得到起点ν1到终点ν7的最短路为ν1→ν3→ν4→ν7，也即该电动汽车从ν1行驶到ν7，所需的最小综合花费为该最短路的总的权值即P （ν7）＝76。 结论 合理规划充电站节点可以为电动汽车充电客户提供更好的服务，优化资源配置，避免因为人为规划的失误或方法科学性的欠缺造成公共资源的浪费。
本文使用最短路的算法对充电站选址进行了研究并通过实例验证了该方法的可行性和科学性，为充电站选址规划提供了一种新的方法和思路。 作者简介：熊媛媛（1990- ），女，汉族，山东临朐人。硕士，单位：华北电力大学经管学院管理科学与工程专业，研究方向：信息管理、电动汽车充电站选址规划。 [1] Wagner,Sebastian ,Götzinger,Markus, Neumann,Dirk.Optimal Location of Charging Stations in Smart Cities: A Point of Interest Based Approach. International Conference on Information Systems, 2013: 2838-2855. [2] 刘柏良，黄学良，李军等.含分布式电源及电动汽车充电站的配电网多目标规划研究[J].电网技术，2015，39（2）：450-456. [3] 贾龙，胡泽春，宋永华等.高速路网上电动汽车充电站布点优化[J].电力系统自动化，2015，39（15）：82-89.
，76） （0V6 （V4，39） （V1，26）
发布评论