基于动态规划算法的故障恢复重构

张 浩 和敬涵 薄志谦 胡 伟 李 珂 周 文

（1.北京交通大学电气工程学院 北京 100044 2.阿尔斯通电网自动化公司 斯塔福德郡 ST17 4LX 英国 3.河北省电力研究院 石家庄 050021）

1 引言

随着电网结构、运行方式的日趋复杂和用户对供电可靠性要求的不断提高，电网的自愈恢复与重构作为智能电网的一项重要功能已经成为电力系统需要迫切考虑的问题之一[1-3]。配电网的故障恢复重构作为网络重构的一种，是指在故障定位和隔离的基础上，在不发生系统安全越限的条件下，通过网络重构快速恢复对非故障区失电负荷的供电。该过程一般要在综合考虑开关操作次数、馈线裕度、负荷恢复量、网络约束、用户优先级等因素下，提出优选的供电恢复方案[4]。这类问题一般不可微、不连续、多维、多约束条件、高度非线性化。对于此类问题的优化求解一直是国内外的研究热点。目前相关的求解思路主要有逻辑法[5]、专家系统[6]、启发式搜索[7-9]，以及多种方法的混合[10-11]。

动态规划（dynamic programming）是运筹学的一个分支，它是解决多阶段决策过程最优化问题的一种方法[12]。本文在总结现有算法成果的基础上，将故障恢复重构过程转化为一个多阶段决策过程，并设计了以动态规划算法为核心的故障恢复重构方案。该方案主要考虑配电网中功率不足时的负荷恢复问题，通过对待恢复区的划分降低了算法的复杂度，提高了算法的运行效率。

2 问题描述

故障恢复过程中，要尽可能多地恢复非故障失电的负荷，还要使开关操作次数最少。同时，为了在尽可能短的时间内恢复对停电区域的供电，减少用户的不满意程度，提高供电可靠性，恢复策略要具备较高的实时性。

重构的约束条件包含等式约束和一系列不等式约束。等式约束主要是潮流约束；不等式约束包括：馈线容量的约束、线路电流的约束、母线电压的约束、变压器过载约束[13]等。

为方便描述和简化计算，故障恢复重构进行如下假设：

（1）配电网中的故障元件均已隔离，且非故障带电区运行正常。

（2）已进行网络的简化等效，所有支路均有开关且可操作。

（3）重构前后网损近似相等，且各支路网损已包含在各节点功率参数内。

以图1所示的33节点系统为例，该系统结构在文献[14]的基础上添加了2个电源（S1，S2）。

图1 33节点网络结构示意图Fig.1 Diagram of 33-bus network

图中细实线为正常运行时的计算支路（如支路2-3），虚线为常开的联络支路（如支路8-21）。若节点7发生故障并被切除，则发电机S2退出运行，与节点7相连的下游区域（8～18节点）为非故障失电区（待恢复区）。

3 恢复重构算法

3.1 恢复区分割

非故障失电区可能同时连接有多个联络开关可用于负荷转供（如图1中的8-21；12-22；18-33）。这就需要考虑将其中的负荷节点分割为多个区域分别进行负荷恢复（简称为分区）。

分区需要综合考虑联络支路容量、联络开关和网络结构等要求，最多分割为与联络支路等数量的负荷区（待恢复区内部的联络支路不考虑，如图1中支路9-15），且每个负荷区的容量与该联络线的传输容量相匹配，尽量使多个负荷区的负荷量平衡，并能满足各约束条件。

分区时首先将恢复区内的所有开关闭合，再采用深度优先搜索方法，找到不同联络开关间的连通路径，并在该路径上断开一个开关，以此类推来实现整个分区过程。

设Lm(y)为分区数量为m的最优分区方案，则对于任一方案y，其负荷均衡系数计算方法为

式中，Ei(y)为方案y中联络支路i的均衡系数；E(y)为方案y的均衡系数；Si和Si_max分别为联络支路i上所分配的负荷容量和该支路所能承受的最大容量；vnode-j为节点j的负荷容量；n为需要恢复的节点数；b为可用于负荷转供的联络支路数。

开关操作比重系数为

式中，k为开关操作次数；α为开关系数，系数越高，开关操作数对分区结果的影响越重。

从而，Lm(y)计算方法为

一般来说，为了覆盖更多的可能分区策略，分区数m应取[1，b]间的所有自然数。每种分区方案均可独立进行重构计算，互不干扰，这就给实际运行提供了较为宽裕的选择余地。在实时性要求较高的情况下也可仅选择m=b以加快求解速度，当然这样会增加获得非最优解的可能性。实际运行中，可根据重构需求对α和m进行不同的取值来选择合适的分区方案。例如，对于图1所示网络结构，取m=b=3，α=2时的分区方案为：[8，9，10]，[11，12，13，14]，[15，16，17，18]。

3.2 动态规划模型

动态规划所研究的多阶段决策问题是指这样一类决策过程[12]：它可以分为若干个互相联系的阶段，在每一阶段分别对应着一组可以选取的决策，当每个阶段的决策选定以后，过程也就随之确定。把各个阶段的决策综合起来，构成一个决策序列，称为一个策略。显然由于各个阶段选取的决策不同，对应整个过程就可以有一系列不同的策略。

