李孫寸 施心陵 張松海 董 易 高 蓮

裝箱問題按照目標(biāo)函數(shù)的不同類型分為容器裝載問題、箱柜裝載問題和背包裝載問題[1].容器裝載問題是將所有待裝箱子裝入一個(gè)不限尺寸的容器中,在諸多方案中找到一個(gè)使容器體積最小的裝載方案,該類型問題一般規(guī)定容器的長(zhǎng)和寬為常數(shù),高為變量;箱柜裝載問題是給定一些規(guī)格統(tǒng)一的方型容器和一些不同類型的方型箱子,找到一個(gè)能把所有箱子裝入最少容器中的裝載方案;背包裝載問題是給定一個(gè)固定規(guī)格的容器和一些有一定價(jià)值的箱子,然后將部分箱子裝入容器中,找到一個(gè)使得裝入容器中箱子總價(jià)值最大的裝載方案,若將箱子的體積作為價(jià)值,則背包裝載問題就轉(zhuǎn)換為找到一個(gè)如何使容器的填充率最大的裝載方案.其中容器裝載問題和箱柜裝載問題具有一定的局限性,限制了其工業(yè)領(lǐng)域的應(yīng)用范圍.因此本文從背包裝載問題入手對(duì)三維裝箱問題作初步研究.

裝箱問題是傳統(tǒng)的NP問題,具有廣泛的應(yīng)用領(lǐng)域.隨著當(dāng)今世界信息技術(shù)、大數(shù)據(jù)、數(shù)據(jù)流、數(shù)據(jù)關(guān)系的分析處理的不斷發(fā)展,為裝箱問題的應(yīng)用拓展了新的領(lǐng)域,例如信息網(wǎng)絡(luò)、交通網(wǎng)和云存儲(chǔ)等有限資源的最大利用率問題,有限資金投資的收益率最大化問題,以及大數(shù)據(jù)相對(duì)關(guān)系匹配度最大化問題等.如何提高容器的空間利用率,是當(dāng)代科學(xué)研究和實(shí)踐中一個(gè)非常重要的課題.找到高利用率的裝箱方案,對(duì)節(jié)約天然資源,降低企業(yè)成本,提高企業(yè)利潤(rùn),有著十分積極的現(xiàn)實(shí)意義.

近年來,國(guó)內(nèi)外的學(xué)者們陸續(xù)提出了一些解決三維裝箱問題的算法.Ngoi等[2]采用獨(dú)特的空間表征技術(shù)求解裝箱問題.Bischoあ等提出了一種啟發(fā)式算法,同時(shí)給出了三維裝箱問題的一些測(cè)試實(shí)例[3?4],其中文獻(xiàn)[3]根據(jù)層和條的選擇策略,提出了按層布局的貪婪算法.Sixt提出了基于元啟發(fā)式的禁忌搜索和模擬退火算法[5].Gehring等提出并行化的遺傳算法,該方法先對(duì)箱子進(jìn)行一定的預(yù)處理,再用遺傳算法對(duì)箱子進(jìn)行優(yōu)化組合來獲得裝載方案[6].Bortfeldt等提出了一種禁忌搜索算法,但該種方法只適用于箱子種類較少的情況[7].接著, Bortfeldt等針對(duì)層的策略,又提出一種混合遺傳算法[8].同時(shí)期,國(guó)內(nèi)學(xué)者何大勇等提出了求解復(fù)雜集裝箱裝載問題的遺傳算法[9].隨后,Eley提出了基于“塊”的算法[10],在此基礎(chǔ)上,Bortfeldt等也基于“塊”的概念,給出了并行禁忌搜索算法[11]. Moura等基于“剩余空間的概念”,提出了一個(gè)貪心隨機(jī)自適應(yīng)搜索算法(Greedy randomized adaptive search procedures,GRASP)[12].張德富等針對(duì)圓形的裝箱問題提出了擬人退火算法[13],隨后,又提出了三維裝箱問題的組合啟發(fā)式算法[14].Parren′oo等在文獻(xiàn)[12]的基礎(chǔ)上往前發(fā)展了一步,將GRASP做了改進(jìn),取得了明顯的裝箱效果[15].Huang等針對(duì)單一類型的裝箱問題提出了一個(gè)有效的擬人型穴度算法[16].張德富等提出了混合模擬退火算法,該方法首先將箱子生成復(fù)合塊,接著給出一個(gè)基于塊裝載的構(gòu)造型啟發(fā)式算法,然后將該啟發(fā)式算法和模擬退火算法相結(jié)合,提出了一個(gè)有效求解三維裝箱問題的混合模擬退火算法[17].Fanslau等也基于復(fù)合塊的概念,設(shè)計(jì)了一個(gè)有效的啟發(fā)式樹狀搜索算法[18].張德富等又在文獻(xiàn)[17?18]的基礎(chǔ)上設(shè)計(jì)了一個(gè)多層啟發(fā)式搜索算法[19],該算法是采用深度和寬度同時(shí)搜索的思想,提出的多層搜索算法,該算法用多層搜索思想來選擇一個(gè)近似最優(yōu)塊進(jìn)行裝載,然后逐步構(gòu)造直到獲得一個(gè)裝載序列,較之前的算法取得了很好的裝載效果,但隨著箱子規(guī)模的增大,該算法需要較長(zhǎng)的計(jì)算時(shí)間.劉勝等提出的求解三維裝箱問題的啟發(fā)式正交二叉樹搜索算法[20],該裝箱算法裝箱效率較已有算法裝箱效率有顯著提高,但是當(dāng)箱子種類較少時(shí),該算法的優(yōu)勢(shì)不明顯.當(dāng)然,還有一些學(xué)者也取得了很好的研究成果[21?28].

