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

doi:10.11985/2021.03.018

摘要/Abstract

摘要：

针对传统输电线路规划效率慢、成本高等问题,结合禁忌搜索算法,根据地理信息因素将规划区划分为不同的单元格,设置邻域函数进行线路搜索得到规划路径。由于输电线路信息数据规模大,算法的效率受到大幅度影响,拐点也会增多,因此对算法进行改造,采用跨越式邻域和双向搜索提高算法的效率,引入方向因子来确保线路能够合并,采用拐点处理机制来减少拐点和迂回的数量,减少了杆塔的使用。以变电站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.

Key words: Route planning, tabu search algorithm, spanning neighborhood, two-way search, turning point processing

中图分类号:

TM92

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

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

图/表 12

表1

图1

表2

图2

图3

图4

图5

图6

图7

图8

表3

图9

参考文献 21

[1]	黄汉杰. 10 kV配网输电线路的规划设计方案[J]. 通信电源技术, 2019, 36(10):128-129.
	HUANG Hanjie. Planning and design scheme of 10 kV distribution network transmission line[J]. Communication Power Technology, 2019, 36(10):128-129.
[2]	张强, 黄璜, 陈跃哲. 基于优化算法的输电线路路径研究[J]. 东北电力技术, 2020, 41(1):38-41.
	ZHANG Qiang, HUANG Huang, CHEN Yuezhe. Research on transmission line path based on optimization algorithm[J]. Northeast Electric Power Technology, 2020, 41(1):38-41.
[3]	秦珂巍. 山区110 kV架空输电线路设计规划的研究[J]. 中国新通信, 2020, 22(9):141-142.
	QIN Kewei. Research on the design and planning of 110 kV overhead transmission lines in mountainous areas[J]. China New Telecommunications, 2020, 22(9):141-142.
[4]	姚慧芳, 李勇, 谭益, 等. 考虑电量外送的多电压等级电网分布式电源优化配置方法[J]. 电力系统保护与控制, 2019, 47(19):54-62.
	YAO Huifang, LI Yong, TAN Yi, et al. Optimal configuration method of multi-voltage grid distributed power generation considering power transmission[J]. Power System Protection and Control, 2019, 47(19):54-62.
[5]	刘畅. 输电线路经济寿命评估及其在电网规划中的应用[J]. 中国市场, 2017(36):57-58.
	LIU Chang. Evaluation of the economic life of transmission lines and its application in power grid planning[J]. China Market, 2017(36):57-58.
[6]	黄志庆. 220 kV架空输电线路规划设计要点[J]. 农村电气化, 2020(9):22-24.
	HUANG Zhiqing. Essentials of 220 kV overhead transmission line planning and design[J]. Rural Electrification, 2020(9):22-24.
[7]	谢景海, 苏东禹, 卢诗华, 等. 基于改进蚁群算法的输电线路路径规划关键技术[J]. 电测与仪表, 2020, 57(4):122-128.
	XIE Jinghai, SU Dongyu, LU Shihua, et al. Key technology of transmission line path planning based on improved ant colony algorithm[J]. Electrical Measurement & Instrumentation, 2020, 57(4):122-128.
[8]	姜冬, 刘鲲鹏. 主动配电网双层实时优化博弈研究[J]. 电测与仪表, 2018, 55(18):50-56.
	JIANG Dong, LIU Kunpeng. Research on two-layer real-time optimization game of active distribution network[J]. Electrical Measurement & Instrumentation, 2018, 55(18):50-56.
[9]	苏海锋, 杨阔, 梁志瑞. 基于改进蚁群算法的输电线路路径自动选择[J]. 电力自动化设备, 2018, 38(1):87-92.
	SU Haifeng, YANG Kuo, LIANG Zhirui. Automatic selection of transmission line path based on improved ant colony algorithm[J]. Electric Power Automation Equipment, 2018, 38(1):87-92.
