改进禁忌搜索算法的线路规划算法优化设计

doi:10.11985/2021.03.018

改进禁忌搜索算法的线路规划算法优化设计

李杰^,, 金超未^,, 帕尔哈提·克衣木^,, 罗瑞雪^,

国网新疆电力有限公司信息通信公司乌鲁木齐 830000

Optimal Design of Route Planning Algorithm Based on Improved Tabu Search Algorithm

LI Jie^,, JIN Chaowei^,, PAERHATI Keyimu^,, LUO Ruixue^,

State Grid Xinjiang Information and Telecommunication Company, Urumqi 830000

收稿日期: 2020-09-15 修回日期: 2021-03-21

Received: 2020-09-15 Revised: 2021-03-21

作者简介 About authors

李杰,男,1978年生,硕士。主要研究方向为电力光纤通信、电力资源共享平台等。E-mail： emrwrunpa@21cn.com

金超未,男,1993年生。主要研究方向为电力通信工程、电力光纤通信等。E-mail： em46777npa@21cn.com

帕尔哈提·克衣木,男,1992年生。主要研究方向为电力通信工程、电力光纤通信等。E-mail： em5677899pa@21cn.com

罗瑞雪,女,1994年生。主要研究方向为电力光纤通信、电力资源共享平台等。E-mail： rwru467888npa@21cn.com

摘要

针对传统输电线路规划效率慢、成本高等问题,结合禁忌搜索算法,根据地理信息因素将规划区划分为不同的单元格,设置邻域函数进行线路搜索得到规划路径。由于输电线路信息数据规模大,算法的效率受到大幅度影响,拐点也会增多,因此对算法进行改造,采用跨越式邻域和双向搜索提高算法的效率,引入方向因子来确保线路能够合并,采用拐点处理机制来减少拐点和迂回的数量,减少了杆塔的使用。以变电站A到变电站B之间的输电线路对算法进行仿真,试验表明,改进后的算法相比之前的算法效率提高了近一倍,成本减少了大约220万元。

关键词： 线路规划 ; 禁忌搜索算法 ; 跨越式邻域 ; 双向搜索 ; 拐点处理

Abstract

In view of the slow efficiency and high cost of traditional transmission line planning, the tabu search algorithm is combined by the author to divide the planning area into different cells according to geographic information factors, and the neighborhood function is set to search for the route to obtain the planned route. Due to the large scale of transmission line information data, the efficiency of the algorithm is greatly affected, and the inflection point would increase. Therefore, the algorithm is modified, and the efficiency of the algorithm is improved by using leapfrogging neighborhood and two-way search. Directional factors are introduced to ensure that the lines could be merged. Inflection point processing mechanism to reduce the number of inflection points and detours, thereby the use of poles and towers is reduced. The algorithm is simulated with the transmission line from substation A to substation B. Tests show that the improved algorithm had nearly doubled the efficiency of the previous algorithm and the cost is reduced by approximately 2.2 million RMB.

Keywords： Route planning ; tabu search algorithm ; spanning neighborhood ; two-way search ; turning point processing

PDF (4879KB) 元数据多维度评价相关文章导出 EndNote| Ris| Bibtex 收藏本文

本文引用格式

李杰, 金超未, 帕尔哈提·克衣木, 罗瑞雪. 改进禁忌搜索算法的线路规划算法优化设计. 电气工程学报[J], 2021, 16(3): 130-136 doi:10.11985/2021.03.018

LI Jie, JIN Chaowei, PAERHATI Keyimu, LUO Ruixue. Optimal Design of Route Planning Algorithm Based on Improved Tabu Search Algorithm. Journal of Electrical Engineering[J], 2021, 16(3): 130-136 doi:10.11985/2021.03.018

1 引言

传统的输电线路规划是根据地理图纸规划大致的方案,然后进行实地考察来确定最终的方案。这种方法主要依靠设计人员的经验,但是由于地图数据需要人为进行更新,造成了数据更新不及时,会导致设计人员判断错误,同时输电线路的影响因素很多,导致工作强度大、时间久,从而影响到输电线路规划的进度。随着国家大力推进智能电网设计,地理信息系统(Geographic information system,GIS)和计算机系统被广泛地应用到电力系统中,给输电线路规划提供了新的思路,文献[1]中对10 kV配网的输电线路规划需要注意的问题进行了说明,但是没有解决人工规划效率慢的问题。文献[2]中提出一种优化算法,根据设置禁忌条件来求解最优路径,但是由于线路规划数据规模大,算法耗时太长。

