计算机应用 ›› 2016, Vol. 36 ›› Issue (9): 2540-2544.DOI: 10.11772/j.issn.1001-9081.2016.09.2540

• 人工智能 • 上一篇    下一篇

基于临界多边形的不规则件启发式排样算法

汤德佑, 周子琳   

  1. 华南理工大学 软件学院, 广州 510006
  • 收稿日期:2016-03-10 修回日期:2016-05-03 出版日期:2016-09-10 发布日期:2016-09-08
  • 通讯作者: 汤德佑
  • 作者简介:汤德佑(1976-),男,湖南浏阳人,副教授,博士,CCF会员,主要研究方向:并行计算、数据库;周子琳(1989-),女,海南海口人,硕士研究生,主要研究方向:排样算法。
  • 基金资助:
    广东省重大科技专项(2012A010701011);广州市科技计划项目(201200000034)。

No-fit-polygon-based heuristic nesting algorithm for irregular shapes

TANG Deyou, ZHOU Zilin   

  1. School of Software Engineering, South China University of Technology, Guangzhou Guangdong 510006, China
  • Received:2016-03-10 Revised:2016-05-03 Online:2016-09-10 Published:2016-09-08
  • Supported by:
    This work is partially supported by the Guangdong Science and Technology Major Project (2012A010701011);Guangzhou Science and Technology Project (201200000034).

摘要: 为提高不规则件启发式排样的材料利用率,提出一种基于重心临界多边形和边适应度的不规则件启发式排样算法GEFHNA。首先,定义了边适应度以衡量排样过程中原材料与不规则件间贴合程度,在此基础上给出了将边适应度与重心NFP(GNFP)相结合的排放策略以减少排样过程中可能产生的空隙面积;其次,给出了基于Weiler-Atherton多边形裁剪算法的剩余原材料求解方法,重用排样过程中产生的孔洞,减少孔洞面积;最后,给出了基于上述排样策略和材料重用策略的启发式排样算法GEFHNA,给出了与智能算法和同类软件的实验比较。对欧洲排样问题兴趣小组提供的基准测试用例的实验结果表明,GEFHNA的耗时约为基于智能算法的排样方法的千分之一,同时在与两款商业软件NestLib和SigmaNest的11个基准测试的对比中,GEFHNA获得了7/11个相对最优的排样面积利用率。

关键词: 二维不规则件, 排样, 临界多边形, 启发式方法

Abstract: To raise the material utilization ratio of heuristic nesting for irregular shapes, a Gravity No-Fit-Polygon (NFP) and Edge Fitness-based Heuristic Nesting Algorithm (GEFHNA) was proposed. Firstly, the definition of Edge Fitness (EF) to measure the fitness between the material and irregular shape produced in the process of packing was defined, and a packing strategy combining Gravity NFP (GNFP) with edge fitness was proposed to reduce the area of gap generated in packing. Secondly, a Weiler-Atherton-based algorithm was presented to compute remained materials and add holes produced in each round of packing to the list of materials. The heuristic packing algorithm prefered the holes in next rounds of packing to reduce proportion of holes in released layout. Finally, a heuristic algorithm based on the previous packing strategy and reuse strategy was put forward and the comparison experiments of GEFHNA with intelligent algorithm and similar softwares were presented. Experimental results on benchmarks provided by ESICUP (EURO Special Interest Group on Cutting and Packing) show that GEFHNA only has about 1/1000 time consumption of intelligent algorithm-based nesting scheme and achieves 7/11 relatively optimal utilization rate in contrast with two commercial softwares NestLib and SigmaNest.

Key words: two-dimensional irregular, packing, No-Fit-Polygon (NFP), heuristic method

中图分类号: