﻿ 输电网接线图增量自动成图算法
 计算机系统应用  2020, Vol. 29 Issue (5): 128-135 PDF

Automatic Drawing Algorithm for Incremental Transmission Grid Wiring Diagram
SHEN Zi-Hu, WU Shu-Wei, GE Yi-Xiao, ZHANG Shou-Tian
NARI Group Corporation Information & Communication Technology Co. Ltd., NARI Group Corporation (State Grid Electric Power Research Institute), Nanjing 210003, China
Abstract: The automatic mapping algorithm for the transmission line network wiring diagram is a very complex global optimization problem. It involves two aspects: the automatic layout of the plant site and the automatic planning of the transmission line. In this study, a specific idea and algorithm for solving this problem are given. The issue is divided into three parts: the first part uses the force-oriented algorithm to make the initial layout of the plant station position, and uses the simulated annealing algorithm to perform iterative calculation, which is realized by concurrent technology. The gravitational and repulsion coefficients are selected to obtain the initial layout of the initial plant with the least cost. In the second part, the A* algorithm is used to plan the transmission line, and a cost model of the line direction is constructed. The cost model is used to standardize the line and obtain a beautiful line layout. In the third part, the layout results are evaluated and feedbacked, and the common layout defects are eliminated through the program, which reduces manual intervention. At the same time, the study also processed the historical line and the newly added line, so that the algorithm can realize the layout planning of the newly added station line without changing the layout of the historical plant station. The experimental results show that the graphical results obtained by the method satisfy the advantages of beautiful line planning, reasonable layout, less crossover, and less corners.
Key words: force-oriented algorithm     A* algorithm     simulated annealing     incremental mapping     cost model

1) 厂站之间的相对空间的位置关系应该和实际的地理相对位置关系大致相似. 此目的是保证使用人员对输电网线路的位置上的使用习惯.

2) 整体布局均匀, 包括厂站和线路.

3) 厂站之间的连接线使用直线连接, 尽量采用横竖直线, 且拐点少.

4) 厂站线路的交叉尽可能少, 避免线路重合和拐点在线路上.

5) 主干线路(500 kV)以上的线路尽量布局在中心位置.

1 厂站网格布局 1.1 厂站网格布局的数学模型

 $S = W \cdot H$ (1)

 $k = \sqrt {\frac{S}{{\left| {{V}} \right|}}}$ (2)

 $d(u,v) = \sqrt {{{({u_x} - {v_x})}^2} + {{({u_y} - {v_y})}^2}}$ (3)

 ${f_a}(u,v) = \frac{{{{(d(u,v))}^2}}}{k} \cdot {F_1}$ (4)

 ${f_r}(u,v) = \frac{{{{(d(u,v))}^2}}}{k} \cdot {F_2}$ (5)

 ${T_{t + 1}} = \gamma \cdot {T_t}$ (6)

${T_t}$ 为当前时刻温度, ${T_{t{\rm{ + }}1}}$ 下一时刻温度, $\gamma$ 为冷却系数, 且一般为略小于1的正数.

1) ${\text{边长偏差}}{\rm{ = }}\dfrac{{{\text{最长边长}} - {\text{最短边长}}}}{{{\text{平均边长}} \times {\text{图的边数}}}}$

2) ${\text{点分布偏差}}{\rm{ = }}\dfrac{{\dfrac{{\text{图的显示面积}}}{{\text{节点个数}}} - {\text{最小节点距离}}}}{{\text{图的显示面积}}}$

3) ${\text{代价}} = \left( {{\text{边长偏差}} + {\text{点分布偏差}}} \right) \times {\text{线路交叉数}}$

1.2 厂站网格布局的算法实现

FR算法的核心步骤主要分为3个部分, 首先计算图中各点之间的斥力, 其次计算有边相连的节点之间的引力, 最后计算斥力和引力的合力来计算节点的移动位置. 然而, 每一次计算只能得到图的部分能量最小, 要得到全局的能量最小, 需要经过多次迭代才能够满足需求.

1.2.1 节点布局的伪代码

 图 1 节点布局算法伪代码

1.2.2 布点实验

 图 2 冷却系数γ取值在0.90~0.95的布点结果图

2 输电线路规划

2.1 目标

1) 线路交叉和拐点尽量少, 且拐点尽量不在线上;

2) 线路尽量横平竖直, 出线和入线为0°、30°、45°、60°和90°;

3) 线路之间重合线尽量少, 出线和入线重合除外;

4) 所有节点必须在网格点上.

2.2 代价函数模型

 ${t_i}{\rm{ = }}{t_{i - 1}} + \min ({\omega _1}{f_1} + {\omega _2}{f_2} + {\omega _3}{f_3} + {\omega _4}{f_4}) = \sum\limits_{k = 0}^i {{g_k}(x)}$ (7)

${t_{i{\rm{ - }}1}}$ 表示起点到当前节点的最小代价, 则 ${t_{\rm end}}$ 表示到从起点到终点的代价值, 其中 $\min ({\omega _1}{f_1} + {\omega _2}{f_2} + {\omega _3}{f_3} +$ ${\omega _4}{f_4})$ 为当前节点到下一节点的 $g(x)$ 最小代价. ${\omega _1}{\text{、}}{\omega _2}{\text{、}}$ ${\omega _3}{\text{、}}{\omega _4}$ 为权重系数, ${f_1}$ 为线路交叉函数; ${f_2}$ 为线路拐角函数; ${f_3}$ 为区域影响函数; ${f_4}$ 为路径长度函数.

 ${{T = }}\sum\limits_{i{\rm{ = }}0}^n {{t_{{\rm end}(i)}}}$ (8)

