張 雨，崔耀東，梁澤華

廣西大學(xué) 計(jì)算機(jī)與電子信息學(xué)院，南寧 530004

1 引言

在家具制造業(yè)和鋸木廠等企業(yè)中，經(jīng)常需要對木材進(jìn)行切割，對于將大塊矩形板材切割成不同規(guī)格的小矩形毛坯的下料問題的研究已經(jīng)比較成熟，然而對于剛砍伐的原始木材這一特殊下料問題的研究還較少。特殊下料問題的研究隨著科技的發(fā)展逐漸受到重視，它往往出現(xiàn)在某個(gè)行業(yè)內(nèi)或者某些行業(yè)的某個(gè)部門里，比如紙卷下料問題，硅鋼片下料問題等。

二維下料問題（Two-Dimensional Cutting Stock Problem，2DCSP）是一個(gè)組合優(yōu)化問題，它的解由若干個(gè)排樣圖組成。下料問題常用的求解算法有列生成算法[1-2]、順序啟發(fā)式算法（Sequential Heuristic Procedure，SHP）[3]以及智能算法[4-5]等。其中，SHP算法簡單明了、易于實(shí)現(xiàn)且計(jì)算速度快，但是存在局部最優(yōu)的問題。為了解決這個(gè)問題，Belov等人提出了將價(jià)值校正和SHP結(jié)合的SVC（Sequential Value Correction）[6-7]算法，有效地避免局部最優(yōu)的問題。

本文采用SVC框架和動(dòng)態(tài)規(guī)劃[8-10]算法求解圓木二維下料問題。通過求解普通的二維背包和特殊的一維背包問題求出單個(gè)排樣圖，而文獻(xiàn)[11]則采用遺傳算法和模擬退火等智能算法來求解，通過遺傳變異來達(dá)到下料的多樣性，但是該算法的實(shí)現(xiàn)比本文算法復(fù)雜，并且需要用商業(yè)軟件CPLEX求解，不利于推廣應(yīng)用。

2 下料問題的模型

從n種圓木上切割m種矩形毛坯（如圖1）。圓木直徑為Dj、供應(yīng)量為Qj，j=1,2,…,n；矩形毛坯寬為wi、高為hi、需求量為bi，i=1,2,…,m。要求在滿足毛坯需求量的情況下，使圓木的使用量最小，即材料利用率最高。

圖1 圓木的切割方式

3 算法實(shí)現(xiàn)

順序啟發(fā)式算法是順序生成下料方案中的排樣圖，但是存在局部最優(yōu)解的問題，而SVC算法能夠很好地解決這個(gè)問題，該算法通過多次迭代生成多個(gè)下料方案，選擇其中最好的一個(gè)方案；順序生成當(dāng)前下料方案中各個(gè)排樣圖，每生成一個(gè)排樣圖就調(diào)整該排樣圖中使用的毛坯的價(jià)值，以實(shí)現(xiàn)下料方案的多樣性，方便優(yōu)選。

SVC算法求解圓木下料問題所涉及的符號如下：

G：表示當(dāng)前下料方案的迭代次數(shù)，初始值為1。

Gmax：表示下料方案迭代次數(shù)的最大值，本文設(shè)定其值為20。

C：C=c1,c2,…,cm，其中ci為毛坯i的價(jià)值，其初始值為毛坯的面積。

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

A：A=a1,a2,…,am，其中ai為排樣圖中排入的毛坯i的數(shù)量。

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

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

f：當(dāng)前排樣圖的最大使用次數(shù)。

3.1 生成圓木下料方案

圓木下料方案的求解過程有如下幾個(gè)步驟，其中排樣圖的生成函數(shù)getPattern（）和毛坯的價(jià)值校正函數(shù)correctValue（）將分別在3.2節(jié)和3.3節(jié)中介紹。

步驟1令G的初始值為1，初始化ci(i=1,2,…,m)為毛坯i的面積。

步驟2如果G=Gmax則轉(zhuǎn)步驟8；否則G=G+1，令ri=bi(i=1,2,…,m)以初始化毛坯的剩余量為其原始需求量，令qj=Qj(j=1,2,…,n)以初始化圓木的剩余量為其原始供應(yīng)量。

步驟3調(diào)用CorrectValue（）生成排樣圖，并且將該排樣圖所選擇的圓木種類記錄為j。

步驟4將排樣圖加入到當(dāng)前的下料方案中，令 f=更新剩余的毛坯需求ri=ri-fai,i=1,2,…,m，更新圓木的供應(yīng)量qj=qj-f。

步驟5調(diào)用價(jià)值校正函數(shù)CorrectValue（）修正當(dāng)前排樣圖中所含毛坯的價(jià)值。

步驟6如果毛坯的剩余需求不全為零，轉(zhuǎn)步驟3。

步驟7若當(dāng)前下料方案的材料利用率比最好下料方案的材料利用率高，則將當(dāng)前下料方案記為最好下料方案。轉(zhuǎn)步驟2。

步驟8輸出最好的下料方案。

3.2 getPattern（）函數(shù)

