最小生成树算法在配电网重构中的应用

， ， ， ，

(1.西南石油大学电气信息学院，四川 成都 610500；2.国网成都供电公司客服中心，四川 成都 610046；3.国网天府新区供电公司， 四川 成都 610000)

0 引 言

作为电力系统重要组成部分的配电系统，由于直接面向终端用户，所以对其供电可靠性和电能质量方面的要求也越来越高，而它的完善与否直接关系着广大用户的用电可靠性和用电质量[1]。随着电力用户逐渐增多，配电线路经常出现超负荷或轻负荷现象，出现电压降低，并且有功损耗增加。

而通过配电网重构可以很好地解决上述问题，实现负荷的均衡和降低有功损耗。通过配电网络重构可以实现降低配电网线损，提高系统经济性；均衡负荷，消除过载，提高供电电压质量，提高供电可靠性。配电网重构的方法有很多，文献[2]采用最短路径算法对配电网进行重构，利用最短路径算法寻找所有负荷节点的供电最短路径，在形成的树状网络中利用最小点电压法进行支路交换操作。该方法对降低系统有功损耗和提高供电质量作用明显，但由于需要寻找根节点向每个负荷节点供电的最短路径，计算复杂。文献[3]采用基于图论的改进遗传算法进行重构优化，在初步连接图的基础上寻找最优的生成树，基于破圈法和环路的性质进行编码操作，得到最优解，该算法在配电网重构中具有理想的效果，能以较大概率保证收敛到全局最优解，但该方法计算量较大，速度较慢。文献[4]提出了一种利用节点电压进行配网重构的方法，将电压均衡指数作为目标函数，通过连续的支路交换操作来寻求配电网的最佳结构，该方法即使在严重缺乏量测点时,仍可以进行。文献[5]提出了通过组合负荷实现寻优的重构方法，利用最短路径法按照某一顺序为每个负荷分别寻找供电路径, 然后利用遗传算法选择最优的负荷排列顺序, 从而实现在局部最优解中寻求全局最优解。因算法不依赖于网络初始结构，可以得到全局最优解，但存在“维数灾”问题。此外，还有应用于智能电网的配电网重构[6]，最小供电成本的配电网重构[7]等，及基于各种智能优化算法[8-10]的配电网重构。

基于图论的最小生成树算法是网络最优化算法中最重要的算法之一，在很多工程技术领域中得到应用。例如，在若干城市之间架设通信线缆，铺设线路、铁路或各种管道，要求总的路线长度最短或材料最省、成本最低等。而目前常用的最小生成树算法有Prim算法和Kruskal算法，这里选用改进Kruskal算法进行配电网重构。通过数学建模建立目标函数后利用潮流算法计算环网节点电压，并对每一条边赋权值后进行最小生成树计算，并通过反复迭代更新权值的方式使网络达到最优。33节点和69节点算例验证了算法的有效性。

1 配电网重构算法

1.1 数学模型

(1)目标函数

配电网重构一般以降低配电网的线路损耗、提高配电网的电压质量、提高供电可靠性和均衡负荷等为目标，也可以综合上述多个指标为目标。采用以最小有功损耗为目标，其表达式为

(1)

(2)

式中，m为网络中支路总数；Pi和Qi为流过支路的有功功率和无功功率；Ri为支路电阻；Ui为支路的首端电压；U为最低节点电压值；ΔP为网络中所有线路的有功损耗之和。

(2 )约束条件

配电网重构的目标是使f最小，且满足下面的约束条件。

Ui，min≤Ui≤Ui，max

(3)

Ii≤Ii，max

(4)

Si≤Si，max

(5)

(6)

式中，Ui，min和分别为节点i的电压下限和上限；Ii，max为支路电流最大值；Si，max为支路i或配电变压器的最大负载能力；PLi和QLi分别为节点i注入的有功功率和无功功率；Gij、Bij、δij分别为节点i、j的电导、电纳和电压相角差；n为系统总节点数；U1、Uj分别为节点i、j的电压幅值。网络辐射状运行，无环路及孤立节点。

1.2 基于Kruskal算法的最小生成树计算原理