基于以上内容,对输电线路的路径选择算法进行优化,采用禁忌搜索算法建立最优线路求解模型,根据规划区内的地理信息因素对规划区进行单元格划分和成本预算,得到一个成本最优、建设难度最小的线路。并针对搜索时间过长和拐点过多等缺陷,提出跨越式邻域和双向搜索方法来缩短算法的计算次数,采用拐点处理机制来减少拐点数量。

2 输电线路优化

2.1 输电线路概念

发电厂发出的电传输到用户需要建设大规模的线路,这部分线路都可以称作输电线路^[3]。发电厂的电经过变压站升压输送到高压输电网,再经过降压和配电才能到达用户家里进行使用,所以输电线路可以分为配电线路和送电线路。通常,配电线路电压小于10 kV,其中低压配电线路电压为1 kV以下,高压配电线路电压为1~10 kV;送电线路电压为35 kV及以上,其中高压送电线路电压为35~220 kV,超高压送电线路电压为330~500 kV^[4]。

2.2 输电线路设计需要注意的因素

输电线路在设计规划时要注意地理位置因素,主要有以下几个方面^[5]。

(1) 避让区域。输电线路在设计时要注意避开军事管理区、自然保护区以及一些易燃易爆的厂房和仓库。

(2) 自然环境。尽量选择空旷的平地进行建设,注意自然生态环境,减少树木的砍伐。

(3) 由于高压线路会产生电磁感应,对人和动物会造成一定的伤害,所以在建造过程中要远离建筑物和人群。

(4) 设计过程中要尽量避开坡度较大的地方,选择坡度小于30°的地方建造杆塔,同时在设计时对原有线路进行改造和升级,不仅可以减少建设时间,还能节约一定成本。

2.3 输电线路优化的目标

输电线路优化的目标是在满足用户用电需求、符合行业标准、保证供电安全稳定性的前提下,在输电线路的起点和终点之间规划出一条成本最低的线路,同时要考虑建设的复杂程度、行业的发展,还要注意保护好自然环境,避免大面积破坏和重建^[6]。

3 线路规划算法模型

3.1 划分单元格

输电线路规划中单元格可以划分为两大类,不可跨越地区(A)和可跨越地区(B),对于可跨越地区,要综合考虑该地区的各种因素来确定成本,采用模糊层次分析法建立分析模型来确定单元格的成本^[7]。

根据地理信息因素对成本的影响,可以引入评分系统对影响可跨越地区成本的因素进行评分,根据以往的经验评分结果如表1所示。

表1 因素评分

评分	成本	建设难易程度
1	很低	很小
2	较低	较小
3	一般	一般
4	较高	较大
5	很高	很大

新窗口打开| 下载CSV

对地理信息层次进行划分,如图1所示。

图1

新窗口打开| 下载原图ZIP| 生成PPT

图1 地理信息层次

主要划分为三层,第一层为目标层代表单元格的成本值,第二层为准则层,由导线成本、基础设施成本、杆塔成本和施工成本组成,成本根据天气和地理因素的变化会有所不同。第三层为第二准层层,影响着准则层,并且影响程度不同^[8]。

采用评分矩阵来计算单元格的成本值^[9]

(1)${X_i}_j = {({x_{ij}})_{n \times m}} = \left\{ {\begin{array}{*{20}{c}}{{x_{11}}}&{{x_{12}}}& \cdots &{{x_{1m}}}\\{{x_{21}}}&{{x_{22}}}& \cdots &{{x_{2m}}}\\ \vdots & \vdots &{}& \vdots \\{{x_{n1}}}&{{x_{n2}}}& \cdots &{{x_{nm}}}\end{array}} \right\}$

式中,${x_{ij}}$为n×m矩阵,表示第$i$个单元格的第$j$个地理影响因素的评分,矩阵的大小根据单元格的和影响因素数量来决定,m为地理影响因素数量,$n$为单元格的数量。

由于评分没有标准,无法进行有意义的评分,采用比较矩阵来解决问题^[10],即两个地理影响因素相互对比,将地理因素两两对比,可得

(2)$A = {({a_{ij}})_{n \times n}} = \left\{ {\begin{array}{*{20}{c}}{{a_{11}}}&{{a_{12}}}& \cdots &{{a_{1n}}}\\{{a_{21}}}&{{a_{22}}}& \cdots &{{a_{2n}}}\\ \vdots & \vdots &{}& \vdots \\{{a_{n1}}}&{{a_{n2}}}& \cdots &{{a_{nn}}}\end{array}} \right\}$

式中,${a_{ij}}$为$n \times n$矩阵,表示第$i$个地理影响因素对$j$个地理影响因素的影响程度,采用表1的数据来表示比较结果。

对矩阵A的行元素求和,得到模糊一致矩阵^[11]

(3)${\alpha _i} = \sum\limits_{k = 1}^n {{\alpha _{ik}}\;\;\;\;\;i = 1,2, \cdots,n}$

