魏 平，熊偉清

求解強(qiáng)異類集裝箱裝載問題的混合蟻群算法

魏 平，熊偉清

針對強(qiáng)異類集裝箱裝載問題，設(shè)計(jì)了一種混合蟻群算法。算法中搜索空間分為貨物擺放的優(yōu)先序列和貨物擺放的狀態(tài)兩部分；引入體積大的貨物優(yōu)先放入的啟發(fā)式規(guī)則；將螞蟻搜索得到的序列與歷史最優(yōu)序列進(jìn)行交叉，取三者最優(yōu)序列作為該螞蟻的搜索路徑；在更新信息素時(shí)，采取兩種揮發(fā)系數(shù)更新信息素以避免信息素過快飽和，同時(shí)分析了算法的復(fù)雜度。通過三個(gè)強(qiáng)異類實(shí)例的測試，表明算法得到的裝載方案有較高的空間利用率。

集裝箱裝載；蟻群優(yōu)化算法；啟發(fā)式規(guī)則；整數(shù)規(guī)劃

1 引言

集裝箱裝載問題（CLP）是物流配送的重要環(huán)節(jié)，其方案的優(yōu)劣對整個(gè)物流系統(tǒng)的效率以及運(yùn)輸成本有著重大的影響，有著廣泛的應(yīng)用背景，如在現(xiàn)實(shí)生活中的包裝、裁剪、內(nèi)存管理等。CLP是一個(gè)具有復(fù)雜約束條件的組合優(yōu)化問題，在理論上屬于NP-hard問題，通常實(shí)用的求解方法都是近似算法[1-2]。目前常用的求解方法有數(shù)學(xué)規(guī)劃法、圖論法、啟發(fā)式方法、遺傳算法、模擬退火算法，以及禁忌搜索算法等[3-4]。Bortfeldt[5]提出按照貨物情形來進(jìn)行分類：（1）“同類”問題，貨物的規(guī)格完全相同，即單一尺寸貨物的裝填問題；（2）“強(qiáng)異類”問題，貨物有很多不同的類型，每類貨物數(shù)量很少；（3）“弱異類”問題，貨物只有少數(shù)幾種不同的類型，每類貨物具有一定的數(shù)量。從分類可以看出，強(qiáng)異類集裝箱裝載是最復(fù)雜得一類集裝箱裝載問題。

蟻群優(yōu)化算法（ACO）是一種仿生學(xué)算法，是由意大利學(xué)者M(jìn).Dorigo[6-7]等人提出的。目前蟻群算法在理論研究和實(shí)際應(yīng)用上均取得了較大發(fā)展，已應(yīng)用于眾多優(yōu)化領(lǐng)域，其中，在組合優(yōu)化領(lǐng)域的應(yīng)用最為廣泛，包括旅行商問題（TSP）、二次指派問題（QAP）、車間作業(yè)調(diào)度問題（JSP）以及車輛調(diào)度問題（VRP）等。

考慮到蟻群算法在求解組合優(yōu)化問題上的優(yōu)勢，本文嘗試?yán)孟伻簝?yōu)化算法求解強(qiáng)異類集裝箱裝載問題。

2 集裝箱裝載問題數(shù)學(xué)模型

假設(shè)集裝箱的長、寬、高分別為L、W、H，最大裝載質(zhì)量為G，貨物的種類數(shù)為n，第i(i=1，2，…，n)類貨物的長、寬、高、數(shù)量分別為li、wi、hi、ki。

裝箱的目標(biāo)為滿足一定約束條件下最大化體積裝載率或重量裝載率，以提高集裝箱的利用率，獲得最佳的效益[1]：

λ為0-1變量。λ=1，表示以最大體積裝載率為目標(biāo)；λ=0，

CNKI出版日期：2011-12-09 http://www.cnki.net/kcms/detail/11.2127.TP.20111209.1000.017.html表示以最大重量裝載率為目標(biāo)。numi表示第i類貨物裝入集裝箱的個(gè)數(shù)，其中0≤numi≤ki。

在實(shí)際的集裝箱裝載問題中，不同的情況需要考慮不同的約束條件。本文考慮如下限制條件：

（1）方向的約束。一般貨物裝載時(shí)的方向約束有兩種，即任意旋轉(zhuǎn)和水平旋轉(zhuǎn)。

（2）貨物穩(wěn)定性的約束。貨物裝載應(yīng)該使重心位于允許的范圍內(nèi)而確保整體穩(wěn)定，以利于運(yùn)輸安全。假設(shè)貨物的重心與貨物的幾何重心相同，則一件貨物堆在另一件貨物之上時(shí)，只要各邊的尺寸的80%～100%被它下面的貨物所支撐，那么這件貨物在運(yùn)輸和裝載過程中就不會傾倒，能夠保持穩(wěn)定。

