返回 科技论文 首页
基于启发式动态分解算法的矩形件优化排样

  文章编号:10019081(2013)07190804
  doi:10.11772/j.issn.10019081.2013.07.1908
  摘 要:
  针对二维矩形件优化排样问题,提出了一种启发式动态分解算法,其可扩展用于三维及多容器全局排样求解。根据排放矩形件对容器进行正交动态分解,计算放置耦合度选择最佳子容器,通过干涉关系实现所有容器状态更新,实现大规模复杂排样问题的快速高效求解。对国际上公认Benchmark多个问题例的计算结果表明,所提算法与同类算法相比优势明显,布局利用率提高达9.4%,计算效率提升达95.7%,并且已在商业化排样软件AutoCUT中应用,应用前景良好。
  关键词:矩形件排样;启发式;动态分解;优化
  中图分类号:TH301.06
  文献标志码:A
  英文标题
  Optimum packing of rectangles based on heuristic dynamic decomposition algorithm
  英文作者名
  LI Bo1*, WANG Shi2, SHI Songxin3, HU Junyong1
  英文地址(
  1. School of Mechanical and Automotive Engineering, Hubei University of Arts and Science, Xiangyang Hubei 441053, China;
  2. Ministry of Information Technology, DGHUST Manufacturing Engineering Institute, Dongguan Guangdong 523808, China;
  3. School of Mechanical Science and Engineering, Huazhong University of Science and Technology, Wuhan Hubei 430074, China英文摘要)
  Abstract:
  
  
  To solve the optimum packing of twodimensional rectangle layout problem, a heuristic dynamic decomposition algorithm was proposed, which can be used in the threedimensional rectangule layout and global optimization problems. The container was orthogonally decomposed according to the emission rectangles, and the best subcontainer was selected according to the degree of place coupling, then the state of all containers was updated by the interference relationship, so the largescale and complex problem can be solved quickly and efficiently. The experimental results of the Benchmark cases internationally recognized show that the proposed algorithm has better performance compared with similar algorithms, in which the layout utilization efficiency is increased by 9.4% and the calculating efficiency is improved up to 95.7%. Finally the algorithm has been applied to the commercialized packing software AutoCUT, and it has good application prospects.
  
  To solve the optimum packing of twodimensional rectangle problem, a heuristic dynamic decomposition algorithm was proposed, which can be used in the threedimensional rectangular layout and global optimization problems. The container was orthogonally decomposed according to the emission rectangle, and the best subcontainer was selected by the degree of place coupling, then the state of all containers was updated by the interference relationship, so the largescale and complex problem can be solved quickly and efficiently. The experimental results of the Benchmark cases internationally recognized show that the proposed algorithm has good performance compared with the similar algorithm, in which the layout utilization efficency is increased by up to 9.4% and the calculating efficiency is improved by up to 95.7%. Finally the algorithm has been applied to the commercialization of nesting software, and it has good application prospects.
  
  英文关键词Key words:
  rectanglepacking; heuristic; dynamic decomposition; optimization
  
  
  
  
  0 引言
  矩形件排样问题[1]是研究一组矩形物体如何在有限区域内互不重叠的布局优化问题,其研究成果应用于板材的切割、集装箱的货运、超大规模集成电路的布图、建筑装修的布局等中。该类问题直接影响到行业效率的提高,其研究具有广泛的实用价值,但该问题又被证明为一个NP难问题[2]。NP难问题精确求解的难度极大,特别是在规模较大的情况下,计算时间以万年为单位。因此,该类问题的快速求解吸引了国内外众多学者的研究。文献[3-12]中提出了多种求解二维矩形件排样问题的算法,如贪心算法、遗传算法、粒子群算法、启发式算法以及混合算法等;文献[13]提出了解决三维矩形件排样问题的拟人化算法,但上述研究成果的应用不具有普遍性,难以应用于其他场景矩形件排样问题的求解。


【相关论文推荐】
  • 基于蚁群算法的带平衡约束矩形布局问题的启发式求解
  • 矩形件排样算法探讨
  • 基于综合启发式算法的物流配送路径优化研究
  • 一种基于启发式约简的案例故障特征优化算法
  • 基于启发式算法的品牌模型的选择
  • 基于启发式包络算法钢板排料方法研究
  • 基于动态三角网格和启发式搜索算法路径规划研究
  • 适合“一刀切”剪切方式的矩形件排样算法
  • 敏捷供应链插单调度优化的启发式算法