联络型区域接线图的自动排布算法

梁 艳 董 昕 钟小泱 郑 鹏 陆 璐

（成都工业学院，四川 成都 611730）

0 引言

区域接线图是配电管理系统实时监控的重要图形依据。配电线之间的联络关系反应了供电情况，是供电运行、故障排除的重要依据。排布清晰、布局科学的联络型区域接线图为实现智能配网调度提供了可能。

区域接线图的自动排布研究主要集中于拓扑搜索优化和布图优化两方面。基于图论对配电网的电气设备数据进行建模，使用关联矩阵法和树搜索法来分析配电网的拓扑结构[1-2]，搜索性能良好。基于深度优先搜索算法，在构造拓扑结构时只考虑闭合的刀闸和开关，降低了算法复杂性并提高了搜索速度[3]。从外向内逐次布局的环形布局算法，可以支持少量联络开关的布局，对存在多个环的复杂线路则需进行手工调整[4]。基于模型驱动及层次结构的一次接线图生成方法，布局布线效果良好[5]。

已有研究解决了单条或多条独立配电线拓扑搜索的性能问题，布图美观，可以基本满足用户的需求。但是难以支撑具有各种联络关系的区域接线图的成图需求。联络型区域接线图，在拓扑检索和布图上构成环，大大增加了算法复杂性；多条配电线的联络关系往往显示不清晰，无法快速找到联络点；另外，联络点如果发生变化，快速重新布图并快速更新区域接线图的效率低，无法满足实时监控要求。

该文基于图论建模，以横平竖直算法为布图[6]策略，针对已有研究无法支撑联络型区域接线图的自动排布的现状，提出跨越联络开关进行拓扑搜索，对目标电气数据构建有向且有环的树，布图阶段先计算设备坐标、再走线，完成具有手拉手联络关系的区域接线图的排布。实验表明，该算法搜索性能良好，布图美观，多条配电线的联络关系一目了然，具有工程应用价值。

1 建立数据模型

对构成区域接线图的配电线上的设备和线路，建立基于CIM（公共信息模型）的数据模型[6]。该文重点讨论联络点处拓扑数据的搜索和建模策略。总体策略为依据搜索范围内的配电线的电气数据，建立线路的树结构：对于相互没有联系的线路，建立各自独立的有向树；有联络关系的多条线路，共同构建一棵树。具体如下。

建模规则1：一条配电线构成的区域接线图的搜索范围是以开闭所的出线开关或者变电站的配电线出线对应的节点为起点，向负荷侧沿线路搜索线路和设备的拓扑数据，直到线路末端，停止线路的搜索。在搜索过程中，如果遇到联络开关，则继续搜索到另一个变电站的配电线出线点（另一个变电站作为普通节点处理）。基于图论理论，一条配电线可建立一棵有一条1 级分支和若干条K 级分支（K ≥1）的有向树[6]。

建模规则2：N（N ≥1）条区域接线图的搜索，每条配电线的搜索遵照一条配电线的搜索规则，逐一搜索出N条配电线的线路和设备数据。对N 条区域接线图的搜索结果进行数据建模，如果N 条配电线中存在联络关系，则记手拉手构成联络关系的联络线路为M（1 ≦M ≦N）对。N 条配电线构成的区域接线图将依据线路彼此的联络关系建立N-M（N＞M）棵有向树；当N 条配电线两两互为联络关系，即N=M 时，N 条配电线建立一棵有向树。

2 联络型区域接线图的自动排布

自动排布算法包括搜索线路和设备、建立线路树结构、建立关键路径和排布4 个步骤。建立线路树是该算法的关键。

2.1 搜索线路和设备

依据建模规则搜索用户所选择的所有配电线的电气数据，即准备好排布所需要的线路和设备的电气数据。在搜索过程中，记录联络开关数据信息，以备生成具有多条联络关系的区域接线图使用。当所有需要生成区域接线图的线路全部搜索完毕，建立树结构。

2.2 建立线路树结构

以图论为基础，将搜索的设备（包括电源点、开关节点、T 节点、线路末梢点、联络开关等）作为点，线路作为有向边，建立有向且有环的树结构（该树的每个子节点可能有多个父节点，每个父节点也可能有多个子节点）。建立线路树结构的过程具体如下。

步骤1：从配电线的出线开始，在已经搜索出的线路和设备的电气数据上进行搜索。

步骤2：按照深度优先递归搜索，穿过联络开关，一直搜索至线路末端或另一个变电站出线节点为止。在搜索的过程中建立具有深度信息、父节点和子节点数据域，可双向搜索的树；同时，设置变电站配电线出线为已经建立树结构的标志；建立好的线路树，存入树表。

步骤3：重复步骤1 和2，完成所有线路树的构建。特别地，由于该树有向且有环，在搜索过程中构成环时做特殊处理。搜索过的每条路径上的节点存储在一个临时队列中，并且设置已访问标记。当再次访问到该队列中已经访问过的节点时，说明构成环，开始进行节点的回退操作，一直回退至可选择其他不构成环的路径为止。最终队列中的全部节点，加入树结构的父子节点关系队列中，此条路径搜索成功。

图1 电气数据搜索结果

2.3 建立关键路径

根据已经建立的树结构，标识树的分支级数和分支添加到排布图的顺序。首先标识1 级分支（每棵树只有一条0 级分支）第1 个参与排布；然后依据2 级分支的根节点在1 级分支中的节点顺序，逐个标识2 级分支的添加顺序；依次标识完所有分支的添加顺序。

