基于VNABC 的多規(guī)格板材二維下料問(wèn)題

蘇 俊， 徐震浩， 顧幸生

（華東理工大學(xué)能源化工過(guò)程智能制造教育部重點(diǎn)實(shí)驗(yàn)室, 上海 200237）

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

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

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

1 模 型

多規(guī)格板材二維下料問(wèn)題可以描述為：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ù)量的毛坯，下料時(shí)毛坯可以旋轉(zhuǎn)90°，尋找合適的下料方案使所消耗的板材浪費(fèi)率最低。

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

1.1 決策變量

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

1.2 約束

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

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

毛坯在板材上進(jìn)行下料時(shí)，所有毛坯均應(yīng)在板材的內(nèi)部，不能超過(guò)板材的尺寸。式(7)和式(8)將毛坯的坐標(biāo)約束在板材范圍內(nèi)。

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

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

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

1.3 目標(biāo)函數(shù)

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

2 VNABC 算法

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

2.1 編 碼

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

圖1 食物源Fig.1 Food source

2.2 解 碼

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

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

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

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

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

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

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

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

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

2.3 優(yōu)化計(jì)算過(guò)程

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

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

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

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

3 仿真實(shí)驗(yàn)與分析

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

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

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

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

標(biāo)準(zhǔn)的二維下料問(wèn)題的benchmark 數(shù)據(jù)里的板材規(guī)格都是單一的，且各規(guī)格毛坯數(shù)量也是單個(gè)。顯然，不滿足多規(guī)格板材二維下料問(wèn)題的特征。由于多規(guī)格板材二維下料問(wèn)題的復(fù)雜性，目前的研究成果不多，沒(méi)有相應(yīng)的標(biāo)準(zhǔn)測(cè)試數(shù)據(jù)，因此在二維下料問(wèn)題benchmark 標(biāo)準(zhǔn)數(shù)據(jù)的基礎(chǔ)上設(shè)計(jì)多規(guī)格板材二維下料問(wèn)題的測(cè)試數(shù)據(jù)，選取了T 系、C 系和M 系。T 系出自Eva[13]，有7 組實(shí)驗(yàn)，每組5 個(gè)，分別用a、b、c、d、e 表示。C 系出自Eva[14]，7 組實(shí)驗(yàn)，每組3 個(gè)。T 系和C 系每種規(guī)格毛坯的數(shù)量在區(qū)間[20,100]內(nèi)。M 系只有3 組實(shí)驗(yàn)，分別是 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 編寫(xiě)，JDK 版本為1.8。

3.3 性能比較

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

表2 解碼方案對(duì)比Table 2 Decoding scheme comparison

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

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

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

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

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

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

表3 T 系實(shí)驗(yàn)結(jié)果Table 3 Results of T series

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

表4 C 系實(shí)驗(yàn)結(jié)果Table 4 Results of C series

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

表5 M 系實(shí)驗(yàn)結(jié)果Table 5 Results of M series

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

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

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

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

4 結(jié) 論

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

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

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

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

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