基于图论的配电网规划问题

曹磊

摘 要：以城镇配电变电站选址和设计最佳配电线路为研究背景，讨论了将配电网络抽象为赋权图后图元及权值的确定方法，构造算例，采用最短路径Dijkstra算法和Kruskal最小生成树算法进行了求解。

关键词：配电网；赋权值图；Kruskal算法；Dijkstra算法

1 配电网拓扑图图元的确定

图是反映对象之间关系的一种分析工具，节点、线段、方向是图的三要素。如果在图的每条线段e上都赋予一个非实数ω（e），则称G为一个赋权图，ω（e）称为线段e的权值，权值可以描述线段具有的特性。

1.1 节点

从单纯的数学对应关系上来说，一个负荷点或是一个线路交点都可以对应图中的一个节点，但实际情况是，配电网络中包含有不胜枚举的负荷、设备或线路交叉点，如果都将其独立视为节点将带来海量的计算与理论分析，势必使研究工作难以正常进行。根据相关要求，城市配电网应根据电压等级、负荷密度和运行管理的需要划分成若干个相对独立的分区配电网。各个分区以现状和规划的主要路网、水系等为界，区域范围内的负荷数量较为集中，负荷类型较为一致，理论上可以将众多的负荷看作是一个整体进而抽象为一个节点。因此拓扑图中的一个节点可以等效一个实际的配电分区。

1.2 线段

图论中的线段代表节点之间的联系，其长短曲直对拓扑结构分析不会造成影响。在配电网络拓扑结构中，线段并不是直接代表实际的输电线路，而代表的是可能架设主干线路的输电走廊。

1.3 权值

配电变电站选址和设计配电线路的问题，两者的分析方法不同，故在同一个拓扑图上，同一条线段会出现两个不同的权值ω1和ω2。

在进行负荷预测的前提下，配电变电站的合理选址需要综合考虑3个原则：等负荷原则A，初始投资最小化原则B，运行费用最小化原则C。原则A主要适用于年负荷变化量较小的场合。原则B主要考虑的是配电线路的架设问题，适用于铜芯导体消耗量大的场合。原则C适用于负荷的年最大计算负荷运行小时数相差很大的场合，运行费用制约着变电站运行的经济性。3种原则有各自的适用范围，彼此有普遍适用性，共同作用影响着变电站的选址：

λ1、λ2、λ3为权重系数，取值越大，说明优先考虑程度越高。ω1i就是配电网络拓扑图中第i条线段的权值。

在进行配电线路的规划中，ω2i是指第i条输电走廊架设输电线路的建设费用wc（主要包括线路材料费用和施工费用）和运行费用wo（主要是线路损耗）之和：

wc一般按照供电部门提供的单位工程造价计算而得，wo根据线损公式计算可得。

2 图论算法及算例

将变电站选址、设计配电线路问题转化为拓扑问题后求解，其实质是基于线段权值和点线连接关系构造矩阵，再利用一定的图论算法进行求解。当变电站节点与配电分区的节点合并时，合并节点与其他节点就构成了一种最短路关系，所以求解最短路径问题即可选择出最佳的变电站建设位置。赋权图中必然会包含赋权的树T，T中所有树枝的权值最小时，称树T为该图的最小生成树。设计最佳配电线路问题就属于最小生成树问题，配电线路相当于拓扑图中的最小树，既要连接所有配电分区（节点），又要最大程度保证运行经济性（权值之和最小）。本文根據如下算例，利用Dijkstra算法和Kruskal算法分别求解最短路径和最小生成树。

城镇某区域内有12个配电分区抽象等效为12个节点。各供电分区之间存在可能架设配电线路的输电走廊，等效为节点之间的14条线段。变电站选址和设计配电线路问题的赋权值图分别为图1和图2。

利用Matlab编程求解可得变电站选址问题计算结果为：

第i行的元素之和为：213，153，111，99，121，133，99，103，119，137，145，177。代表节点i到其他各节点最短路径之和。可以看出99为最小值，V4和V7到其他节点的最短路径和最小，故应选择v4或v7建设配电变电站。

设计配电线路问题的计算结果所构成的最小生成树见图3。

该最小生成树（图中较粗的线段）即为最佳配电线路的走向，输电走廊v2v3，v3v9，v8v11未得到利用。

综合以上两个问题结论，既变电站选址为v4或v7节点，设计的配电线路为：

v1v2—v2v6—v5v6—v3v4—v4v5—v4v7—v7v8—v10v11—v10v12—v9v10—v8v9。

参考文献

[1]乐乐.基于配电网自动化的网络拓扑分析[D].浙江大学，2008.

[2]苏建国，叶剑芳.城市配电网变电站选址优化[J].河南电力，2002，（3）：11-14.