基于贪心算法的配电网负荷转供路径搜索方法

丁建忠，陈 铭

(国网无锡供电公司，江苏 无锡 214061)

基于贪心算法的配电网负荷转供路径搜索方法

丁建忠，陈 铭

(国网无锡供电公司，江苏 无锡 214061)

配电网作为电力系统供电的最后环节，能否紧急应对各类失电故障显得尤为重要。介绍了国内外对配网转供方案的研究包括了启发式算法、随机优化算法、专家系统法、混合算法等。提出了一种基于贪心算法的配电网转供路径搜索方法，能实现开关操作次数最少的情况下，快速找到可行的转供方案，并且尽可能不切负荷，提高了配网的供电可靠性。算例验证所提方法的有效性。

配电网转供；N-1 安全准则；贪心算法；拓扑模型；路径搜索

配电网作为电力系统的最后环节，其供电可靠性直接决定了用电质量和客户满意度。当配电网发生故障时，除了需要隔离故障区域并将其尽快修复，还需要通过负荷转供来尽可能降低故障对配电网整体的影响[1]。

负荷转供是指配电网发生故障并进行隔离之后，通过开关的操作以及部分不重要负荷的切除，在满足安全约束的条件下，快速优先恢复故障下游重要负荷供电的同时，也尽可能恢复其他负荷的供电。负荷转供因其可以明显降低故障带来的损失，提高供电可靠性[2-3]，成为配网自动化系统中重要的核心功能之一。目前国内外许多学者对负荷转供提出的方法基本可以分成以下几类：启发式算法[4-7]、随机优化算法[8-10]、专家系统法[11-14]、混合算法[15-16]。

(1)启发式算法根据规则能够有效缩小求解空间，并且对各种不同结构的网络具有很好的通用性；但方案的最优性是无法做到的，解的优劣依赖于网络的初始状态。

(2)随机优化算法的模型相对完善，在足够的计算时间内可以获得最优或者次优方案，但是计算时间往往较长，不适用于大规模网络中。

(3)专家系统根据某个领域一个或者多个专家提供的知识和经验，进行推理和判断，模拟人类专家的决策过程，能够自动生成恢复故障需要操作的方案，实时性好，适用性广，可应用于网络较大时的方案求解，但库的建立和集成费时费力，而且故障种类众多，无法记录全部情况。

在承担配电网规划、改造、运行、调度与检修等任务时，通常要采用N-1安全准则进行配电网重构的供电安全分析。N-1安全准则是指正常运行方式下电力系统中任意一元件(如线路、发电机、变压器等)无故障或因故障断开后，电力系统应能保持稳定运行和正常供电，其他元件不过负荷，电压和频率均在允许范围内。对配电网影响最大的情况，就是一个供电源出现故障。

目前，N-1安全准则的负荷转供方法主要包括：负荷法[3,17]、主变互联转供法[18-20]、综合转移矩阵法等[21]。

(1)负荷法提出把主变间联络馈线作为负荷转供途径，形成站间负荷转移的思想雏形，但计算过程较为繁琐。

(2)主变互联转供法将故障主变的负荷平均分配给其存在联络关系的主变，转供思路清晰，计算量小，但存在负荷转移路径通畅和设备容量充足的假定，并未计及网络结构和设备容量的约束。

(3)综合转移矩阵法考虑主变和联络线路容量的约束，更贴近实际配电网系统运行状况，但由于未考虑主变容载比，转供后可能出现主变负载率偏高甚至越限，部分主变负载率偏低的情况。

本文使用了一种基于贪心算法的负荷转供策略计算方法，在满足N-1安全准则的前提下，实现通过对开关执行最少次数的操作，来恢复失电区域的供电，考虑到配电网中分布式光伏的建设和发展，本文还讨论了本文方法应用在含分布式光伏配电网时的适用性。

1 配网拓扑模型

对于一个配电网络，可将其抽象为由点集N和边集E构成的拓扑图。根据各节点的不同性质，可将所有节点归为3类集合——电源节点集、负荷节点集和母线节点集。因为母线可以认为是各点无差别的，所以抽象的看就是一个节点。所有节点统一编号，写作代表节点性质字母的下标。拓扑图上连接相邻点的边包含一个开关。

图1为某配网接线图，经过抽象简化后形成如图2所示的拓扑图。

图1 某配电网接线图

图2 某配电网拓扑图

根据图2的拓扑图，可以发现配网可以划分为若干个供电区块。每个供电区块均呈树状，其中的负荷节点和电源节点均为树状图中的叶子节点，即去掉任意电源节点或负荷节点，余下部分依然呈树状。

