韩 伟 张子成

南京财经大学，南京，210046

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

韩 伟 张子成

南京财经大学，南京，210046

针对带贯通性约束的不规则凸多边形的排样问题，提出了一种分阶段构造算法。为了控制每个阶段新生成的组合图形的形状,构造过程引入变动的形状权重，算法运行早期采用较小权重使图形组合具有较高出材率,而在后期采用较大的权重得到类似矩形的复合。基于模拟退火思想引入温度参数控制权重的变化率，在早期和后期形状权重变化率较小而在中期变化率较大。采用ESICUP标准测试数据分别对常数散列、线性散列和温控散列进行对比,结果表明温控散列函数能有效提高排样效率和排样出材率。

不规则排样;贯通约束;模拟退火;形状权重

0 引言

二维排样问题是一类典型的组合爆炸优化问题，广泛应用于玻璃加工、金属切割、服装等行业。研究排样优化算法对提高原料利用率，建立节约型、环境友好型社会具有重要意义。Bennell等[1]分析了二维排样问题的各种矩形优化算法，对于不规则排样问题，由于其组合的可能性增大，零件之间的重叠、相交及相邻关系判断也较为复杂，因此采用传统的数学规划和单一的启发算法较难解决不规则排样问题[2]。李敬花等[3]采用凸多边形包络法对不规则多边形进行处理，结合遗传算法的快速全局搜索能力和模拟退火算法的局部搜索能力，以遗传算法做外层循环，以模拟退火做内层循环，从而改善遗传算法的早熟缺陷。……