馮文健

(柳州鐵道職業(yè)技術(shù)學(xué)院， 廣西 柳州 545616)

0 引言

二維矩形裝箱問題(2D rectangular strip packing problem, 2DRSPP)是將一組長(zhǎng)度、寬度不等的矩形互不重疊的裝入給定寬度、長(zhǎng)度不限的矩形條帶箱中，使得箱子被矩形占用的高度最小。該類問題是NP難問題，在工業(yè)領(lǐng)域被廣泛應(yīng)用，因此對(duì)此類問題的求解有重要的研究?jī)r(jià)值。目前對(duì)2DRSPP的研究主要集中于算法設(shè)計(jì)，可分為精確算法、啟發(fā)式算法和混合智能算法，由于精確算法求解時(shí)間較長(zhǎng)，只適合較小規(guī)模算例。而后兩者成為求解2DRSPP的主流算法[1-4]。近年來，相關(guān)學(xué)者提出一些更有效的啟發(fā)式算法和混合智能算法，尚正陽等[5]設(shè)計(jì)一種啟發(fā)式最優(yōu)剩余空間算法，提出求解二維矩形裝箱問題的啟發(fā)式算法；鄧見凱等[6]提出一種求解二維矩形Packing問題的擬人型全局優(yōu)化算法；羅強(qiáng)等[7]提出求解矩形件排樣問題的十進(jìn)制狼群算法；江林燕[8]提出基于化學(xué)反應(yīng)優(yōu)化算法的裝箱問題研究；車玉馨[9]提出裝箱問題的啟發(fā)式算法研究；高東琛[10]提出二維裝箱問題的啟發(fā)式算法。

本文設(shè)計(jì)了算法1并結(jié)合布谷鳥算法求解二維矩形裝箱問題，通過多組測(cè)試算例的仿真實(shí)驗(yàn)，結(jié)果表明本文設(shè)計(jì)的算法對(duì)部分測(cè)試算例效果較好，對(duì)部分測(cè)試算例效果較差。

1 二維矩形裝箱問題描述

圖1 矩形件裝箱示意圖

假設(shè)第i個(gè)小矩形pi的長(zhǎng)度和寬度分別表示為wi和hi，排放在寬度為W、高度不限的大矩形帶箱strip上，矩形件i排放后左上角的橫坐標(biāo)、縱坐標(biāo)和寬度分別為xi、yi和wi。排放的過程中矩形件之間不重疊、矩形件不超出strip的邊界和矩形件底邊與strip邊平行3個(gè)約束條件。H為n個(gè)矩形件排放完后的最大高度，Y為矩形件面積之和與排樣最大高度之下的面積比。為了便于對(duì)2DRSPP進(jìn)行數(shù)學(xué)描述，以左下角0為坐標(biāo)原點(diǎn)建立如圖1所示的二維坐標(biāo)系，每一個(gè)item用左上角的橫坐標(biāo)、縱坐標(biāo)和寬度來表示，比如矩形1則表示為(0,6,2)，4個(gè)item放置strip中形成3條水平線(圖中a,b,c所示)，2DRSPP的目標(biāo)如下：

(1)

s.t.?pi:0≤xi≤W,0≤xi+wi≤W,yi≥0

(2)

?pi,pj:xi≤xj≤xi+wi

(3)

?pi,pj:yi≤yj≤yi+wi

(4)

其中式(3)和(4)保證所有矩形件互不重疊和不超出strip的邊界，本文研究的2DRSPP是矩形件不可旋轉(zhuǎn)。

2 算法描述

應(yīng)用智能算法求解2DRSPP的關(guān)鍵點(diǎn)在于編碼和解碼，本文采用浮點(diǎn)數(shù)編碼方式，然后對(duì)其排序得到十進(jìn)制整數(shù)，每一個(gè)整數(shù)即為矩形件的唯一標(biāo)識(shí)；解碼即運(yùn)用算法對(duì)有序的整數(shù)序列轉(zhuǎn)化為排樣圖。

