基于网络简化和深度优先遍历的配电网路径搜索算法

徐成司, 董树锋, 孙 洲, 李春筱, 孙 明

(1. 浙江大学电气工程学院, 浙江省杭州市 310027; 2. 国网绍兴供电公司, 浙江省绍兴市 312000)

基于网络简化和深度优先遍历的配电网路径搜索算法

徐成司1, 董树锋1, 孙 洲2, 李春筱2, 孙 明1

(1. 浙江大学电气工程学院, 浙江省杭州市 310027; 2. 国网绍兴供电公司, 浙江省绍兴市 312000)

供电路径分析在配电网分析中有着重要作用,但实际中配电网往往结构复杂,在搜索供电路径前需对配电网模型进行适当的简化处理。文中提出一种基于公共信息模型(CIM)的配电网网络模型简化方法,以及在其简化结果上的一种基于深度优先遍历的配电网路径搜索算法。首先,将配电网模型存储在图数据结构中,利用图论算法进行网络简化。随后,通过路径搜索算法搜索得到负荷节点的所有供电路径,并经过分类得到3类路径集合:按电源分类、按路径终点负荷分类和按路径经过支路分类的路径集合。该路径搜索算法可用于配电网拓扑结构和支路通断状态等配电网分析描述中。最后,以某省会城市的一个实际配电网架和IEEE 123节点系统为例,分别验证了网络简化方法和路径搜索算法的有效性和实用性。

公共信息模型; 网络简化; 深度优先遍历; 配电网拓扑; 路径搜索

0 引言

随着经济的发展,社会对电力的需求量增大,配电网的规划和运行分析日益重要,如规划和静态安全性分析中的N-1校核计算、配电网重构的优化计算、配电网馈线供电能力的评估[1]等。

配电网数学模型的建立是网络分析应用的基础。目前公共信息模型(common information model,CIM)中的配电网扩展模型正不断成熟,在配电网中应用广泛[2-4]。另外,配电网在运行中保持其辐射状结构是一个重要约束条件,有很多学者对配电网的拓扑描述方法展开了研究。文献[5-6]提出用生成树的搜索来得到符合要求的网络拓扑。文献[7]采用同时打开和关闭一个回路中一对开关的方法。文献[8]利用网络的回路关联矩阵动态切割及合并回路,以保证配电网辐射状的拓扑结构。文献[9]提出了配电网满足辐射状拓扑约束的充分必要条件。文献[10]提出了一种基于供电路径的配电网拓扑描述方法,该方法的优势在于可用线性的数学公式清晰地描述配电网的辐射状拓扑结构。文献[10-11]将供电路径应用在配电网重构问题中;采用基于供电路径的配电网拓扑描述,可将重构问题用混合整数确定性优化方法求解[12-13];文献[14]提出了一种基于路径描述的馈线N-1可装容量的计算方法,将配电网的供电路径应用在N-1安全校验分析中,说明了供电路径在配电网分析中的有效性。对于规模较大的配电网,供电路径数量很多,有必要采用高效的路径搜索算法。文献[10]提出的配电网路径搜索方法基于广度优先遍历,需将搜索得到的支路先存储在树结构中以保存路径信息,再对树进行遍历,将路径存于链表中,搜索过程占用的空间较大,并且没有考虑网络中存在多个变电站的情况。文献[15]提出一种基于顶点分裂的路径搜索方法,需频繁改变网络图的结构,且针对图中不同的一对顶点,顶点分裂的结果也不同,效率较低。文献[16-17]提出的搜索方法不能得到网络中所有的供电路径。配电网往往结构复杂,如果直接在CIM中获取供电路径,涉及的路径数量庞大,降低了后续分析的效率,因此需要对配电网进行适当的简化处理[18-19]。文献[18]提出的配电网简化模型难以与CIM建立直接联系。文献[19]涉及的化简方法仅将区域网络边界的多端口元件化简为二端口元件。

针对上述问题,本文提出一种基于CIM的配电网网络模型简化方法,以及在该简化网络上的一种基于深度优先遍历的配电网路径搜索算法。该网络模型简化方法可为后续的路径搜索等分析提供计算性能保证。同时,本文提出的基于深度优先遍历的配电网路径搜索算法,可搜索得到配电网中所有供电路径,并可通过分类得到三类不同的路径集合。该网络简化和路径搜索算法能够应用于配电网N-1分析、配电网重构问题及其他基于供电路径的配电网分析中。