对式(3)进行改造^[12]得到

(4)${\alpha _i}{_j^\prime } = \frac{{({\alpha _i} - {\alpha _j})}}{{2n}} + 0.5$

最终得到的模糊一致矩阵为

(5)$A' = {({\alpha _i}{_j^\prime })_{n \times n}}\;\;\;\;\;i = 1,2, \cdots,n\;\;\;\;\;j = 1,2, \cdots,n$

单元格的成本的组成部分很多,所以要对每个部分的权重进行划分,权重的计算公式为^[13]

(6)$w = {({\omega _1},{\omega _2}, \cdots,{\omega _n})^{\text{T}}}$

对图1的三个层次求解,可以得到综合权重

(7)$W = {\omega _1} + {\omega _2}$

式中,W为综合权重,${\omega _1}$为第二层和第三层之间的权重向量,${\omega _2}$为第一层和第二层之间的权重向量。

根据以上内容,可以求得单元格的地理信息评分向量为

(8)$M = {X_i}_j \times W$

采用GIS和RS技术来进行地理信息的采集和处理^[14],分为A、B两类单元格。通过上述计算能够获得单元格建设的成本值,再加上单元格的位置信息,得到如表2所示的单元格属性表。

表2 单元格属性

名称	定义
单元格位置(x, y)	在单元格的位置
单元格类型A、B	单元格划分
单元格成本值C	跨越这个单元格成本

新窗口打开| 下载CSV

3.2 线路规划模型

采用禁忌搜索算法来建立输电线路规划模型,禁忌搜索线路优化算法中最常用的一种人工智能算法,能够模仿人类的记忆功能,被广泛运用到线路规划中^[15]。算法流程如下所示。

(1) 初始化设置。禁忌表T设置为空,设定算法的参数和初始解n,这里采用随机产生的方式^[16]。

(2) 判断初始解。因为初始解是随机产生的,具有不确定性,所以要对其进行判断,满足条件则输出结果,不满足则进行下一步。

(3) 确定候选解。由于初始解不满足设定的条件,所以要进行计算来确定候选结果,即计算当前解的邻域范围内满足设定要求的解的集合。

(4) 判断候选解。根据设定的特赦条件来判断候选解是否满足对应的条件,若满足,则用候选解集合里的最优解来代替当前解作为新的当前解,并替换禁忌表内容。然后转至第二步,若不满足,则进行下一步。

(5) 选择候选解。即选择候选解集中的最优解来替换当前解,并替换禁忌表内容。

(6) 继续执行第(2)步。

4 线路规划算法改进

根据划分的单元格,采用上述模型能够从确定好的起点和终点得到一条满足条件的最优输电线路。但是由于输电线路的影响因素过多,算法的时间会大幅度增加,就失去了算法效率高的特点。因此,需要对上述得到模型进行改进和完善,主要有以下几种方式^[17]。

(1) 跨域式邻域。在上述算法中,在利用邻域函数求解邻域范围内的解的集合时,选择的是以当前位置为中心的8个单元格^[18],如图2所示。

图2

新窗口打开| 下载原图ZIP| 生成PPT

图2 改进前的邻域选择

这种方式一般用来处理少量数据,随着数据规模的变大,这种方式的处理速度也会变慢,因此引入跨越式邻域来解决处理速度慢的问题,改进后的邻域选择如图3所示。

图3

新窗口打开| 下载原图ZIP| 生成PPT

图3 改进后的邻域选择

改进之后的邻域选择机制能够缩短数据的计算次数,通过图3中阴影部分的面积,可以看到,改进后的邻域选择范围更宽,使得需要计算的区域增加,相应的计算量也应增加,采用固定的跨越式邻域可能会出现没有最优解的情况,这时可以考虑缩小或者增大跨越距离^[19]。

(2) 双向搜索。为了解决算法运算时间多长问题,采用起点和终点同时开始搜索的方式来缩短算法的运算时间,这种方式可能会出现无法相遇的情况,为此引入方向引导因子^[20,21],如图4所示。

图4

新窗口打开| 下载原图ZIP| 生成PPT

图4 方向引导因子

其中,线段1为当前位置与终点的连线,线段2为当前位置与相邻单元格A的连线,线段3为当前位置与相邻单元格B的连线。θ₁表示线段1和线段2的夹角,θ₂表示线段1和线段3的夹角。

令方向控制因子为$f$,则有

(9)$f = \cos \theta$

如果方向因子f越大,则表示θ₁,θ₂越小,即移动的方向越接近终点,当禁忌表在搜索后逐渐增加时,会出现搜索范围集中在目标范围同一侧的情况,因此,引入方向因子限制系数$\eta$,$\eta \in (0,\;1)$,则有

