基于最大最小蟻群算法的智能裝載方法

葛瑋,徐衛(wèi)紅,程海水

江西廣播電視大學,江西南昌330000

基于最大最小蟻群算法的智能裝載方法

葛瑋,徐衛(wèi)紅,程海水

江西廣播電視大學,江西南昌330000

三維裝箱問題在現(xiàn)實生活中有著廣泛的應用，是具有復雜約束的組合優(yōu)化問題，理論上屬于NP-hard問題。針對貪心算法通常得到的是局部最優(yōu)解以及基本蟻群算法存在不足等問題，本文首先給出了啟發(fā)式裝箱規(guī)則，然后結(jié)合最大最小蟻群算法對裝載順序進行優(yōu)化，提出了一個求解三維裝箱問題的混合蟻群算法，最后通過實驗對比驗證了該算法的有效性和優(yōu)越性，并給出了三維效果展示圖。

三維裝箱;啟發(fā)式;最大最小蟻群算法

裝箱問題在現(xiàn)實生活中具有廣泛應用，如切割加工業(yè)和運輸業(yè)。高利用率的切割和裝載可以節(jié)約大量成本。實際應用中由于不同的優(yōu)化目標和裝載約束，導致了不同種類的裝箱問題。Dyckhoff和Finke概述了不同類型的裝箱問題[1]。本文所處理的三維裝箱問題是其中之一。

三維裝箱問題是具有復雜約束條件的組合優(yōu)化問題，理論上屬于NP-hard問題[2]，采用精確求解算法是不現(xiàn)實的，因此啟發(fā)式求解方法成為理論研究和實際應用的首選。Ngoi[3]以及Bischoff[4]等提出了一些啟發(fā)式算法。Gehring[5]等將遺傳算法應用到裝箱問題中。Bortfeldt[6]等分別提出了禁忌搜索求解算法、混合遺傳求解算法和基于分支定界的一個啟發(fā)式算法。Moura等提出了一個隨機自適應啟發(fā)式算法GRASP[7].國內(nèi)學者在三維裝箱問題的研究上，也取得了不錯的成果[8-14]，特別是黃文奇等提出了一種最大穴度的占角動作優(yōu)先的擬人型求解算法[13]，張德富等將啟發(fā)式算法和模擬退火算法相結(jié)合，提出了混合求解算法[14]。通過對上述文獻的研究分析，發(fā)現(xiàn)啟發(fā)式算法和一些智能算法以及二者的結(jié)合對解決三維裝箱問題很有效果。

本文采用最大最小蟻群算法結(jié)合啟發(fā)式算法對其進行優(yōu)化，提出了一個有效的求解三維裝箱問題的混合算法，克服了傳統(tǒng)貪心算法容易陷入局部最優(yōu)值的不足。

1 問題描述

本文探討的三維裝箱問題的形式化定義：給定一個長方體容器C和一個待裝箱的長方體箱子集合B={b1,...,bn}，容器C的長寬高分別為L, W, H，最大載重量Z，為每個箱子bi的長寬高為li, wi, hi，重量為zi。設(shè)S為B的一個子集，問題的目標是確定一個可行的放置箱子的方案，即選擇B的一個合適的子集S使得滿足給定約束的情況下，容器的空間利用率最大，即

放置方案要求滿足如下7個條件：

(1)被裝載的箱子必須完全被包含在容器中；

(2)任何兩個被裝載的箱子不能相互重疊；

（3）所有被裝載的箱子的擺放方向與容器的三維保持正交；

（4）方向約束C1：分為任意翻轉(zhuǎn)和水平旋轉(zhuǎn)兩種；

（5）容器最大承重約束C2：裝載完成后，貨物的總重量不得超過容器的最大限重；

（6）穩(wěn)定性約束C3：每個被裝載的箱子必須得到容器底部或者其他箱子的支撐，也就是說禁止被裝載的箱子懸空；

（7）承壓約束C4：本文只考慮0～1承壓約束，即該箱子上可放置(1)或不可放置(0)其他箱子。

2 基于最大最小蟻群算法的智能裝載方法

2.1 啟發(fā)式裝箱算法