（3）任意兩件已放進(jìn)集裝箱的貨物沒有嵌入（即兩貨物重疊的體積不能大于0）。

（4）任一放進(jìn)集裝箱的貨物的每一個(gè)面必須和集裝箱的某一個(gè)面平行。

（5）任一放進(jìn)集裝箱的貨物不能超出集裝箱的邊界。

3 空間三叉樹定義與裝載策略

3.1 空間三叉樹定義

為了確保貨物沒有懸空現(xiàn)象，對空間采用三叉樹分割法。當(dāng)貨物放入集裝箱后，該集裝箱被分割成前、右、上三個(gè)空間，每個(gè)子空間在裝填貨物過程中，在放入貨物后同樣被繼續(xù)分割為三個(gè)空間[1]?？臻g劃分如圖1所示。

圖1 空間劃分示意圖

空間三叉樹定義如下：

空間三叉樹

{

數(shù)據(jù)對象D：D表示可利用的空間

數(shù)據(jù)關(guān)系R：R是如下二元關(guān)系：

若D=Φ，則R=Φ，為空三叉樹；

若D≠Φ，則R={H}，H是如下二元關(guān)系：

在D中存在唯一的根元素root，若 D-{root}≠Φ，則存在D-{root}={Dt，Dr，Df}，且Dt∩Dr=Φ，Dt∩Df=Φ，Dr∩Df=Φ。

若 Dt≠Φ，則 Dt中存在唯一的元素 xt，＜root，xt＞∈H，且存在 Dt上的關(guān)系Ht?H；若Dr≠Φ，則Dr中存在唯一的元素xr，＜root，xr＞∈H，且存在Dr上的關(guān)系Hr?H；若Df≠Φ，則Df中存在唯一的元素 xf，＜root，xf＞∈H，且存在Df上的關(guān)系Hf?H。H={＜root，xt＞，＜root，xr＞，＜root，xf＞，Ht，Hr，Hf}；

(Dt，{Ht})是一棵符合本定義的三叉樹，為根的左子樹，(Dr，{Hr})是一棵符合本定義的三叉樹，為根的中子樹，(Df，{Hf})是一棵符合本定義的三叉樹，為根的左子樹。

基本操作P：

CreateChild(T，e)：T為當(dāng)前生成的三叉樹，e為T的葉子結(jié)點(diǎn)，設(shè)GS表示未裝入集裝箱的貨物集，V表示結(jié)點(diǎn)e代表的空間，GV表示能裝入V的貨物集(GV={g|g∈GS，V≥g})，若GV≠Φ，選擇其中一件貨物裝入V，并為結(jié)點(diǎn)e產(chǎn)生三個(gè)子結(jié)點(diǎn)；否則結(jié)點(diǎn)e為最終生成三叉樹的葉子結(jié)點(diǎn)。

CreateTree()：根結(jié)點(diǎn)代表集裝箱的空間，通過操作CreateChild(T，e)，按照左子樹、中子樹和右子樹的順序深度優(yōu)先構(gòu)造三叉樹，最終生成的三叉樹對應(yīng)一個(gè)裝載方案。

}

其中，＜root，xt＞，＜root，xr＞，＜root，xf＞表示在空間root中裝入貨物后，xt、xr、xf分別為將空間root劃分產(chǎn)生的上空間、右空間、前空間。

3.2 裝載策略

一次裝箱過程實(shí)際可以看做一棵三叉樹的建立過程，結(jié)點(diǎn)代表可利用的空間，一個(gè)結(jié)點(diǎn)是否還有子結(jié)點(diǎn)取決于是否還有貨物能裝入該結(jié)點(diǎn)所代表的空間。由于可利用空間可用三叉樹來表示，那么可用遞歸算法進(jìn)行描述：

步驟1把一件貨物裝入一個(gè)可利用空間中，將可利用空間分成三個(gè)子空間。

步驟2把每個(gè)子空間中按照步驟1的方法遞歸的裝入貨物。如果子空間的大小只能裝入一件貨物，那么，就把那件貨物直接裝入子空間中。

步驟3每個(gè)子空間的解結(jié)合起來就是裝箱問題的解。偽代碼如下：

4 混合蟻群算法設(shè)計(jì)

4.1 目標(biāo)函數(shù)