在很多實(shí)際工業(yè)應(yīng)用中,待裝箱子具有規(guī)格多樣性和數(shù)量不確定性等特點(diǎn).因此本文結(jié)合最優(yōu)化原理,用多元優(yōu)化算法(Multi-variant optimization algorithm,MOA)實(shí)現(xiàn)三維裝箱問題的求解,該算法的基本思想是隨機(jī)放置、局部調(diào)整和逐步逼近.通過對(duì)BR1～BR10共1000組實(shí)例的仿真測(cè)試,取得明顯的裝箱效果,證明了本文算法的有效性和可行性.

1 問題描述

給定一個(gè)長(zhǎng)L、寬W、高H的矩形容器C和n個(gè)矩形箱子b1,···,bi,···,bn.每個(gè)箱子bi的長(zhǎng)為li,寬為wi,高為hi,體積為vi=li×wi×hi,容器C的體積V=L×W×H.該問題的目標(biāo)為:在箱子沒有溢出容器,且滿足方向性約束和穩(wěn)定性約束的條件下使容器的填充率最大,即要盡可能多地將箱子裝入容器中.問題的目標(biāo)函數(shù)為

在實(shí)際裝箱問題中,一般會(huì)遇到3個(gè)著名的約束條件[18]:

約束1(C1).方向性約束.在許多應(yīng)用場(chǎng)合下,箱子的裝載具有方向性約束.方向性約束即為箱子的長(zhǎng)度邊、寬度邊和高度邊是否可以與容器的高度邊平行放置.若沒有這個(gè)約束條件的問題,在裝箱過程中,箱子的任意一條邊都可以豎直放置.

約束2(C2).穩(wěn)定性約束.在許多應(yīng)用場(chǎng)合下,像在物流和交通運(yùn)輸?shù)阮I(lǐng)域中,有時(shí)箱子在裝載時(shí)必須滿足穩(wěn)定性約束.也就是說每個(gè)箱子在裝載時(shí)要必須得到容器底部或是其他已經(jīng)裝載了的箱子的支撐.針對(duì)不同的應(yīng)用情況,穩(wěn)定性約束有部分支撐約束和完全支撐約束.部分支撐約束是指被裝載箱子的底部允許有部分懸空,完全支撐約束是指被裝載箱子的底部不允許有懸空的部分.

約束3(C3).完全切割約束.在切割時(shí),每一刀必須將材料完全分割成兩個(gè)部分.例如在木材和石材等的切割應(yīng)用中,一般的切割機(jī)只能做到完全切割.

本文算法在裝箱過程中,箱子的放置方式只選擇其中的幾種,即并不是箱子的每一條邊都可以與容器的高度邊平行放置,這就保證了本文算法滿足C1方向性約束,箱子的放置方式見第2.3節(jié)述;同時(shí),剩余空間的分割與合并方式保證了本文算法滿足C2穩(wěn)定性約束,剩余空間的分割與合并方式見第2.2節(jié)和第2.4節(jié).綜上所述,本文算法是基于C1和C2兩個(gè)約束進(jìn)行的.

2 裝箱準(zhǔn)備

2.1 最優(yōu)化原理

根據(jù)一類多階段決策問題的特性,由Bellman等提出了解決動(dòng)態(tài)規(guī)劃的“最優(yōu)化原理”,作為整個(gè)過程的最優(yōu)策略具有這樣的性質(zhì):無論過去的狀態(tài)和決策如何,對(duì)當(dāng)前決策形成的狀態(tài)而言,余下的所有狀態(tài)必須構(gòu)成最優(yōu)策略.即若要解決某一個(gè)優(yōu)化問題,需要做出n個(gè)決策D1,···,Di,···,Dn,若這個(gè)決策序列是最優(yōu)策略,對(duì)于任何一個(gè)i,1＜i＜n,不論前面的i個(gè)決策是如何,i決策以后的最優(yōu)決策只取決于由前面決策所確定的當(dāng)前的i狀態(tài),即以后的決策Di+1,Di+2,···,Dn也是最優(yōu)的[29].

2.2 空間的劃分

箱子的裝載是在容器的剩余空間中進(jìn)行的,剩余空間是指容器中未被填充的空間.箱子理論上可以放在容器的任意位置,但不能超出容器的容納范圍,也不能與其他貨物交迭放置.為了滿足裝箱問題的穩(wěn)定性約束和保證每一個(gè)箱子裝進(jìn)容器之前,剩余空間都是立方體空間,本文選擇將箱子從容器的原點(diǎn)坐標(biāo)處開始放置,并且箱子擺放時(shí)必須與坐標(biāo)軸平行或正交,不能斜放,也不能懸浮放置.當(dāng)?shù)谝粋€(gè)箱子裝進(jìn)容器后,將剩余空間分割成相對(duì)于剛剛裝入的箱子的前空間、右空間和上空間三個(gè)立方體空間,如圖1所示.對(duì)每一個(gè)箱子裝入容器后產(chǎn)生的剩余空間都嚴(yán)格做同樣的分割處理.為了裝箱的有效進(jìn)行,每裝進(jìn)一個(gè)箱子,更新記錄一次容器的剩余空間.

圖1 空間的分割Fig.1 Space division

2.3 箱子的放置

假設(shè)箱子的擺放沒有方向性約束C1,則在裝箱過程中,箱子的任意一條邊都可以豎直放置,此時(shí)可以將箱子的擺放方式細(xì)分為6種:1)l平行于L,w平行于W,h平行于H;2)w平行于L,l平行于W,h平行于H;3)l平行于L,h平行于W,w平行于H;4)h平行于L,l平行于W,w平行于H; 5)h平行于L,w平行于W,l平行于H;6)w平行于L,h平行于W,l平行于H.如圖2(a)～2(f)所示.如果箱子的擺放有方向性約束C1,則根據(jù)具體的方向性約束來選擇箱子的擺放方式.箱子放入容器時(shí),本文算法先選擇擺放方式后選擇放置空間.