2.1.1 空間分解本文對容器布局空間的分解過程采用單鏈表數(shù)據(jù)結(jié)構(gòu)表示。首先對原始布局空間求解，此時，原始布局空間為容器的內(nèi)部空間，單鏈表中只有一項，包含該空間的左后下角的三維坐標(0,0,0)以及容器長寬高的值。然后按照某一裝載順序，從可選待裝載箱子中選擇一個箱子，在鏈表中從表頭開始查找一塊可裝下該箱子的空間并將其定位于當前布局空間左后下角，如圖1位置所示。由圖可知，箱子將原空間劃分為前空間fronts，右空間rights和上空間ups，將這三個空間按序插入到鏈表中，并刪除原空間，從可選待裝載箱子集合中刪除該箱子。對這三個布局空間依次重復上述過程，直至所有箱子裝載完成或容器已沒有可利用空間。

圖1 空間劃分示意圖Fig.1 Schematic diagram of space division

2.1.2 剩余空間合并剩余空間指待裝填的空間。在算法初始階段，剩余空間是整個集裝箱。隨著上節(jié)的空間分解，剩余空間越來越多，體積越來越小，會產(chǎn)生一些不能裝入任何箱子的剩余空間。如果能將這些較小的剩余空間盡量與其他剩余空間進行合并，則可大大提高空間利用率。剩余空間合并的算法細化如下：

假設(shè)待插入鏈表的空間為s，剩余空間鏈表S={si}，算法的具體流程如下圖2所示。

2.1.3 算法規(guī)則首先根據(jù)待裝載的箱子集合B={b1,...,bn }得到一個序列p={P1, P2,...,Pn }，Pi∈[1,n]且為整數(shù)，其值代表箱子的編號，按這個順序進行裝填。整體的算法流程如下：

1初始化：剩余空間鏈表S，表中只有一項s0，即容器的內(nèi)部空間，左后下角坐標為(0,0,0)，

圖2 剩余空間合并算法流程圖Fig.2 The remaining space merging algorithm flow chart

長寬高為容器的長寬高(,,L W H)；箱子集合B中所有箱子的狀態(tài)標記isLoaded=false。

返回容器C最終的空間利用率。

2.2 基于最大最小蟻群算法的裝載算法

2.2.1 蟻群算法蟻群算法是一種模擬進化算法，利用蟻群在搜索食物源的過程中體現(xiàn)出的尋優(yōu)能力解決一些離散系統(tǒng)優(yōu)化中的問題。蟻群算法不需要任何先驗知識，最初只是隨機地選擇搜索路徑，隨著對解空間的“了解”，搜索變得有規(guī)律，逐漸逼近從而最終到達全局最優(yōu)解。對解空間的“了解”

主要表現(xiàn)兩個方面：①螞蟻之間利用信息素相互通信：螞蟻在所選擇的路徑上會釋放一種稱為信息素的物質(zhì)，當螞蟻選擇路徑時，會根據(jù)路徑上殘留的信息素進行選擇；②群體智能：通過一只螞蟻的運動很難找到食物源，但整個蟻群進行搜索一般就能找到。當某些路徑上的信息素量越來越多，螞蟻選擇該路徑的概率隨之增加，進而又增加了該路徑上的信息素強度。同時所有路徑上的信息素隨時間而蒸發(fā)。模擬這種現(xiàn)象即可利用群體智能建立尋優(yōu)機制，使蟻群算法的搜索向最優(yōu)解推進。本文采用的最大最小蟻群算法是改進的蟻群算法，比基本的蟻群算法的尋優(yōu)效果更佳。

2.2.2 混合蟻群算法的啟發(fā)式裝裝載方法1）編碼編碼是把一個問題的可行解從其解空間轉(zhuǎn)換到蟻群算法所能處理的搜索空間操作。本文將待裝載箱子的編號按某一裝載順序編成串作為一個解的編碼，也是一條路徑，即

式中：n為待裝載的箱子的個數(shù)；iP為整數(shù)，其值代表箱子的編號。簡單地，可以根據(jù)箱子的體積從大到小排序，即貪心策略得到序列p，是可行解集合中的一個。

通過信息素對串P進行操作實際上就是改變待裝載箱子的裝載順序，從而可以產(chǎn)生不同的解序列。

2）信息素與路徑選擇概率蟻群覓食時，信息素濃度越大的路徑總長度越短。對于三維裝箱來說，可以用適應度函數(shù)來評價一個解的好壞，適應度值越大，解的質(zhì)量越高。本文的適應度函數(shù)f取容器的空間利用率，。路徑上的信息素更新滿足如下公式：