1 配电网网络简化

1.1 基于CIM的配电网网络模型

采用CIM建模技术中的节点—开关模型[20-21]对配电网建模,得到配电网的原始模型。该模型描述了网络中不同导电设备(conducting equipment)之间的连接关系,其中连接节点(connectivity node)、端子(terminal)和导电设备之间的关系如图1所示。

图1 连接节点、端子和导电设备之间的关系Fig.1 Relationship between connectivity node, terminal and conducting equipment

为在模型简化过程中利用图论算法,将配电网网络存储在图数据结构中,过程如下。

1)将原始CIM中的连接节点存储在图的节点中。

2)将原始模型中包含2个端子的导电设备存储在图的边中,边的两个顶点是根据2个端子分别找到的2个连接节点。

3)对配电网中的电力变压器(power transformer),为其建立一个虚拟连接节点;再对变压器的各绕组,根据端子找到另一个连接节点,将各绕组存储在图的边中。

4)对得到的图进行连通性分析,获得连通子图,在连通子图中找出有源电气岛。

1.2 基于图论算法的网络简化方法

文献[22]提出了一种基于CIM的配电网拓扑收缩方法,对关联3个及以上端子数的连接节点进行分支线收缩和负荷点归并处理。为提高网络简化效果,本文进一步考虑配电网中开关与交流线段等设备的简化。简化步骤如下。

步骤1:将原图中的连接节点作为母线节点(topological node)的成员,再将图中的节点改为对应的母线节点,边中的顶点信息也进行相应替换,得到初始简化图。

步骤2:合并交流线段(AC line segment)两端的节点。首先,找到交流线段的2个顶点v1和v2。对其中一个顶点如v2,找出除该交流线段外的与其相连的所有边。对其中每一条边,将这条边上的设备加到v1与该边的非v2顶点之间的边上,并删除这条边。若v1与该边的非v2顶点之间原来不存在边,则需新建一条边。最后,将顶点v2包含的连接节点加入顶点v1中,并删除节点v2和该交流线段。

步骤3:在图中找出所有含有开关的边,分别进行如下处理。首先从图中删去这条边,获得连通子图,如果网络没有分裂,则该开关的状态对配电网的运行有影响,重新将这条边加入图中。如果网络分裂成2个,则要对下面两种情况进行处理:①一是无源的且包含负荷的子网,说明删去的边对应的开关状态必然为闭合,则将该边两端的节点合并,合并的方法与步骤2中相同;②二是无源的不包含负荷的子网,说明该子网对配电网的运行无影响,则从图中删除该子网。若不出现上述两种情况,则重新将删去的边加入图中。

步骤4:删除只与两条边连接的联络节点。将与联络节点相连的两条边合并为一条,并将该节点删除。

图2以某配电网网络为例表述网络简化的过程。经步骤3简化后的网络如图2(c)所示,图中已无联络节点,则图2(c)即为所得的简化配电网网络。

图2 配电网网络简化示例Fig.2 Illustration of distribution network simplification

图2(c)中S1和S2为电源节点,L1,L2,L3为负荷节点。其中L1,L2,L3分别对应原网络中的负荷Load1和Load2,Load3和Load4,Load5和Load6。简化后网络图的边上均有开关设备。该简化可提高路径搜索、配电网重构和供电能力分析等的效率。

2 基于深度优先遍历的配电网路径搜索算法

在经过简化的配电网网络图中搜索供电路径。目前的配电网路径搜索算法仍基于图论算法[23],文献[24]采用深度优先和广度优先两种方法寻找故障恢复路径,文献[25]采用深度优先方法搜索负荷转移路径。这些方法无法搜索得到图中所有的供电路径,不能满足描述配电网拓扑的需要。在此基础上,本文提出一种基于深度优先的配电网路径搜索算法,对深度优先遍历的规则进行一定调整,以得到所有的供电路径。同时通过分类得到3类供电路径:按电源分类的路径;按路径终点负荷分类的路径;按路径中经过支路分类的路径,以便于配电网拓扑的描述。

2.1 搜索按电源分类的所有供电路径算法

(1)

