多尺寸圆木二维下料问题研究

张 雨，崔耀东，梁泽华

广西大学 计算机与电子信息学院，南宁 530004

1 引言

在家具制造业和锯木厂等企业中，经常需要对木材进行切割，对于将大块矩形板材切割成不同规格的小矩形毛坯的下料问题的研究已经比较成熟，然而对于刚砍伐的原始木材这一特殊下料问题的研究还较少。特殊下料问题的研究随着科技的发展逐渐受到重视，它往往出现在某个行业内或者某些行业的某个部门里，比如纸卷下料问题，硅钢片下料问题等。

二维下料问题（Two-Dimensional Cutting Stock Problem，2DCSP）是一个组合优化问题，它的解由若干个排样图组成。下料问题常用的求解算法有列生成算法[1-2]、顺序启发式算法（Sequential Heuristic Procedure，SHP）[3]以及智能算法[4-5]等。其中，SHP算法简单明了、易于实现且计算速度快，但是存在局部最优的问题。为了解决这个问题，Belov等人提出了将价值校正和SHP结合的SVC（Sequential Value Correction）[6-7]算法，有效地避免局部最优的问题。

本文采用SVC框架和动态规划[8-10]算法求解圆木二维下料问题。通过求解普通的二维背包和特殊的一维背包问题求出单个排样图，而文献[11]则采用遗传算法和模拟退火等智能算法来求解，通过遗传变异来达到下料的多样性，但是该算法的实现比本文算法复杂，并且需要用商业软件CPLEX求解，不利于推广应用。

2 下料问题的模型

从n种圆木上切割m种矩形毛坯（如图1）。圆木直径为Dj、供应量为Qj，j=1,2,…,n；矩形毛坯宽为wi、高为hi、需求量为bi，i=1,2,…,m。要求在满足毛坯需求量的情况下，使圆木的使用量最小，即材料利用率最高。

图1 圆木的切割方式

3 算法实现

顺序启发式算法是顺序生成下料方案中的排样图，但是存在局部最优解的问题，而SVC算法能够很好地解决这个问题，该算法通过多次迭代生成多个下料方案，选择其中最好的一个方案；顺序生成当前下料方案中各个排样图，每生成一个排样图就调整该排样图中使用的毛坯的价值，以实现下料方案的多样性，方便优选。

SVC算法求解圆木下料问题所涉及的符号如下：

G：表示当前下料方案的迭代次数，初始值为1。

Gmax：表示下料方案迭代次数的最大值，本文设定其值为20。

C：C=c1,c2,…,cm，其中ci为毛坯i的价值，其初始值为毛坯的面积。

R：R=r1,r2,…,rm，其中ri为毛坯i的剩余需求量。

A：A=a1,a2,…,am，其中ai为排样图中排入的毛坯i的数量。

B：B=b1,b2,…,bm，其中bi为毛坯i的需求量。

Q：Q=q1,q2,…,qn，其中qi为圆木i的剩余量。

f：当前排样图的最大使用次数。

3.1 生成圆木下料方案

圆木下料方案的求解过程有如下几个步骤，其中排样图的生成函数getPattern（）和毛坯的价值校正函数correctValue（）将分别在3.2节和3.3节中介绍。

步骤1令G的初始值为1，初始化ci(i=1,2,…,m)为毛坯i的面积。

步骤2如果G=Gmax则转步骤8；否则G=G+1，令ri=bi(i=1,2,…,m)以初始化毛坯的剩余量为其原始需求量，令qj=Qj(j=1,2,…,n)以初始化圆木的剩余量为其原始供应量。

步骤3调用CorrectValue（）生成排样图，并且将该排样图所选择的圆木种类记录为j。

步骤4将排样图加入到当前的下料方案中，令 f=更新剩余的毛坯需求ri=ri-fai,i=1,2,…,m，更新圆木的供应量qj=qj-f。

步骤5调用价值校正函数CorrectValue（）修正当前排样图中所含毛坯的价值。