圖2 圓木的區(qū)域劃分

對于區(qū)域A通過求解有界二維背包確定該部分的排樣方式，優(yōu)化目標(biāo)是使該區(qū)域價(jià)值（指所含毛坯的總價(jià)值）最大，并且該部分的毛坯數(shù)量不能超出毛坯的剩余需求量。建立平面直角坐標(biāo)系，原點(diǎn)位于區(qū)域A左上角，X軸水平向右，Y軸豎直向下。用F(x,y)表示寬x高y的子板的價(jià)值。如圖3所示，該部分可按水平放置一排（圖3（a））或豎直放置一列（圖3（b））第 i種毛坯。圖中F(x,y-hi)和F(x-wi,y)表示未添加第i種毛坯時(shí)的價(jià)值，kxi表示水平放置時(shí)最多能放入第i種毛坯的數(shù)量；kyi表示縱向放置時(shí)最多能放入第i種毛坯的數(shù)量；kxivi和kyivi分別表示水平放置時(shí)第i種毛坯的總價(jià)值和縱向放置時(shí)第i種毛坯的總價(jià)值；在兩種放置方式中，選擇使價(jià)值F(x,y)較大的那種放置方式。

圖3 中間部分毛坯的放置方式

當(dāng)中間區(qū)域確定之后，對于剩下的4個(gè)側(cè)面部分，可通過直角三角形求解各區(qū)域的底邊長度和高度，如圖4所示（其中虛線矩形長xA寬yA，表示原來的中心區(qū)域）。區(qū)域B的大小不調(diào)整，它的底邊ac的長為xA，高h(yuǎn)B為；區(qū)域C的高h(yuǎn)C為(yA-yF)，底邊dg的長為區(qū)域D

公式（1）的含義：初始化子板 x#y(寬#高)的價(jià)值F(x,y)為兩塊較小子板x#(y-1)和(x-1)#y中價(jià)值較大者，然后依次考慮每種毛坯以改善該子板的解。對于第i種毛坯，需要考察圖3所示兩種放置方式。若采用圖3（a）的水平放置方式，相當(dāng)于在子板x#(y-hi)的下面拼接了一個(gè)寬x高h(yuǎn)i的矩形，其中含第i種毛坯kxi個(gè)，拼接后對應(yīng)子板x#y的價(jià)值為若采用圖3（b）的豎直放置方式，相當(dāng)于在子板(x-wi)#y的右邊拼接了一個(gè)寬wi高y的矩形，其中含第i種毛坯 kyi個(gè)，拼接后對應(yīng)子板 x#y的價(jià)值為 kyivi+

用traceBack(x,y)來記錄中間區(qū)域毛坯的放置方式以便回退畫出排樣圖，當(dāng)圖3中水平放入一排第i種毛坯時(shí)，traceBack(x,y)=i，豎直放入一排第i種毛坯時(shí)，traceBack(x,y)=-i，否則traceBack(x,y)=0。根據(jù) traceBack(x,y)的值回退，令 x=xA,y=yA，則：（1）當(dāng)traceBack(x,y)=0并且 F(x-1,y)小于 F(x,y-1)則 y=y-1；（2）當(dāng) traceBack(x,y)=0并且 F(x-1,y)大于 F(x,y-1)則 x=x-1，重復(fù)（1）、（2）這兩個(gè)步驟直到traceBack(x,y)的值不為0，將對應(yīng)x和y的值分別記為該區(qū)域?qū)嶋H占用的寬度xF和實(shí)際占用的高度yF。的高h(yuǎn)D為，底邊ae的長為yF；區(qū)域E高h(yuǎn)E為，底邊bf的長為yF。對于這4個(gè)部分采用特殊的一維背包求解出該部分的排樣方式。其求解的遞推公式類似，因此只對其中區(qū)域E的求解進(jìn)行說明，因?yàn)樵搮^(qū)域具有概括性，其他區(qū)域可視為該區(qū)域的特殊情況。個(gè)數(shù)，則kEivi為所拼接的這一排毛坯的總價(jià)值。定義集 合當(dāng)y＞0時(shí)，確定子板xE@y之價(jià)值的遞推公式如下，邊界條件為FE(0)=0，y=0,1,…,hE。

圖4 側(cè)面的底邊和高

公式（2）的含義：初始化子板材xE@y（下底邊@高）的價(jià)值FE(y)為FE(y-1)，然后依次考慮每種毛坯以改善該子板的解。如圖5所示，相當(dāng)于在子板材xE@(y-hi)的上面拼接了一個(gè)高為hi，寬為x的矩形，其中含第i種毛坯kEi個(gè)，拼接了之后對應(yīng)子板材xE@y的價(jià)值為

該部分毛坯只采用豎直放置的方式。如圖5所示，建立平面直角坐標(biāo)系，原點(diǎn)位于E區(qū)域的點(diǎn)b，X軸為邊bf的方向，Y軸為與邊bf相垂直的方向，并將該區(qū)域逆時(shí)針旋轉(zhuǎn)90°。對于類似于金字塔形狀的子板，用FE(y)表示高度為y時(shí)的價(jià)值，該子板上底邊的寬度x可根據(jù)子板的高度y計(jì)算出來，用kEi表示拼接毛坯的

