基于VNABC 的多規格板材二維下料問題

蘇 俊， 徐震浩， 顧幸生

（華東理工大學能源化工過程智能制造教育部重點實驗室, 上海 200237）

實現資源高效利用是綠色制造的重要課題，也是可持續發展的關鍵要素。制造業中的二維下料問題廣泛存在于玻璃、木材、皮革、鋼板等制造過程中。優化的下料方案能夠有效地提高原料利用率，對降低生產成本、提高企業競爭力具有重要的意義。

二維下料問題（Two-Dimensional Cutting Stock Problem，2DCSP）在實際生產中的應用范圍廣，求解難度大，許多學者進行了大量研究。Clautiaux 等[1]研究了二維斷頭臺切割庫存問題中的單批次問題，提出一種基于列生成的潛水啟發式方法，使用動態規劃解決定價問題，同時利用部分枚舉技術減少動態程序解空間中非正確模式的數量。Wang 等[2]針對允許刮削并考慮設置成本的2DCSP，建立了整數規劃模型并使用了列和行生成算法，提出一種基于匹配級別的潛水啟發式算法。Kwon 等[3]針對二維兩階段直線切割下料問題，提出了基于模式的模型并分析了全模式模型和階段模式模型的列生成問題。上述研究的背景是單一板材且毛坯數量為單個，而實際生產中板材規格多樣且毛坯較多。Supphakorn 等[4]考慮固定大小的可用余料，研究了具有多種庫存的二維兩階段切割庫存問題(2D-2CP)，應用色譜柱生成技術試圖找到一種使總浪費最小化的解決方案。Fabio 等[5]研究了具有不同可用庫存且必須通過兩階段斷頭臺切割的二維下料問題，提出并比較了3 種混合整數規劃模型。Jin 等[6]針對庫存多樣且有缺陷的二維斷頭臺切割問題，提出了一種新的基于樹的兩部分啟發式算法。吳電建等[7]針對多規格、大批量的矩形件優化下料問題，提出了一種基于候選板條和連續啟發式算法的面向可加工性的二維下料方法。楊威等[8]對大規模矩形零件在板材上的下料問題設計了基于剩余矩形匹配算法的遺傳算法（LRFGA）。人工蜂群算法(Artificial Bee Colony Algorithm,ABC)是Dervis[9]于2005 年提出的一種智能算法，它具有結構簡單、尋優能力強等優點，被廣泛應用于各種工程領域，如電力系統、無人機軌跡規劃、生產調度等。Bahriye 等[10]提出改進的MRABC 算法，引入了振動頻率MR 以及變化的振動幅度SF，增強了算法的收斂能力。劉東林等[11]提出了基于花香濃度的人工蜂群算法（FABC），在傳統的人工蜂群算法中加入了步長和視野范圍這兩個因素提升求解精度，并在偵查蜂階段提出了花香濃度機制，避免陷入局部最優，提高收斂速度。

本文針對板材規格多樣、毛坯規格多樣且數量龐大的多規格板材二維下料問題，將下料過程分解成規整和非規整兩個階段，其中規整階段提出組合塊和零散塊兩種處理方法；并針對問題特點提出了一種變鄰域人工蜂群算法（Variable Neighborhood Artificial Bee Colony Algorithm，VNABC）來求解優化模型。

1 模 型

多規格板材二維下料問題可以描述為：m種不同規格的板材，第i種規格板材用Pi表示，i∈I,I={1,2,···,m}。Pi的寬度為Wi，高度為Hi。k種不同規格的毛坯，第j種規格的毛坯用Rj表示，j∈J,J={1,2,···,k}。Rj的寬度為wj，高度為hj，需求量為cj。要求在不同規格的板材上下料給定數量的毛坯，下料時毛坯可以旋轉90°，尋找合適的下料方案使所消耗的板材浪費率最低。

存在如下假設：不同規格的板材種類相同，數量不限；毛坯能在任意規格板材上下料；下料過程中毛坯從板材左下角開始下料，先向上疊加，再向右延伸；毛坯在板材上下料時只能90°旋轉。

1.1 決策變量

決策變量如下：Ni：板材i的投入數量； λi,a,j,b：二進制變量，表示第a塊Pi上第b塊Rj的擺放，0 表示橫放，1 表示豎放；X1i,a,j,b：第a塊Pi上第b塊Rj左下角的橫坐標；Y1i,a,j,b：第a塊Pi上第b塊Rj左下角的縱坐標；X2i,a,j,b：第a塊Pi上第b塊Rj右上角的橫坐標；Y2i,a,j,b：第a塊Pi上第b塊Rj右上角的縱坐標；ni,a,j：第a塊Pi上Rj的數量； tls ：板材的修剪損失。

