基于多元優化算法的三維裝箱問題的研究

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

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

裝箱問題是傳統的NP問題,具有廣泛的應用領域.隨著當今世界信息技術、大數據、數據流、數據關系的分析處理的不斷發展,為裝箱問題的應用拓展了新的領域,例如信息網絡、交通網和云存儲等有限資源的最大利用率問題,有限資金投資的收益率最大化問題,以及大數據相對關系匹配度最大化問題等.如何提高容器的空間利用率,是當代科學研究和實踐中一個非常重要的課題.找到高利用率的裝箱方案,對節約天然資源,降低企業成本,提高企業利潤,有著十分積極的現實意義.

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

在很多實際工業應用中,待裝箱子具有規格多樣性和數量不確定性等特點.因此本文結合最優化原理,用多元優化算法(Multi-variant optimization algorithm,MOA)實現三維裝箱問題的求解,該算法的基本思想是隨機放置、局部調整和逐步逼近.通過對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.該問題的目標為:在箱子沒有溢出容器,且滿足方向性約束和穩定性約束的條件下使容器的填充率最大,即要盡可能多地將箱子裝入容器中.問題的目標函數為

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

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

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

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

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

2 裝箱準備

2.1 最優化原理

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

2.2 空間的劃分

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

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

2.3 箱子的放置

假設箱子的擺放沒有方向性約束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,則根據具體的方向性約束來選擇箱子的擺放方式.箱子放入容器時,本文算法先選擇擺放方式后選擇放置空間.

2.4 剩余子空間的合并

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

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

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

3 多元優化算法

3.1 算法簡述

多元優化算法(Multi-variant optimization algorithm,MOA)是基于全局和局部搜索交替進行的思想提出的一種全新的群智能算法,該算法在問題的解空間中隨機產生全局搜索元及相應的局部搜索元,對解空間進行全面細致地搜索,從而逐漸逼近全局最優解.算法基于計算機的數據結構,構造多元化結構體,結構體用于記憶并協調搜索信息、調動全局局部交替尋優、記憶尋優過程,多次全局局部交叉搜索后,獲得全局最優解和多個次優解[30].結構體是搜索元全局和局部交替尋優信息交流的平臺,是尋優過程記憶的載體.搜索元和結構體構成了MOA的基本框架[30].

結構體是一種能夠按照一定規則,記憶協調搜索信息,有固定結構的數據表,如圖4所示.

圖4 MOA數據結構圖Fig.4 The data structure diagram of MOA

結構體是用指針實現的二維有序鏈表,由全局鏈表和局部鏈表組成.結構體中,第一行為全局鏈表,用于保存全局搜索元并記憶和共享全局信息;每一列叫做局部鏈表,用于保存各個局部解空間內的局部搜索元和記憶局部信息.

全局鏈表和局部鏈表都是以搜索元的適應度值為關鍵字(Key)的有序鏈表.全局鏈表中前端搜索元優于后端搜索元,局部鏈表中上部搜索元優于下部搜索元.搜索元是結構體的組織細胞,用于存放和接收尋優信息.搜索元具有進行全局探索和局部調整的功能.

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

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

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

將全局鏈表記憶較優的全局元作為具有搜索價值的局部解空間的中心,根據其所在全局鏈表中的位置共享該局部解空間在所有已經發現的具有搜索價值局部解空間中的優越程度:位置越靠前,其所在區域越優.當局部搜索元發現優于全局元的解時,局部鏈表記憶較優的局部元將取代全局元作為新的具有搜索價值的局部解空間的中心,以分享局部搜索獲得的信息.

為了更好地說明MOA的實現過程,給出測試函數

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

圖5 測試尋優過程圖Fig.5 The test optimization graph

圖6 測試尋優結果圖Fig.6 The result of test results

3.2 問題的解

針對待裝箱子在實際應用中的復雜性和不確定性,本文采用多元優化算法實現三維裝箱問題,基本思想是:

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

2)局部調整:對裝入容器的局部箱子按目標函數值作局部調整;

3)逐步逼近:遞推的局部隨機放置與調整優化,使目標函數值逐步逼近最優值.

在用MOA實現三維裝箱問題的求解之前進行預處理:

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

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

多元優化算法實現背包裝載問題的具體步驟如下:

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

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

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

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

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

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

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

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

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

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

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

算法的偽代碼如下:

Begin

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

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

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

4 實驗測試

4.1 測試準備

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

4.2 測試過程

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

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

1)在測試之前的預處理

預處理1.讀取表1數據.通過程序將表1轉換為具體的數據矩陣,數據矩陣的每一行代表一種類型的箱子,每一行的前三列分別代表箱子的長、寬、高的值,最后一列代表該種類型箱子的數量.

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

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

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

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

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

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

4.3 實驗結果與分析

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

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

表2 某次實驗得到的填充率的變化關系表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測試時的具體細節.表5中從左起的第三列Minimum到最后一列Average分別表示本文算法在同一類型的100個測試實例的運行中記錄下的最短運行時間、最長運行時間、平均運行時間、最小填充率、最大填充率和平均填充率,這里的運行時間指程序的實際運行時間.

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

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

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

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

表5 多元優化算法實現三維裝箱問題時的一些測試細節Table 5 Some test details of MOA for 3D packing problem

5 結束語

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

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

(何大勇,查建中,姜義東.遺傳算法求解復雜集裝箱裝載問題方法研究.軟件學報,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

(張德富,魏麗軍,陳青山,陳火旺.三維裝箱問題的組合啟發式算法.軟件學報,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

(張德富,彭煜,朱文興,陳火旺.求解三維裝箱問題的混合模擬退火算法.計算機學報,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

(張德富,彭煜,張麗麗.求解三維裝箱問題的多層啟發式搜索算法.計算機學報,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

(劉勝,朱鳳華,呂宜生,李元濤.求解三維裝箱問題的啟發式正交二叉樹搜索算法.計算機學報,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

(王巖,潘衛平,張俊暉.單一尺寸長方體三維裝箱問題的一種求解算法.包裝工程,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

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

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

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

(何琨,黃文奇.基于動作空間的三維裝箱問題的確定性高效率求解算法.計算機學報,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

(夏成仁.關于最優化原理的教學.安慶師范學院學報(自然科學版), 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

(李寶磊,施心陵,茍常興,呂丹桔,安鎮宙,張榆鋒.多元優化算法及其收斂性分析.自動化學報,2015,41(5):949?959)