2 贪心转供算法

当配网中任意一个电源节点因故障退出运行，为了尽可能保证该电源节点对应的供电区块负荷不断电，需要采取转供手段，从其他供电区块调取电力。

贪心算法决策的基本原则是当前最优原则，即每一步动作只需要考虑如何使当前环境下的效益最大化，结合配网转供的具体问题来看，即如何尽可能的使实际开关投切总次数最少化。例如，能只从一个相邻供电区块获得全部所需的电力，就不从两个相邻供电区块获得。为了满足供电可靠性的要求，本文提出的贪心算法分为2个过程。过程一不包含切负荷操作，即寻找一种不断电的转供方案；如果过程一找不到这种方案，则进入过程二，通过切除一部分负荷，获得可行的转供方案。

2.1 贪心算法过程一

当供电区块的电源点退出运行，搜索所有与相邻且处于正常供电状态的区块，并找到其为转供所需要闭合的连接开关。记可为转供电力的相邻供电区块总数为t。过程一分为多步，最多执行的步骤数为t。

第一步：任意闭合一个连接开关，遍历所有可能情况。若任意一种情况下，潮流计算结果满足正常运行条件，则停止并记录该转供方案。否则，若，执行过程一第二步；若，执行过程二。

第二步：任意闭合两个连接开关，遍历所有可能情况。为了避免出现环状结构，需要将划分为2个子供电区、。以连接开关对应的中的2个节点为起、始点，搜寻供电干路。从任意一侧开始，依次试断开干路上的各开关。若任意一种情况下，潮流计算结果满足正常运行条件，则停止并记录该转供方案。否则，若，执行过程一第三步；若，执行过程二。

第三步：任意闭合三个连接开关，遍历所有可能情况。为了避免出现环状结构，需要将划分为3个子供电区、、。具体实现方法类似第二步。若任意一种情况下，潮流计算结果满足正常运行条件，则停止并记录该转供方案。否则，若，执行过程一第四步；若，执行过程二。

后续步骤与上述过程类同。

2.2 贪心算法过程二

当过程一无法提供可行方案时，需要进入过程二，通过切除部分负荷，得到可行的转供方案。定性分析可知，提供转供电力的邻近区块越多，失电区块所需切除的负荷就越少，因此在过程二中，t个连接开关均需闭合。搜索t个连接开关所在干路，试断开干路上的t-1个开关将划分为t个子供电区，直到满足前t-1个子供电区最大程度的利用所连接的邻近供电区块。易知，最后一个子供电区必然不能正常运行。按照从小到大的顺序依次切除连接其上的负荷，当余下负荷恰能满足正常运行条件时，停止并记录该可行转供方案。

图3为贪心算法整体流程。

图3 贪心算法整体流程图

3 应用于含分布式光伏配电网的情况

分布式光伏发电是分布式电源技术和光伏发电技术的结合产物，其利用光伏组件，将太阳能转化为电能。相比于集中式的光伏发电，分布式光伏发电更加靠近用户，减少了电力运输过程中的损耗，降低了成本，是一种经济、安全、环保的新能源利用方式。独立的光伏发电系统由于存在随机性和波动性等缺点，直接接入电网，容易引发电压波动、功率平衡等问题[22]，所以也会配套使用储能系统，构成光伏-储能系统，保证供电的稳定性。

随着化石能源的不断枯竭，能源结构转型实为大势所趋，可以预见未来配网中分布式光伏发电系统所占比例会越来越大。为了增强本文所提方法的适用性，结合实时情况，可将配网中的一个分布式光伏发电系统等效为一个电源节点加上一个负荷节点。当该光伏发电系统作为电源向外提供能量时，可将负荷节点消耗功率标记为0；当该光伏发电系统作为电池吸收外界能量时，可将电源节点发电功率标记为0。在不改变配网拓扑的前提下，该方法能够表征分布式光伏发电系统的各种工作情况。

4 算例分析

为了更好的理解算法，以图2拓扑图为例，讨论各种情况下的转供方案。图2中的光伏-储能系统处于吸收外界能量状态，故等效的电源节点标记为0。该图可以划分为3个供电区块。各负荷大小及电源节点容量上限见表1。

表1 节点参数表

本算例中，线路容量与对应的电源容量一致，故在电源不超载运行时，线路也可正常运行，所以线路容量约束条件在本算例可不考虑。