2.4 剩余子空間的合并

隨著裝箱的不斷進(jìn)行,剩余空間中可能會(huì)產(chǎn)生一些廢棄空間,廢棄空間指的是裝不下任何一個(gè)待裝箱子的剩余子空間.要提高容器的利用率,就要最大程度的使用廢棄空間,即要盡可能地將廢棄空間變?yōu)榭捎每臻g,唯一的辦法就是將廢棄空間與其他剩余子空間合并.空間合并需同時(shí)滿足3個(gè)條件:1)兩個(gè)空間相鄰;2)兩個(gè)空間底面同高;3)兩個(gè)空間合并后,可用空間必須增大.在同時(shí)滿足上述3個(gè)條件時(shí),根據(jù)兩個(gè)相鄰空間的相對(duì)位置,將空間的合并方式分為左右合并和前后合并兩種方式,如圖3所示.

圖2 箱子的擺放方式Fig.2 The placement method of box

圖3 空間合并方式Fig.3 The merging method of residual space

3 多元優(yōu)化算法

3.1 算法簡(jiǎn)述

多元優(yōu)化算法(Multi-variant optimization algorithm,MOA)是基于全局和局部搜索交替進(jìn)行的思想提出的一種全新的群智能算法,該算法在問題的解空間中隨機(jī)產(chǎn)生全局搜索元及相應(yīng)的局部搜索元,對(duì)解空間進(jìn)行全面細(xì)致地搜索,從而逐漸逼近全局最優(yōu)解.算法基于計(jì)算機(jī)的數(shù)據(jù)結(jié)構(gòu),構(gòu)造多元化結(jié)構(gòu)體,結(jié)構(gòu)體用于記憶并協(xié)調(diào)搜索信息、調(diào)動(dòng)全局局部交替尋優(yōu)、記憶尋優(yōu)過程,多次全局局部交叉搜索后,獲得全局最優(yōu)解和多個(gè)次優(yōu)解[30].結(jié)構(gòu)體是搜索元全局和局部交替尋優(yōu)信息交流的平臺(tái),是尋優(yōu)過程記憶的載體.搜索元和結(jié)構(gòu)體構(gòu)成了MOA的基本框架[30].

結(jié)構(gòu)體是一種能夠按照一定規(guī)則,記憶協(xié)調(diào)搜索信息,有固定結(jié)構(gòu)的數(shù)據(jù)表,如圖4所示.

圖4 MOA數(shù)據(jù)結(jié)構(gòu)圖Fig.4 The data structure diagram of MOA

結(jié)構(gòu)體是用指針實(shí)現(xiàn)的二維有序鏈表,由全局鏈表和局部鏈表組成.結(jié)構(gòu)體中,第一行為全局鏈表,用于保存全局搜索元并記憶和共享全局信息;每一列叫做局部鏈表,用于保存各個(gè)局部解空間內(nèi)的局部搜索元和記憶局部信息.

全局鏈表和局部鏈表都是以搜索元的適應(yīng)度值為關(guān)鍵字(Key)的有序鏈表.全局鏈表中前端搜索元優(yōu)于后端搜索元,局部鏈表中上部搜索元優(yōu)于下部搜索元.搜索元是結(jié)構(gòu)體的組織細(xì)胞,用于存放和接收尋優(yōu)信息.搜索元具有進(jìn)行全局探索和局部調(diào)整的功能.

式中,li和ui分別為第i維待優(yōu)化參數(shù)xi的下限和上限,unifrnd(li,ui)為返回li和ui之間的一個(gè)隨機(jī)數(shù).

局部搜索元La(Local atom)是以某個(gè)全局元為中心的局部鄰域內(nèi)隨機(jī)生成的一個(gè)解.以全局元為中心的局部搜索元描述如下:

式中r為局部鄰域半徑,決定了局部搜索的范圍.

將全局鏈表記憶較優(yōu)的全局元作為具有搜索價(jià)值的局部解空間的中心,根據(jù)其所在全局鏈表中的位置共享該局部解空間在所有已經(jīng)發(fā)現(xiàn)的具有搜索價(jià)值局部解空間中的優(yōu)越程度:位置越靠前,其所在區(qū)域越優(yōu).當(dāng)局部搜索元發(fā)現(xiàn)優(yōu)于全局元的解時(shí),局部鏈表記憶較優(yōu)的局部元將取代全局元作為新的具有搜索價(jià)值的局部解空間的中心,以分享局部搜索獲得的信息.

為了更好地說明MOA的實(shí)現(xiàn)過程,給出測(cè)試函數(shù)

在給定的區(qū)間0≤x≤1內(nèi),用MOA求F(x)取最大值時(shí)對(duì)應(yīng)的解,尋優(yōu)過程如圖5所示,多個(gè)全局搜索元和對(duì)應(yīng)的局部搜索元對(duì)解空間進(jìn)行全面細(xì)致地搜索,逐漸逼近最優(yōu)解x=0.1,搜索結(jié)果如圖6所示.

圖5 測(cè)試尋優(yōu)過程圖Fig.5 The test optimization graph

圖6 測(cè)試尋優(yōu)結(jié)果圖Fig.6 The result of test results

3.2 問題的解

針對(duì)待裝箱子在實(shí)際應(yīng)用中的復(fù)雜性和不確定性,本文采用多元優(yōu)化算法實(shí)現(xiàn)三維裝箱問題,基本思想是:

1)隨機(jī)放置:裝入容器的箱子以及箱子的擺放方式均隨機(jī)選擇;