步骤6如果毛坯的剩余需求不全为零，转步骤3。

步骤7若当前下料方案的材料利用率比最好下料方案的材料利用率高，则将当前下料方案记为最好下料方案。转步骤2。

步骤8输出最好的下料方案。

3.2 getPattern（）函数

图2 圆木的区域划分

对于区域A通过求解有界二维背包确定该部分的排样方式，优化目标是使该区域价值（指所含毛坯的总价值）最大，并且该部分的毛坯数量不能超出毛坯的剩余需求量。建立平面直角坐标系，原点位于区域A左上角，X轴水平向右，Y轴竖直向下。用F(x,y)表示宽x高y的子板的价值。如图3所示，该部分可按水平放置一排（图3（a））或竖直放置一列（图3（b））第 i种毛坯。图中F(x,y-hi)和F(x-wi,y)表示未添加第i种毛坯时的价值，kxi表示水平放置时最多能放入第i种毛坯的数量；kyi表示纵向放置时最多能放入第i种毛坯的数量；kxivi和kyivi分别表示水平放置时第i种毛坯的总价值和纵向放置时第i种毛坯的总价值；在两种放置方式中，选择使价值F(x,y)较大的那种放置方式。

图3 中间部分毛坯的放置方式

当中间区域确定之后，对于剩下的4个侧面部分，可通过直角三角形求解各区域的底边长度和高度，如图4所示（其中虚线矩形长xA宽yA，表示原来的中心区域）。区域B的大小不调整，它的底边ac的长为xA，高hB为；区域C的高hC为(yA-yF)，底边dg的长为区域D

公式（1）的含义：初始化子板 x#y(宽#高)的价值F(x,y)为两块较小子板x#(y-1)和(x-1)#y中价值较大者，然后依次考虑每种毛坯以改善该子板的解。对于第i种毛坯，需要考察图3所示两种放置方式。若采用图3（a）的水平放置方式，相当于在子板x#(y-hi)的下面拼接了一个宽x高hi的矩形，其中含第i种毛坯kxi个，拼接后对应子板x#y的价值为若采用图3（b）的竖直放置方式，相当于在子板(x-wi)#y的右边拼接了一个宽wi高y的矩形，其中含第i种毛坯 kyi个，拼接后对应子板 x#y的价值为 kyivi+

用traceBack(x,y)来记录中间区域毛坯的放置方式以便回退画出排样图，当图3中水平放入一排第i种毛坯时，traceBack(x,y)=i，竖直放入一排第i种毛坯时，traceBack(x,y)=-i，否则traceBack(x,y)=0。根据 traceBack(x,y)的值回退，令 x=xA,y=yA，则：（1）当traceBack(x,y)=0并且 F(x-1,y)小于 F(x,y-1)则 y=y-1；（2）当 traceBack(x,y)=0并且 F(x-1,y)大于 F(x,y-1)则 x=x-1，重复（1）、（2）这两个步骤直到traceBack(x,y)的值不为0，将对应x和y的值分别记为该区域实际占用的宽度xF和实际占用的高度yF。的高hD为，底边ae的长为yF；区域E高hE为，底边bf的长为yF。对于这4个部分采用特殊的一维背包求解出该部分的排样方式。其求解的递推公式类似，因此只对其中区域E的求解进行说明，因为该区域具有概括性，其他区域可视为该区域的特殊情况。个数，则kEivi为所拼接的这一排毛坯的总价值。定义集 合当y＞0时，确定子板xE@y之价值的递推公式如下，边界条件为FE(0)=0，y=0,1,…,hE。

图4 侧面的底边和高

公式（2）的含义：初始化子板材xE@y（下底边@高）的价值FE(y)为FE(y-1)，然后依次考虑每种毛坯以改善该子板的解。如图5所示，相当于在子板材xE@(y-hi)的上面拼接了一个高为hi，宽为x的矩形，其中含第i种毛坯kEi个，拼接了之后对应子板材xE@y的价值为