圖5 右側(cè)面毛坯的放置方式

getPattern（）函數(shù)求解圓木排樣圖的過程，可以通過一個(gè)完整的框架圖來表示，如圖6。

3.3 correctValue（）函數(shù)

雖然SHP算法簡單明了、易于實(shí)現(xiàn)且計(jì)算速度快，但算法存在局部最優(yōu)的問題，它容易使得好的排樣圖在前面出現(xiàn)，從而導(dǎo)致后面的排樣圖的材料利用率偏低的情況。為了解決這個(gè)問題，SVC框架將在生成一個(gè)排樣圖之后，就根據(jù)當(dāng)前排樣圖使用的毛坯種類以及數(shù)量等相關(guān)信息，調(diào)整毛坯的價(jià)值，使得毛坯的價(jià)值趨于合理，從而跳出局部最優(yōu)。由于較大面積的毛坯會(huì)不利于組合，因此對于面積較大的毛坯會(huì)適當(dāng)調(diào)大它的價(jià)值，使得它的需求優(yōu)先被滿足，具體的毛坯價(jià)值校正公式[12]如下：

圖6 getPattern（）函數(shù)的框架

公式（3）中 g1的范圍為[0，1]的任意實(shí)數(shù)，g2=1-g1，p則略大于1。公式（4）中si=wihi，U 為排樣方式的利用率。

4 實(shí)驗(yàn)計(jì)算

本文算法采用C#實(shí)現(xiàn)，實(shí)驗(yàn)平臺(tái)為Win10操作系統(tǒng)，實(shí)驗(yàn)使用的計(jì)算機(jī)配置為i5，主頻為3.2 GHz，內(nèi)存為8 GB，實(shí)驗(yàn)所使用的參數(shù)g1=0.2，p=1.3。

由于圓木二維下料問題的研究很少，因此，本文隨機(jī)采取8道例題進(jìn)行測試并與SHP算法的實(shí)驗(yàn)結(jié)果進(jìn)行對比。其中圓木的種類n∈[1,8]，每種圓木的供應(yīng)量Qj∈[10,200]，圓木的直徑 Dj∈[300,600]，毛坯的種類m∈[6,20]，毛坯的需求量bi∈[20,1 000]。

算法測試結(jié)果如表1所示，其中u表示廢料率，實(shí)驗(yàn)結(jié)果表明，SVC算法能較好地提高圓木的利用率，其中SVC算法的平均計(jì)算時(shí)間為282 s，而SHP算法的平均計(jì)算時(shí)間為38 s，比本文的算法的時(shí)間要少，但是對于實(shí)際應(yīng)用而言，本文算法的計(jì)算時(shí)間是合理的。本文算法的時(shí)間消耗主要是中間區(qū)域布局的計(jì)算，其時(shí)間的復(fù)雜度為O(L×W×m)，其中L與W分別為中間區(qū)域的高度和寬度，m為毛坯的種數(shù)。

表1 8道例題測試結(jié)果

表2和表3分別給出了第一道例題所使用的圓木的種類與供應(yīng)量和毛坯的尺寸以及需求量。圖7是本文算法生成的第一個(gè)例題的下料方案，一共包含8個(gè)排樣圖，每個(gè)排樣圖左面的一串文本從左往右依次是圓木的ID號，圓木的直徑以及圓木的使用數(shù)量。

表2 第一道例題的毛坯數(shù)據(jù)

表3 第一道例題的圓木數(shù)據(jù)

圖7 第一道例題的下料方案

與智能算法方面的比較，已有的研究結(jié)果表明，和智能算法相比（文獻(xiàn)[11]就是智能算法），用基于SVC技術(shù)的算法求解下料或裝箱問題，通常能夠收到更好的效果。例如，文獻(xiàn)[13]中求解線材下料問題，證實(shí)SVC算法比文獻(xiàn)[14]中的智能算法效果好；文獻(xiàn)[12]中求解二維下料/裝箱問題，證實(shí)SVC算法比文獻(xiàn)[15]中的智能算法效果好。因此，基于SVC技術(shù)求解圓木下料問題，是一個(gè)值得研究的課題，本文對該問題做了開創(chuàng)性的探索。此外，基于SVC技術(shù)的算法實(shí)現(xiàn)比較簡單，能夠更容易地處理實(shí)際下料工藝的約束，有利于工程方面的推廣應(yīng)用。

5 結(jié)束語

本文基于SVC與動(dòng)態(tài)規(guī)劃技術(shù)求解圓木二維下料問題，采用順序啟發(fā)式算法和價(jià)值校正策略相結(jié)合的方式來生成下料方案，能較好地避免陷入局部最優(yōu)，得到材料利用率較高的下料方案。本文的算法實(shí)現(xiàn)比較簡單，而且與SHP算法相比能有效地提高材料利用率。將圓木的彎曲的情況考慮，可作為今后的一個(gè)研究方向。