2)局部調(diào)整:對(duì)裝入容器的局部箱子按目標(biāo)函數(shù)值作局部調(diào)整;

3)逐步逼近:遞推的局部隨機(jī)放置與調(diào)整優(yōu)化,使目標(biāo)函數(shù)值逐步逼近最優(yōu)值.

在用MOA實(shí)現(xiàn)三維裝箱問題的求解之前進(jìn)行預(yù)處理:

1)箱子編號(hào):按自然數(shù)序列對(duì)待裝箱子進(jìn)行編號(hào),若待裝箱子總數(shù)為d,則所有待裝箱子的編號(hào)為1,2,···,i,···,d.若箱子數(shù)量很龐大或不確定,則可以省略這一步,直接分批次裝即可.

2)箱子擺放方式編號(hào):若沒有方向性約束C1,則待裝箱子的擺放方式編號(hào)為:1,2,3,4,5,6,這6種擺放方式分別代表第2.3節(jié)中描述的6種擺放方式;若有方向性約束C1,則根據(jù)具體的方向約束,待裝箱子的擺放方式編號(hào)為第2.3節(jié)中的一種或幾種.

多元優(yōu)化算法實(shí)現(xiàn)背包裝載問題的具體步驟如下:

步驟1.編碼.編碼是應(yīng)用多元優(yōu)化算法首先要解決的問題.根據(jù)不同研究對(duì)象的不同性質(zhì),把一個(gè)問題的可行解從其解空間轉(zhuǎn)換到多元優(yōu)化算法能處理的搜索空間中.假設(shè)總共有d個(gè)待裝的箱子,則MOA結(jié)構(gòu)體里一個(gè)全局搜索元的編碼方式為是1～d之間的隨機(jī)的且互不重復(fù)的整數(shù),表示箱子的序號(hào),i表示箱子ai裝入容器的次序.d維的搜索元P由全局搜索元式(2)產(chǎn)生,裝箱問題中,需要全局搜索,同時(shí)對(duì)局部進(jìn)行調(diào)整.

步驟2.分批隨機(jī)放置箱子.在實(shí)際應(yīng)用中,待裝箱子的種類多樣且數(shù)量龐大,因此將待裝箱子分幾批次裝入容器.首先取出中的前n個(gè)待裝箱子,即第一批次的裝箱個(gè)數(shù)為n,然后將此批次的箱子依次裝入容器中,n的大小根據(jù)箱子的數(shù)量設(shè)置.每一個(gè)箱子裝入容器時(shí),采取一種擬人的方法,先隨機(jī)放置,再做逐步調(diào)整.具體如下:

步驟2.1.首先隨機(jī)選取一個(gè)可用空間即剩余空間,然后隨機(jī)選取一種貨物即箱子的擺放方式,最后按該種擺放方式將箱子裝入選取好的剩余空間.

步驟2.2.若該箱子無法以該種擺放方式裝入剩余空間,則從箱子剩下的幾種擺放方式中再隨機(jī)選取一種,并判斷是否可以裝入剩余空間.如果可以,則將箱子放入所選的剩余空間并記錄箱子的擺放方式;反之,繼續(xù)選取擺放方式,直到將箱子放入剩余空間或已遍歷完該箱子的所有擺放方式為止.

步驟2.3.重復(fù)步驟2.1和步驟2.2,直到將箱子放入剩余空間或遍歷完所有的剩余空間為止.每裝一個(gè)箱子,更新記錄一次容器的剩余空間,若有廢棄空間且滿足合并的條件,則將廢棄空間與其相鄰的剩余空間合并.

步驟2.4.重復(fù)步驟2.1～2.3,直到無剩余空間可裝載或這一批次的n個(gè)箱子全部裝入為止.

步驟3.調(diào)整優(yōu)化.利用最優(yōu)化原理調(diào)整優(yōu)化容器的填充率.已有的決策序DDD1=[a1,a2,···,an]不一定是最優(yōu)的決策序列,要使該序列為最優(yōu)決策序列,利用最優(yōu)化原理逐步調(diào)整該序列,直到得到一個(gè)滿意的結(jié)果,具體步驟如下:

步驟3.1.在容器外未裝的箱子集中隨機(jī)抽取一個(gè)箱子及其對(duì)應(yīng)的擺放方式.

步驟3.2.將抽取的箱子的體積與a1的體積相比較,若抽取的箱子體積大于a1的體積,同時(shí)抽取的箱子能夠放入a1放進(jìn)容器之前對(duì)應(yīng)的剩余空間(指a1被放入容器之前算法記錄的剩余空間),則用隨機(jī)抽取的箱子替換a1.反之,若抽取的箱子的體積小于或等于a1的體積,或者抽取的箱子不能放入a1放進(jìn)容器之前對(duì)應(yīng)的剩余空間,則a1不用被隨機(jī)抽取的箱子替換.用同樣的方法依次優(yōu)化該批次裝進(jìn)容器的箱子,得到新的裝箱序列DDD2=[a1,a2,···,an],DDD2是DDD1的優(yōu)化序列.

步驟 3.3.將下一批箱子裝入容器后,按步驟3.1和步驟3.2中的方法對(duì)新裝進(jìn)容器的幾個(gè)箱子進(jìn)行調(diào)整優(yōu)化.重復(fù)上述步驟,直到待裝箱子已裝完或剩余空間全為廢棄空間時(shí),即可獲得一個(gè)潛在的裝箱方案.由于局部調(diào)整后的每一個(gè)局部序列都是最優(yōu)序列,因此整個(gè)全局序列同樣也是最優(yōu)序列,符合最優(yōu)化原理.

步驟4.逐次逼近,漸近收斂裝箱過程,直到滿意為止.

算法的偽代碼如下:

Begin

