论文部分内容阅读
在全球能源互联网的环境下电动汽车作为缓解能源和环境压力的不二选择引起了众人关注，因而充电站规划的科学性和合理性也越来越重要。充电站的选址问题是涉及环境、能源、电网规划等领域的综合性、系统性的问题。本文使用了图与网络分析的最短路算法对充电站选址规划问题进行分析并通过实例验证了该算法的可行性和科学性，为充电站选址规划提供了一种新的方法和思路。
电动汽车 充电站选址 最短路算法 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以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中可以得到起点ν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.
电动汽车 充电站选址 最短路算法 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以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中可以得到起点ν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.