全 文 ：第 50 卷 第 6 期
2 0 1 4 年 6 月
林 业 科 学
SCIENTIA SILVAE SINICAE
Vol. 50，No. 6
Jun．，2 0 1 4
doi:10．11707 / j．1001-7488．20140624
收稿日期: 2013 － 12 － 13; 修回日期: 2014 － 02 － 12。
基金项目:中国林业科学研究院林业新技术所基本科研业务费专项(CAFINT2012K01)。
* 侯晓鹏为通讯作者。
基于分组降维规则和遗传算法的人造板材矩形件优化下料方法*
张国梁1，2，3 侯晓鹏1，3 苗 虎1，3 安 源1，3 周玉成1，3 姚永和4
(1． 中国林业科学研究院林业新技术研究所 北京 100091; 2． 河北农业大学林学院 保定 071000;
3．中国林业科学研究院木材工业研究所 北京 100091; 4． 上海跃通木工机械设备有限公司 上海 201505)
关键词: 优化下料; 分组降维; 混合惩罚函数; 遗传算法
中图分类号: TP391 文献标识码: A 文章编号: 1001 － 7488(2014)06 － 0181 － 06
Layout Method of Ｒectangular Wood Based Panel Parts Based on
Grouping and Dimension Ｒeducing Heuristic Ｒule and Genetic Algorithm
Zhang Guoliang 1，2，3 Hou Xiaopeng1，3 Miao Hu1，3 An Yuan1，3 Zhou Yucheng1，3 Yao Yonghe4
(1 ． Ｒesearch Institute of Forestry New Technology，CAF Beijing 100091; 2 ． College of Forestry，Agricultural University of Hebei Baoding 071000;
3． Ｒesearch Institute o f Wood Industry，CAF Beijing 100091; 4． Shanghai Yuetong Woodworking Machine Equipment Co．，Ltd．， Shanghai 201505)
Abstract: Algorithms which were available in most literatures for whole layout of large scale rectangular parts gave
solutions that resulted in frequent change of saw line and therefore dropped sawing velocity down． To solve this problem，
a grouping and dimension-reducing heuristic rule which took areas of rectangular parts as priority was put forward in this
paper． According to this rule，no more than three kinds of rectangular parts were considered in each layout calculation．
Corresponding mathematical model was set up． Hybrid punishment function that was the combination of interior point
method and exterior point one was applied to deal with constrains． Genetic algorithm (GA) was adopted to search global
optimal solution for layout． It was proved by example that the algorithm used in this paper could provide layout solution
which exactly fulfilled guillotine cutting requirement and had saw line in order and therefore was useful to increase of
sawing efficiency．
Key words: optimization layout; grouping and dimension-reducing; hybrid punishment function; genetic algorithm
(GA)
人造板材矩形件优化下料属二维下料问题，并
已经被证明是具有高度复杂性的 NP 完备问题(吴
杰君，2004; 卢开澄，1998)，目前尚无有效的最优
解算法。国内外对此类问题的研究主要考虑某种近
似算法和启发式算法，很多专家和学者做了卓有成
效的研究工作 ( Suliman，2006; 季君等，2012;
Furini et al．，2013)。遗传算法的全局搜索和并行处
理能力使其在优化下料问题中得到了大量应用，无
论是标准遗传算法或与其他算法相结合都体现出其
解决复杂问题的有效性 (曹炬等，1999; 马炫等，
2007; 蒋兴波等，2008)。然而，现有排样算法中大
多考虑大规模零件的整体套排(岳琪，2005; 高乐
文，2010)，排样方案虽能获得较高的基材利用率和
较小的余料损失，但过多的零件组合导致开料锯在
切割过程中锯路变化烦琐，从而降低开料速度。因
此下料算法的设计应充分考虑实际的生产工艺。一
般情况下，在一块完整的基材上允许参与排样的零
件种类数应为 2 ～ 3 种(张文江，1999)。
本文针对大规模矩形零件的优化排样，设计了
分组降维的启发式规则，将整体套排简化为若干组、
每组不多于 3 种矩形零件的优化排样和组合问题，
并将遗传算法和惩罚函数相结合求解优化排样数学
模型。
1 大规模矩形零件分组降维排样的启发式规则
设共有 M 种矩形零件参与排样，分组的组数为
g，第 j 组零件的种类数为 Mj，则
林 业 科 学 50 卷
M = ∑
g
j = 1
Mj，(1 ≤ j ≤ g)。 (1)
根据排样准则，每组零件种类数不大于 3，即
1≤Mj≤3。设第 i 种矩形零件尺寸为 li × wi，需求量
为 ni(1≤ i≤M)。根据矩形零件面积大小决定优先
级，通常情况下，单个矩形件面积越小，基材利用率
越高; 且先排放大面积的矩形件，后排放小面积的
矩形件，基材的利用率不会太低。
首先计算所有 M 种矩形零件的面积，Si = li ×
wi，并按降序排列，即 S1≥S2≥…S i≥…≥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 组矩形零件排样完毕，基材
板用量为 Nαj = α·Nj 张。
4) 第 k 种矩形零件排样完毕，横排时在第 t
(1≤t≤ α·Nj )张基材板上所排行数为 Ｒjtk，竖排时
所排行数为 Cjtk。
5) 不考虑纹理要求，则零件既可横排又可竖
排。设变量 pjk表示第 j 组矩形零件内第 k 种矩形零
件的排放方式，横排，则 pjk = 1; 竖排，pjk = 0(同一种
零件或横排或竖排，pjk ∈［0，1］)。
6) 第 t 张基材板上第 k 种零件横排一行内零
件数为 njtk; 竖排一行内零件数为 mjtk;
7) 设数控板材开料锯的锯路宽度为 w s，不失
一般性，为每个矩形零件的长和宽都加上一个单位
的 w s，同时，原料板的长和宽方向也各加上一个单
位的 w s，以此抵消在原料板的最下端和最右端的
“虚拟锯路损失”。
8) 在基材板的长度方向，所有零件长度之和应
不大于基材板宽度 L，即
(L + w s) － ［( l jk + w s)·njtk·pjk +
(wjk + w s)·mjtk·(1 － pjk)］≥ 0。 (2)
9) 在基材板的宽度方向，所有零件宽度之和应
不大于基材板宽度 W，即
(W + w s) －∑
M j
k = 1
［(wjk + w s)·Ｒjtk·pjk +
( l jk + w s)·Cjtk·(1 － pjk)］≥ 0。 (3)
10) 每一张基材板上，排样零件面积总和应不
大于基材板面积，即
L·W －∑
M j
k = 1
l jk·wjk·［pjk·njtk·Ｒjtk +
(1 － pjk)·mjtk·Cjtk］≥ 0。 (4)
11) 排样数量的限制
0 ≤ njtk ≤
Njk
Ｒ jtk
; (5)
0 ≤ mjtk ≤
Njk
C jtk
; (6)
0 ≤ Ｒjtk ≤ Njk; (7)
0 ≤ Cjtk ≤ Njk; (8)
∑
Naj
t = 1
∑
M j
k = 1
Ｒjtk·njtk·pjk +
Cjtk·mjtk·(1 － pjk) － Njk = 0。 (9)
根据上述约束条件，构建分组降维排样的数学
模型如下:
F = Min∑
Nαj
t = 1
{L·W －∑
M j
k = 1
l jk·wjk·［pjk·njtk·Ｒjtk +
(1 － pjk)·mjtk·Cjtk］}。 (10)
281
第 6 期 张国梁等: 基于分组降维规则和遗传算法的人造板材矩形件优化下料方法
s． t．
(L + w s) － ［( l jk + w s)·njtk·pjk + (wjk + w s)·mjtk·(1 － pjk)］≥ 0;
(W + w s) －∑
M j
k = 1
［(wjk + w s)·Ｒjtk·pjk + ( l jk + w s)·Cjtk·(1 － pjk)］≥ 0;
0 ≤ njtk ≤
Njk
Ｒ jtk
;
0 ≤ mjtk ≤
Njk
C jtk
;
0 ≤ Ｒjtk ≤ Njk;
0 ≤ Cjtk ≤ Njk;
pjk ∈［0，1］;
∑
Naj
t = 1
Ｒjtk·njtk·pjk + Cjtk·mjtk·(1 － pjk) = Njk;
L·W －∑
M j
k = 1
l jk·wjk·［pjk·njtk·Ｒjtk + (1 － pjk)·mjtk·Cjtk］≥ 0




 。