設(shè)置全局元個(gè)數(shù)m;每個(gè)全局元內(nèi)部的局部元個(gè)數(shù)即分的批次數(shù)bn;每個(gè)局部元的維度即每批次裝箱的個(gè)數(shù)bni(1≤i≤bn);全局解空間的下限l=1和上限u=sumbox,sumbox為箱子總數(shù);最大循環(huán)次數(shù)Imax;最大適應(yīng)度值(即最大填充率)fitinessmax;初始化適應(yīng)度值fitinessbest=0,K=0.

算法的時(shí)間復(fù)雜度分析.如算法的偽代碼所示,算法中最外層的While大循環(huán)內(nèi)有兩層并列的循環(huán),其中第一個(gè)For循環(huán)內(nèi)的每一個(gè)全局元是一個(gè)隨機(jī)生成的數(shù)組,只需一個(gè)執(zhí)行周期,即生成每個(gè)全局元的時(shí)間復(fù)雜度為O(1),因此第一個(gè)For循環(huán)的時(shí)間復(fù)雜度為O(m);第二個(gè)循環(huán)內(nèi)包含兩層嵌套的For循環(huán),其中內(nèi)層的For循環(huán)內(nèi)的局部元生成的時(shí)間復(fù)雜度為O(1),由于對(duì)每一個(gè)局部元優(yōu)化調(diào)整的次數(shù)即每批次裝箱的個(gè)數(shù)bni與局部元的個(gè)數(shù)bn相互獨(dú)立,則內(nèi)層For循環(huán)的時(shí)間復(fù)雜度為O(sumbox+bn),因此第二個(gè)循環(huán)的時(shí)間復(fù)雜度為O(m(sumbox+bn));再綜合最外層While大循環(huán)的時(shí)間復(fù)雜度O(K),因此算法的時(shí)間復(fù)雜度的通式為O(K(m+m(sumbox+bn))).

由于算法中fitinessbest的更新具有隨機(jī)性,在最好的情況下,在K=1時(shí),fitinessbest=fitinessmax,此時(shí)算法的時(shí)間復(fù)雜度為 O(m+m(sumbox+bn)),但發(fā)生這種情況的概率極小.在一般情況中,fitinessbest只會(huì)不斷趨近于fitinessmax,因此算法在一般情況下的時(shí)間復(fù)雜度為O(Imax(m+m(sumbox+bn))).

4 實(shí)驗(yàn)測(cè)試

4.1 測(cè)試準(zhǔn)備

為了證明本文算法的有效性和可行性,用具體的三維裝箱測(cè)試數(shù)據(jù)對(duì)算法做了大量測(cè)試.采用的測(cè)試數(shù)據(jù)來自文獻(xiàn)[9],測(cè)試了其中的BR1～BR10共1000個(gè)實(shí)例,這些數(shù)據(jù)可以從OR-Library網(wǎng)站下載.在BR1～BR10中,每種類型有100組測(cè)試實(shí)例,同時(shí)每種類型中箱子的類型數(shù)分別為3,5,8, 10,12,15,20,30,40,50,箱子的多樣性從弱到強(qiáng),從而能夠更好地反映算法在不同多樣性裝箱問題中的應(yīng)用情況.本文算法用Matlab實(shí)現(xiàn),實(shí)驗(yàn)程序運(yùn)行在Intel Core(TM)i3-3240 CPU@3.40GHz處理器上,運(yùn)行環(huán)境為Windows 7專業(yè)版.

4.2 測(cè)試過程

以BR1中第1組實(shí)例為例具體描述測(cè)試過程,將該實(shí)例取名為BR1-1.表1為BR1-1的待裝箱子的三維值及數(shù)量.

表1 BR1-1待裝箱子的三維值及數(shù)量Table 1 The speci fi cation and quantity of BR1-1

1)在測(cè)試之前的預(yù)處理

預(yù)處理1.讀取表1數(shù)據(jù).通過程序?qū)⒈?轉(zhuǎn)換為具體的數(shù)據(jù)矩陣,數(shù)據(jù)矩陣的每一行代表一種類型的箱子,每一行的前三列分別代表箱子的長(zhǎng)、寬、高的值,最后一列代表該種類型箱子的數(shù)量.

預(yù)處理 2.對(duì)所有箱子按順序編號(hào).由表1可知,BR1-1中共有112個(gè)箱子,其中,第1種類型有40個(gè),第2種類型有33個(gè),第3種類型有39個(gè).因此第1種類型的箱子的編號(hào)為1～40,第2種類型的箱子的編號(hào)為41～73,第3種類型的箱子的編號(hào)為74～112.

2)以BR1-1為例的測(cè)試過程

步驟 1.編碼.隨機(jī)產(chǎn)生112個(gè)1～112之間不重復(fù)的整數(shù)串,如[91,63,3,36,18,39,···,52, 74,10,97,2],此整數(shù)串中的每一個(gè)整數(shù)與預(yù)處理2中的箱子的編號(hào)對(duì)應(yīng),例如91代表91號(hào)箱子.相當(dāng)于把所有待裝箱子打亂.

步驟2.分批次裝載箱子.根據(jù)待裝箱子的總數(shù)設(shè)置裝箱過程分幾批次裝載,同時(shí)設(shè)定每一批次裝多少個(gè)箱子.例如BR1-1有112個(gè)待裝箱子,裝箱過程即可設(shè)置為分5批次裝載,第1批次裝32個(gè),第2批次裝27個(gè),第3批次裝22個(gè),第4批次裝17個(gè),第5批次裝14個(gè),這些具體的數(shù)據(jù)只是某一次實(shí)驗(yàn)設(shè)置的結(jié)果,并不是固定不變的.接著進(jìn)行裝箱過程,先將在步驟1產(chǎn)生的箱子序列串中從91號(hào)開始的前32個(gè)箱子依次裝入容器中,每一個(gè)箱子裝入容器之前更新記錄一次當(dāng)前的剩余空間,若中間有裝不下的箱子,則取該箱子后面的箱子繼續(xù)裝,直到已裝入容器的個(gè)數(shù)達(dá)到設(shè)定的32個(gè)或者是剩余空間已裝不下任何一個(gè)未被裝的箱子為止,此時(shí)將箱子分為已裝箱子和未裝箱子兩部分.