對于集裝箱裝載問題，關(guān)注的目標(biāo)可能有多方面，例如容積利用率、重量裝載率、穩(wěn)定性等，但容積利用率是集裝箱裝載問題最為關(guān)注的目標(biāo)。本文以集裝箱的容積利用率最大化為目標(biāo)，即取λ=1，目標(biāo)函數(shù)為：

各參數(shù)含義見第2章。

4.2 編碼和解碼

（1）編碼

對于每個(gè)可利用的空間，要選擇一件貨物以某一狀態(tài)裝入。因此，編碼時(shí)考慮貨物裝載優(yōu)先順序和貨物放置狀態(tài)。編碼 p={p1，p2，…，pn}，對于 pi(i=1，2，…，n)包含兩部分，貨物的編號ki(1≤ki≤n)和放置狀態(tài)si，其中?i≠j，ki≠kj。

貨物狀態(tài)定義如下：

對于第i類貨物，若方向上沒有約束，則其放置的狀態(tài)有P33=6種（固定集裝箱的L、W、H順序，貨物l、w、h的全排列）。分別為

若方向上有約束（某個(gè)面必須朝上），則其放置的狀態(tài)有P22=2種。分別為：

（2）解碼

根據(jù)編碼p得到實(shí)際裝載方案步驟如下：

步驟1棧S保存可利用的空間，初始時(shí)保存集裝箱的空間。

步驟2若S中還有可利用的空間，取出棧頂?shù)目臻g作為當(dāng)前待裝空間V；否則結(jié)束。

步驟3按照編碼p中的順序，依次對 pi進(jìn)行判斷，直到滿足如下條件：貨物ki未裝入，并且按狀態(tài)si能裝入V中。

步驟3.1若存在這樣的貨物，則按指定狀態(tài)放入集裝箱，將貨物ki標(biāo)記為已裝入，將V劃分成三個(gè)子空間壓入S，返回步驟2。

步驟3.2若不存在這樣的貨物，則丟棄空間V，返回步驟2。

4.3 算子設(shè)計(jì)

（1）序列選擇

螞蟻根據(jù)路徑上的信息素以及啟發(fā)信息選擇貨物序列。t時(shí)刻，螞蟻k選擇首件貨物編號為i的概率(t)為：

螞蟻k選擇貨物i后緊接著選擇貨物j的概率 pkij(t)：

其中，τi，j(t)為t時(shí)刻從貨物i到貨物j的信息素，為t時(shí)刻螞蟻k在選擇貨物i后剩余未被選擇貨物的集合。初始時(shí)貨物序列信息素如下：

選擇貨物后，為該貨物選擇擺放狀態(tài)。對于貨物i選擇狀態(tài)s的概率為：

（2）交叉操作

將螞蟻搜索得到的序列與歷史最優(yōu)序列進(jìn)行交叉，取三者最優(yōu)序列作為該螞蟻的搜索路徑。為了保證交叉后還是有效序列，即同一個(gè)貨物編號不能在序列中重復(fù)出現(xiàn)，將螞蟻搜索得到的序列 p1與歷史最優(yōu)序列 p*進(jìn)行序交叉，得到兩個(gè)新的序列 p2，p3。將序列 p1，p2，p3解碼，取其最優(yōu)序列作為該螞蟻的搜索路徑。設(shè)歷史最優(yōu)序列為：，當(dāng)前螞蟻搜索的序列為：p1={p11，p12，…，p1n}。

序交叉具體操作如下：

