基于多元優(yōu)化算法的三維裝箱問題的研究

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

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

裝箱問題是傳統(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)和云存儲等有限資源的最大利用率問題,有限資金投資的收益率最大化問題,以及大數(shù)據(jù)相對關(guān)系匹配度最大化問題等.如何提高容器的空間利用率,是當(dāng)代科學(xué)研究和實踐中一個非常重要的課題.找到高利用率的裝箱方案,對節(jié)約天然資源,降低企業(yè)成本,提高企業(yè)利潤,有著十分積極的現(xiàn)實意義.

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

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

1 問題描述

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

在實際裝箱問題中,一般會遇到3個著名的約束條件[18]:

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

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

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

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

2 裝箱準(zhǔn)備

2.1 最優(yōu)化原理

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

2.2 空間的劃分

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

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

2.3 箱子的放置

假設(shè)箱子的擺放沒有方向性約束C1,則在裝箱過程中,箱子的任意一條邊都可以豎直放置,此時可以將箱子的擺放方式細分為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ù)具體的方向性約束來選擇箱子的擺放方式.箱子放入容器時,本文算法先選擇擺放方式后選擇放置空間.

2.4 剩余子空間的合并

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

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

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

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

3.1 算法簡述

多元優(yōu)化算法(Multi-variant optimization algorithm,MOA)是基于全局和局部搜索交替進行的思想提出的一種全新的群智能算法,該算法在問題的解空間中隨機產(chǎn)生全局搜索元及相應(yīng)的局部搜索元,對解空間進行全面細致地搜索,從而逐漸逼近全局最優(yōu)解.算法基于計算機的數(shù)據(jù)結(jié)構(gòu),構(gòu)造多元化結(jié)構(gòu)體,結(jié)構(gòu)體用于記憶并協(xié)調(diào)搜索信息、調(diào)動全局局部交替尋優(yōu)、記憶尋優(yōu)過程,多次全局局部交叉搜索后,獲得全局最優(yōu)解和多個次優(yōu)解[30].結(jié)構(gòu)體是搜索元全局和局部交替尋優(yōu)信息交流的平臺,是尋優(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)體是用指針實現(xiàn)的二維有序鏈表,由全局鏈表和局部鏈表組成.結(jié)構(gòu)體中,第一行為全局鏈表,用于保存全局搜索元并記憶和共享全局信息;每一列叫做局部鏈表,用于保存各個局部解空間內(nèi)的局部搜索元和記憶局部信息.

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

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

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

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

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

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

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

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

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

3.2 問題的解

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

算法的偽代碼如下:

Begin

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

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

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

4 實驗測試

4.1 測試準(zhǔn)備

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

4.2 測試過程

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

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

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

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

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

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

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

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

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

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

4.3 實驗結(jié)果與分析

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

從表3和表4中可以看出:1)從橫向數(shù)據(jù)來看,針對每一種算法,表3的裝箱效果明顯優(yōu)于表4中的裝箱效果,且從相鄰算例之間填充率的變化量來看,表3要小于表4.不難看出是箱子種類數(shù)的不同造成這一現(xiàn)象.表3中箱子的種類數(shù)、相鄰算例之間箱子種類數(shù)的變化量都小于表4.箱子種類數(shù)很多即同類箱子的數(shù)量很少時,裝箱過程中立方體對齊的難度大大增加,箱子與箱子中間產(chǎn)生的廢棄空間就隨之增多,從而問題求解結(jié)果的優(yōu)度呈單調(diào)遞減的趨勢,這在一定程度上體現(xiàn)了三維裝箱問題存在的一個難題:箱子的種類數(shù)越多,即箱子的多樣性越強,問題的求解就越困難.2)從具體的平均填充率數(shù)據(jù)來看,在同時滿足方向性約束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 某次實驗得到的填充率的變化關(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給出了本文算法對BR1～BR10測試時的具體細節(jié).表5中從左起的第三列Minimum到最后一列Average分別表示本文算法在同一類型的100個測試實例的運行中記錄下的最短運行時間、最長運行時間、平均運行時間、最小填充率、最大填充率和平均填充率,這里的運行時間指程序的實際運行時間.

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

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

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

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

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

5 結(jié)束語

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

(張德富,彭煜,朱文興,陳火旺.求解三維裝箱問題的混合模擬退火算法.計算機學(xué)報,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ā)式搜索算法.計算機學(xué)報,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ā)式正交二叉樹搜索算法.計算機學(xué)報,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

(張雅艦,劉勇,謝松江.一種求解裝箱問題的改進遺傳算法.控制工程,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)平,張俊暉.單一尺寸長方體三維裝箱問題的一種求解算法.包裝工程,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

(任岳淼,陳賢富,劉斌.面向梯形箱子的三維裝箱問題算法研究.微型機與應(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

(游偉,雷定猷,朱向.三維裝箱問題的偏隨機密鑰混合遺傳算法.計算機工程與應(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

(張瑩,劉二超,戚銘堯.考慮支撐面約束的三維裝箱問題快速求解方法.交通運輸系統(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

(何琨,黃文奇.基于動作空間的三維裝箱問題的確定性高效率求解算法.計算機學(xué)報,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é)報(自然科學(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)化算法及其收斂性分析.自動化學(xué)報,2015,41(5):949?959)