1.2 約束

任意毛坯尺寸均小于所有板材尺寸。式(1)表示毛坯的高度不超過任意板材的高度，式(2)表示毛坯的寬度不超過任意板材的高度，式(3)和式(4)分別表示毛坯的高度、寬度不超過任意板材的寬度。

毛坯在板材上的位置與其擺放方式有關。式(5)和式(6)表明毛坯右上角坐標與毛坯左下角坐標的關系。

毛坯在板材上進行下料時，所有毛坯均應在板材的內部，不能超過板材的尺寸。式(7)和式(8)將毛坯的坐標約束在板材范圍內。

式(9)表示該板材上所有毛坯面積之和不能大于該板材的面積。

式(10)表示在同一塊板材上進行下料的任意兩個毛坯不能重疊。假設有兩個毛坯R1 和R2，R1 在R2 的左下方，它們的左下角坐標分別為 (X1,Y1) 和(X1′,Y1′)，右上角坐標分別為 (X2,Y2) 和 (X2′,Y2′) ，則R1、R2 必須滿足X2 ≤X1′或Y2 ≤Y1′才能保證兩者不重疊。

式(11)表示每種毛坯的下料數量必須滿足毛坯的需求量。

1.3 目標函數

以所消耗板材的浪費率為優化目標，如式(12)所示。

2 VNABC 算法

ABC 算法模擬蜜蜂采蜜行為，3 種蜜蜂以及作用分別為：引領蜂負責采蜜和傳遞信息，并將食物源的信息共享；跟隨蜂獲得食物源信息后選擇一個較優的食物源采蜜；偵察蜂巡視所有食物源，一旦發現某個食物源枯竭，拋棄此食物源并尋找新的食物源。根據本文研究內容的特點，在ABC 算法的基礎上提出了VNABC 算法，對模型進行求解。

2.1 編 碼

針對多規格板材二維下料問題特點，將食物源設計成雙層。第1 層表示毛坯下料順序和擺放方式，正數表示橫放，負數表示豎放，數字絕對值代表毛坯類型。第2 層表示板材，與第1 層數字對應。圖1 所示的食物源中有5 種毛坯、2 種板材。毛坯的下料順序是R4、R1、R3、R5、R2，其中R2 豎放，其余毛坯橫放。其中R3 和R5 在P2 上下料，其余毛坯在P1 上下料。

圖1 食物源Fig.1 Food source

2.2 解 碼

食物源確定了每個毛坯對應的板材，根據該特點，設計兩種不同的解碼方案：（1）嚴格解碼STD(Strict Decoding)，毛坯只能下料到與之對應的板材上。例如圖1 中R3 只能在P2 上下料，不能下料到P1；（2）松弛解碼SLD(Slack Decoding)，如果上一塊板材剩余空間足夠，則將當前毛坯下料到上一塊板材上，否則在新的對應板材上下料。例如圖1 中，如果上一塊板材P1 能夠下料R3，則R3 優先在P1 上下料，若P1 無法下料，則R3 在新的P2 上下料。

整個下料過程分為規整階段和非規整階段。規整階段完成各規格毛坯主體下料任務，下料樣式規整。非規整階段下料剩余毛坯并且下料樣式非規整。解碼流程圖如圖2 所示。

圖2 解碼流程圖Fig.2 Flow chart of decode

2.2.1 規整階段 規整階段針對各規格毛坯設計了組合塊CB(Combination Block)和零散塊FB(Fragmentary Block)下料。對于某種毛坯，將板材高度方向上能夠下料該毛坯的最大數量稱為高度最大數量HMC。以HMC 個毛坯為一組向右連續下料，CB 就是由毛坯構成的矩形塊。

FB 可以由不同規格的毛坯組成。在圖3 中，當R3 所在的CB 下料結束，會產生上方余料EU（Empty Up），而R1 所在的CB 下料結束除了產生EU 外還會產生最右側余料ER（Empty Right），零散塊只能在EU 和ER 上下料。本文提出4 種零散塊下料策略，一個臺階最優OS（One Step Optimum）下料、兩個臺階最優TS（Two Step Optimum）下料、高度最優HO（Height Optimum）下料和寬度最優WO（Width Optimum）下料。以EU 為例，OS 下料策略為：首先針對EU 的最大高度，尋找可以放入的毛坯集合。在集合中尋找具有最大高度的毛坯，并從左向右依次填入EU 中，直到該高度的毛坯全部下料結束。如果右邊剩余空間寬度小于閾值，則停止；否則在集合中尋找具有第2 高度的毛坯，在該層重復上述下料過程。直至該層填充結束，更新余料高度，如果余料高度超過閾值，則重復上述步驟，否則停止下料。OS 下料EU 或ER 的每一層只出現2 種高度，類似一個臺階。