为得到按电源分类的所有供电路径,需要对每一个电源节点分别搜索出以该电源为起点的所有路径。与深度优先遍历类似,搜索从一个电源出发的所有路径也是一个递归的过程。为了在搜索到某个节点时,能够向前推出该节点到电源节点的供电路径信息,本文采用一个堆栈结构来实现递归。将搜索得到的路径集合存入数组R中。

栈中存储的元素是图中的节点。基于深度优先的思路,每次成功访问一个节点后,需要令该节点入栈,再对新栈顶元素T的邻接点进行搜索。若T的所有邻接点都不满足被访问的条件,则T出栈。将栈中保存的节点依次相连,就能得到从栈底节点,即电源节点到栈顶节点之间的一条路径。再将栈顶节点与新搜索到的节点相连,得到一条新的路径r。新搜索到的节点需要满足下列3个条件才能入栈:①该节点不存在于栈中;②当前生成的该节点的供电路径r与已经搜索得到的路径都不同;③该节点不是电源节点。

若新搜索到的节点不满足上述任意一个条件,则继续对T的下一个邻接点进行搜索,否则节点入栈,同时增加一条新的路径记录r。若在搜索T的邻接点过程中没有新节点入栈,则T出栈,据此设置一个标记变量f记录T是否需要出栈。

所述算法的流程如图3所示。

图3 搜索按电源分类的所有路径的算法流程Fig.3 Flow chart of algorithm for searching all paths sorted by power sources

2.2 搜索按电源分类的路径算法复杂度分析

设网络图中电源节点数为n,负荷节点数为m。因配电网中一般电源数较少,n可表示为O(1)[26]。由于配电网通常为弱环网,一个负荷节点的供电路径数的数量级为常数级,因此配电网中总供电路径数可表示为O(m)。

堆栈中存放一个电源节点和多个负荷节点,其大小不超过m+1。路径在最长的情况下包括了所有的负荷节点,平均长度可表示为O(m)。由此,数组R的大小可表示为O(m2),这也是该算法所用存储空间的主要部分,即算法的空间复杂度。

进栈操作次数的量级与路径数量相同,为O(m)。每得到一条新的路径,均需要与已获得的路径相比较。因路径比较需对其包含元素分别依次比较,则比较次数的量级为O(m2),故该算法的时间复杂度为O(m3)。

2.3 按终点负荷节点分类和按经过支路分类的路径

本节所述的两类路径均可通过搜索2.1节的路径得到。搜索以某个负荷为终点的所有路径,过程如下:遍历按电源分类的所有路径,对每一条路径,判断其终点处的节点是否为指定的负荷节点,若是,则记录该路径。进而,对图中的每一个负荷节点,进行上述搜索,可得到按路径终点负荷分类的所有路径。

(2)

(3)

搜索经过某一条支路的所有路径,过程如下:遍历从电源出发的所有路径,对每一条路径中所包含的支路进行搜索,若含有指定支路,则记录该路径。进而,对图中的每一条支路进行相应搜索,可得到按路径中经过支路分类的所有路径。

(4)

按电源分类和按终点负荷分类的路径,二者所包含的路径数量均等于配电网中所有的供电路径数。

3 供电路径在配电网拓扑描述中的应用

3.1 配电网辐射状结构的描述

配电网辐射状结构可以用该网络中所有负荷节点供电路径状态的集合加以描述。文献[10]证明了若以下2个约束条件成立,则网络为辐射状。

1)对于任意一个负荷节点i,以该节点为终点的所有供电路径中,有且仅有一条连通,即

(5)

(6)

约束条件1)中涉及路径即为按终点负荷分类的路径。

3.2 支路开关状态描述

3.3 电源和支路上负荷量的描述

(7)

(8)

上述供电路径对配电网辐射状约束等拓扑关系的描述,在配电网重构和配电网供电能力分析等问题中均会涉及,可以加以应用。

4 算例分析

4.1 配电网网络简化算例分析

附录A图A1给出了某省会城市的一个实际配电网网架图,其中包含3个变电站,分别为S1,S2和S3。该模型的连接节点有668个,导电设备有784个。采用1.1节所述方法,将该网架模型存储在图数据结构中,得到1个有源电气岛,其中节点的数量为633,边的数量为632。