步驟3.調(diào)整優(yōu)化.從未被裝入容器的箱子中隨機(jī)抽取一個(gè)如編號(hào)為10的箱子,比較10號(hào)箱子與91號(hào)箱子的體積大小,若10號(hào)箱子的體積小于91號(hào)箱子的體積,則裝入容器的箱子保持不動(dòng),同時(shí)將10號(hào)箱子放回未被裝入容器的箱子集中,此時(shí)默認(rèn)91號(hào)箱子作為第一個(gè)裝入容器的最優(yōu)態(tài);接著從剩下的未被裝入容器的箱子中隨機(jī)抽取一個(gè)如編號(hào)為97的箱子,比較63號(hào)箱子與97號(hào)箱子的體積大小,若97號(hào)箱子的體積大于63號(hào)箱子,則此時(shí)判斷若97號(hào)箱子是否能被63號(hào)箱子裝入容器之前的剩余空間裝下,若能裝下,則將63號(hào)箱子替換成97號(hào)箱子作為第二裝入容器的最優(yōu)態(tài),63號(hào)箱子則放到未裝的箱子集中.替換后及時(shí)更新剩余空間,以便于下一個(gè)箱子正確地裝入容器中.如上所述,依次將第1批的32個(gè)箱子優(yōu)化完后,繼續(xù)將第2批次的箱子裝入容器中,對(duì)第2批次裝入的箱子也做同樣的優(yōu)化處理,第3批、第4批和第5批亦然.

步驟4.逐次逼近.經(jīng)過5次的裝載調(diào)整優(yōu)化之后,容器的填充率逐漸逼近上限100%.表2是某一次實(shí)驗(yàn)時(shí)容器填充率逐漸變化逼近的過程.整個(gè)裝箱過程滿足最不利原則.最不利原則是指:若最不利的情況也能滿足問題的要求,則其他情況必然滿足問題的要求.

4.3 實(shí)驗(yàn)結(jié)果與分析

許多國(guó)內(nèi)外的研究者對(duì)文獻(xiàn)[3]中的測(cè)試數(shù)據(jù)做了一些測(cè)試,本文對(duì)文獻(xiàn)[18]提出的啟發(fā)式樹狀搜索算法、文獻(xiàn)[3]提出的按層布局的貪婪算法、文獻(xiàn)[6]提出的并行遺傳算法、文獻(xiàn)[7]提出的禁忌搜索算法、文獻(xiàn)[12]提出的貪心隨機(jī)自適應(yīng)搜索算法、文獻(xiàn)[15]提出的改進(jìn)的GRASP、文獻(xiàn)[17]提出的混合模擬退火算法、文獻(xiàn)[19]提出的多層啟發(fā)式搜索算法、文獻(xiàn)[24]提出的VNS算法和文獻(xiàn)[25]提出的FDA算法等比較典型的算法得到的裝箱效果進(jìn)行比較分析,這些算法的計(jì)算結(jié)果與用多元優(yōu)化算法實(shí)現(xiàn)裝箱問題的計(jì)算結(jié)果如表3和表4所示.表3是前500組實(shí)例的測(cè)試結(jié)果,表4是后500組實(shí)例的測(cè)試結(jié)果.表4中最后一列是每個(gè)算法針對(duì)裝箱實(shí)例BR1～BR10取得的平均填充率.

從表3和表4中可以看出:1)從橫向數(shù)據(jù)來看,針對(duì)每一種算法,表3的裝箱效果明顯優(yōu)于表4中的裝箱效果,且從相鄰算例之間填充率的變化量來看,表3要小于表4.不難看出是箱子種類數(shù)的不同造成這一現(xiàn)象.表3中箱子的種類數(shù)、相鄰算例之間箱子種類數(shù)的變化量都小于表4.箱子種類數(shù)很多即同類箱子的數(shù)量很少時(shí),裝箱過程中立方體對(duì)齊的難度大大增加,箱子與箱子中間產(chǎn)生的廢棄空間就隨之增多,從而問題求解結(jié)果的優(yōu)度呈單調(diào)遞減的趨勢(shì),這在一定程度上體現(xiàn)了三維裝箱問題存在的一個(gè)難題:箱子的種類數(shù)越多,即箱子的多樣性越強(qiáng),問題的求解就越困難.2)從具體的平均填充率數(shù)據(jù)來看,在同時(shí)滿足方向性約束C1和穩(wěn)定性約束C2的情況下,填充率最高的是由張德富等提出的多層啟發(fā)式搜索算法MLHS的94.02%,第2是本文算法MOA的93.64%,第3是Fanslau等提出的啟發(fā)式搜索算法CLTRS的93.42%,第4是由張德富等提出的混合模擬退火算法HAS的92.24%,第5為Bortfeldt等提出的禁忌搜索算法的 89.00%,第6為Gehring等提出的并行化遺傳算法的87.20%,第7是Bischoあ等提出的按層布局的貪婪算法的81.88%.因此從數(shù)據(jù)分析結(jié)果來看,本文算法具有有效性和可行性.

表2 某次實(shí)驗(yàn)得到的填充率的變化關(guān)系表Table 2 The change table of fi lling rate obtained from an experiment

