2014, Vol. 50
文章信息
- 张国梁, 侯晓鹏, 苗虎, 安源, 周玉成, 姚永和
- Zhang Guoliang, Hou Xiaopeng, Miao Hu, An Yuan, Zhou Yucheng, Yao Yonghe
- 基于分组降维规则和遗传算法的人造板材矩形件优化下料方法
- Layout Method of Rectangular Wood Based Panel Parts Based on Grouping and Dimension Reducing Heuristic Rule and Genetic Algorithm
- 林业科学, 2014, 50(6): 181-186
- Scientia Silvae Sinicae, 2014, 50(6): 181-186.
- DOI: 10.11707/j.1001-7488.20140624
-
文章历史
- 收稿日期：2013-12-13
- 修回日期：2014-02-12
-
作者相关文章
2. 河北农业大学林学院 保定 071000;
3. 中国林业科学研究院木材工业研究所 北京 100091;
4. 上海跃通木工机械设备有限公司 上海 201505
2. College of Forestry, Agricultural University of Hebei Baoding 071000;
3. Research Institute o f Wood Industry, CAF Beijing 100091;
4. Shanghai Yuetong Woodworking Machine Equipment Co., Ltd., Shanghai 201505
人造板材矩形件优化下料属二维下料问题，并已经被证明是具有高度复杂性的NP 完备问题(吴杰君，2004； 卢开澄，1998)，目前尚无有效的最优解算法。国内外对此类问题的研究主要考虑某种近似算法和启发式算法，很多专家和学者做了卓有成效的研究工作(Suliman，2006； 季君等，2012； Furini et al. ，2013)。遗传算法的全局搜索和并行处理能力使其在优化下料问题中得到了大量应用，无论是标准遗传算法或与其他算法相结合都体现出其解决复杂问题的有效性(曹炬等，1999； 马炫等，2007； 蒋兴波等，2008)。然而，现有排样算法中大多考虑大规模零件的整体套排(岳琪，2005； 高乐文，2010)，排样方案虽能获得较高的基材利用率和较小的余料损失，但过多的零件组合导致开料锯在切割过程中锯路变化烦琐，从而降低开料速度。因此下料算法的设计应充分考虑实际的生产工艺。一般情况下，在一块完整的基材上允许参与排样的零件种类数应为2～3种(张文江，1999)。
本文针对大规模矩形零件的优化排样，设计了分组降维的启发式规则，将整体套排简化为若干组、每组不多于3种矩形零件的优化排样和组合问题，并将遗传算法和惩罚函数相结合求解优化排样数学模型。
1 大规模矩形零件分组降维排样的启发式规则设共有M种矩形零件参与排样，分组的组数为g，第j组零件的种类数为Mj，则
| $ M = \sum\limits_{j = 1}^g {{M_j},(1 \le j \le g)} 。 $ | (1) |
根据排样准则，每组零件种类数不大于3，即1≤Mj≤3。设第i种矩形零件尺寸为li×wi，需求量为ni(1≤i≤M)。根据矩形零件面积大小决定优先级，通常情况下，单个矩形件面积越小，基材利用率越高； 且先排放大面积的矩形件，后排放小面积的矩形件，基材的利用率不会太低。
首先计算所有M种矩形零件的面积，Si=li×wi，并按降序排列，即S1≥S2≥…Si≥…≥SM。提取前3种面积最大的矩形零件为第1组g1，然后再次提取剩余的M-3种矩形零件中面积最大的3种零件为第2组g2，依次类推。设第j次分组后共提取的矩形零件种类数为Mtj=3·j。此时，如果剩余的零件数小于或等于3，即M-Mtj≤3，则将剩余的M-Mtj种零件统一归为一组，也是最后一组。
经过上述过程，将M种零件的排样通过分组的方式分解为g组、每组不超过3种零件的小规模零件的排样过程，起到了降维目的。
2 分组降维排样的数学模型 2.1 问题描述据前述分组降维的启发式规则，大规模矩形零件的排样转化为组内矩形零件的优化排样以及组间零件的顺序承接问题，通过设定合适的变量，采用循环迭代即可完成组间零件的顺序承接。因此解决问题的关键在于组内矩形零件的优化排样。
组内矩形零件优化排样的目标是原料板材利用率最高、废料最少，同时需考虑锯路损失。组内矩形零件的排样应满足如下约束条件：
1)零件之间不能相互重叠；
2)零件必须排入基材板内，即排样后零件不超过基材板宽度和长度；
3)满足“一刀切”的切割方式——开料锯切割路径为直线，且每一次切割都必须贯通整个矩形；
4)每一行只排样一种零件。
2.2 数学模型为建立分组降维排样的数学模型，各参数详述如下。
1)设基材尺寸为L×W。
2)在第j组矩形零件中，称第k种矩形零件为Mjk，其面积为Sjk，需求量为Njk，尺寸为ljk×wjk(1≤j≤g； 1≤k≤Mj)，根据定序规则，有Sj1≥Sj2≥Sj3。
3)根据所有矩形零件的总面积计算出第j组零件排样完毕，最少需要基材板张数为Nj，设α为冗余次数(α≥1)，则第j组矩形零件排样完毕，基材板用量为Njα=α·Nj张。
4)第k种矩形零件排样完毕，横排时在第t(1≤t≤α·Nj)张基材板上所排行数为Rjtk，竖排时所排行数为Cjtk 。
5)不考虑纹理要求，则零件既可横排又可竖排。设变量pjk表示第j组矩形零件内第k种矩形零件的排放方式，横排，则pjk=1； 竖排，pjk=0(同一种零件或横排或竖排，pjk∈[0，1])。
6)第t张基材板上第k种零件横排一行内零件数为njtk； 竖排一行内零件数为mjtk ；
7)设数控板材开料锯的锯路宽度为ws，不失一般性，为每个矩形零件的长和宽都加上一个单位的ws，同时，原料板的长和宽方向也各加上一个单位的ws，以此抵消在原料板的最下端和最右端的“虚拟锯路损失”。
8)在基材板的长度方向，所有零件长度之和应不大于基材板宽度L，即
| $ \begin{array}{l} (L + {w_s}) - [({l_{jk}} + {w_s}) \bullet {n_{jtk}} \bullet {p_{jk}} + \\ ({w_{jk}} + {w_s}) \bullet {m_{jtk}} \bullet (1 - {p_{jk}})] \ge 0。 \end{array} $ | (2) |
9)在基材板的宽度方向，所有零件宽度之和应不大于基材板宽度W，即
| $ \begin{array}{l} (W + {w_s}) - \sum\limits_{k = 1}^{{M_j}} [ ({w_{jk}} + {w_s}) \bullet {R_{jtk}} \bullet {p_{jk}} + \\ ({l_{jk}} + {w_s}) \bullet {C_{jtk}} \bullet (1 - {p_{jk}})] \ge 0。 \end{array} $ | (3) |
10)每一张基材板上，排样零件面积总和应不大于基材板面积，即
| $ \begin{array}{l} L \bullet W - \sum\limits_{k = 1}^{{M_j}} {{l_{jk}} \bullet } {w_{jk}} \bullet [{p_{jk}} \bullet {n_{jtk}} \bullet {p_{jk}} + \\ (1 - {p_{jk}}) \bullet {m_{jtk}} \bullet {C_{jtk}}] \ge 0。 \end{array} $ | (4) |
11)排样数量的限制
| $ 0 \le {n_{jtk}} \le \frac{{{n_{jk}}}}{{{R_{jtk}}}}; $ | (5) |
| $ 0 \le {m_{jtk}} \le \frac{{{N_{jk}}}}{{{C_{jtk}}}}; $ | (6) |
| $ 0 \le {R_{jtk}} \le {N_{jk}}; $ | (7) |
| $ 0 \le {C_{jtk}} \le {N_{jk}}; $ | (8) |
| $ {C_{jtk}} \bullet {m_{jtk}} \bullet (1 - {p_{jk}}) - {N_{jk}} = 0。 $ | (9) |
根据上述约束条件，构建分组降维排样的数学模型如下：
| $\begin{array}{l} F = Min\sum\limits_{t = 1}^{N_J^a} \{ L \bullet W - \sum\limits_{k = 1}^{{M_j}} {{l_{jk}} \bullet } {w_{jk}} \bullet [{p_{jk}} \bullet {n_{jtk}} \bullet {p_{jk}} + \\ (1 - {p_{jk}}) \bullet {m_{jtk}} \bullet {C_{jtk}}]\} 。 \end{array} $ | (10) |
上述公式中，已知参数为： L，W，Mj，ljk，wjk，Njk，ws，Njα； 未知参数为： Rjtk，Cjtk，njtk，mjtk，pjk。因此确定第j组内Mj种矩形零件的排样方案包括以下5个方面：
1)在第t张基材板上，第k种零件横排行数Rjtk；
2)在第t张基材板上，第k种零件竖排行数Cjtk ；
3)在第t张基材板上，第k种零件横排时一行的零件数njtk；
4)在第t张基材板上，第k种零件竖排时一行的零件数mjtk ；
5)第j组矩形零件内第k种矩形零件的排放方式pjk；
3 遗传算法求解 3.1 算法流程采用遗传算法求解排样问题的算法流程如图 1所示。
 |
