基于双向广度优先搜索的配电网可靠性评估

卢纯，刘少云

(1．国网新源建设有限公司，北京100000;2．国网新疆电力公司，新疆乌鲁木齐830001)

基于双向广度优先搜索的配电网可靠性评估

卢纯1，刘少云2

(1．国网新源建设有限公司，北京100000;2．国网新疆电力公司，新疆乌鲁木齐830001)

配电网是电力系统与用电客户的连接环节，对配电网进行可靠性评估，可以发现配电网的薄弱环节，为电网的维护提供重要信息。针对配电网负荷点密集、计算量大的特点，文章应用双向广度优先搜索方法进行最小路的搜索。该方法具有搜索快、用时短、准确性高的优点，通过C++实现程序设计，使得整个配电网可靠性评估过程迅速且准确进行。对某配电网实例进行可靠性评估，得到了与传统方法相同的结果，并且速度较快。算例结果表明基于双向广度优先搜索的配电网可靠性评估方法是有效的。

配电网;可靠性评估;双向广度优先搜索;最小路

0 引言

配电系统是电力系统中供电点与用户之间的整个配电部分，配电网的可靠性对社会经济等各方面有着直接影响。因此对配电网的可靠性展开快速准确的评估，并提高其可靠性具有重要的现实意义［1－3］。

目前，我国关于配电网的可靠性评估已有一部分研究，但是很多局限于理论方面的探讨，未能应用到实践，没有满足对电网的建设发展等提供有效的指导。从当前关于可靠性的研究成果可知，对于可靠性评估的方法主要分为两类:第一类被称为解析法(Analytical Method)，如故障后果分析法、网络等值法［4］、最小割集法［5］、最小路法［6－8］等;第二类叫做模拟法(Simulation Technique)，通常指的就是蒙特卡洛模拟法［9－10］。

随着电网结构复杂程度的增加，如何快速准确实现可靠性指标的计算成为众多可靠性评估方法研究的关键。文献［11］构建了采用GO法的可靠性评估模型，该模型对复杂系统不用定性分析，所以不会随电网结构的扩大而变得复杂，可以较快计算出评估电网可靠性所需要的指标数据。文献［12］研究了广度优先算法和最小路法结合的可靠性评估模型，采用广度优先搜索算法不重复搜索的特点进行最短路径的搜索。文献［13］采用Dijkstra算法来求取最短路径，然后基于最小路径实现可靠评估。这种求解最短路径的方法是逐步求出距离原点距离最短的点，而且更新该点与其相邻各点的距离，最终求出最短路径。上述所提方法中，都涉及到如何在保证评估准确性的同时提高搜索速度的问题。

本文研究了一种基于双向广度优先搜索(Double Breadth First Search，DBFS)［14］算法的配电网可靠性评估方法。该方法具有搜索快、用时短、准确性高的优点，将DBFS方法用于求取最小路径，然后用最小路法进行评估，可以显著提高运算速度。利用C++实现程序设计，通过对某配电网开展可靠性评估，验证了算法的准确性与快速性。

1 配电网可靠性指标

配电系统可靠性侧重点是配电系统电源对广大用电客户保持持续供电的能力。配电系统的可靠性最终要借助各种可靠性指标来评估。无论是配电系统的性能，还是负荷以及元件的性能，往往都是具有概率的特征。因此，现在国内外关于配电系统的可靠性评估相关研究，选用的分析指标均是基于概率的指标［15－16］。

1.1 负荷点的可靠性指标

(1)平均故障率

平均故障率(λ，次/a)表示的是系统内某一负荷点在一个具体的时间段内，由于系统的元件故障引起的停电次数。可以采用下式计算:

(2)平均停运持续时间

平均停运持续时间(r，h/次)表示的是从停电开始到恢复供电这个时间段的平均值。

(3)平均停运时间

平均停运时间U(h/a)表示的是用电客户在某一给定的时间段内停电时长的平均值。通常，平均停运时间越大，那么该负荷点的故障排除需要的时间也就越长，供电可靠性水平越低。

式中:λ'i为元件i故障率;λ″i为元件i检修停运率;γ'i为元件i的平均故障修复时间;γ″i为元件i的平均检修持续时间;n为负荷点与电源之间的电气元件总数。

1.2 系统的可靠性指标

系统的可靠性评估指标为:系统平均停电持续时间SAIDI、系统平均停电频率SAIFI、用户平均停电持续时间CAIDI、用户平均停电频率CAIFI、不可靠率ASUI，根据分析获得的负荷点的可靠性指标作为基础，可求出系统的可靠性指标，具体公式如下:

式中:λi为负荷点i的平均故障率;Ni为负荷点i的用户数;Ui为负荷点i的年平均停运时间。

1.3 典型网络结构可靠性计算

一个完整的电力网络是通过各种各样的元件连接而成，在对配电网开展可靠性方面的评估时，可以通过对并联或者串联的若干元件进行等效处理，简化为一个元件，这样可以使整个评估过程的计算量得到很大程度的降低。

1.3.1 串联网络的计算

对于由n个可修复元件组成的串联网络如图1所示，串联系统的多种参数可以采用如下公式进行计算。

等效故障率:

等效每次故障平均停电持续时间:

等效年平均停电时间:

图1 串联等值网络

1.3.2 并联网络的计算

对于并联的网络结构，如图2所示。

图2 并联等值网络

等效每次故障平均停电持续时间:

等效年平均停电时间:

在实际处理过程中，通常会遇到含有三个甚至更多的元件所组成的网络，先把其中的两个元件等效处理为一个元件，然后将合并后的元件再和第三个元件进行组合处理，以此类推进行处理。

等效故障率:

2 双向广度优先搜索算法

2.1 最小路评估方法

在实际配电网当中，不同的网络其线路结构以及电气设备都有所区别，所选择的计算方式也不可能完全相同，根据实际情况改变计算方式，无形之中增加了计算的复杂程度，加大了可靠性评估的难度。为了有效应对与解决这些潜在的问题，以降低配电系统可靠性方面评估的难度，相关学者提出了基于最小路的配电网评估方法。

基于最小路的评估方法的核心是首先寻找配电系统中的所有负荷点与电源点之间的最小路，然后根据最小路的选择情况，将整个配电系统的所有元件分成两类:一类元件是处在最小路上的;另一类元件是处在非最小路上。对于最小路上的元件以及非最小路上的元件进行计算以及处理的原则详见文献［8］。

2.2 广度优先搜索求取最小路

广度优先搜索(BreadthFirstSearch，BFS)［17－18］是图论中的一个较为简单的搜索方法。在实际搜索过程中，BFS搜索方法是一种“广撒网”的理论，在开始搜索之前，并没有预期或者估计可能的位置节点，不具有针对性，而是直接对整张图进行全面、系统的展开搜索，一直到寻求到想要的结果才结束。BFS搜索法的流程图如图3所示。

图3 BFS流程图

2.3 双向广度优先算法

尽管广度搜索的方法可以获得最优解，但由于其自身的搜索特点，造成空间消耗过快，影响计算效率。假如从起点和终点同时开始展开搜索，理论上可以减少一半的搜索时间，进而提高了效率。双向广度优先搜索方法是以常规的广度优先搜索为基础，分别从初始点与目标点同时按BFS方式进行扩展，使之在中间某节点相遇。图4描述了双向广度优先搜索的思路和执行过程:分别从初始节点沿着正方向开始搜索、从目标节点沿着反方向朝着出始节点开始搜索，一直到两个搜索过程同时到达在中间某个节点时结束，从而得到网络中的一条路径。和常规的广度优先搜索算法不同的是，双向广度优先算法在搜索过程中减少了扩展出的状态数，双向进行，因此提高了效率，加快了整个网络结构的搜索过程;同时可以和BFS一样，具有“求出的解是最优解”的优点。

为了详细说明DBFS算法搜索的实现过程，以图4所示的7节点无向图为例进行详细介绍。

图47 节点系统图

DBFS算法的详细过程可以描述为:搜索开始后，起始节点V1和目标节点V4、V7、V6同时向前开始搜索，然后在中间节点V2、V5、V3中某个位置会和，完成路径搜索。采用DBFS对图进行搜索时，整个过程是逐层搜索，出现重复的次数比较少，效率相对较高。

2.4 双向广度优先算法的C++程序实现

对于复杂的网络结构，节点及支路数目较多，将配网系统的的等效有向图作为原始数据，可以用C++编写计算机程序，使搜索过程更加便捷，提高效率。计算机程序实现的流程图如图5所示。

3 算例分析

本文以南方某配电系统为例，进行可靠性分析，采用BFS和DBFS两种搜索方法同时计算，以验证基于双向广度优先搜索的评估方法的准确性与快速性。该配电网络具有3 000 kW的备用容量，不考虑变电站10 kV母线停运及断路器相邻两侧隔离开关的故障。该配电网的接线图如图6所示，线路和负荷参数详见表1和表2。

图5 计算机程序流程图

图6 配电网接线图

对于算例中较简单的网络结构，采用BFS和DBFS分别搜索最小路径，两种方法的所用时间如表3所示。

然后采用最小路法进行评估，得到配电网的可靠性指标结果是相同的，如表4和表5所示。

表1 供电干线参数

表2 系统元件可靠性参数

表3 两种方法时间对比

表4 各负荷点的可靠性指标

表5 系统可靠性指标