由于配电网是闭环设计，开环呈辐射状运行，配电网络重构问题所求的最优解可看作是在赋权图中寻找以根节点为起点，满足目标函数的最小生成树问题[11]。将Kruskal算法应用于配电网络重构的一个显著优势就是可以建立所有负荷节点与根节点的连接，并自动形成辐射状网络。

为便于描述,可用G=(V,E)来描述一个配电网络(其中V为节点集合、E为边集合)[12]，配电网重构问题所求的最优解可以认为是满足目标函数中的一棵最小生成树T。用l(e)表示边的权值，则所有负荷节点和根节点的最小生成树可以表示为[8]

(7)

Kruskal算法是目前公认的求最小生成树问题的最好方法。对于一个连通赋权图G=(V,E)，图G的最小生成树T按下述方法构造：在E中选择权值最小的边，作为T的第一条边，相继选择E剩下的边中权值最小的边加入T，且该边满足不与前面所选的边构成圈，持续这种做法，直至产生一个生成树[9]。

1.3 配电网重构的搜索算法

由于Kruskal算法不依赖网络的初始结构,使得形成树状网络变得较容易，并且易于解决复杂结构网络的寻优问题。具体步骤如下。

由文献[4]可知，在仅能够获得配电线路沿线柱上开关处的量测信息的情况下，仍然能够求解出网络重构后沿线各处的电压降落，因此对于量测不足的配电系统，也可以认为其电压降落是已知的。所以对于配电网来说其各节点电压值是很容易得到的。由此，文献[4]提出基于电压的平衡指数来调整联络开关和分段开关的位置，最终得到一个满足约束的最优网络。定义网络中各联络开关和分段开关的电压平衡指数为VBLi-j。

VBLi-j=max(UNi，UNj)/min(UNi，UNj)

(8)

式中，min(UNi，UNj)表示取小值；max(UNi，UNj)表示取大值。

所提算法主要步骤如下。

(1)求电压平衡指数：闭合配电网中的所有联络开关，通过计算环网潮流得到节点电压，以此来求得各开关的电压平衡指数。

(2)初始最小生成树的生成：以各开关的电压平衡指数为求最小生成树的边的权值，利用最小生成树算法Kruskal算法求得最小树T(K)，这是对配电网的初次优化，得到一个辐射状运行的网络，通过潮流计算得到最小生成树T(K)的有功损耗和最低节点电压。

(3)联络开关排序：将得到的除最小生成树T(K)外断开的开关按权值从小到大的顺序放入队列Q中，在下面所用的标准算例中，得到断开的开关有5条，作为联络开关处理。

(4)联络开关排序：取出队列Q之首的开关k放到T(K)中，由此产生一个环路，计算当前网络的权值，选择除新加边外环路上所有开关，按权值从小到大排列放入队列Q1中。

(5)迭代更新：断开队列Q1之首的开关n，即可构成一棵新的树T(N)。进行潮流计算，比较T(N)和T(K)的有功损耗。

比较结果分为以下两种情况。

1)若T(N)的有功损耗小于T(K)的有功损耗，且满足约束，则此联络开关闭合为最优结果，将Q1中断开的开关n放入队列Q的末端，并且清空队列Q1，返回步骤(4)。

2)若T(N)的有功损耗大于T(K)的有功损耗，将Q1中首元素n置于Q1队列末端,返回步骤(5)，反复迭代。

在此过程中可能会出现依次断开Q1队列的所有开关后依然无法得到使T(N)的有功损耗小于T(K)的有功损耗的开关n。在这种情况下，开关k为最优开关，将开关k放入队列Q的末端，并且清空队列Q1，返回步骤(4)。

当初始队列Q中的联络开关全部动作完时算法结束。

2 算例分析

为验证所提方法的正确性和可行性,选择文献[4]所用的2个标准算例33节点系统和69节点系统进行验证,并将计算结果和不同算法重构的运算结果进行比较。

2.1 33节点系统

该配电网为12.66 kV的配电系统，有33个节点、37条支路,其中的5条为联络开关，系统总有功负荷为3 715 kW，初始有功损耗为202.68 kW。采用所提方法得到的优化结果如表1所示。