步驟1隨機(jī)取交叉位a(1≤a≤n-2)，p2={p11， p12，…，。

2一元素的貨物編號相同，若存在相同，測試下一元素；否則，將該元素加入到序列p2中。

（3）信息素更新

若本代最優(yōu)值大于歷史最優(yōu)值時(shí)，則更新貨物序列信息素和貨物狀態(tài)信息素。避免某些路徑的信息素過快飽和，本文依據(jù)上次更新情況采用不同的揮發(fā)系數(shù)，將本代最優(yōu)路徑與上一次更新的路徑進(jìn)行比較，對于那些相同的子路徑，用較小的揮發(fā)系數(shù)進(jìn)行更新。設(shè)上次更新時(shí)，首件貨物編號為f，貨物i的擺放狀態(tài)為 psi，后繼貨物編號pni。本代最優(yōu)序列為 p={p1，p2，…，pn}，對于結(jié)點(diǎn) pi的貨物編號為ki，狀態(tài)為si。首件貨物信息素更新：

其中，ρ1、ρ2為兩種揮發(fā)系數(shù)，ρ2＞ρ1。

后繼貨物信息素更新：

貨物狀態(tài)信息素更新：

其中，ρ′1、ρ′2為兩種揮發(fā)系數(shù)，ρ′2＞ρ′1。

4.4 算法步驟

求解強(qiáng)異類集裝箱裝載問題算法步驟如下：

步驟1初始化貨物序列信息素和貨物狀態(tài)信息素、迭代次數(shù)loop、螞蟻個(gè)數(shù)m，揮發(fā)系數(shù)ρ1,ρ2,ρ′1,ρ′2。

步驟2 m只螞蟻按公式（3）、（4）、（6）分別進(jìn)行遍歷，得到序列，并與歷史最優(yōu)序列進(jìn)行交叉、解碼，取最優(yōu)序列作為該螞蟻遍歷的序列。

步驟3若本代最優(yōu)解Pcurrent優(yōu)于歷史最優(yōu)解Pbest，按照公式（7）、（9）、（11）更新序列信息素和狀態(tài)信息素。若當(dāng)前代數(shù)q＜loop，返回步驟2；否則結(jié)束。

4.5 算法時(shí)間復(fù)雜度分析

設(shè)貨物數(shù)量為n，螞蟻個(gè)數(shù)為m，迭代次數(shù)為loop，每只螞蟻搜索貨物裝入優(yōu)先序列的時(shí)間復(fù)雜度為O(n2)，搜索貨物狀態(tài)序列的時(shí)間復(fù)雜度為O(n)，對得到的序列進(jìn)行交叉的時(shí)間復(fù)雜度為O(n2)，對序列進(jìn)行解碼的時(shí)間復(fù)雜度為O(n2)，信息素更新的時(shí)間復(fù)雜度為O(n2)，故算法總的時(shí)間復(fù)雜度為O(loop×m×n2)。

5 實(shí)驗(yàn)結(jié)果

參數(shù)設(shè)置如下：ρ1=0.08，ρ2=0.15，ρ′1=0.05，ρ′2=0.1，m=50，loop=500。

算例1實(shí)驗(yàn)數(shù)據(jù)來源于文獻(xiàn)[8]。具體數(shù)據(jù)如下：待裝集裝箱為一個(gè)6 096 mm國際標(biāo)準(zhǔn)的集裝箱，尺寸為2 352 mm× 2 388 mm×5 899 mm。貨物尺寸見表1。

表1 算例1貨物數(shù)據(jù)

圖2和圖3所示為本文算法求解算例1的裝載方案，體積利用率為89.04%，而文獻(xiàn)[8]得到的體積利用率為85.19%。

圖2 算例1裝載計(jì)劃表

圖3 算例1裝箱效果圖

算例2實(shí)驗(yàn)數(shù)據(jù)來源于文獻(xiàn)[9]。具體數(shù)據(jù)如下：待裝集裝箱為一個(gè)6 096 mm國際標(biāo)準(zhǔn)的集裝箱，尺寸為235.2 cm× 238.8 cm×589.9 cm。貨物尺寸見表2。

表2 算例2貨物數(shù)據(jù)

圖4和圖5所示為本文算法求解算例2的裝載方案，體積利用率為85.83%，文獻(xiàn)[9]得到80%的利用率，文獻(xiàn)[10]得到82.8%的利用率，文獻(xiàn)[11]得到85.04%的利用率。

圖4 算例2裝載計(jì)劃表

圖5 算例2裝箱效果圖

算例3實(shí)驗(yàn)數(shù)據(jù)來源于文獻(xiàn)[12]。具體數(shù)據(jù)如下：待裝集裝箱尺寸為5.8 m×2.4 m×2.4 m。貨物尺寸見表3。

表3 算例3貨物數(shù)據(jù)

圖6和圖7所示本算法求解算例3的裝載方案，體積利用率為87.16%。文獻(xiàn)[12]得到總空間利率為83.3%，文獻(xiàn)[13]得到總空間利率為82.7%。

圖6 算例3裝載計(jì)劃表

圖7 算例3裝箱效果圖

6 結(jié)束語

集裝箱裝載問題的搜索空間分為貨物擺放的優(yōu)先序列和貨物擺放的狀態(tài)兩部分，對應(yīng)設(shè)計(jì)了兩種信息素序列信息素和狀態(tài)信息素，在更新信息素時(shí)，采取兩種揮發(fā)系數(shù)更新信息素以避免信息素過快飽和。另外，引入體積大的貨物優(yōu)先放入的啟發(fā)式規(guī)則，將螞蟻搜索得到的序列與歷史最優(yōu)序列進(jìn)行交叉，取三者最優(yōu)序列作為該螞蟻的搜索路徑。通過三個(gè)實(shí)例計(jì)算結(jié)果表明，本文設(shè)計(jì)的混合蟻群該算法可以得到一個(gè)合理的布局及裝載方案，提高集裝箱的空間利用率；同時(shí)，也表明在具體應(yīng)用中，蟻群算法結(jié)合啟發(fā)式規(guī)則求解像集裝箱裝載等組合優(yōu)化問題是有效的設(shè)計(jì)方案；說明將智能優(yōu)化算法和具體問題的啟發(fā)式算法結(jié)合有利于問題的求解。

[1]Bischof E E.Three-dimensional packing of items with limited load bearing strength[J].European JournalofOperationalResearch，2006，168（3）：952-966.

[2]Wu Y，Li W，Goh M，et al.Three-dimensional bin packing problem with variable bin height[J].European Journalof Operational Research，2010，202（2）：347-355.

[3]屈援，王雪蓮.基于禁忌算法的多約束集裝箱裝載問題研究[J].中國航海，2007，73（4）：73-76.

[4]許光濘，俞金壽.應(yīng)用自適應(yīng)遺傳算法解決集裝箱裝載問題[J].控制與決策，2007，22（11）：1280-1283.

[5]Bortfeldt A.A genetic algorithm for the container loading problem[C]//Proceedings of the Conference on Adaptive Computing and Information Processing，London，1994，44：145-159.

[6]Dorigo M，Stützle T.Ant colony optimization[M].[S.l.]：MIT Press，2004.

[7]Dorigo M，Caro G D.Ant colony optimization：a new metaheuristic[C]//Proc ofthe 1999 Congress on Evolutionary Computation.Washington，DC，USA：IEEE Press，1999：1470-1477.

[8]許光濘，俞金壽.集裝箱裝載問題的一種DNA遺傳算法計(jì)算機(jī)[J].計(jì)算機(jī)工程與應(yīng)用，2008，44（22）：237-240.

[9]Gehring H，Menschner K，Meyer M.A computer-based heuristic for packing pooled shipment containers[J].European Journal of Operational Research，1990，44：277-288．

[10]姜義東，查建中，何大勇.集裝箱裝載矩形貨物的布局研究[J].鐵道學(xué)報(bào)，2002，22（6）：13-18.

[11]劉嘉敏，馬廣煜，黃有群.基于組合的三維集裝箱裝入啟發(fā)式算法的研究[J].工程圖學(xué)學(xué)報(bào)，2005（1）：22-25.

[12]王若恩，陳錦昌，郭水平.三維空間最優(yōu)裝載模式的算法研究與實(shí)現(xiàn)[J].工程圖學(xué)學(xué)報(bào)，2005（5）：6-13.

[13]王亞英，邵惠鶴，田雅杰.一種平板車裝載問題的啟發(fā)式算法[J].計(jì)算機(jī)工程，2001，27（4）：87-88.

WEI Ping,XIONG Weiqing

寧波大學(xué) 電子商務(wù)與物流研究所，浙江 寧波 315211

Institute of Electronic Commerce and Logistics,Ningbo University,Ningbo,Zhejiang 315211,China

Aiming at the strongly heterogeneous Container Loading Problem（CLP）,a mixed Ant Colony Algorithm（ACO）is designed.The solution of problem is divided in two parts,the priority of the goods and the goods'state.Based on heuristic rules,the larger goods have priority to pack in container,so volume is considered as heuristic information.The sequence that ant has searched crosses with historical optimal sequence.The optimal one among the three sequences is choose as the wanted sequence.In order to avoid pheromone over-rapid saturated,pheromone is updated by adopting two volatile coefficients.The complexity of the algorithm is analyzed.Through testing three examples,the space utilization is high by using this algorithm.

Container Loading Problem（CLP）;Ant Colony Algorithm（ACO）;heuristic rules;integer programming

A

TP391

10.3778/j.issn.1002-8331.1108-0361

浙江省自然科學(xué)基金（No.Y1100052）；浙江省教育廳科研項(xiàng)目（No.Y201017000）。

魏平（1965—），女，副教授，主要研究方向：進(jìn)化計(jì)算，計(jì)算智能等；熊偉清（1966—），男，教授，主要研究方向：進(jìn)化計(jì)算，計(jì)算智能，軟件工程等。E-mail：weiping@nbu.edu.cn

2011-08-25

2011-10-13

1002-8331（2013）07-0252-06

WEI ping,XIONG Weiqing.Hybrid binary ant colony algorithm for strongly heterogeneous container loading problem. Computer Engineering and Applications,2013,49（7）：252-257.