2.1 算法1

算法1過程描述如下：

(1)初始化最低水平線及strip的寬度；

(2)按面積從大到小排序，得到排序序號(hào)集set；

在選購(gòu)機(jī)械設(shè)備的過程中，要將效益放在首要位置，爭(zhēng)取企業(yè)的效益能夠?qū)崿F(xiàn)最大化，選擇設(shè)備時(shí)需要按照經(jīng)濟(jì)實(shí)惠的原則。

(3)如果集合set不為空；循環(huán)執(zhí)行步驟4～6；

(4)統(tǒng)計(jì)所有未放入strip中的矩形newdata；

(5)判斷newdata中是否存在能夠放入strip中的矩形；

(6)如果存在，則將矩形放入strip中，求解新的水平線并刪除寬度為0的水平線，再判斷最低水平線是否可以合并，如果可以則合并最低水平線并更新最低水平線，然后從集合set中刪除相應(yīng)的矩形；如果不存在，則將此時(shí)最低水平線提升至與其相鄰矩形中最低高度齊平，然后合并最低水平線寬度。

(7)直至集合set為空退出循環(huán)，輸出最大高度。

2.2 布谷鳥算法

布谷鳥算法(cuckoo search algorithm，CS)是YANG Xin-she和DEB Suash于2009年提出[11]，該算法結(jié)構(gòu)簡(jiǎn)單、容易實(shí)現(xiàn)，其全局搜索過程依靠Levy飛行選擇鳥巢，其迭代式如下：

(5)

局部搜索過程則以一定概率pa拋棄鳥巢和新建鳥巢。

(6)

2.3 策略1

由于在棄巢過程中未利用群體的最佳位置，可能會(huì)導(dǎo)致收斂速度和精度不高，因此將式(6)改為下式：

(7)

其中，r1,r2∈[0,1]之間的隨機(jī)數(shù)，m1，m2，m3表示n個(gè)不重復(fù)的隨機(jī)整數(shù)。

2.4 策略2

為了增強(qiáng)局部搜索能力，對(duì)當(dāng)前鳥巢執(zhí)行輪盤賭選擇(參見遺傳算法)、交叉(隨機(jī)選擇兩個(gè)鳥巢和隨機(jī)選擇兩個(gè)位置進(jìn)行交叉)和逆序(隨機(jī)選擇兩個(gè)位置進(jìn)行倒序)操作。

2.5 改進(jìn)布谷鳥算法

改進(jìn)布谷鳥算法(improved cuckoo search algorithm，ICS)求解過程如下：

(1)初始化種群數(shù)目、最大迭代次數(shù)、棄巢率和邊界等參數(shù)。

(2)在邊界范圍內(nèi)隨機(jī)初始化種群并降序排列，按算法1求解目標(biāo)值(高度)，求解當(dāng)前種群最優(yōu)值(最小高度)及最優(yōu)解。

(3)開始循環(huán)迭代，按式(5)獲得新鳥巢然后評(píng)估最優(yōu)值及最優(yōu)解，若較之前的優(yōu)越則替換；按式(7)建立新鳥巢并重新評(píng)估最優(yōu)值及最優(yōu)解，若較之前的優(yōu)越則替換。

(4)執(zhí)行N=5次數(shù)策略2并重新評(píng)估最優(yōu)值及最優(yōu)解，若較之前的優(yōu)越則替換。

(5)判斷循環(huán)是否結(jié)束，如果是輸出最優(yōu)值及最優(yōu)解，對(duì)最優(yōu)解降序排列得到的序列即為矩形件的排樣順序，否則跳轉(zhuǎn)至步驟(3)。

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