2.4 排布

遍历已经建立的每棵树的关键路径，按照分支添加顺序，依次排布每一个分支、计算分支上各个节点坐标，最终形成不交叉、不重叠且横平竖直排布的区域接线图。具体流程如下。

步骤1：遍历第一棵树。按照分支的添加顺序，遍历每条分支上的设备，计算坐标。首先，遍历1 级分支，分支上的节点按照从父到子的顺序，依次计算每个设备的坐标；记录该分支上设备的最大T1（xmax，ymax）、最小T1（xmin，ymin）坐标值。然后，遍历第一个2 级分支，分支上的节点按照由父到子的顺序，依次计算每个设备的坐标；记录该分支上设备的最大T2（xmax，ymax）、最小T2（xmin，ymin）坐标值。此时，将此2 级分支与已经添加的1 分支进行交叉重叠判断，如果无交叉，则坐标计算成功；否则，从相交点开始，通过左右平移或上下平移的方式，修正所有相交设备的坐标[6]。

步骤2：同理，完成树的每条分支的坐标计算，记录整棵树的最大纵坐标Ytree1。

步骤3：遍历第N（N ≥2）棵树，参考第一棵树的最大纵坐标Ytree1，同上计算第N 棵树所有设备坐标。

步骤4：最后，依据画布大小，整体缩放区域接线图内的所有设备，保证图形全部显示在窗口内。

3 实例

3.1 搜索线路和设备

依据用户选择的区域接线图的配电线，搜索出每条配电线相关的线路、设备和拓扑数据。在此用户选择了3 条配电线路Fdr1、Fdr2、Fdr3，则搜索得到三条线路的电气数据，有1 条独立线路，2 条有联络关系的线路。每条配电线都是从变电站的出线开关开始向负荷侧搜索，直到线路末端停止。搜索结果如图1 所示，图中包括变电站SS1、SS2和SS3，站房设备S1和S2，1 个联络开关LSW，3 个黑色矩形表示的开关及若干个菱形悬挂设备。联络开关为配电线Fdr2 和Fdr3 的联络点。3 条配电线中的电气设备和线路构成联络型区域接线图的基础电气数据。

3.2 建立线路树

依据已经搜索得到的配电线的电气数据，建立树结构。由于3 条配电线中，Fdr1为独立的配电线，其对应的树为Tree1。Fdr2和Fdr3为有联络关系的配电线，共同建立一棵树，对应树Tree2，如图2 所示。设备树Tree2的构建过程中，从变电站SS2的出线开关开始搜索，跨越联络开关LSW，一直搜索至线路末端或变电站SS3的出线开关停止，所以，设备树Tree2由配电线Fdr2和Fdr3的电气设备共同组成，且共享联络开关LSW。

3.3 建立关键路径

依据已经建立的树结构，针对每一棵树，建立关键路径。依据树深度，搜索每条路径包括的结点，标识1 级分支、分级分支，直至标记完所有分支，并标记分支添加的顺序，以此作为分支计算坐标的顺序。Tree1包括一条1 级分支和3 条2 级分支，按照2 级分支的根节点在1 级分支中出现的顺序，识别3 条2 级分支。Tree2包括一条1 级分支和4 条2 级分支，按照2 级分支的根节点在1 级分支中出现的顺序，识别4 条2 级分支。

根据上一步建立的树结构，Tree1是由Fdr1建立的树，Tree2是由Fdr2和Fdr3共同建立的一棵树。在此对Tree1和Tree2建立关键路径，并标识分支等级及分支的添加顺序。自动布图效果的示意图，如图3 所示。

特别地，在做设备横平竖直化排布处理时，为了避免交叉，二级分支在排布时进行上下交错排布处理，在图例中，Tree1的第一条2 级分支2.1 自下向上排布，第二条2 级分支则自上而下排布。这样极大的减少了交叉的可能，节省了相交平移设备的坐标修正成本。

Tree2由2 条配电线构成，在设备树构建环节已经将两条线路融合。排布过程中，会将联络开关LSW 作为普通线路中的节点进行处理而不是作为线路末端。在实例情形中，联络开关作为1 级分支节点参与排布，为了能快速识别联络点，可在着色时高亮显示。变电站SS3，也作为普通站房节点参与排布，成为2 级分支的一部分。

3.4 应用分析

图3 构成了3 条配电线组成的联络型区域接线图，在实际工程应用中，联络开关的属性和开合状态有可能发生变化，增量更新显示范围，快速重新成图供工程监控人员使用，尤其重要。在该实例中，更改联络开关LSW 的状态为合且修改属性为普通开关，则配电线2 的搜索范围会增大。搜索算法快速搜索新范围的电气设备数据，然后在已有排布数据基础上，继续增量排布，在保留已有排布效果的同时大大提高了布图速度。

图2 设备树结构示意图

图3 自动布图效果

4 结语

通过实验验证，该文提出的算法兼容各种联络关系的区域接线图的自动布图，具有良好的适应性；对联络型线路的排布，联络点显示清晰，方便工程人员监控调度；联络关系发生变化时，基于已有拓扑数据基础，可以快速重新构建排布树，效率高。算法遵守横平竖直的排布原则，部分多联络架空线路的排布，有走线重叠的现象，需要手动调图，对于这种情况，有待进一步优化。另外，排布过程中对于分支的上下交错排布处理，虽然避免了相交的可能，但可能造成排布空间的浪费。