其中，ρ為信息素殘留因子（1-ρ為信息素揮發(fā)因子），Δτbest=1/f( Sbest)，f( Sbest)為全局最

ij優(yōu)路徑或局部最優(yōu)路徑的適應度值。本文采用的最大最小蟻群算法，路徑上的信息素濃度，最大信息素閾值取適應度，即maxbestfτ=，最小信息素閾值其中參數(shù)bestp一般取0.5，n為待裝載箱子的數(shù)量。

路徑選擇概率：在運動過程中，第k只螞蟻根據(jù)各條路徑上的信息素濃度決定轉(zhuǎn)移方向，即第k只螞蟻在i節(jié)點時選擇下一個節(jié)點j的概率為

其中，ijη為期望啟發(fā)信息，這里選取箱子i與箱子j占容器C總體積的比值差的倒數(shù)；α為信息素啟發(fā)式因子，β為期望啟發(fā)式因子。

3）算法流程

本文提出混合蟻群算法是先采用蟻群算法得到一個初始的裝箱順序，然后再調(diào)用啟發(fā)式算法解碼，原裝箱順序可能因為約束等因素會有所改變，信息素是根據(jù)解碼后實際的裝箱順序來更新的，具體如下：

步驟1：初始化參數(shù)，設(shè)定迭代次數(shù)ncmax，nc，螞蟻數(shù)量m，α、β的值，初始化信息素啟發(fā)表τij(0)，計算啟發(fā)式信息表ηij。

步驟2：將螞蟻k( k=1,2,...,m)的初始出發(fā)點置于當前解集中（初始解集為空），由式（2）的概率pk(t)計算螞蟻k，移至下一結(jié)點，將結(jié)點j加入當前解集，最后得出一組編碼P，ij即一個裝箱順序。

步驟3：調(diào)用啟發(fā)式算法對編碼進行譯碼，實際裝箱順序可能會有所改變，記為P'，計算各螞蟻走完完整路徑后得到的適應度值，記錄當前最好的解P'best。

步驟4：按式（1）更新路徑上的信息素。

步驟5：nc＜--nc+1。若nc＜ncmax，則返回步驟（2）。

步驟6：輸出當前最優(yōu)解。

3 實驗對比及結(jié)果展示

假設(shè)待布局的容器為國際標準的集裝箱，尺寸為2.352 m×2.388 m×5.899 m，最大承載質(zhì)量為18.07 t[9]。首先根據(jù)文獻[4]中隨機產(chǎn)生箱子的方法，與第3節(jié)中基于貪心算法的簡單啟發(fā)式算法進行比較實驗。箱子的種類為8種，每個箱子ib的尺寸滿足：0.05 L＜li＜0.5 L，0.05 W＜wi＜0.5W，0.05 H＜hi＜0.5 H；重量約束滿足：zi＜0.05 Z。在滿足約束C1（可任意翻轉(zhuǎn)）、C2、C3和C4（可放置）的條件下，50組隨機數(shù)據(jù)實驗的平均結(jié)果為：混合蟻群算法空間利用概率為83.92%，基于貪心算法的簡單啟發(fā)式算法空間利用概率為75.68%。混合蟻群算法的結(jié)果明顯優(yōu)于啟發(fā)式算法，并且發(fā)現(xiàn)箱體尺寸越小，數(shù)目越多，混合蟻群算法的結(jié)果越好，啟發(fā)式算法結(jié)果越差。

另外將本文混合蟻群算法與文獻[10]中采用基本蟻群算法進行了比較實驗，滿足約束C1（可任意翻轉(zhuǎn)）、C2、C3和C4（可放置）。待裝載的箱子數(shù)據(jù)參見文獻[10]中的表1，箱子數(shù)量為30。蟻群算法的參數(shù)設(shè)置：ncmax=50，m=30，α=1，β=5，ρ=0.95。運行10次的平均結(jié)果如下：本文算法的空間利用率為85.67%，文獻[10]中采用基本蟻群算法得到的空間利用率為84.09%，簡單啟發(fā)式算法的空間利用率只有82.28%。相比之本文算法效果更佳，速度跟文獻[10]中的算法差不多。下表1是本文算法的最好結(jié)果。

表1 裝箱測試結(jié)果Table1 Loading test results

在x3dom網(wǎng)上開放源代碼的基礎(chǔ)上，制作了一個可以展示三維裝箱的html網(wǎng)頁，表1的裝箱測試結(jié)果的三維展示效果圖如圖3所示。

