孙 波，李粉利，刘 璐，刘 峥

（西安工业大学 机电工程学院，西安710021）

研究板材的排样问题，可以有效提高钣金材料的利用率，从而降低生产成本，对提高企业的经济效益意义重大．在20世纪30年代，Kantorovich首先提出了排样问题．随着研究的不断深入，国外许多学者对排样问题进行了研究，同时提出了很多可行的排样算法．文献［1］将人的经验和启发式思想融合，应用于矩形件的排样中，根据矩形件的长和宽判定排样顺序，并依照最左最下原则，优先将矩形件排放到板材的左下角．文献［2］将不规则件拟合为凸多边形，再将凸多 边形组合为正六边形，然后对不规则件求解排样问题．文献［3］在解决定宽无限长板材的排样问题中使用了神经网络法、遗传算法等，并把遗传算法与模拟退火算法结合，通过对实例进行计算、分析评价，证明了多种算法结合求解排样问题比单一排样算法效果更好．国内研究起步较晚，从20世纪80年代开始研究排样问题．文献［4］将遗传算法与改进后的下台阶（Bench Lower，BL）算法应用于矩形件排样问题，取得了较好的排样效果．文献［5］将遗传算法和模拟退火算法结合应用于矩形件排样，利用遗传算法的全局寻优能力找到排列最紧密的次序，然后结合填充算法填充空余部分．文献［6］用包络矩形法求解不规则件的排样问题，最后将矩形还原为多边形，避免了不规则件直接排样．文献［7］用离散网格表示不规则件，加速了重叠零件的判断．文献［8］将遗传算法应用于解决不规则件的排样优化问题．

本文旨在对剩余矩形排样算法进行改进，并结合遗传算法，提出一个有效的求解矩形排样优化的方法，以期提高钣金材料的利用率．

1 剩余矩形排样算法的优化

对于钣金件展开后的排样问题，目前比较有效的方法是先转化为包络矩形排样问题．剩余矩形排样算法，是目前较为有效的一种算法．该算法需要计算板材上所有未被利用的剩余空间，考虑将待排放的矩形件插入到板材任何可能的空白区域中，可以有效提高钣金材料的利用率．将剩余矩形排样算法与遗传算法等智能算法联合使用，能够得到更好的排样效果．

1．1 剩余矩形排样算法的改进

剩余矩形排样算法用矩形数据集合来表示板材中剩余的未排样的空白区域，没有被利用的区域都会记录到剩余矩形集合中．根据剩余矩形集合中的记录位置按照优先最左最下排样原则选择一个位置来插入待排放的矩形件．剩余矩形排样算法在一定程度上能有效的提高钣金材料的利用率，但是对于某些排样序列来说，并未起到有效利用材料的目的，如图1所示，图中1，2，3，4为矩形件编号．在图1（a）中，矩形件4的高度大于板材下方空白矩形区域的高度，此时它就不能插入到此位置，只能寻找下一个矩形区域来排放．此时板材下方的区域闲置，就导致了钣金材料的浪费．若将矩形件4旋转90°，则正好可以插入到板材的下部区域，如图1（b）所示．与图1（a）相比，图1（b）有效地提高了板材利用率．可见，将矩形件转动90°后优先考虑将其排放到位置最低的剩余矩形中，可以有效降低排样图的最大高度．

图1 剩余矩形排样算法的改进Fig．1 Improving the surplus rectangle layout algorithm

但在有些条件下，将矩形件转动90°后排样会增大排样图的最大高度，因而不适宜转动后排样，如图2所示，图中1，2为矩形件编号．在图2（a）中，插入矩形件1后，板材上有两个剩余矩形，分别是阴影部分和矩形件1上方的部分．矩形件2的宽度大于最低剩余矩形的宽度，因此不能将矩形件2直接插入最低剩余矩形来排样；若将矩形件2转动90°后插入，虽然可以插入，但是排样后的已用板材的最大高度较大．而不转动，直接将矩形件2左对齐排放在矩形件1的上方，而此时已用的板材的最大高度较小．

鉴于以上情况，排样时不能简单的以转动或者不转动的方式来排样，还需考虑已用板材的最大高度．下面以4个矩形件为例，说明改进的剩余矩形排放算法的具体步骤．板材和矩形件的信息见表1，排样过程如图3所示，图中1，2，3，4为矩形件编号．

假定本例中4个矩形件的排样序列Q＝｛1，2，3，4｝，用改进的剩余矩形排样算法排样的步骤为

