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

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

江西廣播電視大學(xué),江西南昌330000

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

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

江西廣播電視大學(xué),江西南昌330000

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

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

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

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

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

1 問題描述

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

放置方案要求滿足如下7個(gè)條件：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3）算法流程

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

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

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

步驟3：調(diào)用啟發(fā)式算法對編碼進(jìn)行譯碼，實(shí)際裝箱順序可能會有所改變，記為P'，計(jì)算各螞蟻?zhàn)咄晖暾窂胶蟮玫降倪m應(yīng)度值，記錄當(dāng)前最好的解P'best。

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

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

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

3 實(shí)驗(yàn)對比及結(jié)果展示

假設(shè)待布局的容器為國際標(biāo)準(zhǔn)的集裝箱，尺寸為2.352 m×2.388 m×5.899 m，最大承載質(zhì)量為18.07 t[9]。首先根據(jù)文獻(xiàn)[4]中隨機(jī)產(chǎn)生箱子的方法，與第3節(jié)中基于貪心算法的簡單啟發(fā)式算法進(jìn)行比較實(shí)驗(yàn)。箱子的種類為8種，每個(gè)箱子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組隨機(jī)數(shù)據(jù)實(shí)驗(yàn)的平均結(jié)果為：混合蟻群算法空間利用概率為83.92%，基于貪心算法的簡單啟發(fā)式算法空間利用概率為75.68%?；旌舷伻核惴ǖ慕Y(jié)果明顯優(yōu)于啟發(fā)式算法，并且發(fā)現(xiàn)箱體尺寸越小，數(shù)目越多，混合蟻群算法的結(jié)果越好，啟發(fā)式算法結(jié)果越差。

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

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

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

4 總結(jié)

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

本文優(yōu)化算法采用的是最大最小蟻群算法，對參數(shù)值的大小依賴很高，今后的研究可以考慮改進(jìn)最大最小蟻群算法，使其更好地與三維裝箱問題相結(jié)合；還可以考慮換成其他更新更先進(jìn)的智能算法，可能會得到更好的解。本文只研究了單一容器的三維裝箱問題，今后可以考慮在此基礎(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.計(jì)算機(jī)和難解性—NP完全性理論導(dǎo)論[M].張立昂譯.北京:科學(xué)出版社,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]李廣強(qiáng),滕弘飛.裝填布局的同構(gòu)和非同構(gòu)模式[J].計(jì)算機(jī)學(xué)報(bào),2003,10:1248-1254

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

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

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

[12]寧愛兵,熊小華,馬良.城市物流配送中的三維裝箱算法[J].計(jì)算機(jī)工程與應(yīng)用,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].計(jì)算機(jī)學(xué)報(bào),2009,32(11):2147-2156

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

[16]吳楚楠,劉科峰,彭斯俊,等.大規(guī)模集裝箱裝載問題[J].計(jì)算機(jī)工程與應(yīng)用,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-),男,碩士,講師,主要從事智能計(jì)算機(jī)研究.