计算电缆优化分割问题的全局启发-两层求解算法  

A Global Heuristic and Two-Tier Algorithm to Solve Power Cable Optimal Cutting Problem

作　　者：花新乐[1] 张骞[1] 付文杰[1] 张旭东[1] 王石[1] 王清亮[1] 栗军[1] 

机构地区：[1]河北省电力公司,河北省石家庄市050021

出　　处：《电网技术》2012年第6期238-243,共6页Power System Technology

基　　金：国家863高技术基金项目(2011AA040506)~~

摘　　要：针对电力电缆优化分割下料问题,提出了全局启发两层求解算法。算法定义了电缆的全局启发价值并先进行计算,然后基于剪枝回溯算法递归求解0-N背包问题,从而获得既有较高局部价值又有较高全局价值的分割方式,最后通过多级贪心策略逐步启发得到问题的全局优化分割方案。基于该算法研制的电缆优化分割计算平台,求解结果既可精确满足电缆需求,又达到余料高度集中的效果,不需调整就可直接应用。实践应用和算例比较表明,该算法计算速度快,求解质量高,通常情况下能够获得理想最优解。A global heuristic two-tier algorithm to the problem of power cable optimal cutting is solve proposed. Firstly the global heuristic values of power cables are defin by this algorithm and calculates them; then based on pruned backtracking algorithm the O-N knapsack problem recursively solved to attain a power cable cutting mode with both higher local and global values; finally, through step-by-step elicitation of multipole greedy strategy the global solution of the problem is achieved. Based on the proposed algorithm a calculation platform for power cable optimal cutting is developed and the solutions of this platform can meet the requirement of cable cutting accurately and original scattered short oddments of power cables after traditional cutting can be highly centralized to a single cable as a whole, besides, needing not adjustment, the developed calculation platform can be directly applied. Both results from actual application and calculation examples show that the proposed algorithm possesses the advantages of high computing speed, satisfied solution quality, and under normal circumstances ideal optimal solution can be obtained, thus the proposed algorithm is significant to the saving of the usage amount of power cable and the reduction of the cost of power construction. The proposed algorithm is available to the cutting of common wire rods.

关 键 词：电缆优化分割 全局启发两层算法 余料集中 云计算平台 最优解 

分 类 号：TM72[电气工程—电力系统及自动化]