该部分毛坯只采用竖直放置的方式。如图5所示，建立平面直角坐标系，原点位于E区域的点b，X轴为边bf的方向，Y轴为与边bf相垂直的方向，并将该区域逆时针旋转90°。对于类似于金字塔形状的子板，用FE(y)表示高度为y时的价值，该子板上底边的宽度x可根据子板的高度y计算出来，用kEi表示拼接毛坯的

图5 右侧面毛坯的放置方式

getPattern（）函数求解圆木排样图的过程，可以通过一个完整的框架图来表示，如图6。

3.3 correctValue（）函数

虽然SHP算法简单明了、易于实现且计算速度快，但算法存在局部最优的问题，它容易使得好的排样图在前面出现，从而导致后面的排样图的材料利用率偏低的情况。为了解决这个问题，SVC框架将在生成一个排样图之后，就根据当前排样图使用的毛坯种类以及数量等相关信息，调整毛坯的价值，使得毛坯的价值趋于合理，从而跳出局部最优。由于较大面积的毛坯会不利于组合，因此对于面积较大的毛坯会适当调大它的价值，使得它的需求优先被满足，具体的毛坯价值校正公式[12]如下：

图6 getPattern（）函数的框架

公式（3）中 g1的范围为[0，1]的任意实数，g2=1-g1，p则略大于1。公式（4）中si=wihi，U 为排样方式的利用率。

4 实验计算

本文算法采用C#实现，实验平台为Win10操作系统，实验使用的计算机配置为i5，主频为3.2 GHz，内存为8 GB，实验所使用的参数g1=0.2，p=1.3。

由于圆木二维下料问题的研究很少，因此，本文随机采取8道例题进行测试并与SHP算法的实验结果进行对比。其中圆木的种类n∈[1,8]，每种圆木的供应量Qj∈[10,200]，圆木的直径 Dj∈[300,600]，毛坯的种类m∈[6,20]，毛坯的需求量bi∈[20,1 000]。

算法测试结果如表1所示，其中u表示废料率，实验结果表明，SVC算法能较好地提高圆木的利用率，其中SVC算法的平均计算时间为282 s，而SHP算法的平均计算时间为38 s，比本文的算法的时间要少，但是对于实际应用而言，本文算法的计算时间是合理的。本文算法的时间消耗主要是中间区域布局的计算，其时间的复杂度为O(L×W×m)，其中L与W分别为中间区域的高度和宽度，m为毛坯的种数。

表1 8道例题测试结果

表2和表3分别给出了第一道例题所使用的圆木的种类与供应量和毛坯的尺寸以及需求量。图7是本文算法生成的第一个例题的下料方案，一共包含8个排样图，每个排样图左面的一串文本从左往右依次是圆木的ID号，圆木的直径以及圆木的使用数量。

表2 第一道例题的毛坯数据

表3 第一道例题的圆木数据

图7 第一道例题的下料方案

与智能算法方面的比较，已有的研究结果表明，和智能算法相比（文献[11]就是智能算法），用基于SVC技术的算法求解下料或装箱问题，通常能够收到更好的效果。例如，文献[13]中求解线材下料问题，证实SVC算法比文献[14]中的智能算法效果好；文献[12]中求解二维下料/装箱问题，证实SVC算法比文献[15]中的智能算法效果好。因此，基于SVC技术求解圆木下料问题，是一个值得研究的课题，本文对该问题做了开创性的探索。此外，基于SVC技术的算法实现比较简单，能够更容易地处理实际下料工艺的约束，有利于工程方面的推广应用。

5 结束语

本文基于SVC与动态规划技术求解圆木二维下料问题，采用顺序启发式算法和价值校正策略相结合的方式来生成下料方案，能较好地避免陷入局部最优，得到材料利用率较高的下料方案。本文的算法实现比较简单，而且与SHP算法相比能有效地提高材料利用率。将圆木的弯曲的情况考虑，可作为今后的一个研究方向。