[10]	NAHMAN J, SALAMON D. Mutual interference of neighboring grounding systems and approximate formulation[J]. Electric Power Systems Research, 2017, 151:166-173. doi: 10.1016/j.epsr.2017.05.029
[11]	HOU Kaiyuan, SHAO Guanghui, WANG Haiming, et al. Research on practical power system stability analysis algorithm based on modified SVM[J]. Protection and Control of Modern Power Systems, 2018, 3(1):1-7. doi: 10.1186/s41601-017-0075-8
[12]	周鹏程. 基于层次分析评价线路输电路径优化设计应用研究[J]. 电气技术与经济, 2018(5):50-52.
	ZHOU Pengcheng. Research on the application of analytic hierarchy process to evaluate the optimal design of transmission routes[J]. Electrical Technology and Economy, 2018(5):50-52.
[13]	刘凯, 陈才学, 文军. 基于固态变压器直流侧电压平衡控制的SVPWM算法[J]. 电气工程学报, 2018, 13(2):29-35.
	LIU Kai, CHEN Caixue, WEN Jun. SVPWM algorithm based on DC side voltage balance control of solid-state transformer[J]. Journal of Electrical Engineering, 2018, 13(2):29-35.
[14]	刘婷婷, 高尚. 基于A*初始解的禁忌搜索算法优化及仿真应用[J]. 计算机与数字工程, 2020, 48(7):1568-1571.
	LIU Tingting, GAO Shang. Tabu search algorithm optimization and simulation application based on A* initial solution[J]. Computer and Digital Engineering, 2020, 48(7):1568-1571.
[15]	胡勋, 陶群, 万媛, 等. 一种检测室内侧装悬架式高压大电流隔离开关[J]. 电气工程学报, 2018, 13(10):35-40.
	HU Xun, TAO Qun, WAN Yuan, et al. A side-mounted suspension type high-voltage high-current isolating switch in the detection room[J]. Journal of Electrical Engineering, 2018, 13(10):35-40.
[16]	冯倩倩. 基于智能优化算法的输电线路路径优化问题的研究[D]. 济南:山东师范大学, 2016.
	FENG Qianqian. Research on transmission line path optimization problem based on intelligent optimization algorithm[D]. Jinan:Shandong Normal University, 2016.
[17]	苏海锋, 许道林, 李汶江, 等. 基于改进蚁群A*算法的输电线路路径搜索[J]. 河北大学学报, 2017, 37(1):92-100.
	SU Haifeng, XU Daolin, LI Wenjiang, et al. Transmission line path search based on improved ant colony A* algorithm[J]. Journal of Hebei University, 2017, 37(1):92-100.
[18]	王庆斌, 石亮缘, 黄辉, 等. 基于改进粒子群算法的输电线路路径规划研究[J]. 广东电力, 2018, 31(9):135-141.
	WANG Qingbin, SHI Liangyuan, HUANG Hui, et al. Research on transmission line path planning based on improved particle swarm algorithm[J]. Guangdong Electric Power, 2018, 31(9):135-141.
[19]	李程, 徐天奇, 李琰. 恒、变磁通共铁心的自耦变压器的研制[J]. 电气工程学报, 2018, 13(3):34-41.
	LI Cheng, XU Tianqi, LI Yan. Development of a common core autotransformer with constant and variable magnetic flux[J]. Journal of Electrical Engineering, 2018, 13(3):34-41.
[20]	孟遂民, 刘闯, 卢银均, 等. 输电网规划全寿命周期综合成本计算研究[J]. 三峡大学学报, 2017, 39(5):84-89.
	MENG Suimin, LIU Chuang, LU Yinjun, et al. Research on comprehensive life cycle cost calculation of transmission network planning[J]. Journal of China Three Gorges University, 2017, 39(5):84-89.
[21]	李忠华. 非线性绝缘电介质介电特性表征与测试[J]. 电气工程学报, 2018, 13(11):11-20.
	LI Zhonghua. Characterization and testing of dielectric characteristics of nonlinear insulating dielectrics[J]. Journal of Electrical Engineering, 2018, 13(11):11-20.

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

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

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