图 1 遗传算法排样流程 Fig. 1 Program of genetic algorithm |
图 1所示遗传算法排样流程针对组内Mj中矩形零件的排样过程。遵循遗传算法的一般规律，在参数编码的基础上首先建立初始种群，随后执行遗传操作，并以遗传代数超限为停止准组。
3.2 算法描述1)基材需求量估算 为得到第j组矩形零件排样后所需基材数量Njα，调用基材需求量估算函数Njalefa_Solve.m。该函数的建立和求解是十分必要的，因为Njα的大小决定遗传算法中待编码的变量个数。假设Njα=2，第j组内矩形零件种类数Mj=3，则变量维数Nvar=(4·Njα+1)·Mj=(4×2+1)×3=27，分布如图 2所示。
 |
图 2 待编码变量分布 Fig. 2 Distribution of parameter to be coded |
图 2所示立方体中，第1层表示第1张基材板； 第2层表示第2张基材板； 每一层上行表示零件种类数，列表示每种零件的排样信息； 当所需基材板数和第j组内矩形零件种类数变化时，此立方体的层数和每一层的行数将发生变化。
2)定义遗传算法参数 ①初始群体规模可根据排样矩形零件的个数在10～200之间选定； 最大遗传代数根据实际情况选取； 代沟是一个小于1的正数，表明经过重组之后新旧种群规模的差异。
②参数采用二进制编码方式，定义一条染色体是第j组矩形零件排样结果。一个基因即一种矩形零件排样结果，包括5个方面内容： 横排行数Rjtk、竖排行数Cjtk、横排零件数njtk、竖排零件数mjtk和排放方式pjk。
③区域描述器中，染色体长度取决于变量维数和每个变量的二进制位数，染色体使用算数刻度且包含边界。
3)遗传操作 ①分配个体适应度值 变量的解码使用二进制到实值转换函数bs2rv.m，采用基于秩的适应度分配函数ranking.m，排序方式为线性排序，选择压差为2。
②操作算子 为从群体中产生优良个体，采用随机遍历抽样的选择方式sus.m； 单点交叉函数xovrp.m，交叉概率为0.7； 离散变异算子mut.m，变异概率为0.7/染色体长度； 使用reins.m函数生成重插入子代到新种群。
3.3 混合惩罚函数法1)惩罚函数法基本形式 采用惩罚函数法处理数学模型中等式约束和不等式约束。惩罚函数法分为外点法和内点法：内点法将惩罚函数定义于可行域内，且求解无约束优化问题的搜索点总是保持在可行域内，一般只用于不等式约束情况； 外点法既可用于求解不等式约束优化问题，又可用于求解等式约束优化问题，主要特点是惩罚函数定义于可行域的外部，从而在求解系列无约束优化问题的过程中，从可行域外部逐渐逼近原约束优化问题最优解(骆志高等，2009； 张波等，2004)。
内点法和外点法各有所长，可结合使用。对p个等式约束，采用外点法，对m个不等式约束采用内点法，构成混合函数如下：
| $ P(X,{r^k}) = f(X) + {r^k}\sum\limits_{v = 1}^p {[{h_v}} (X){]^2} + \frac{1}{{{r^k}}}\sum\limits_{u = 1}^m {\frac{1}{{{g_u}(X)}}} 。 $ | (11) |
2)混合惩罚函数法的应用 由数学模型可知，等式和不等式约束条件有8项，对应式(2)～(9)，本文对此8项约束的处理采取3种不同的方式： 式(2)～(6)为不等式约束，采用内点惩罚函数法； 式(9)为等式约束，采用外点惩罚函数法； 式(7)和式(8)属于变量的上下边界约束，因此置于遗传算法区域描述器的上下界中。为便于计算和编程，取出式(9)等号左边项的最大值和最小值，只要最大和最小值等于0，则等号左边每一项都等于0。
使用Matlab建立6个惩罚函数，P1=Punishment_1()对应式(2)； P2=Punishment_2()对应式(3)； P3=Punishment_3()对应式(5)； P4=Punishment_4()对应式(6)； [P5_Min，P5_Max]=Punishment_5()对应式(9)； P6=Punishment_6()对应式(4)； ObjV_1=Cutting_pattern()对应式(10)，由此建立的辅助函数为：
| $ \begin{array}{l} ObjV = ObjV\_1 + a1./[P1. \times (W - P1)] + \\ a2./[P2. \times (L - P2)] + a3./P3 + a4./P4 + a51. \times \\ (P5\_Min) + a52. \times (P5\_Min)\\ a6./[P6. \times (L \times W - P6)]。 \end{array} $ | (12) |
试验数据来源于上海跃通木工机械设备有限公司在数控板材开料锯研发过程中所做板材锯切试验，基材板长2 440 mm，宽1 220 mm，排样矩形件共有6种，数量和尺寸见表 1。
|
根据分组降维规则，排样矩形件分为2组，分组方式见表 2。
|
|
惩罚因子取为： a1=1×1010； a2=1×1011； a3=1×1012； a4=1×1013； a51=1/a1； a52=1/a2； a6=1×1014； 初始群体规模为50； 最大遗传代数MaxGen=1 000。运行遗传算法得到第一组矩形零件的排样结果如图 3。
 |