其中: 1 ≤ j≤ g，1 ≤ k≤ Mj，0 ≤ Nj，1≤t≤ α·Nj。
图 1 遗传算法排样流程
Fig． 1 Program of genetic algorithm
上述公式中，已知参数为: L，W，Mj，l jk，wjk，Njk，
ws，N
α
j ; 未知参数为: Ｒjtk，Cjtk，njtk，mjtk，pjk。因此确定
第 j 组内 Mj种矩形零件的排样方案包括以下 5 个
方面:
1) 在第 t 张基材板上，第 k 种零件横排行
数 Ｒjtk;
2) 在第 t 张基材板上，第 k 种零件竖排行
数 Cjtk;
3) 在第 t 张基材板上，第 k 种零件横排时一行
的零件数 njtk;
4) 在第 t 张基材板上，第 k 种零件竖排时一行
的零件数 mjtk;
5) 第 j 组矩形零件内第 k 种矩形零件的排放方
式 pjk;
3 遗传算法求解
3. 1 算法流程 采用遗传算法求解排样问题的算
法流程如图 1 所示。
381
林 业 科 学 50 卷
图 1 所示遗传算法排样流程针对组内 Mj中矩
形零件的排样过程。遵循遗传算法的一般规律，在
参数编码的基础上首先建立初始种群，随后执行遗
传操作，并以遗传代数超限为停止准组。
3. 2 算法描述 1) 基材需求量估算 为得到第 j
组矩形零件排样后所需基材数量 Nαj ，调用基材需求
量估算函数 Njalefa_Solve． m。该函数的建立和求解
是十分必要的，因为 Nαj 的大小决定遗传算法中待编
码的变量个数。假设 Nαj = 2，第 j 组内矩形零件种
类数 Mj = 3，则变量维数 N var = (4·N
α
j + 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 个方面内容: 横排行数 Ｒjtk、
竖排行数 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，rk) = f(X) + rk∑
p
v = 1
［hv(X)］
2 + 1
rk∑
m
u = 1
1
gu(X)
。
(11)
式中:惩罚因子 r k 是一个递增的正数序列，且
lim
k→∞
r k = ∞ 。
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)，由此建立的辅助函数为:
ObjV = ObjV_1 + a1． /［P1． × (W-P1)］+
a2． /［P2． × (L-P2)］+ a3． / P3 + a4． / P4 + a51． ×
(P5_Min) + a52． × (P5_Max) +
a6． /［P6． × (L × W-P6)］。 (12)
式中:a1，a2，a3，a4，a51，a52 和 a6 为惩罚因子。
481
第 6 期 张国梁等: 基于分组降维规则和遗传算法的人造板材矩形件优化下料方法
4 计算实例
试验数据来源于上海跃通木工机械设备有限公
司在数控板材开料锯研发过程中所做板材锯切试
验，基材板长 2 440 mm，宽 1 220 mm，排样矩形件共
有 6 种，数量和尺寸见表 1。
表 1 排样矩形件数据
Tab． 1 Data of rectangular parts
编号
Number
数量
Quantity
长
Length /mm
宽
Width /mm
1 11 210 140
2 22 200 150
3 28 240 170
4 20 320 220
5 16 260 160
6 7 320 140
根据分组降维规则，排样矩形件分为 2 组，分组
方式见表 2。
表 2 矩形件分组方式
Tab． 2 Grouping of rectangular parts
组号
Group
零件编号
No．
数量
Quantity
4 20
1 6 7
5 16
3 28
2 2 22
1 11
惩罚因子取为: 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)。
虽然本文实例表明了单独使用遗传算法的有效性，
但与其他算法的结合研究也是本文下一步需要探索
和试验的问题。
从试验结果来看，本文所给出的排样方案每一
行只排样一种零件，由于零件规格一致，因此开料锯
在锯切过程中完全满足“一刀切”的锯切要求，这种
581
林 业 科 学 50 卷
排样方案使数控开料锯的编程相对容易。从图 4 可
以看出，当排样零件面积总和相比于基材尺寸较小
时，遗传算法给出的排样方案存在较大的空白区域，
如图 4 中的“Null”区域。这一空白区域可以作为另
一基材用于排样面积较小的矩形零件，这也表明本
文所用基材尺寸并不唯一。
本文分组降维启发式规则是以面积大小排序，
这种规则对于长宽比相差不大的矩形零件分组排样
是十分有效的，但是针对矩形零件的长宽比很大的
情况，不应单独使用面积去排序，长宽比也应是另一
考虑因素，或者将长宽比很大的零件组合，在考虑锯
路损失的基础上作为一个零件参与排样。
参 考 文 献
曹 炬，冯 松 ． 1999．遗传算法在矩形件优化排样中的应用 ．计算机
工程与应用，(5) :5 － 7，10．
陈江义，宋雪枫，张明伟 ． 2011．融合蚁群算法和遗传算法的矩形件排
样问题研究 ．郑州大学学报: 理学版，43(2) :79 － 82．
高乐文 ． 2010．基于遗传蚁群算法的优化下料方法的研究与实现 ． 哈
尔滨:东北林业大学博士学位论文 ．
黄 岚，齐 季，谭 颖，等 ． 2012．一种求解矩形排样问题的遗传 －
离散粒子群优化算法 ．电子学报，40(6) :1103 － 1107．
季 君，陆一平，查建中，等 ． 2012．生成矩形毛坯最优两段排样方式
的确定型算法 ．计算机学报，35(1) :183 － 191．
蒋兴波，吕肖庆，刘成城 ． 2008．求解矩形件优化排样的自适应模拟退
火遗传 算 法 ． 计 算 机 辅 助 设 计 与 图 形 学 学 报，20 ( 11 ) :
1625 － 1631．
卢开澄 ． 1998．组合数学算法与分析 (下) ． 北京:清华大学出版社，
312 － 370．
骆志高，王 洋，李 举，等 ． 2009． 遗传算法与惩罚函数法在辗轧成
形工 艺 参 数 优 化 中 的 应 用 ． 中 国 机 械 工 程， 20 ( 14 ) :
1704 － 1707．
马 炫，张亚龙 ． 2007．基于遗传算法的大规模矩形件优化排样 ． 智
能系统学报，2(5) :48 － 52．
吴杰君 ． 2004．板材下料优化排样系统研究与实现 ．合肥:合肥工业大
学硕士学位论文 ．
岳 琪 ． 2005．基于遗传退火算法板式家具大规模矩形件优化下料研
究 ．哈尔滨:东北林业大学博士学位论文 ．
张 波，孙自强 ． 2004．含约束条件遗传算法在连续催化重整优化操
作中的应用 ．华东理工大学学报，30(5) :564 － 566，575．
张文江 ． 1999．家具制造厂板材综合下料问题的研究 ． 林产工业，26
(4) :15 － 17．
Furini F，Malaguti E． 2013． Models for the two-dimensional two-stage
cutting stock problem with multiple stock size． Computers ＆
Operations Ｒesearch，40(8) : 1953 － 1962．
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．
(责任编辑 石红青)
681