蘇 俊， 徐震浩， 顧幸生

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

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

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

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

1 模 型

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

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

1.1 決策變量

決策變量如下：Ni：板材i的投入數(shù)量； λ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的數(shù)量； tls ：板材的修剪損失。

1.2 約束

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

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

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

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

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

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

1.3 目標函數(shù)

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

2 VNABC 算法

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

2.1 編 碼

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

圖1 食物源Fig.1 Food source

2.2 解 碼

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

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

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

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

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

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

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

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

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

2.3 優(yōu)化計算過程

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

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

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

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

3 仿真實驗與分析

3.1 參數(shù)設(shè)置

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

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

3.2 測試數(shù)據(jù)

標準的二維下料問題的benchmark 數(shù)據(jù)里的板材規(guī)格都是單一的，且各規(guī)格毛坯數(shù)量也是單個。顯然，不滿足多規(guī)格板材二維下料問題的特征。由于多規(guī)格板材二維下料問題的復雜性，目前的研究成果不多，沒有相應的標準測試數(shù)據(jù)，因此在二維下料問題benchmark 標準數(shù)據(jù)的基礎(chǔ)上設(shè)計多規(guī)格板材二維下料問題的測試數(shù)據(jù)，選取了T 系、C 系和M 系。T 系出自Eva[13]，有7 組實驗，每組5 個，分別用a、b、c、d、e 表示。C 系出自Eva[14]，7 組實驗，每組3 個。T 系和C 系每種規(guī)格毛坯的數(shù)量在區(qū)間[20,100]內(nèi)。M 系只有3 組實驗，分別是 2×5 算例、3×10算例和 5× 19 算例。 2×5 算例[15]有2 種板材，5 種毛坯，板材規(guī)格為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 種毛坯， 板材規(guī)格為250×250， 300×250， 300×300。5×19算例[17]有5 種板材，19 種毛坯，板材規(guī)格為3 750×3 200、3 600×2 700、3 300×2 900、3 500×2 600 和3 800×3 000。

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

3.3 性能比較

針對2.2 節(jié)提出的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 個測試數(shù)據(jù)，每個實驗運行5 次。實驗結(jié)果如表2 所示，其中 No.表示第幾次實驗，“～”表示該解碼方案未能在1 min 內(nèi)得到結(jié)果， tls 的最優(yōu)結(jié)果加粗顯示。

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

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

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

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

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

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

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

表3 T 系實驗結(jié)果Table 3 Results of T series

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

表4 C 系實驗結(jié)果Table 4 Results of C series

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

表5 M 系實驗結(jié)果Table 5 Results of M series

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

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

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

表6 單規(guī)格板材實驗結(jié)果Table 6 Experimental results of single specification plate

4 結(jié) 論

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

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

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

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

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