图 3 第1组矩形零件排样方案 Fig. 3 Layout of the first group of rectangular parts |
图 3表明，4号零件竖排，共排了2行，每一行排列10个零件； 6号零件横排，排了1行； 5号零件横排，排了2行，每一行排列8个零件； 相邻的2个零件之间存在5 mm的锯路损失，与开料锯所用锯片的锯料宽一致。考虑锯路损失，本块基材的利用率为83.2%。
运行遗传算法得到第2组矩形零件的排样结果如图 4。
 |
图 4 第2组矩形零件排样方案 Fig. 4 Layout of the second group of rectangular parts |
图 4表明，3，2和1号零件都为横排，分别排了4，2和1行，同样，在相邻的2个零件之间存在5 mm的锯路宽度。考虑锯路损失，本块基材的利用率为75%。从图中可以看出，排样方案满足“一刀切”要求。开料锯在切割过程中，可以从任意2行中间锯缝处开始切割，对于同一种零件，开料锯可分组锯切，也可锯切单个零件。
5 结论与讨论本文针对现有大规模零件整体套排的排样方案锯路变化烦琐、降低锯切速度的问题，设计了以面积为决定因素的分组降维启发式规则，将大规模矩形零件的排样问题转化为每组不大于3种零件的排样和组间零件的顺序承接问题； 建立了相应的数学模型并详细描述了各参数，从而将组内矩形零件的排样方案转化为5个设计变量的解； 采用二进制编码的遗传算法求解数学模型中设计变量，针对模型中的约束项，采用内点法和外点法相结合的惩罚函数法处理。试验结果表明，本文所设计的基于分组降维规则的遗传算法和惩罚函数相结合求解矩形件排样问题的方案是可行的，且排样方案满足“一刀切”工艺要求，从而有利于提高开料锯锯切速度。
遗传算法的群体搜索性能和高度的并行性使其能够求解复杂非线性问题。模拟自然界生物行为的算法多样，将遗传算法和其他算法相融合，取长补短解决下料问题的研究不在少数，且都给出了较为理想的排样结果(黄岚等，2012； 陈江义等，2011)。虽然本文实例表明了单独使用遗传算法的有效性，但与其他算法的结合研究也是本文下一步需要探索和试验的问题。
从试验结果来看，本文所给出的排样方案每一行只排样一种零件，由于零件规格一致，因此开料锯在锯切过程中完全满足“一刀切”的锯切要求，这种排样方案使数控开料锯的编程相对容易。从图 4可以看出，当排样零件面积总和相比于基材尺寸较小时，遗传算法给出的排样方案存在较大的空白区域，如图 4中的“Null”区域。这一空白区域可以作为另一基材用于排样面积较小的矩形零件，这也表明本文所用基材尺寸并不唯一。
本文分组降维启发式规则是以面积大小排序，这种规则对于长宽比相差不大的矩形零件分组排样是十分有效的，但是针对矩形零件的长宽比很大的情况，不应单独使用面积去排序，长宽比也应是另一考虑因素，或者将长宽比很大的零件组合，在考虑锯路损失的基础上作为一个零件参与排样。
| [1] |
曹炬,冯松.1999.遗传算法在矩形件优化排样中的应用.计算机工程与应用,(5):5-7,10.( 1)
|
| [2] |
陈江义,宋雪枫,张明伟.2011.融合蚁群算法和遗传算法的矩形件排样问题研究.郑州大学学报: 理学版,43(2):79-82.(1)
|
| [3] |
高乐文. 2010.基于遗传蚁群算法的优化下料方法的研究与实现.哈尔滨:东北林业大学博士学位论文.(1)
|
| [4] |
黄岚,齐季,谭颖,等. 2012.一种求解矩形排样问题的遗传-离散粒子群优化算法.电子学报,40(6):1103-1107.(1)
|
| [5] |
季君,陆一平,查建中,等. 2012.生成矩形毛坯最优两段排样方式的确定型算法.计算机学报,35(1):183-191.(1)
|
| [6] |
蒋兴波,吕肖庆,刘成城.2008.求解矩形件优化排样的自适应模拟退火遗传算法.计算机辅助设计与图形学学报, 20(11):1625-1631.(1)
|
| [7] |
卢开澄.1998.组合数学算法与分析(下).北京:清华大学出版社,312-370.(1)
|
| [8] |
骆志高,王洋,李举,等.2009.遗传算法与惩罚函数法在辗轧成形工艺参数优化中的应用.中国机械工程, 20(14):1704-1707.(1)
|
| [9] |
马炫,张亚龙. 2007.基于遗传算法的大规模矩形件优化排样.智能系统学报,2(5):48-52.(1)
|
| [10] |
吴杰君.2004.板材下料优化排样系统研究与实现.合肥:合肥工业大学硕士学位论文.(1)
|
| [11] |
岳琪.2005.基于遗传退火算法板式家具大规模矩形件优化下料研究.哈尔滨:东北林业大学博士学位论文.(1)
|
| [12] |
张波,孙自强. 2004.含约束条件遗传算法在连续催化重整优化操作中的应用.华东理工大学学报,30(5):564-566,575.(1)
|
| [13] |
张文江. 1999.家具制造厂板材综合下料问题的研究.林产工业,26(4):15-17.(1)
|
| [14] |
Furini F, Malaguti E.2013.Models for the two-dimensional two-stage cutting stock problem with multiple stock size. Computers & Operations Research, 40(8): 1953-1962.(1)
|
| [15] |
Suliman S M A.2006. A sequential heuristic procedure for the two-dimensional cutting-stock problem. International Journal of Production Economics, 99(1/2):177-185.(1)
|