1) 线路交叉函数

 ${f_1}{\rm{ = }}{a_1}m + {b_1}n + {c_1}({b_1} > {a_1})$ (9)

2) 线路拐角函数

3) 区域影响函数

 ${f_3} = {a_3} \cdot F(P,E) + {b_3}F(Q,E) + {c_3},\;\;{a_3} > {b_3}$

 $F(P,Q){\rm{ = }}\left\{ {\begin{array}{*{20}{c}} 1,&\begin{gathered} \min ({x_p},{x_q}) \le x \le \max ({x_p},{x_q})\;{\rm or} \\ \min ({y_p},{y_q}) \le x \le \max ({y_p},{y_q}) \\ \end{gathered} \\ 0,&{{\rm{otherwise}}} \end{array}} \right.$ (12)

4) 路径长度函数

 图 3 区域影响函数示意图

 ${f_4}{\rm{ = }}{{{a}}_4} \cdot d$ (13)
2.3 路径规划算法

 $f(x) = h(x) + g(x)$ (14)

2.3.1 数据预处理

1) 线路去重

2) 线路排序

3) 剔除T接线

T接线是输电线路中比较特殊的情况, 它的一端直接连接到一条主干线路上. 而普通的线路时连接着两端厂站, 这种情况直接进行线路规划; 而对T接线则需要重新计算T接点的位置后在进行线路规划. 故需要对其剔除特殊处理.

2.3.2 路径规划算法描述

(1) 依次处理预先已排序的线路, 优先对高电压等级的线路进行布线. 设定电压门槛值, 若高于此值, 则出线方向为上下左右及各个方向的45度角等8个方向; 否则出线方向增加30度和60度等16个方向. 此为第一步出线.

(2) 使用A*算法实现从起点到终点的线路规划, 得到路径的中间拐点.

(1) 将重复的线路分组.

(2) 将每条线路的中间节点进行优化, 若连续的3个点在一条直线上, 则去除中间点. 此过程是减少线路中的多余节点. 若中间节点太多, 则加入反馈列表, 对厂站布局进行反馈.

(3) 对重复的线路按照某种特定的规则进行偏移. 本文实验中采用每两条线相隔4个单位.

(4) 最后输出线路及中间拐点.

2.4 路径规划算法样例

3 线路规划反馈厂站布局

 图 4 线路规划代价图

 图 5 线路规划反馈算法流程图

 图 6 反馈成图效果

4 增量厂站线路规划

1) 数据预处理

2) 厂站布局

3) 线路规划

 图 7 增量成图效果

5 评价及实验结果

 图 8 冷却系数γ取值在0.90~0.95的布线结果

6 结语

 [1] 沈伟, 吴文传, 张伯明, 等. 能量管理系统中电网潮流单线图自动生成算法. 电力系统自动化, 2010, 34(6): 48-53. [2] 徐本柱, 程光春, 李忠泽, 等. 基于力导向算法的线束连接图自动布局研究. 工程图学学报, 2010, 31(6): 171-177. [3] Delling D, Sanders P, Schultes D, et al. Engineering route planning algorithms. In: Lerner J, Wagner D, Zweig HA, eds. Algorithmics of Large and Complex Networks: Design, Analysis, and Simulation. Berlin, Heidelberg: Springer, 2009. 117–139. [4] Eades PA. A heuristic for graph drawing. Congressus Numerantium, 1984, 42: 149-160. [5] Fruchterman TMJ, Reingold EM. Graph drawing by force-directed placement. Software: Practice and Experience, 1991, 21(11): 1129-1164. DOI:10.1002/spe.4380211102 [6] Kamada T, Kawai S. An algorithm for drawing general undirected graphs. Information Processing Letters, 1989, 31(1): 7-15. DOI:10.1016/0020-0190(89)90102-6 [7] Sugiyama K, Misue K. A simple and unified method for drawing graphs: Magnetic-spring algorithm. Proceedings of DIMACS International Workshop Graph Drawing. New Jersey, NJ, USA. 1995. 364–375. [8] 李海峰. 图布局力导引算法的研究与实现[硕士学位论文]. 镇江: 江苏大学, 2012. 21–22. [9] Dijkstra EW. A note on two problems in connexion with graphs. Numerische Mathematik, 1959, 1(1): 269-271. DOI:10.1007/BF01386390 [10] Goldberg AV, Radzik T. A heuristic improvement of the Bellman-Ford algorithm. Applied Mathematics Letters, 1993, 6(3): 3-6. DOI:10.1016/0893-9659(93)90022-F [11] Fox GC, Holmes KC. An alternative method of solving the layer scaling equations of Hamilton, Rollett and Sparks. Acta Crystallographica, 1966, 20(6): 886-891. DOI:10.1107/S0365110X66002007 [12] 夏正冬, 卜天明, 张居阳. SPFA算法的分析及改进. 计算机科学, 2014, 41(6): 180-184, 213. DOI:10.11896/j.issn.1002-137X.2014.06.035 [13] 林田, 董云珠, 周正. 新型实用布线算法: L–M算法. 计算机辅助设计与图形学学报, 1994, 6(4): 302-306. [14] 史辉, 曹闻, 朱述龙, 等. A*算法的改进及其在路径规划中的应用. 测绘与空间地理信息, 2009, 32(6): 208-211. DOI:10.3969/j.issn.1672-5867.2009.06.070 [15] 魏征. 基于图统计特征的图像识别算法研究[硕士学位论文]. 合肥: 安徽大学, 2013. [16] 杨浩, 张二喜, 蒋卓芸. 基于距离测度的PCA人脸识别研究. 陕西理工学院学报(自然科学版), 2016, 32(4): 45-50.