圖3 毛坯下料Fig.3 Roughcast cutting stock

TS 下料過程和OS 類似，考慮到計算時間成本，TS 在OS 基礎上對每一層余料多填充一次，因此每層最多出現3 種高度，類似兩個臺階。對于HO 下料，首先找出毛坯的最優組合來填充余料的高。接著盡量填充每一層，允許不同規格的毛坯存在，但是要求毛坯高度一致。WO 下料和HO 下料類似，不同的是WO 下料尋找毛坯最優組合填充余料的寬，并盡量填充每一列。

2.2.2 非規整階段 當規整階段結束仍存在剩余毛坯時，則進入非規整階段處理剩余毛坯，否則下料過程結束。由于規整階段已經下料了大多數毛坯，剩余毛坯不多，故采用BL 算法（Bottom Left Algorithm）[12]解決非規整階段下料問題。BL 算法的原理是毛坯每次從板材的右上角開始下料，不斷向下、向左嘗試移動，直到不能移動為止，期間該毛坯不能與其他毛坯重疊且不能越過板材的邊界。

非規整階段的下料需要考慮毛坯的下料順序和擺放，也是復雜的組合優化問題。從剩余毛坯中找出較優的下料順序和擺放時間成本太高，考慮到實際生產過程中的時間因素，非規整階段毛坯的下料順序和規整階段保持一致，擺放方式為橫放。

2.3 優化計算過程

針對雙層食物源，為引領蜂和跟隨蜂設計不同的鄰域搜索策略。偵察蜂負責全局搜索，避免算法陷入局部最優，拓展算法搜索廣度。

引領蜂鄰域搜索采用變步長逆序交換方案。假設當前迭代次數是i，總的迭代次數為c，食物源的維度是d，則變化片段 fragment 的長度 len 為floor(d×(1-i/c))。隨著i的增加， len 越來越小，有利于算法后期收斂。首先在區間 [0,d-1] 內產生一個隨機位置a，從該位置開始往后尋找一個長度為 len 的區間，如果位置a到食物源末端的長度小于 len ，則往前尋找，直到區間的長度達到 len 。接著生成一個[0,1]之間的隨機數r，如果r超過0.5，將變化區間所有的數字逆序，否則單點交換兩個隨機位置的數。最后，生成一個區間 [0,d-1] 內的隨機位置，將該位置的元素乘以-1，表示毛坯旋轉90°。

跟隨蜂的鄰域搜索采用比例加一方案。假設食物源維度為d，板材種類數量為m，則需要改變的元素個數 num=floor(d/5) ，如果 num ＜1 ，將 num 置為1。隨機生成 num 個區間[0,d-1 ]內的位置，將食物源這些位置對應的元素加1，若加1 后的元素大于m，則置1。

偵察蜂的全局搜索采用重新初始化方案。具體為：假設食物源的長度為d，板材種類數量為m，食物源第1 層是亂序數字 1 ～d，并且隨機給這些元素取負；食物源第2 層的每個元素都是從整數1～m中隨機選取。

3 仿真實驗與分析

3.1 參數設置

VNABC 算法中，主要參數包括食物源的數量N、迭代次數I和食物源探索上限L。采用響應面法來確定合適的參數，使用的工具為Design Expert 12。采用Box Behnken 實驗設計，參數取值范圍：N為40～100，I為500～1 000，L為50～100，得到擬合方程：Y=0.1812-0.0022×A-0.1115×B-0.0011×C，為了計算方便，參數均取整數值，N=100，I=1 000，L=75。表1 示出了模型的方差分析，P值小于0.050 0表示模型項顯著，失擬F值為3.17，意味著失擬相對于純誤差并不顯著，擬合效果好。實驗結果表明模型建立合理，能夠很好地預測試驗結果。

表1 模型方差分析Table 1 Model variance analysis

3.2 測試數據