根据1.2节的网络简化方法对有源电气岛进行简化处理,得到的配电网网络图如附录A图A2所示。对简化网络中的节点重新编号,S1,S2和S3对应电源节点,L1～L16对应负荷节点。其中S1,S2和S3分别与附录A图A1中的变电站S1,S2和S3相对应。

经简化,网络图中有19个节点和18条边。有源电气岛的节点和边的数量分别减少为原来的3%和2.8%。若采用文献[22]的拓扑收缩简化方法,所得简化图中节点的数量为89,边的数量为88,有源电气岛节点和边的数量分别减少为原来的14.1%和13.9%。与文献[22]相比,所提算法简化后的配电网网络图的节点数量及边的数量明显减少,简化效果更为显著。

4.2 配电网路径搜索算法算例分析

本文以IEEE 123节点系统为例,验证基于深度优先的配电网路径搜索算法。网络接线图如图4所示,图中包含2个电源、129条支路和127个负荷节点,其中电源节点为点150和451。

图4 算例网络Fig.4 Example network

所提路径搜索算法基于Java语言编程实现,采用的计算机CPU型号为Intel Core i5-3337U、内存为4 GB。经路径搜索,得到该算例中所有的供电路径,总数为782条,其中以电源点150为起点的路径有377条,以电源点451为起点的路径有405条。搜索过程共耗时32 ms,说明该算法的时间复杂度较优越,可用于实际配电网的高效分析中。

从电源150和451出发的部分路径搜索结果列于附录B表B1中。

(9)

分类上述经搜索得到的路径,可得到按路径终点负荷分类的路径和按路径经过支路分类的路径。以带有开关的支路300-350为例分析供电路径的应用,附录B表B2展示了经过支路300-350的所有路径。设表B2中路径1～6的状态为W1～W6,节点350的负荷量为Q350,则通过支路300-350的功率如下:

S300-350=(W1+W2+W3+W4+W5+W6)Q350

(10)

同时,附录B表B2中列出的路径也是经过支路300-350,同时为负荷节点300和350供电的所有路径,故支路300-350上的开关状态可表示为:W1+W2+W3+W4+W5+W6。

5 结语

本文提出的配电网模型简化方法可使网络中的节点和支路数量显著减少,从而避免在后续分析中计算量过大的问题。对不同的配电网问题,可适当选取4个简化步骤中的一部分操作,并在简化过程中采用图论算法改变网络结构,使该方法具有较好的普适性。例如在供电能力分析中,可执行所有步骤的简化;在需考虑电压降落和网损的问题中,不进行步骤2(合并交流线段两端节点)的操作。

本文提出的基于深度优先遍历的配电网路径搜索算法,能够高效地搜索得到配电网中所有的供电路径。基于该算法得到的路径能够适应配电网拓扑的描述,可应用于基于路径描述的配电网N-1校验、N-1可装容量分析、配电网重构等问题中。基于本文和文献[14]成果的供电能力分析软件已经应用于某实际配电网,取得了较好的效果。

为保留快速查找的优势,本文方法将供电路径存储在数组中,但由于搜索前路径的数量未知,数组初始长度不易确定,因此估算网络中供电路径的数量,提高算法效率,是进一步的研究方向。