动态规划本身是一种方法而不是一种算法。本文结合配电网的恢复重构需求，对动态规划中的相关概念进行解释和设计以形成用于故障恢复的动态规划重构算法。

（1）阶段。阶段是对整个过程的自然划分。将联络支路作为计算阶段，则其也可以用联络支路符号i表示。用ci表示第i阶段进行转供的负荷节点串，用Ci表示第i阶段的节点串集合。

（2）状态。每个阶段开始时所处的自然状况叫做状态。定义网络的功率裕量与节点串的组合为状态。用hi表示第i阶段的功率裕量，xi表示该阶段的一个状态变量，Xi表示允许状态集合。则有

（3）决策。当一个阶段的状态确定后，可以做出各种选择从而演变到下一阶段的某个状态，这种选择手段称为决策。用ui(xi)表示第i阶段处于状态xi时的决策变量，Ui(xi)表示xi的允许决策集合。

（4）策略。决策组成的序列称为策略。由初始状态x1开始的全过程的策略记作p1m(x1)，即

式中，m为计算阶段数（分区数）。

（5）状态转移方程。在确定性过程中，一旦某阶段的状态和决策为已知，下阶段的状态便完全确定。用状态转移方程表示这种演变规律，写作

（6）指标函数和最优值函数。指标函数是衡量过程优劣的数量指标，用fi,m(Xi，ui，Xi+1，…，um)表示，i=1，2，…，m-1。指标函数的最优值，称为最优函数，记为fi(Xi)，表示从第i阶段的状态Xi开始到第m阶段的终止状态的过程，采取最优策略所得到的指标函数值，即

式中，opt表示最优结果。

3.3 恢复重构的动态规划算法

网络的功率裕量表示该网络可用于转供的最大负荷量。故障被隔离后，网络的初始裕量为

式中，h1为重构计算的初始功率裕量；S为网络中的电源提供的总功率；vuse为网络中未失电的负荷总量；β为可靠系数，优选取值0.8～0.95。

每一阶段中，根据所选节点的先后顺序不同而形成不同的操作序列，该序列可用节点串表示。例如3.1节举例分区方案中的一个分区[11，12，13，14]，从节点12开始，恢复供电的操作序列有三个（见图2）：

序列1｛(12)；(12,13)；(12,13,14)；(11,12,13,14)｝；

序列2｛(12)；(12,13)；(11,12,13)；(11,12,13,14)｝；

序列3｛(12)；(11,12)；(11,12,13)；(11,12,13,14)｝。

图2 节点串序列拓展示意图Fig.2 Node string sequence diagram

由此，对负荷节点恢复顺序的选择转化为对操作序列中节点串的选择。

不同阶段的操作序列进行组合，生成计算序列组。用ni表示第i阶段的操作序列数，则计算序列组数有

对于每组计算序列的第i阶段任一xi，有

式中，vci-1表示选节点串ci-1的容量。

从而第i阶段有效节点串集合为

式中，R表示重构过程中各类电气约束条件。

有效节点串的提取可减少计算组合数，从而提高计算效率，加快算法的实现。

定义f（ixi）表示状态变量xi的允许决策集合与前一阶段每个状态变量的最优结果进行组合的最优结果，有

对于第i阶段，计算出每个状态变量的fi函数以后，记下hi及所选的节点串ci-1。继续计算该阶段的最优函数，记为f（xi）。

定义C0=φ，则对于第1阶段的任一状态变量x1，可得到该状态的fi函数为

利用上述方法可以得到第1阶段的最优函数f1(x1)及f1(X1)。进而求取各阶段最优目标f(Xi)达到本网络容纳负荷量最优。

算法实施描述如下：

（1）根据重构请求，启动重构算法。获取故障发生前的网络相关信息（如网络的潮流、电压、功率分布等），计算待恢复区负荷容量及网络功率裕量。

（2）进行分区计算，并计算序列组的生成。同时判断网络功率裕量和网络结构是否足够恢复所有负荷。是，则直接输出计算结果；否，则转（3）。

（3）判断是否已经完成所选序列组的计算。若是，则输出计算结果；否，则进行序列选择并转（4）。

（4）计算第i阶段中网络的功率裕量hi及该阶段的有效节点串集合optCi。计算最优函数fi(xi)及fi(Xi)。判断是否已经遍历联络支路及待恢复区的所有节点。若是，则转（5）输出计算结果；若否，则转（4）进行循环计算。

（5）输出计算结果。

重构算法流程如图3所示。

图3 算法流程图Fig.3 Flow chart of the algorithm

4 算例分析

用33节点和69节点两个算例来验证本文算法的有效性。采用简单遗传算法（SGA）和本文所用动态规划算法（DP）进行计算结果对比。遗传算法初始种群40个，迭代次数为50，交叉变异概率分别为0.8和0.07。动态规划算法分区数m取[1，b]间的所有自然数。为简化描述，这里仅以有功功率为例进行功率计算，所有节点优先级相同，假设所有支路上限容量均为5MW，网络初始功率裕量h1=0.5MW。两种算法均采用重复计算100次求平均的方法计算耗时。