為了驗(yàn)證ICS的性能，本文實(shí)驗(yàn)1數(shù)據(jù)來源于文獻(xiàn)[12]，實(shí)驗(yàn)2的數(shù)據(jù)來源于http://people.brunel.ac.uk/～mastjjb/jeb/info.html；所有實(shí)驗(yàn)基于windows平臺(tái)使用matlab語言編寫實(shí)現(xiàn)，硬件環(huán)境為i7-9750H 2.60GHz CPU,8G內(nèi)存。算法的參數(shù)設(shè)置：種群規(guī)模為20，棄巢率為0.25，交叉率為0.85，最大迭代次數(shù)為100。

表1 算例N的比較結(jié)果

3.1 實(shí)驗(yàn)1

實(shí)驗(yàn)1采用經(jīng)典的N算例對(duì)本文算法進(jìn)行測(cè)試，并與GA+BLF，SA+BLF，GA+IHR算法進(jìn)行比較，統(tǒng)計(jì)結(jié)果見表1，排樣效果如圖2、圖3所示。表1中的n，w，hopt分別表示矩形個(gè)數(shù)、strip寬度和已知最優(yōu)高度。

圖2 N4排樣圖 圖3 N7排樣圖

表2 ngcut和beng算例的統(tǒng)計(jì)結(jié)果

從表2可知，本文算法在N4、N6和N7算例上求解的最優(yōu)值均優(yōu)于GA+BLF、SA+BLF和GA+IHR算法；本文算法在N3～N9算例上求解的最優(yōu)值均優(yōu)于GA+BLF和SA+BLF算法，在N10,11算例上求解的最優(yōu)值與其一致，僅在N2算例上求解的最優(yōu)值較其差；與GA+IHR算法相比，求解結(jié)果優(yōu)于的有算例N1、N2、N4和N7；求解結(jié)果一致的有N3和N6；求解結(jié)果較差的有算例N5、N8、N9、N10和N11。通過11個(gè)N類算例驗(yàn)證了本文的有效性。

3.2 實(shí)驗(yàn)2

實(shí)驗(yàn)2的ngcut算例共有12個(gè)子算例，均屬于小規(guī)模問題。beng算例共有10個(gè)子算例。矩形為20～200個(gè)。采用相對(duì)距離來評(píng)價(jià)計(jì)算結(jié)果，gap=(h*-hopt)/hopt×100 ，h*表示計(jì)算的最優(yōu)值，hopt為已知最優(yōu)值，gap越小表示算法越好。并與文獻(xiàn)[13～17]、DWPA算法進(jìn)行比較，統(tǒng)計(jì)結(jié)果見表2，部分排樣效果如圖4、圖5所示。表2中的n，w，hopt分別表示矩形個(gè)數(shù)、strip寬度和已知最優(yōu)高度。

圖4 beng4排樣圖 圖5 beng7排樣圖

從表2可知，對(duì)ngcut小規(guī)模的測(cè)試算例，本文的求解效果與GRASP效果一致，優(yōu)于ISA、SRA、文獻(xiàn)[16]、文獻(xiàn)[17]算法，差于DWPA算法，但對(duì)ngcut 5算例，本文和其他算法均優(yōu)于DWPA算法。對(duì)于beng測(cè)試算例，本文的求解效果差于其他算法。因此，從所有的測(cè)試算例來看，本文設(shè)計(jì)的算法對(duì)N類和ngcut類裝箱問題求解效果較好，但對(duì)beng類裝箱問題求解效果差于其他算法。

4 結(jié) 語

本文在布谷鳥算法基礎(chǔ)之上設(shè)計(jì)算法1，并改進(jìn)局部搜索迭代公式，同時(shí)為增強(qiáng)局部勘探能力，對(duì)鳥巢進(jìn)行輪盤賭選擇、交叉和逆序操作，采用浮點(diǎn)數(shù)編碼方式求解二維矩形裝箱問題，應(yīng)用多組測(cè)試算例對(duì)算法進(jìn)行仿真實(shí)驗(yàn)，并與其他智能算法進(jìn)行比較，結(jié)果表明對(duì)N類和ngcut類裝箱問題求解效果較好，但對(duì)beng類裝箱問題求解效果較差，如何進(jìn)一步提高裝箱效果是下一步研究方向。