多尺寸圓木二維下料問題研究

張 雨，崔耀東，梁澤華

廣西大學 計算機與電子信息學院，南寧 530004

1 引言

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

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

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

2 下料問題的模型

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

圖1 圓木的切割方式

3 算法實現(xiàn)

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

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

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

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

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

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：當前排樣圖的最大使用次數(shù)。

3.1 生成圓木下料方案

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

步驟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調(diào)用CorrectValue（）生成排樣圖，并且將該排樣圖所選擇的圓木種類記錄為j。

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

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

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

步驟7若當前下料方案的材料利用率比最好下料方案的材料利用率高，則將當前下料方案記為最好下料方案。轉步驟2。

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

3.2 getPattern（）函數(shù)

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

對于區(qū)域A通過求解有界二維背包確定該部分的排樣方式，優(yōu)化目標是使該區(qū)域價值（指所含毛坯的總價值）最大，并且該部分的毛坯數(shù)量不能超出毛坯的剩余需求量。建立平面直角坐標系，原點位于區(qū)域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種毛坯的數(shù)量；kyi表示縱向放置時最多能放入第i種毛坯的數(shù)量；kxivi和kyivi分別表示水平放置時第i種毛坯的總價值和縱向放置時第i種毛坯的總價值；在兩種放置方式中，選擇使價值F(x,y)較大的那種放置方式。

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

當中間區(qū)域確定之后，對于剩下的4個側面部分，可通過直角三角形求解各區(qū)域的底邊長度和高度，如圖4所示（其中虛線矩形長xA寬yA，表示原來的中心區(qū)域）。區(qū)域B的大小不調(diào)整，它的底邊ac的長為xA，高hB為；區(qū)域C的高hC為(yA-yF)，底邊dg的長為區(qū)域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)來記錄中間區(qū)域毛坯的放置方式以便回退畫出排樣圖，當圖3中水平放入一排第i種毛坯時，traceBack(x,y)=i，豎直放入一排第i種毛坯時，traceBack(x,y)=-i，否則traceBack(x,y)=0。根據(jù) 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的值分別記為該區(qū)域實際占用的寬度xF和實際占用的高度yF。的高hD為，底邊ae的長為yF；區(qū)域E高hE為，底邊bf的長為yF。對于這4個部分采用特殊的一維背包求解出該部分的排樣方式。其求解的遞推公式類似，因此只對其中區(qū)域E的求解進行說明，因為該區(qū)域具有概括性，其他區(qū)域可視為該區(qū)域的特殊情況。個數(shù)，則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區(qū)域的點b，X軸為邊bf的方向，Y軸為與邊bf相垂直的方向，并將該區(qū)域逆時針旋轉90°。對于類似于金字塔形狀的子板，用FE(y)表示高度為y時的價值，該子板上底邊的寬度x可根據(jù)子板的高度y計算出來，用kEi表示拼接毛坯的

圖5 右側面毛坯的放置方式

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

3.3 correctValue（）函數(shù)

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

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

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

4 實驗計算

本文算法采用C#實現(xiàn)，實驗平臺為Win10操作系統(tǒng)，實驗使用的計算機配置為i5，主頻為3.2 GHz，內(nèi)存為8 GB，實驗所使用的參數(shù)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，比本文的算法的時間要少，但是對于實際應用而言，本文算法的計算時間是合理的。本文算法的時間消耗主要是中間區(qū)域布局的計算，其時間的復雜度為O(L×W×m)，其中L與W分別為中間區(qū)域的高度和寬度，m為毛坯的種數(shù)。

表1 8道例題測試結果

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

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

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

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

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

5 結束語

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