验证平台电脑CPU为奔腾四2.6GHz，内存1GB，操作系统为Windows XP，程序采用Matlab编写。

4.1 33节点算例

如图1所示33节点系统，节点功率数据来自文献[14]，并在其基础上添加了两个电源。所有负荷节点总有功容量：3.715MW。假设节点7出现故障并被切除，则电源S2停运，非故障失电区容量为0.765MW。有三个分区方案，分别为

两种算法均能恢复0.495MW的负荷，且均找到两种最优结果（最大恢复容量和开关操作数均相同且最优）。由于篇幅所限，这里仅列出一种最优结果见表1。

表1 33节点恢复重构计算结果Tab.1 Results with 33-bus system

忽略两者在具体编程过程中的编程风格不一致等情况带来的影响。简单遗传算法由于在交叉运算中易产生大量不可行解，耗时较长，而且在部分重复计算过程中收敛于非最优解；而动态规划算法每次计算结果均相同，耗时较短。最终恢复供电结构如图4所示，经潮流计算证明该结果可行。

图4 33节点恢复后结构Fig.4 33-bus network reconfiguration

4.2 69节点算例

图5 69节点网络结构示意图Fig.5 Diagram of 69-bus network

图5 所示为69节点网络结构系统，节点功率数据来自文献[15]，并在其基础上添加了两个电源。假设节点10出现故障并被切除，则电源S2停运，非故障失电区容量为0.7398MW。三个分区方案为

计算结果与前一算例类似，两种算法仅在计算时间上有明显差别。动态规划算法比简单遗传算法具有更短的计算周期。表2为16个最优结果中的一个。

表2 69节点恢复重构计算结果Tab.2 Results with 69-bus system

5 结论

本文结合配电网重构问题的特点和动态规划思想提出一种电网恢复重构方案。通过对非故障失电区的分区、计算序列生成，将配电网恢复重构过程转换为一个多阶段决策过程，并以此构建了多阶段决策模型，设计了动态规划算法，可在网络功率裕量不足时快速实现网络重构，从而提高系统的供电可靠性，减少负荷断电时间。

[1] 余贻鑫,栾文鹏.智能电网述评[J].中国电机工程学报,2009,29(34): 1-8.Yu Yixin,Luan Wenpeng.Smart grid and its implementations[J].Proceedings of the CSEE,2009,29(34): 1-8.

[2] Heydt G T.The next generation of power distribution systems[J].IEEE Transactions on Smart Grid,2010,1(3): 225-235.

[3] 王明俊.自愈电网与分布能源[J].电网技术,2007,31(06): 1-7.Wang Mingjun.Self healing grid and distributed energy resource[J].Power System Technology,2007,31(06)1-7.

[4] 陈竟成,徐德超,于尔铿,等.配电网故障恢复系统[J].电力系统自动化,2000,24(4): 46-51.Chen Jingcheng,Xu Dechao,Yu Erkeng,et al.Distribution fault detection,isolation and restoration system in a distribution management system [J].Automation of Electric Power Systems,2000,24(4):46-51.

[5] 刘健,倪建立,邓永辉.配电自动化系统[M].北京:中国水利水电出版社,1999.

[6] Men Shen T.Development of an object-oriented service restoration expert system with load variations[J].IEEE Transactions on Power Systems,2008,23(1): 219-225.

[7] Sudhakar T D,Vadivoo N S,Slochanal M R.Heuristic based strategy for the restoration problem in electric power distribution systems[C].2004 International Conference on Power System Technology,Singapore,2004,1: 635-639.

[8] Luan W P,Irving M R,Daniel J S.Genetic algorithm for supply restoration and optimal load shedding in power system distribution networks[J].IEE Proceedings Generation,Transmission and Distribution,2002,149(2): 145-151.

[9] Watanabe I,Nodu M.A genetic algorithm for optimizing switching sequence of service restoration in distribution systems[C].Congress on Evolutionary Computation,CEC2004,Portland,Oregon,America,2004,2: 1683-1690.

[10] Hsiao Y T,Chien C Y.Enhancement of restoration service in distribution systems using a combination fuzzy-GA method[J].IEEE Transactions on Power Systems,2000,15(4): 1394-1400.

[11] Seong Il L,Seung Jae L,Myeon Song C,et al.Service restoration methodology for multiple fault case in distribution systems[J].IEEE Transactions on Power Systems,2006,21(4): 1638-1644.

[12] 吴祈宗.运筹学[M].北京: 机械工业出版社,2007.

[13] 徐青山.电力系统故障诊断及故障恢复[M].北京:中国电力出版社,2007.

[14] Baran M E,Wu F F.Network reconfiguration in distribution systems for loss reduction and load balancing[J].IEEE Power Engineering Review,1989,9(4): 101-102.

[15] Baran M E,Wu F F.Optimal capacitor placement on radial distribution systems[J].IEEE Transactions on Power Delivery,1989,4(1): 725-734.