4 總結(jié)

通過對大量三維裝箱方面文獻的閱讀和研究分析，發(fā)現(xiàn)將智能算法和啟發(fā)式算法結(jié)合對解決三維裝箱問題很有效果。因此，本文將最大最小蟻群算法與啟發(fā)式規(guī)則相結(jié)合，提出了一個解決三維裝箱問題的混合蟻群算法。通過實驗對比，驗證了該算法的優(yōu)越性。

本文優(yōu)化算法采用的是最大最小蟻群算法，對參數(shù)值的大小依賴很高，今后的研究可以考慮改進最大最小蟻群算法，使其更好地與三維裝箱問題相結(jié)合；還可以考慮換成其他更新更先進的智能算法，可能會得到更好的解。本文只研究了單一容器的三維裝箱問題，今后可以考慮在此基礎(chǔ)上研究多容器的裝箱問題。

圖4 表1中裝箱結(jié)果的三維展示Fig.4 Three dimensional display cases results in table 1

[1]Guntram Scheithauer.Algorithms for the Container Loading Problem[J].Operations Research Proceedings,1992,1991:445 -452

[2]Johnson D S.計算機和難解性—NP完全性理論導論[M].張立昂譯.北京:科學出版社,1990

[3]Ngoi BKA,Tay ML,Chua ES.Applying spatial representation techniques to the container packing problem[J]. International Journal of Production Research,1994,32(1):111-123

[4]Bisehoff E E,Ratcliff B S W.Issues in the development of approaches to container loading[J].Omega,1995, 23(4):377-390

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

[6]Bortfeldt A,Gehring H.A hybrid genetic algorithm for the container loading problem[J].European Journal of Operational Research,2001,13l(1):143-161

[7]MouraA,Oliveira J F.AGRASP approach to the container loading problem[J].IEEE Intelligent,2005,20(4):50-57

[8]李廣強,滕弘飛.裝填布局的同構(gòu)和非同構(gòu)模式[J].計算機學報,2003,10:1248-1254

[9]陳建嶺.集裝箱裝載問題的啟發(fā)式優(yōu)化算法[J].山東交通學院學報,2005,13(3):53-56

[10]莊鳳庭,張磊,張春鮮,等.基于蟻群算法的集裝箱裝載問題[J].江南大學學報(自然科學版),2007,12(6):795-799

[11]張德富,魏麗軍,陳青山,等.三維裝箱問題的組合啟發(fā)式算法[J].軟件學報,2007,18(9):2083-2089

[12]寧愛兵,熊小華,馬良.城市物流配送中的三維裝箱算法[J].計算機工程與應用,2009,45(9):207-211

[13]Huang Wen-Qi,He Kun.A caving degree approach for the single container loading problem[J].European Journal of Operational Research,2009,196(1):93-101

[14]張德富,彭煜,朱文興,等.求解三維裝箱問題的混合模擬退火算法[J].計算機學報,2009,32(11):2147-2156

[15]藍啟明,張東站.公路物流智能配載的研究和裝載算法設(shè)計[J].計算機工程與應用,2012,48(33):237-243

[16]吳楚楠,劉科峰,彭斯俊,等.大規(guī)模集裝箱裝載問題[J].計算機工程與應用,2013,49(1):231-233,257

Intelligent Loading Methods Based on Max-min Ant Colony Algorithm

GE Wei,XU Wei-hong,CHENG Hai-shui
Jiangxi Radio&TV University,Nanchang 330000,China

Three dimensional container loading problem in real life has a wide range of applications,and it is a combination of complex constrained optimization problems belong to NP-hard in the theory.For the greedy algorithm usually to get a local optimal solution and the basic ant colony algorithm deficiencies and other issues.Firstly this paper gave a Heuristics boxing rules,and then combined the max-min ant colony optimization algorithm to optimize the loading sequence and proposed to solve a three-dimensional hybrid ant colony algorithm for bin packing problem.Finally validated by experiments comparing the effectiveness and superiority of the algorithm,and gave a figure of three-dimensional demonstration.

Three dimensional container loading problem;heuristics;max-min ant colony algorithm

TP18

A

1000-2324(2014)03-0366-06

2013-03-11

2013-04-25

江西省教育廳發(fā)展規(guī)劃課題(JXJG-13-71-4)

葛瑋(1981-),男,碩士,講師,主要從事智能計算機研究.