標準的二維下料問題的benchmark 數據里的板材規格都是單一的，且各規格毛坯數量也是單個。顯然，不滿足多規格板材二維下料問題的特征。由于多規格板材二維下料問題的復雜性，目前的研究成果不多，沒有相應的標準測試數據，因此在二維下料問題benchmark 標準數據的基礎上設計多規格板材二維下料問題的測試數據，選取了T 系、C 系和M 系。T 系出自Eva[13]，有7 組實驗，每組5 個，分別用a、b、c、d、e 表示。C 系出自Eva[14]，7 組實驗，每組3 個。T 系和C 系每種規格毛坯的數量在區間[20,100]內。M 系只有3 組實驗，分別是 2×5 算例、3×10算例和 5× 19 算例。 2×5 算例[15]有2 種板材，5 種毛坯，板材規格為3 660 × 2 440 和3 300 × 2 134，毛坯信息為{900-360-5, 1 003-900-10, 600-550-18, 1 250-600-43, 856-475-25}，其中格式x-y-z中x、y、z分別表示寬、高和需求量。 3×10 算例[16]有3 種板材，10 種毛坯， 板材規格為250×250， 300×250， 300×300。5×19算例[17]有5 種板材，19 種毛坯，板材規格為3 750×3 200、3 600×2 700、3 300×2 900、3 500×2 600 和3 800×3 000。

本文中的所有程序在Windows 10 系統、Intel Corei5 處理器、內存為16 GB 的PC 上使用Java 編寫，JDK 版本為1.8。

3.3 性能比較

針對2.2 節提出的2 種解碼策略和4 種零散塊下料策略，組合出8 種不同的解碼方案，分別是STDOS、 STD-TS、 STD-HO、 STD-WO、 SLD-OS、 SLDTS、SLD-HO、SLD-WO，分別簡寫為STO、STT、STH、STW、SLO、SLT、SLH 和SLW。對8 種解碼方案進行測試，以浪費率 tls （百分比%）和計算時間t（ms）為評價指標，選取T1a、T2a、T3a 和T4a 這4 個測試數據，每個實驗運行5 次。實驗結果如表2 所示，其中 No.表示第幾次實驗，“～”表示該解碼方案未能在1 min 內得到結果， tls 的最優結果加粗顯示。

表2 解碼方案對比Table 2 Decoding scheme comparison

從表2 中可以看出，對于浪費率 tls ，從解碼策略的角度看，SLD 具有絕對的優勢。除了T1a_4 中STO 和STT 的13.02 小于SLO 和SLT 的14.02 外，其余tls 都是SLO 和SLT 小于STO 和STT。從零散塊下料策略的角度看，OS 和TS 也比HO 和WO 有優勢，TS 比OS 更優。綜上所述，解碼方案采用SLT，即松弛解碼和兩個臺階下料。

下面以 2×5 算例為例介紹整個下料過程。毛坯中最小邊為360，因此閾值設定為360。板材P1 規格為3 660×2 440，P2 規格為3 300×2 134。按照圖1 所示食物源，R4 第1 個下料。8 塊R4 組成的CB 下料到P1 上，上方余料EU 高度小于閾值，無法利用。接著由2 塊R2 和1 塊R1 組成的FB 下料到右側余料ER 上，第1 塊P1 下料結束，如圖4(a)所示。在圖4中，黑色數字表示毛坯，紅色數字表示板材。R4 還有剩余，則繼續在新的P1 下料，過程相同。等到第5 塊P1 上R4 組成的CB 下料結束，R4 剩下1 塊，小于R4 的HMC，輪到下一類毛坯下料。同理，R1 剩下1 塊，小于R1 的HMC，輪到下一類毛坯下料。R3 理應在P2 上下料，由于松弛解碼SLD 設定優先在上一塊可下料板材上繼續下料，因此R3 在上一塊P1 上料，下料過程與之前類似。等到R2 下料結束，此時規整階段結束，剩下1 片R4、1 片R1 和2 片R5，進入非規整階段。非規整階段使用BL 算法下料剩余毛坯的效果圖如圖4(h)所示。

圖4 2×5 算例下料方案Fig.4 2×5 cutting stock plan

為了驗證VNABC 算法的性能，將其與遺傳算法（GA）[18]、改進粒子群優化算法（NUS）[19]、模擬退火算法（SA）[20]和人工蜂群算法（ABC）[9]進行比較。所有算法采用相同的語言編寫并且都在同一實驗環境下運行，終止條件都設為1 000 次。VNABC 算法的參數為3.1 節響應面法確定的參數，而其余算法參數則按照文獻里參數設置，每個實驗運行10 次。算法性能指標由相對百分比偏差平均值(MRPD)、相對百分比偏差標準差(SDRPD)、相對百分比偏差最優值(BRPD)表示，它們的計算公式如下：

其中：ck表示算法第k次運算的結果，c*為所有算法得到的最優值。BRPD 指標越小，表明尋找到的解質量越高，越接近最優解。MRPD 指標越小，表明10 次運行的結果與最優值的偏差越小。而SDRPD 指標越小，表示10 次運行結果都較為接近MRPD，即算法的穩定性較好。