1）将矩形件1排放到板材的左下角，计算剩余矩形集合，此时形成了两个剩余矩形区域，如图3（a）所示．

2）排放矩形件2，先考虑将矩形件2排放到最低剩余矩形区域，发现不能插入，如图3（b）所示；考虑将矩形件2转动90°后再次插入，此时可以插入，插入后记录已利用的板材的最大高度，如图3（c）所示；然后将矩形件2不转动，直接将矩形件2排放到下一个剩余矩形区域中，也就是排放在矩形件1的左上方，记录此时已利用板材的最大高度，如图3（d）所示，比较矩形件2两次排样后已利用板材的最大高度，选择高度较小的一种排样方案，同时重新计算剩余矩形集合．

表1 矩形件信息Tab．1 Rectangular parts information

图2 转动90°后使高度增大的情况Fig．2 Increasing height after rotating 90degrees

图3 改进后剩余矩形排样算法的排样过程Fig．3 The layout process by the improved surplus rectangle algorithm

3）排放矩形件3，先考虑将其排放到最低矩形区域，发现可以插入排放，如图3（e）所示，同时重新计算剩余矩形集合．

4）排放矩形件4，先考虑排放到最低剩余矩形区域，发现不能插入排放，如图3（g）所示，将其转动90°后，发现可以排放到最低剩余矩形区域，记录此时已利用板材的最大高度，如图3（h）所示；将矩形件不旋转，直接排放到下一个可排放的剩余矩形区域，记录此时已利用板材的最大高度，如图3（i）所示；比较矩形件4两次排样后已利用板材的最大高度，选择高度较小的一种排样方案．此时，也得到了最终的排样方案图，如图3（h）所示．

1．2 改进前后板材利用率对比

以文献［4］中的25个矩形件数据信息为例，在长30mm高度足够高的板材上排样，随机生成100组排样序列，分别用剩余矩形排样算法与改进后的剩余矩形排样算法排样，这两种算法排样的利用率如图4～5所示．

图4 剩余矩形排样算法的利用率Fig．4 Utilization rate before improving

图5 改进后后的剩余排样算法的利用率Fig．5 Utilization rate after improving

用剩余矩形排样算法排样得到的板材最大利用率是0．909 1，平均利用率是0．832 4；改进后的剩余矩形排样算法排样后板材的最大利用率是0．952 4，平均利用率是0．854 1．由此可见，改进后的剩余矩形排样算法能更有效的利用板材材料．

2 遗传算法支持的剩余矩形件排样优化

剩余矩形排样算法具有较强的局部优化性能，而遗传算法具有全局寻优搜索的性能，将二者结合使用，能更加有效的解决矩形钣金件的排样优化问题，以便寻求最优的排样方案．

2．1 编码和解码

编码方式采用十进制顺序编码，将每一个矩形件顺序编号，在编号的同时确定正负值，规定矩形件横放时编号为正，竖放时编号为负．横放表示矩形件的长边与水平轴平行，竖放表示矩形件的短边与垂直轴平行．对于一个染色体（3，-1，2，-4，5）来说，矩形件排样顺序是3，1，2，4，5，其中3号横放，1号竖放，2号横放，4号竖放，5号横放．

对于矩形件的排样问题，解码就是将染色体转化为排样图的过程，这里采用优化后的剩余矩形排样算法生成排样图．

2．2 选择算子

在解决矩形件排样优化问题时，选择算子采用轮盘赌选择法，具体过程为

1）对种群中每个个体预排样，求出每个个体的适应度值，再求出所有个体的适应度值总和．

2）求出每个个体的相对适应度（也就是被选中概率）Pi＝Fi／Fsum．其中Pi表示第i个个体被选中概率，Fi表示第i个个体的适应度值，Fsum表示所有个体的适应度值之和．

3）求出每个个体的的累积选择概率qi．

4） 产 生 一 个 随 机 数 rand＝ ［0，1］．若rand＜q1，第一个个体被选中，否则第i个个体被选中，使qi-1＜rand＜qi成立．重复该操作，直到选择的个体数等于初始种群的个体总数．

2．3 交叉算子