(10)$f' = \frac{{f(1 - \eta )}}{m}$

式中,$m$为迭代次数。

(3) 拐角处理。在输电线路建设中,如果拐点过多,就会建设大量杆塔和基础设施,造成成本的大幅增长。在搜索时,会出现如图5所示的情况。

图5

新窗口打开| 下载原图ZIP| 生成PPT

图5 搜索示意图

图5中阴影部分为不可跨越区域,假设从A点到E点需要规划输电线路,经过算法的搜索规划出了A→B→C→D→E方案,但是这样拐点过多会造成成本的大幅度增加,为此引入拐点处理机制,比较AB和BC的斜率。如果斜率不同,表示三点未在同一直线上,此时可以判断AC是否处于不可跨越区域,否则比较AC和AB+BC的成本选择较小的成本线路。经过改进和完善后的算法最终流程图如图6所示。

图6

新窗口打开| 下载原图ZIP| 生成PPT

图6 改进算法流程

与之前的算法相比,改进后的算法的因为采用了跨越式邻域和同时从起点终点出发,缩短了数据处理速度,同时引进拐点处理机会,让最终的线路成本更小。

5 试验仿真

采用基于Visual C#2010和ArcGis10.0开发的软件平台对上述算法进行仿真,其中硬件环境为interi5-9700h,运行内存16 G,硬盘大小5 T。以变电站A到变电站B为例,在该区域进行路径搜索。

采用ArcGis软件对规划区内的地理位置信息进行处理,采用上述分类,补充了风速、地形、冰覆盖等因素,对规划区进行单元格划分,划分结果如图7所示。

图7

新窗口打开| 下载原图ZIP| 生成PPT

图7 单元格划分

图7中,A、B是两个变电站,要在其中间建设输电线路,将规划区域划分为$m \times n$的单元格,采用上述的成本计算方式来计算每个单元格的成本值,由于单元格数量较多,截取一部分,得到如图8所示的单元格成本图。

图8

新窗口打开| 下载原图ZIP| 生成PPT

图8 单元格成本

图8中的数字字母,第一行表示单元格序号,第二行表示单元格成本,第三行字母表示变电站,只有一行数字的表示不可跨越地区,数字表示单元格序号。

采用Matlab仿真软件对上述的搜索禁忌算法和改进算法分别进行路径搜索,仿真搜索结果如下。

(1) 基本算法结果：103→90→77→78→65→80→67→54→55→41→42→28→29→15。

(2) 改进算法结果：103→91→66→30→15。

对两种算法的路径拐点、成本值、所需时间进行计算,将得到的数据进行整理得到表 3 的数据对比。

从表3数据可以看出,改进禁忌搜索算法的拐点数和迂回数减少,得到的规划线路也更合理,同时也减少了杆塔的使用,降低了成本,另外改进算法在搜索时间上也要比之前的算法更短,从而体现了计算机算法的优势。

表3 算法对比

名称	禁忌搜索算法	改进禁忌搜索算法
拐点数	12	3
迂回数	1	0
成本值/万元	1 758.581	1 526.325
时间/s	112	55

新窗口打开| 下载CSV

在检验所提拐角处理机制的有效性时,通过设置不同的拐点数,将利用拐角处理机制和未利用拐角处理机制进行对比分析,则正确率如图9所示。

图9

新窗口打开| 下载原图ZIP| 生成PPT

图9 拐角处理机制对比示意图

在进行对比试验时,采用拐角处理机制和未采用拐角处理机制分别进行对比分析,未采用拐角处理机制也即是通过常规人工作业的方式,比如采用目测方式,在90 s的时间内,发现本研究方法比传统技术的方法准确率高。

6 结论

针对已有的禁忌搜索算法的不足,对其进行相应的改进,并得出以下结论。

(1) 起点和终点同时进行搜索可以减少算法的搜索时间,但是要引入方向因子来确保能够合并。

(2) 跨越式确定邻域也能减少算法的搜索时间,但是需要注意跨越距离要随着邻域函数结果进行改变。

(3) 拐点处理机制能够减少路线的拐点数量和迂回数量,使得路线规划更加合理,同时减少了杆塔的使用,降低了成本。

利用实验室设备对算法进行了仿真验证,验证结果表明了改进算法的有效性,具有良好的应用前景,但是由于处于实验室环境,数据规模较小,研究还需要进一步的改进和完善。

参考文献

原文顺序

文献年度倒序

文中引用次数倒序

被引期刊影响因子

[1]

黄汉杰

10 kV配网输电线路的规划设计方案

[J]. 通信电源技术, 2019, 36(10):128-129.