表3 各種算法的裝箱效果比較(1～500組)Table 3 Comparison of packing eあects of various(groups 1～500)algorithms

表4 各種算法的裝箱效果比較(501～1000)Table 4 Comparison of packing eあects of various(groups 501～1000)algorithms

表5給出了本文算法對(duì)BR1～BR10測(cè)試時(shí)的具體細(xì)節(jié).表5中從左起的第三列Minimum到最后一列Average分別表示本文算法在同一類型的100個(gè)測(cè)試實(shí)例的運(yùn)行中記錄下的最短運(yùn)行時(shí)間、最長(zhǎng)運(yùn)行時(shí)間、平均運(yùn)行時(shí)間、最小填充率、最大填充率和平均填充率,這里的運(yùn)行時(shí)間指程序的實(shí)際運(yùn)行時(shí)間.

從表5可以看出,1)算法最短運(yùn)行時(shí)間與最長(zhǎng)運(yùn)行時(shí)間相差很大,原因是本文算法具有較強(qiáng)的隨機(jī)性;2)隨著箱子種類數(shù)的增加,算法的運(yùn)行時(shí)間近似呈單調(diào)遞增的趨勢(shì),這是由于箱子種類數(shù)越多,在求解問題時(shí),箱子的組合情況越復(fù)雜,要取得好的裝箱效果就需付出較大的時(shí)間代價(jià).

用多元優(yōu)化算法實(shí)現(xiàn)三維裝箱問題時(shí),經(jīng)多批次隨機(jī)放置和局部調(diào)整優(yōu)化,裝箱結(jié)果逐步逼近全局最優(yōu)解的過程如圖7所示.在實(shí)驗(yàn)過程中,裝箱的批次數(shù)和每批次的裝箱個(gè)數(shù)等這些參數(shù)的設(shè)置與每一個(gè)算例的箱子總數(shù)緊密相關(guān).針對(duì)1000個(gè)算例,經(jīng)過測(cè)試,得出裝箱的批次數(shù)的取值范圍為[5,12]比較適中,每批次的裝箱個(gè)數(shù)呈緩慢遞減的趨勢(shì).

圖7 MOA實(shí)現(xiàn)裝箱問題過程中填充率變化圖Fig.7 The fi lling rate variation diagram of packing problem with MOA

本文主要驗(yàn)證MOA算法實(shí)現(xiàn)三維裝箱問題的有效性和可行性,進(jìn)一步工作將對(duì)算法參數(shù)的設(shè)置做自適應(yīng)討論研究.

表5 多元優(yōu)化算法實(shí)現(xiàn)三維裝箱問題時(shí)的一些測(cè)試細(xì)節(jié)Table 5 Some test details of MOA for 3D packing problem

5 結(jié)束語(yǔ)

三維裝箱問題屬于典型的NP難題,本文采用多元優(yōu)化算法求解,具有隨機(jī)放置、局部調(diào)整和逐步逼近三大特性.經(jīng)過多次實(shí)驗(yàn)測(cè)試,取得理想的裝箱效果,證明了多元優(yōu)化算法實(shí)現(xiàn)三維裝箱問題的有效性和可行性.由于本文采用的是分批次隨機(jī)放置,因此針對(duì)實(shí)際裝箱問題中的復(fù)雜性和不確定性具有很好的優(yōu)勢(shì).但是算法若要得到更高的裝箱效果,就要增大試驗(yàn)次數(shù),隨之計(jì)算時(shí)間也會(huì)增大.同時(shí),分多少批次裝載和每批次裝多少個(gè)等這些參數(shù)的設(shè)置與對(duì)象緊緊相關(guān),不具有一般性.

1 DyckhoあH,Finke U.Cutting and Packing in Production and Distribution.Heidelberg:Physica-Verlag,1992.

2 Ngoi B K A,Tay M L,Chua E S.Applying spatial representation techniques to the container packing problem.International Journal of Production Research,1994,32(1):111?123

3 BischoあE E,RatcliあB S W.Issues in the development of approaches to container loading.Omega,1995,23(4):377?390

4 Davies A P,BischoあE E.Weight distribution considerations in container loading.European Journal of Operational Research,1999,114(3):509?527

5 Sixt M.Dreidimensionale Packprobleme.Losungsverfahren Basierend auf den Meta-Heuristiken Simulated Annealing und Tabu-Suche.Frankfurt am Main:Europaischer Verlag der Wissenschaften,1996.

6 Gehring H,Bortfeldt A.A genetic algorithm for solving the container loading problem.International Transactions in Operational Research,1997,4(5?6):401?418

7 Bortfeldt A,Gehring H.A tabu search algorithm for weakly heterogeneous container loading problems.OR Spectrum, 1998,20:237?250

8 Bortfeldt A,Gehring H.A hybrid genetic algorithm for the container loading problem.European Journal of Operational Research,2001,131(1):143?161

9 He Da-Yong,Zha Jian-Zhong,Jiang Yi-Dong.Research on solution to complex container-loading problem based on genetic algorithm.Journal of Software,2001,12(9):1380?1385

(何大勇,查建中,姜義東.遺傳算法求解復(fù)雜集裝箱裝載問題方法研究.軟件學(xué)報(bào),2001,12(9):1380?1385)

10 Eley M.Solving container loading problems by block arrangement.European Journal of Operational Research, 2002,141(2):393?409

11 Bortfeldt A,Gehring H,Mack D.A parallel tabu search algorithm for solving the container loading problem.Parallel Computing,2003,29(5):641?662

12 Moura A,Oliveira J F.A GRASP approach to the containerloading problem.IEEE Intelligent Systems,2005,20(4):50?57

13 Zhang D F,Li X.A personi fi ed annealing algorithm for circles packing problem.Acta Automatica Sinica,2005,31(4): 590?595