T 系的實驗結果如表3 所示，其中T1～T7 括號中的數字表示毛坯的種類數量，各項性能指標最優值加粗顯示。從表3 中可以看出，大多數實驗中VNABC 算法的BRPD 指標為0，說明VNABC 算法找到的解是5 種算法中最優的，它的尋優能力較強。VNABC 算法的MRPD 指標和SDRPD 指標在T1～T4實驗中幾乎都是最小的，表明VNABC 算法在規模較小時穩定性較好且解的質量高。T5～T7 實驗中，VNABC 算法的MRPD 指標和BRPD 指標也幾乎都是最小的，但SDPRD 指標并非如此。例如T6a 中，VNABC 算法的MRPD 指標和BRPD 指標分別為0.28 和0，而SDRPD 指標為0.16，大于ABC 算法的SDRPD 指標0.10。這說明隨著問題規模的變大，VNABC 算法穩定性變差。因此5 種算法中，VNABC算法的尋優能力較強，搜索空間大，這得益于兩種蜜蜂不同的鄰域搜索。

表3 T 系實驗結果Table 3 Results of T series

C 系的實驗結果如表4 所示。針對C1 和C2，5 種算法的3 個指標差距不大，效果都比較好。針對C3～C7，5 種算法的差距逐漸體現出來，其中SA 的結果最差。例如，C1-2 和C2-3 的5 種算法的指標都為0，表明5 種算法效果相同。C4-2、C5-3、C6-2 和C7-1 中VNABC 的3 種指標都取得了最低值，效果最佳。綜合來看，VNABC 算法是最優的，其次是GA 算法。

表4 C 系實驗結果Table 4 Results of C series

M 系中 2×5 算例、 3×10 算例和 5×19 算例的結果如表5 所示。3 個算例中，VNABC 算法除了3×10算例的SDRPD 指標0.37 不是最優外，其余指標都是最優，因此VNABC 算法具有明顯優勢。

表5 M 系實驗結果Table 5 Results of M series

圖5 示出了不同算例5 種算法的收斂曲線。從圖5 中可以看出，VNABC 算法在計算過程前期收斂較快，得益于引領蜂的變步長逆序交換，搜索空間大；后期變化步長小，搜索空間變小，算法逐漸收斂。VNABC 算法能較好地解決該問題，尋優能力較強。

圖5 不同算例部分收斂曲線Fig.5 Partial convergence curves of different examples

為了驗證VNABC 算法具有普適性，增加單規格板材二維下料實驗。矩形毛坯規格數據跟C 系保持一致，板材規格數據只取其中一種，實驗結果如表6所示。表6 中出現了較多的0，這表明5 種算法取得了相同結果，出現這種情況的原因是板材規格和毛坯規格的差距過大，不管毛坯怎么擺放，它都能容納毛坯，因此按照式(12)計算得到的利用率不會發生變化。C22 中，VNABC、NUS 和ABC 算法的BRPD為0，表明這些算法都找到了最優解。而VNABC 算法的MRPD 為15.37，優于其他算法，效果最好。同理，C32、C41、C42 和C51 中VNABC 算法均取得了最優結果。實驗結果表明VNABC 算法可以用來解決其他同類問題。

表6 單規格板材實驗結果Table 6 Experimental results of single specification plate

4 結 論

本文在板材規格多樣且數量不限的條件下，以板材浪費率最小為優化目標，研究了多規格板材二維下料問題：

（1）整個下料過程設計成兩個階段。規整階段主要承擔下料任務和下料規整，如果規整階段結束仍有毛坯剩余，則非規整階段使用BL 算法下料剩余毛坯。

（2）規整階段設計了組合塊和零散塊下料過程。組合塊在板材上下料，零散塊在EU 和ER 兩種余料上下料。針對零散塊提出了4 種零散塊下料策略，進一步降低板材浪費率。

（3）提出改進的VNABC 算法，設計雙層編碼并提出了兩種不同的解碼策略SLD 和STD。改進了VNABC 算法的3 種操作算子，提出變步長逆序交換的鄰域搜索，提高算法性能。

（4）采用響應面法確定VNABC 算法的參數并且使用不同的數據集對VNABC 算法進行測試，將測試結果與GA、NUS、SA 和ABC 算法進行對比，實驗結果驗證了VNABC 算法解決多規格板材二維下料問題的可行性與高效性。同時，VNABC 算法能解決其他同類問題，具有一定的適應性。