表1 33节点系统配电网络重构结果

由表1结果可以看出所提算法与文献[4]的结果一致。重构前系统最低电压为0.913 1 p.u.,重构后系统最低电压为0.937 8 p.u.，提高了2.7%，从一定程度上改善了电压质量，系统重构前后电压变化如图1所示。重构前系统有功损耗为202.68 kW，重构后系统有功损耗为139.55 kW，降低了31.1%。

图1 33节点系统重构前后节点电压比较

2.2 69节点系统

该配电网为12.66 kV的配电系统，有69个节点、73条支路,其中的5条为联络开关，系统总有功负荷为3 802.19 kW，初始有功损耗为226.05 W。采用所提方法得到的优化结果如表2所示。由于所采用的节点编号与文献[4]不同，所以得到的开关编号不同，但最终结果是一致的。

在系统规模增大后，所得计算结果仍与文献[4]的结果保持一致，这说明了针对不同规模的配电系统所提算法仍然适用。由表2可知，重构前系统最低电压为0.901 8 p.u.，重构后系统最低电压为0.942 8 p.u.，提高了4.5%，改善了整个配电系统的电压质量；重构前系统有功损耗为226.05 kW，重构后系统有功损耗为99.67 kW，降低了56.03%。

表2 69节点系统配电网络重构结果

图2 69节点系统重构前后节点电压比较

3 结 论

(1)提出了以有功损耗最小为目标函数的配电网络重构方法,该方法利用Kruskal算法在配电网所有开关闭合的情况下,将线路电压平衡指数为权值,通过寻找图的最小生成树初步优化网络,为后续的细致优化提供一个可行的初始解。通过Kruskal算法的初步优化使得所提算法不依赖网络的初始结构，具有更好的适用性。

(2)通过动态调整各条边的权值并反复迭代进行支路交换操作，细致优化网络,进一步寻找满足目标函数的网络拓扑,两个常用算例表明该算法取得了满意的效果。

通过对以上算例的分析可知,利用算法对网络进行重构后,网络的供电电压质量明显提高,有功损耗也大为降低,重构效果明显，与此同时适用不同规模的配电网络。

[1] 王守相,王成山.现代配电系统分析[M].北京：高等教育出版社，2007.

[2] 王磊,柯丽芳,姚李孝,等.基于最短路算法和最小节点电压法的配电网络重构[J].电网与清洁能源,2011,27(6):4-7.

[3] 杨建军,战红.基于图论的改进遗传算法在配网重构中的应用[J].电力系统保护与控制,2010,38(21):122-125.

[4] 毕鹏翔,刘健,张文元.以提高供电电压质量为目标的配网重构[J].电网技术,2002,26(2):41-43.

[5] 余贻鑫,段刚.基于最短路算法和遗传算法的配电网络重构[M].中国电机工程学报,2000,20(9):44-49.

[6] Daniel P Bernardon,Luciano L Pfitscher,Luciane N Canha.Smart Grid Concepts Applied to Distribution Network Reconfiguration[C].Universities Power Engineering Conference(UPEC), 47th International 2012：1-6.

[7] Miguel Arias-Albornoz.Distribution Network Configuration for Minimum Energy Supply Cost[J].IEEE Transactions on Power Systems, 2004(1)：538-542.

[8] 许立雄，吕林，刘俊勇.基于改进粒子群优化算法的配电网络重构[J].电力系统自动化，2006,30(7):27-30.

[9] 李振坤，陈星莺，余昆,等.配电网重构的混合粒子群算法[J].中国电机工程学报，2008,31(28):35-41.

[10] 陈春，汪沨，刘蓓，等.基于基本环矩阵与改进和声搜索算法的配电网重构[J]. 电力系统自动化，2014，38(6):55-60.

[11] 王磊,吕娟,张强. 基于最小生成树算法的配电网络重构[J].陕西电力，2009(1)：13-17.

[12] 龚勋.图论与网络最优化算法[M].重庆：重庆大学出版社,2009.