摘要
为提高不规则件启发式排样的材料利用率,提出一种基于重心临界多边形和边适应度的不规则件启发式排样算法GEFHNA。首先,定义了边适应度以衡量排样过程中原材料与不规则件间贴合程度,在此基础上给出了将边适应度与重心NFP(GNFP)相结合的排放策略以减少排样过程中可能产生的空隙面积;其次,给出了基于WeilerAtherton多边形裁剪算法的剩余原材料求解方法,重用排样过程中产生的孔洞,减少孔洞面积;最后,给出了基于上述排样策略和材料重用策略的启发式排样算法GEFHNA,给出了与智能算法和同类软件的实验比较。对欧洲排样问题兴趣小组提供的基准测试用例的实验结果表明,GEFHNA的耗时约为基于智能算法的排样方法的千分之一,同时在与两款商业软件Nest Lib和Sigma Nest的11个基准测试的对比中,GEFHNA获得了7/11个相对最优的排样面积利用率。
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.
出处
《计算机应用》
CSCD
北大核心
2016年第9期2540-2544,共5页
journal of Computer Applications
基金
广东省重大科技专项(2012A010701011)
广州市科技计划项目(201200000034)~~
关键词
二维不规则件
排样
临界多边形
启发式方法
two-dimensional irregular
packing
No-Fit-Polygon （NFP）
heuristic method