由上面数据可以知道，BFS和DBFS两种方法均可实现最短路径的搜索，而且DBFS搜索效率更高。可靠性指标的数据相同，表明DBFS的搜索结果是正确的，可以在提高速度的同时实现对配电网的准确评估。

4 结论

对配电网进行有效及时的状态评估至关重要。最小路法评估模型适用于各种电网结构，如何准确快速地完成最小路径搜索，实现指标计算是评估过程中非常关键的环节。本文研究了基于双向广度优先算法的配电网评估方法，利用广度优先搜索算法搜索电网结构的最短路径，具有快速、准确的优点，提高了配电网评估的效率。通过编写C++计算机程序，结合算例，证明了这种方法是有效可行的。

［1］程德才，赵书强，马燕峰．配电网可靠性指标的灰色组合预测方法及应用［J］．电力科学与工程，2009，25(3):18－21．

［2］任建文，李越佳．基于馈线分区的分布式电源接入配电网可靠性评估［J］．华北电力大学学报(自然科学版)，2015，42(6):29－34．

［3］徐其迎，王少卿，李日隆．基于区间算法的配电系统可靠性评估方法［J］．电力科学与工程，2003，19(4):26－28．

［4］张杰，王晓刚，邓智杰，等．基于改进网络等值和故障影响矩阵的复杂配电网可靠性评估［J］．中国电力，2016，49(7):20－26．．

［5］相晓鹏，邵玉槐．基于最小割集法的配电网可靠性评估算法［J］．电力学报，2006，21(2): 149－153．

［6］XIE K，ZHOU J，BILLINTON R．Reliability evaluation algorithm for complex medium voltage electrical distribution networksbasedontheshortestpath［J］．IEEE Proceedings-Generation，Transmission andDistribution，2003，150(6):686－690．

［7］周念成，谢开贵，周家启，等．基于最短路的复杂配电网可靠性评估分块算法［J］．电力系统自动化，2005，29(22):39－44．

［8］戴雯霞，吴捷．基于最小路的配电网可靠性快速评估法［J］．电力自动化设备，2002，22(7): 29－31．

［9］侯雨伸，王秀丽，刘杰，等．基于拟蒙特卡罗方法的电力系统可靠性评估［J］．电网技术，2015，39(3):744－750．

［10］侯雨伸，王秀丽，张玥，等．考虑维度重要性的电力系统可靠性评估拟蒙特卡洛方法［J］．电力系统自动化，2016，40(16):31－37．

［11］徐荆州，李扬，陈霄．基于GO法的配电网可靠性评估［J］．电力系统及其自动化学报，2006，18(5):66－69．

［12］郭慧敏．应用最小路－广度优先搜索的配电系统可靠性评估［J］．电力系统保护与控制，2007，35(22):14－17．

［13］张小娟，李泽荣，张重远，等．基于最小路法的配电网可靠性评估［J］．电网与清洁能源，2010，26(8):24－28．

［14］王桂平，张帅．基于双向广度优先搜索的魔力方块问题求解［J］．计算机工程，2011，37(20): 219－222．

［15］葛少云，季时宇，刘洪，等．基于多层次协同分析的高中压配电网可靠性评估［J］．电工技术学报，2016，31(19):172－181．

［16］胡美玉，胡志坚，邓奥攀，等．基于元件层级和电源可达性的配电网可靠性评估混合算法［J］．电力系统保护与控制，2016，44(8):22－29．

［17］张海波，张晓云，张莉，等．基于广度优先搜索的配电网故障恢复算法［J］．电网技术，2010，34(7):103－108．

［18］刘爱国，张弘．一种基于广度优先搜索配电网潮流计算的改进编号方法［J］．中国电力，2016，49(10): 74－78．

Reliability Evaluation of Distribution Network Based on Double Breadth First Search

LU Chun1，LIU Shaoyun2
(1．State Grid Xin Yuan Construction Co．，Ltd．，Beijing 100000，China; 2．State Grid Xinjiang Electric Power Company，Urumchi 830001，China)

As alink between power system and customers，the distribution network is of great importance．And the reliability evaluation of the distribution network can find the weakness and provide important information for the maintenance of the power grid．According to the characteristics of heavy load and large amount of calculation in distribution network，the double first search method is used to search the minimal path in this paper．This method has the advantages of fast searching，short consumption time and high accuracy．Through the implementation of C++programming，the reliability evaluation process is carried out with speed and accuracy．The reliability of a distribution network is evaluated，and the accuracy and rapidity of the algorithm are verified．

distribution network;reliability evaluation;double breadth first search; the minimal path

TM73

A

1672－0792(2017)07－0009－06

卢纯(1986－)，男，硕士研究生，工程师，研究方向为配电网规划、电网状态评估;刘少云(1985－)，男，工程师，研究方向配电网规划、电网状态评估。

10.3969/j.ISSN.1672－0792.2017.07.002

2017－05－22。