当因故退出运行，搜索的邻近供电区块，有，则t=2，连接开关分别为、。首先进入贪心过程一，因为t=2，所以最多执行两步：(1)第一步，闭合、中的任意一个开关。和的备用容量分别为800 kW和1 100 kW，而失电区总负荷为1 700 kW，易知第一步无任意情况满足正常运行条件；(2)第二步，闭合、两个开关。搜索与连接开关、对应节点、之间的供电干路。上不带负荷，故应断开开关。由于所带总负荷为1 200 kW，超过备用容量，则第二步仍无任意情况满足正常运行条件。进入贪心过程二，闭合、两个开关。断开，所在子供电区最大程度利用。切除，剩余，最后一个子供电区能正常运行。输出转供方案，过程结束。

5 结语

本文将配电网中的节点归为三类，提出了一种配电网拓扑图的生成方法。在此基础上，提出了一种基于贪心算法的配网转供路径搜索方法。该方法分为两个过程：过程一不进行任何切负荷操作；当过程一无法找到可行的转供方案，过程二通过切除部分负荷，提供合适的转供方案。该方法能实现开关操作次数最少的情况下，快速找到可行的转供方案，并且尽可能满足不切负荷，提高了配网的供电可靠性。经算例验证，本文所提方法有效。

[1] 廖怀庆，刘 东，黄玉辉，等.考虑新能源发电与储能装置接入的智能电网转供能力分析[J].中国电机工程学报，2012，32(16)：9-16.

LIAO Huai-qing, LIU Dong, HUANG Yu-hui, et al. Smart grid power transfer capability analysis considering integrated renewable energy resources and energy storage systems[J]. Proceedings of the CSEE, 2012, 32(16): 9-16.

[2]邱生敏，王浩浩，管 霖.考虑复杂转供和预安排停电的配电网可靠性评估[J].电网技术，2011，35(5)：121-126.

QIU Sheng-min, WANG Hao-hao, GUAN Lin. An improved algorithm for reliability assessment of distribution network considering complex load transfer and scheduled outage[J]. Power System Technology, 2011, 35(5): 121-126.

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

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

[4]郑 兰，别朝红，王秀丽.一种快速启发式配电网故障恢复算法[J].电力自动化设备，2004，24(2)：16-19.

ZHENG Lan, BIE Zhao-hong, WANG Xiu-li. A fast heuristic service restoration method for distribution network[J]. Electric Power Automation Equipment, 2004, 24(2): 16-19.

[5]RODRIGO J. RODRIíGUEZ A, ALBERTO VARGAS. Fuzzy-heuristic methodology to estimate the load restoration time in MV networks[J]. IEEE Transactions On Power Systems, 2005, 20(2): 1095-1102.

[6]周永勇，周 湶，刘育明，等.基于启发式搜索和模糊评价算法的配电网故障恢复[J].重庆大学学报，2010，33(5)：78-82.

ZHOU Yong-yong, ZHOU Quan, LIU Yu-ming, et al. Heuristic research and fuzzy evaluation for-post-fault restoration in distribution networks[J]. Journal of Chongqing University, 2010, 33(5):78-82.

[7]臧天磊，钟佳辰，何正友，等.基于启发式规则与熵权理论的配电网故障恢复[J].电网技术，2012，36(5)：251-257.

ZANG Tina-lei, ZHONG Jia-chen, HE Zheng-you, et al. Service restoration of distribution network based on heuristic rules and entropy weight[J]. Power System Technology, 2012, 36(5): 251-257.

[8]张玉春，杨成峰，曹海英，等.配电网故障恢复重构的改进遗传算法[J].华中电力，2007，20(4)：18-22.

ZHANG Yu-chun, YANG Cheng-feng, CAO Hai-ying, et al. Improved genetic algorithm for service restoration in distribution system[J]. Central China Electric Power, 2007, 20(4): 18-22.

[9]张 钊，封亚琴.一种新型的配电网供电恢复重构寻优算法[J].电网技术，2008，32(7)：51-55,65.

ZHANG Zhao, FENG Ya-qin. A novel optimization reconfiguration algorithm for power supply restoration of distribution network[J]. Power System Technology, 2008, 32(7): 51-56,65.

[10]文 莹.基于蚁群算法的配电网故障恢复策略研究[D].河北：燕山大学，2015.

[11]陈竟成，徐德超，于尔铿.配电网故障恢复系统[J].电力系统自动化，2000，24(4)：46-51.

CHEN Jing-cheng, XU De-chao, YU Er-keng. Distribution fault detection, isolation and restoration system in a distribution management system[J]. Automation of Electric Power Systems, 2000,24(4): 46-51.