附录见本刊网络版(http://www.aeps-info.com/aeps/ch/index.aspx)。

[1] 肖峻,谷文卓,贡晓旭,等.基于馈线互联关系的配电网最大供电能力模型[J].电力系统自动化,2013,37(17):72-77.

XIAO Jun, GU Wenzhuo, GONG Xiaoxu, et al. A total supply capability model for power distribution network based on feeders interconnection[J]. Automation of Electric Power Systems, 2013, 37(17): 72-77.

[2] NEUMANN S. CIM extensions for electrical distribution[C]// Proceedings of 2001 IEEE Power Engineering Society Winter Meeting, January 28-February 1, 2001, Columbus, OH, USA: 904-907.

[3] WANG X F, SCHULZ N N, NEUMANN S. CIM extensions to electrical distribution and CIM XML for the IEEE radial test feeders[J]. IEEE Trans on Power Systems, 2003, 18(3): 1021-1028.

[4] 李荔芳,刘东,陈清鹤.公共信息模型在配电网建模工具中的应用[J].电力系统自动化,2005,29(24):55-59.

LI Lifang, LIU Dong, CHEN Qinghe. Application of CIM in distribution grid modeling tool[J]. Automation of Electric Power Systems, 2005, 29(24): 55-59.

[5] ENACHEANU B. Radial network reconfiguration using genetic algorithm based on the matroid theory[J]. IEEE Trans on Power Systems, 2008, 23(1): 186-195.

[6] LI J. Distribution system restoration with microgrids using spanning tree search[J]. IEEE Trans on Power Systems, 2014, 29(6): 3021-3029.

[7] SYAHPUTRA R, ROBANDI I, ASHARI M. Distribution network efficiency improvement based on fuzzy multiobjective method[J]. IPTEK Journal of Proceedings Series, 2014, 1(1): 224-229.

[8] 黄弦超,杨雨,范闻博.配电网多故障抢修与供电恢复联合优化模型[J].电力系统自动化,2014,38(11):68-73.DOI:10.7500/AEPS20130506015.

HUANG Xianchao, YANG Yu, FAN Wenbo. Combined optimization model for maintenance scheduling and service restoration of distribution system[J]. Automation of Electric Power Systems, 2014, 38(11): 68-73. DOI: 10.7500/AEPS20130506015.

[9] LAVORATO M, FRANCO J F, RIDER M J, et al. Imposing radiality constraints in distribution system optimization problems[J]. IEEE Trans on Power Systems, 2012, 27(1): 172-180.

[10] ROMERO R E, EXPSITO A G, SANTOS J R, et al. Path-based distribution network modeling: application to reconfiguration for loss reduction[J]. IEEE Trans on Power Systems, 2005, 20(2): 556-564.

[11] DUAN Dongli, LING Xiaodong, WU X Y, et al. Reconfiguration of distribution network for loss reduction and reliability improvement based on an enhanced genetic algorithm[J]. International Journal of Electrical Power & Energy Systems, 2015, 64(64): 88-95.

[12] JABR R A, SINGH R, PAL B C. Minimum loss network reconfiguration using mixed-integer convex programming[J]. IEEE Trans on Power Systems, 2012, 27(2): 1106-1115.

[13] BORGHETTI A. A mixed-integer liner programming approach for the computation of the minimum-losses radial configuration of electrical distribution networks[J]. IEEE Trans on Power Systems, 2012, 27(3): 1264-1273.

[14] 孙明,董树锋,夏圣峰,等.基于路径描述的馈线分区N-1可装容量计算方法[J].电力系统自动化,2017,41(16):123-129.DOI:10.7500/AEPS20161101003.

SUN Ming, DONG Shufeng, XIA Shengfeng, et al. Path-based calculation method for feeder partition available capability satisfied withN-1 security criterion[J]. Automation of Electric Power Systems, 2017, 41(16): 123-129. DOI: 10.7500/AEPS20161101003.

[15] 张旭,程雪婷,赵冬梅,等.一种基于顶点分裂的电网在线故障恢复路径搜索方法[J].电力系统自动化,2014,38(10):71-77.DOI:10.7500/AEPS20131104018.

ZHANG Xu, CHENG Xueting, ZHAO Dongmei, et al. A path searching method based on vertex splitting for online power grid fault restoration[J]. Automation of Electric Power Systems, 2014, 38(10): 71-77. DOI: 10.7500/AEPS20131104018.

[16] 张海波,张晓云,陶文伟.基于广度优先搜索的配电网故障恢复算法[J].电网技术,2010,34(7):103-108.

ZHANG Haibo, ZHANG Xiaoyun, TAO Wenwei. A breadth-first search based service restoration algorithm for distribution network[J]. Power System Technology, 2010, 34(7): 103-108.

[17] 王超杰,任建文,徐伟男,等.基于距离向量的失电孤岛供电路径搜索方法[J].电力系统自动化,2016,40(6):65-70.DOI:10.7500/AEPS20150720003.

WANG Chaojie, REN Jianwen, XU Weinan, et al. Power supply path searching algorithm for an electricity losing island based on distance vector[J]. Automation of Electric Power Systems, 2016, 40(6): 65-70. DOI: 10.7500/AEPS20150720003.

[18] 刘健,程红丽,毕鹏翔.配电网的简化模型[J].中国电机工程学报,2001,21(12):77-82.

LIU Jian, CHENG Hongli, BI Pengxiang. A simplified model for distribution system[J]. Proceedings of the CSEE, 2001, 21(12): 77-82.

[19] 王旭东,林济铿.基于网络化简的含分布式电源的配电网可靠性分析[J].电力系统自动化,2010,34(4):38-43.

WANG Xudong, LIN Jikeng. Reliability evaluation based on network simplification for the distribution system with distributed generation[J]. Automation of Electric Power Systems, 2010, 34(4): 38-43.

[20] 郭创新,董树锋,张金江.电力信息技术[M].北京:科学出版社,2015.

[21] 汪华.基于公共信息模型的电网建模[J].电网技术,2008,32(增刊2):186-188.

WANG Hua. Power network model based on CIM[J]. Power System Technology, 2008, 32(Supplement 2): 186-188.

[22] 廖怀庆,刘东,黄玉辉,等.基于公共信息模型拓扑收缩的配电网转供能力分析[J].电网技术,2012,51(6):51-55.

LIAO Huaiqing, LIU Dong, HUANG Yuhui, et al. Analysis on transfer capability of distribution network based on CIM topological contraction[J]. Power System Technology, 2012, 51(6): 51-55.

[23] 周云,严正,李乃湖,等.系统恢复路径搜索新算法及其适用性研究[J].中国电机工程学报,2016,36(15):4152-4161.

ZHOU Yun, YAN Zheng, LI Naihu, et al. A new system restoration path search algorithm and its applicability research[J]. Proceedings of the CSEE, 2016, 36(15): 4152-4161.

[24] BABU P R, KRISHNA K V, SHIRISHA W, et al. Heuristic search strategy for service restoration using DFS and BFS techniques[C]// India International Conference on Power Electronics, January 28-30, 2011, New Delhi, India: 8p.

[25] 姜惠兰,史建昇,曾凯,等.基于风险的电网调度操作最佳供电路径生成策略[J].电力系统自动化,2015,39(10):157-162.DOI:10.7500/AEPS20140708010.

JIANG Huilan, SHI Jiansheng, ZENG Kai, et al. Optimal power supply path in dispatching operation based on risk[J]. Automation of Electric Power Systems, 2015, 39(10): 157-162. DOI: 10.7500/AEPS20140708010.

[26] WEISS M A. Data structures and algorithm analysis in C[M].2版.北京:机械工业出版社,2010.

APathSearchingAlgorithmforDistributionNetworkBasedonNetworkSimplificationandDepthFirstTraversal

XUChengsi1,DONGShufeng1,SUNZhou2,LIChunxiao2,SUNMing1

(1. College of Electrical Engineering, Zhejiang University, Hangzhou310027, China;2. State Grid Shaoxing Electric Power Company, Shaoxing312000, China)

The power supply paths play an important role in the distribution network analysis. However, the distribution network is often complex in practice and it is necessary to simplify the distribution network model before searching the power supply paths. A simplified method of distribution network model based on common information model (CIM) and a path searching algorithm for distribution network based on the depth first traversal in the network simplification results are proposed. Firstly, the distribution network model is stored in a graph data structure and the network is simplified by using the graph theory algorithms. Subsequently, all the power supply paths of load nodes are searched in the distribution network by the path searching algorithm and classified into three categories of path sets respectively in terms of electric source, the load at the end of paths and the branch which the paths pass through. The path searching algorithm can be applied to the distribution network analysis such as describing the topological structure of the distribution network and the state of the branch switches. Finally, a typical distribution network framework in a provincial capital and IEEE network with123nodes are taken as examples to validate the effectiveness and practicability of the proposed network simplification method and path searching algorithm.

common information model (CIM); network simplification; depth first traversal; distribution network topology; path searching

2017-06-05;

2017-09-16。

上网日期: 2017-11-13。

徐成司(1995—),男,主要研究方向:电气与自动化。E-mail： 3140103128@zju.edu.cn

董树锋(1982—),男,通信作者,博士,副教授,主要研究方向:智能电网优化与控制技术。E-mail: dongshufeng@zju.edu.cn

孙 洲(1987—),男,工程师,主要研究方向:电网规划。E-mail: 419535239@qq.com

(编辑章黎)