设定交叉操作算子的方法如下：在染色体上选择一个位置作为交叉位置，交叉位置之前的基因片段不交叉，交叉位置之后的片段交叉．比较两个参与交叉的染色体，将交叉位置之前的相同基因去除，将交叉位置之前的剩余基因顺序不变的存入数组p［］和q［］中．然后对染色体的交叉部分进行交叉，若交叉部分的基因不等于这两个数组中基因，则直接交换；若与数组中的基因相同，则先把相同基因换成数组p［］或q［］中对应基因之后再交换．

2．4 适应度函数

对于矩形件的排样优化问题，一般有两种适应度函数，一种是用板材实际使用的最大高度的倒数表示；另一种是使用板材的利用率来确定适应度函数．对于定宽无限长的板材，本文设定遗传算法的适应度函数为

式中：h为排样图的最大高度；w为板材的宽度；areal为所有矩形件的总面积．

3 矩形件排样优化实例及分析

为了测试遗传算法支持的剩余矩形件排样算法的有效性，对文献［4］中的算例进行求解，进行实例验证．在一块高40mm、长15mm的矩形板材上，排列25块尺寸已知的矩形件．按照本文提出的矩形件排样问题的算法方案，设置初始种群为50个，遗传代数为100代，优化后得到的排样结果如图6所示．

图6 优化的排样结果Fig．6 The optimized result of layout

排样结果：板材利用率0．975 61，按照本文提出的排样算法得到的排样序列为P＝｛14，-6，7，-20，5，-15，10，1，25，24，8，-11，-3，-17，-22，-13，-18，2，21，9，19，4，23，-12，-16｝，而文献［4］中的最优排样板材利用率为0．937 5．通过与文献［4］中数据的比较，可见本文提出的矩形件排样算法在提高板材利用率方面有一定的优越性．

4 结 论

1）剩余矩形排样算法在求解排样问题时具有局部性，其在钣金件排样过程中板材利用率未达到全局最优．对其进行改进，给出了改进剩余矩形排样算法，该算法可使板材利用率提高．

2）通过遗传算法与改进剩余矩形排样算法相结合，给出了剩余矩形排样遗传优化算法，获得了排样最优解．该算法钣金件排样的板材利用率优于剩余矩形排样算法，排样得以优化．

［1］ YNAASEE H H，ZNIOBER A S．Two-Dimensional Cutting Stock with Multiple Stock Sizes［J］．Journal of the Operational Research Society，1991，42（8）：673．

［2］ DORI D，BEN B M．Efficient Nesting of Congruent Convex Figures［J］．Communications of the ACM，1984，27（3）：228．

［3］ DAGLI C H，POSHYANONDA P．New Approaches to Nesting Rectangular Patterns［J］．Journal of Intelligent Manufacturing，1997（8）：177．

［4］ 刘德全，滕弘飞．矩形件排样问题的遗传算法求解［J］．小型微型计算机系统，1998，19（12）：20．LIU De-quan，TENG Hong-fei．On Genetic Algorithm for the Orthogonal Packing of Rectantangles［J］．Mini-Micro System，1998，19（12）：20．（in Chinese）

［5］ 杨彩，史俊友，顾海明．基于遗传模拟退火算法的矩形件排样［J］．青岛科技大学学报：自然科学版，2004，25（5）：452．YANG Cai，SHI Jun-you，GU Hai-ming．Packing of Rectangular Using Genetic Simulated Annealing Algorithm［J］．Journal of Qingdao University of Science and Technology：Nature Science Edition，2004，25（5）：452．（in Chinese）

［6］ 黄红兵，蒋望东．二维不规则零件排样问题的研究［J］．广西科学院学报，2004，20（4）：225．HUANG Hong-bing，JIANG Wang-dong．On the Pattern Techniques of the Two-Dimensional Irregular Parts［J］．Journal of Guangxi Academy of Sciences，2004，20（4）：225．（in Chinese）

［7］ 张玉萍，张春丽，蒋寿伟．皮料优化排样的有效方法［J］．软件学报，2005，16（2）：316．ZHANG Yu-ping，ZHANG Chun-li，JIANG Shou-wei．An Effective Approach for Leather Nesting［J］．Journal of Software，2005，16（2）：316．（in Chinese）

［8］ 贾志欣，殷国富，罗阳．二维不规则零件排样问题的遗传算法求解［J］．计算机辅助设计与图形学学报，2002，14（5）：467．JIA Zhi-xin，YIN Guo-fu，LUO Yang．Two-Dimensional Irregular Parts Packing with Genetic Algorithm［J］．Journal of Computer-Aided Design ＆ Computer Graphics，2002，14（5）：467．（in Chinese）