基于摇瓶策略求解二维不规则件排样问题  

2-D irregular polygon nesting with shaking bottle strategy

作　　者：罗立宏[1,2] 冯开平[2] 叶家玮[2] 

机构地区：[1]广东工业大学数字媒体系,广东广州510006 [2]华南理工大学土木与交通学院,广东广州510641

出　　处：《南京理工大学学报》2015年第2期194-201,共8页Journal of Nanjing University of Science and Technology

基　　金：国家自然科学基金(50575046)

摘　　要：针对基于序列的二维排样问题求解策略的不足,提出采用"摇晃瓶子"的策略求解二维不规则件排样问题。基于图像和颜色直方图方法实现零件的重叠检测、出界检测和方案评价。对模拟退火提出两种改进措施:动态邻域尺度方法和并行退火方法。动态邻域尺度方法可使模拟退火用于摇瓶策略,解决了采用离散方法检测零件重叠时精度和时间的矛盾;并行退火方法进一步加快了求解速度。实验对比证明了动态邻域算法和并行退火算法有效,且能满足工程应用要求。分析了动态邻域和并行退火的复杂度,从理论上说明了这两种方法缩短排样时间的原因。The strategy of＂ shaking bottle＂ is presented to overcome the inadequacy of the strategy based on sequence in the 2-D nesting problem. Based on the image and color histogram, a new method for overlap testing, outside testing and estimating is put forward. Two measures are used to improve the simulated annealing （SA） algorithm：the dynamic neighborhood dimension and the parallel annealing. The dynamic annealing makes SA be used for the shaking bottle strategy, and overcomes the contradiction between precision and time in the discrete methods of polygon overlap testing. The parallel annealing speeds up the nesting velocity further. Experiments and comparison prove that the dynamic neighborhood and the parallel annealing algorithm are effective and can be used for engineering application. Complexity of the algorithm is analyzed and the reason why the nesting time is shorten is analysed theoretically.

关 键 词：排样 不规则件 模拟退火 重叠检测 

分 类 号：TP391.9[自动化与计算机技术—计算机应用技术]