查询结果:   梁涛,李卫东,徐爱东.考虑容量约束的电缆敷设变邻域搜索优化算法[J].计算机应用与软件,2016,33(6):291 - 293.
中文标题
考虑容量约束的电缆敷设变邻域搜索优化算法
发表栏目
算法
摘要点击数
724
英文标题
A VARIABLE NEIGHBOURHOOD SEARCH ALGORITHM FOR CABLE LAYOUT PROBLEMS WITH CAPACITY CONSTRAINTS
作 者
梁涛 李卫东 徐爱东 Liang Tao Li Weidong Xu Aidong
作者单位
山东电力工程咨询院有限公司 山东 济南 250013 华能西宁热电有限责任公司 青海 西宁 810000    
英文单位
Shandong Electric Power Engineering Consulting Institute Co., Ltd., Jinan 250013,Shandong,China Huaneng Xining Thermal Power Co., Ltd., Xining 810000,Qinghai,China    
关键词
电缆敷设 变邻域搜索 优化算法
Keywords
Cable layout Variable neighbourhood search Optimisation algorithm
基金项目
作者资料
梁涛,工程师,主研领域:复杂系统建模与优化,电力系统运行与控制技术。李卫东,高工。徐爱东,教授级高工。 。
文章摘要
针对一类考虑容量约束的电缆敷设优化问题,提出一种新的变邻域搜索优化算法。首先,分析电缆敷设问题的优化要求,基于图论给出具有容量约束的电缆敷设优化问题的数学描述;然后,结合问题特征提出基于Dijkstra算法的初始解生成策略,构建依据解间距离的邻域结构和局部启发式搜索策略,在此基础上给出电缆敷设变邻域搜索优化算法;最后通过实例求解结果表明,该算法能在短时间内获得问题的最优解或近优解,验证了算法的有效性和优越性。
Abstract
We presented a new optimised variable neighbourhood search algorithm for a kind of cable layout optimisation problem with capacity constraints. First, we analysed the optimisation demands of cable layout problems, and presented based on graph theory the mathematical description of cable layout optimisation problem with capacity constraints. Then in combination with the problem features, we introduced an initial solution generation strategy using Dijkstra algorithm, and built up a solution-distance-based neighbourhood structure and a local heuristic search strategy. On this basis, we proposed the optimised variable neighbourhood search algorithm for cable layout. Finally, it was demonstrated through the example of solving results that the presented algorithm could obtain optimal solutions or near-optimal solutions in a short time, which verified the effectiveness and superiority of the algorithm.
下载PDF全文