14 Zhang De-Fu,Wei Li-Jun,Chen Qing-Shan,Chen Huo-Wang.A combinational heuristic algorithm for the threedimensional packing problem.Journal of Software,2007, 18(9):2083?2089

(張德富,魏麗軍,陳青山,陳火旺.三維裝箱問題的組合啟發(fā)式算法.軟件學(xué)報(bào),2007,18(9):2083?2089)

15 Parren′oo F,Alvarez-Valdes R,Oliveira J F,Tamarit J M.A maximal space-algorithm for the container loading problem.INFORMS Journal on Computing,2008,20(3):412?422

16 Huang W Q,He K.A caving degree approach for the single container loading problem.European Journal of Operational Research,2009,196(1):93?101

17 Zhang De-Fu,Peng Yu,Zhu Wen-Xing,Chen Huo-Wang. A hybrid simulated annealing algorithm for the threedimensional packing problem.Chinese Journal of Computers,2009,32(11):2147?2156

(張德富,彭煜,朱文興,陳火旺.求解三維裝箱問題的混合模擬退火算法.計(jì)算機(jī)學(xué)報(bào),2009,32(11):2147?2156)

18 Fanslau T,Bortfeldt A.A tree search algorithm for solving the container loading problem.INFORMS Journal on Computing,2010,22(2):222?235

19 Zhang De-Fu,Peng Yu,Zhang Li-Li.A multi-layer heuristic search algorithm for three dimensional container loading problem.Chinese Journal of Computers,2012,35(12):2553?2561

(張德富,彭煜,張麗麗.求解三維裝箱問題的多層啟發(fā)式搜索算法.計(jì)算機(jī)學(xué)報(bào),2012,35(12):2553?2516)

20 Liu Sheng,Zhu Feng-Hua,Lv Yi-Sheng,Li Yuan-Tao.A heuristic orthogonal binary tree search algorithm for three dimensional container loading problem.Chinese Journal of Computers,2015,38(8):1530?1543

(劉勝,朱鳳華,呂宜生,李元濤.求解三維裝箱問題的啟發(fā)式正交二叉樹搜索算法.計(jì)算機(jī)學(xué)報(bào),2015,38(8):1530?1543)

21 Zhang Ya-Jian,Liu Yong,Xie Song-Jiang.An improved genetic algorithm for bin-packing problem.Control Engineering of China,2016,23(3):327?331

(張雅艦,劉勇,謝松江.一種求解裝箱問題的改進(jìn)遺傳算法.控制工程,2016,23(3):327?331)

22 Wang Yan,Pan Wei-Ping,Zhang Jun-Hui.An algorithm for solving the problem of three-dimensional packing of singlesized cuboids.Packaging Engineering,2015,36(11):96?99

(王巖,潘衛(wèi)平,張俊暉.單一尺寸長(zhǎng)方體三維裝箱問題的一種求解算法.包裝工程,2015,36(11):96?99)

23 Ren Yue-Miao,Chen Xian-Fu,Liu Bin.Study on algorithm of three-dimensional bin packing problem for trapezoidal bin.Microcomputer and Its Applications,2015,34(9):18?21,25

(任岳淼,陳賢富,劉斌.面向梯形箱子的三維裝箱問題算法研究.微型機(jī)與應(yīng)用,2015,34(9):18?21,25)

24 Parre?no F,Alvarez-Valdes R,Oliveira J F,Tamarit J M. Neighborhood structures for the container loading problem: a VNS implementation.Journal of Heuristics,2010,16(1): 1?22

25 He K,Huang W Q.An eきcient placement heuristic for three-dimensional rectangular packing.Computers and Operations Research,2011,38(1):227?233

26 You Wei,Lei Ding-You,Zhu Xiang.Biased random-key hybrid genetic algorithm for three-dimensional loading problem.Computer Engineering and Applications,2014,50(22): 265?270

(游偉,雷定猷,朱向.三維裝箱問題的偏隨機(jī)密鑰混合遺傳算法.計(jì)算機(jī)工程與應(yīng)用,2014,50(22):265?270)

27 Zhang Ying,Liu Er-Chao,Qi Ming-Yao.Quick algorithm for the three-dimensional bin packing problem with support surface constraints.Journal of Transportation Systems Engineering and Information Technology,2014,14(2):192?198

(張瑩,劉二超,戚銘堯.考慮支撐面約束的三維裝箱問題快速求解方法.交通運(yùn)輸系統(tǒng)工程與信息,2014,14(2):192?198)

28 He Kun,Huang Wen-Qi.An action space based deterministic eきcient algorithm for solving the three-dimensional container loading.Chinese Journal of Computers,2014,37(8): 1786?1793

(何琨,黃文奇.基于動(dòng)作空間的三維裝箱問題的確定性高效率求解算法.計(jì)算機(jī)學(xué)報(bào),2014,37(8):1786?1793)

29 Xia Cheng-Ren.Methodology of teaching the principal of optimality.Journal of Anqing Teachers College(Natural Science),2003,9(2):93?95

(夏成仁.關(guān)于最優(yōu)化原理的教學(xué).安慶師范學(xué)院學(xué)報(bào)(自然科學(xué)版), 2003,9(2):93?95)

30 Li Bao-Lei,Shi Xin-Ling,Gou Chang-Xing,Lv Dan-Ju,An Zhen-Zhou,Zhang Yu-Feng.Multivariant optimization algorithm and its convergence analysis.Acta Automatica Sinica, 2015,41(5):949?959

(李寶磊,施心陵,茍常興,呂丹桔,安鎮(zhèn)宙,張榆鋒.多元優(yōu)化算法及其收斂性分析.自動(dòng)化學(xué)報(bào),2015,41(5):949?959)