[12]葛朝强，唐国庆，王 磊. 综合智能式的故障恢复专家系统——与故障恢复算法集相结合的自学习模糊专家系统[J].电力系统自动化，2000，24(2)：17-21.

GE Zhao-qiang, TANG Guo-qing, WANG Lei. Integrated intelligent service restoration system for distribution network —— an auto-learning fuzzy expert system combined with service restoration algorithm set[J]. Automation of Electric Power Systems, 2000，24(2): 17-21.

[13]杨成峰，乐秀璠.配电网故障恢复专家系统的一种实现[J].电力自动化设备，2001，21(11)：28-31.

YANG Cheng-feng, LE Xiu-fan. An implementation of service restoration expert system for power distribution network[J]. Electric Power Automation Equipment, 2001, 21(11): 28-31.

[14]KURISU SHINYA, TAKESHI NAGATA. A multi-agent systems for voltage control of distribution networks by coordination power factors of distributed generators[C]//2016 IEEE 16th international conference on environment and electrical engineering (EEEIC). Florence: EEEIC, 2016: 1-5.

[15]Ying-Tung Hsiao, Ching-Yang Chien. Enhancement of Restoration Service in Distribution Systems Using a Combination Fuzzy-GA Method[J]. IEEE Transactions on Power Systems, 2000, 15(4): 1394-1400.

[16]Seong-I1 Lim, Seung-Jae Lee, Myeon-Song Choi, et al. Service Restoration Methodology for Multiple Fault Case in Distribution Systems[J]. IEEE Transactions on Power Systems, 2006, 21(4): 1638-1644.

[17]欧阳武，程浩忠，张秀彬，等.城市中压配电网最大供电能力评估方法[J].高电压技术，2009，35(2)：403-407.

OUYANG Wu, CHENG Hao-zhong, ZHANG Xiu-bin, et al. Evaluation method for maximum load capability of urban medium-voltage distribution system[J]. High Voltage Engineering, 2009, 35(2): 403-407.

[18]王成山，罗凤章，肖 峻，等.基于主变互联关系的配电系统供电能力计算方法[J].中国电机工程学报，2009，29(13)：86-91.

WANG Cheng-shan, LUO Feng-zhang, XIAO Jun, et al. An evaluation method for power supply capability of distribution system based on analyzing interconnection of main transformers[J]. Proceedings of the CSEE, 2009, 29(13): 86-91.

[19]LUO Feng-zhang, WANG Cheng-shan, XIAO Jun, et al. Rapid evaluation method for power supply capability of urban distribution system based on N-1 contingency analysis of main-transformers[J]. International Journal of Electrical Power & Energy Systems, 2010, 32(10): 1063-1068.

[20]XIAO Jun, LI Fang-xing, GU Wen-zhuo, et al. Total supply capability and its extended indices for distribution systems: definition, model calculation and applications[J]. IET Generation, Transmissions & Distributions, 2011, 5(8): 869-876.

[21]葛少云，韩 俊，刘 洪，等.计及主变过载和联络容量约束的配电系统供电能力计算方法[J].中国电机工程学报，2011，31(25)：97-103.

GE Shao-yun, HAN Jun, LIU Hong, et al. Power supply capability determination considering constraints of transformer overloading and tie-line capacity[J]. Proceedings of the CSEE, 2011, 31(25): 97-103.

[22]徐少华，李建林.光储微网系统并网/孤岛运行控制策略[J].中国电机工程学报，2013，33(34)：25-33.

XU Shao-hua, LI Jian-lin. Grid-connected/island operation control strategy for photovoltaic/battery micro-grid[J]. Proceedings of the CSEE, 2013, 33(34): 25-33.

(本文编辑：杨林青)

Route Search Method for Distribution Network Load Transfer Based on Greedy Algorithm

DING Jian-zhong, CHEN Ming

(State Grid Wuxi Power Supply Company, Wuxi 214061, China)

It is particularly important for distribution network, as the final part of power system, to handle different kinds of blackout. This paper reviews the research on distribution network load transfer schemes, including heuristic algorithm, stochastic optimization algorithm, expert system method and mixed algorithm. Then it proposes a method to search load transfer route in distribution network based on greedy algorithm, which can locate a feasible way fast with the least switch operations, and shed as less load as possible to reach the reliability demand. Calculation has verified the effectiveness of the proposed method.

load transfer in distribution network; N-1 safety criterion; greedy algorithm; topological model; route search

10.11973/dlyny201606004

丁建忠(1969)，男，高级工程师，副总经理，从事电网规划、调度及生产管理工作。

TM76

A

2095-1256(2016)06-0681-05

2016-10-11