基于模拟退火的贯通约束不规则排样

摘要

A layered constructive algorithm was proposed for 2D irregular guillotine bin packing problems.Variant shape weighs were introduced to control the shapes of each evolved block,which indicated the similarity of the resulted shape to rectangle in each iteration.To get better utilization, smaller shape weights were used in early periods to get shapes with higher ratio of utilization,while larger weights were introduced in the last periods to let the shape be similar to rectangle.Based on simulated annealing,a parameter named temperature was introduced to control the change rate weights.The change of shape weights was smaller in early and later periods and larger in middle peri-ods.Based on ESICUP standard test data,several weight adjustment strategies were examined,inclu-ding fixed weight,linear change and temperature-controlled change,the results show that tempera-ture-controlled change effectively improves the layout effiency and the material rate of layout.%针对带贯通性约束的不规则凸多边形的排样问题，提出了一种分阶段构造算法。为了控制每个阶段新生成的组合图形的形状，构造过程引入变动的形状权重，算法运行早期采用较小权重使图形组合具有较高出材率，而在后期采用较大的权重得到类似矩形的复合。基于模拟退火思想引入温度参数控制权重的变化率，在早期和后期形状权重变化率较小而在中期变化率较大。采用ESICUP标准测试数据分别对常数散列、线性散列和温控散列进行对比，结果表明温控散列函数能有效提高排样效率和排样出材率。