求解強異類集裝箱裝載問題的混合蟻群算法

魏 平，熊偉清

求解強異類集裝箱裝載問題的混合蟻群算法

魏 平，熊偉清

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

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

1 引言

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

蟻群優(yōu)化算法（ACO）是一種仿生學(xué)算法，是由意大利學(xué)者M.Dorigo[6-7]等人提出的。目前蟻群算法在理論研究和實際應(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ōu)化算法求解強異類集裝箱裝載問題。

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

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

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

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

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

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

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

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

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

（4）任一放進集裝箱的貨物的每一個面必須和集裝箱的某一個面平行。

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

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

3.1 空間三叉樹定義

為了確保貨物沒有懸空現(xiàn)象，對空間采用三叉樹分割法。當貨物放入集裝箱后，該集裝箱被分割成前、右、上三個空間，每個子空間在裝填貨物過程中，在放入貨物后同樣被繼續(xù)分割為三個空間[1]。空間劃分如圖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為當前生成的三叉樹，e為T的葉子結(jié)點，設(shè)GS表示未裝入集裝箱的貨物集，V表示結(jié)點e代表的空間，GV表示能裝入V的貨物集(GV={g|g∈GS，V≥g})，若GV≠Φ，選擇其中一件貨物裝入V，并為結(jié)點e產(chǎn)生三個子結(jié)點；否則結(jié)點e為最終生成三叉樹的葉子結(jié)點。

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

}

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

3.2 裝載策略

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

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

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

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

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

4.1 目標函數(shù)

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

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

4.2 編碼和解碼

（1）編碼

對于每個可利用的空間，要選擇一件貨物以某一狀態(tài)裝入。因此，編碼時考慮貨物裝載優(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的全排列）。分別為

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

（2）解碼

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

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

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

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

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

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

4.3 算子設(shè)計

（1）序列選擇

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

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

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

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

（2）交叉操作

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

序交叉具體操作如下：

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

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

（3）信息素更新

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

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

后繼貨物信息素更新：

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

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

4.4 算法步驟

求解強異類集裝箱裝載問題算法步驟如下：

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

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

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

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

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

5 實驗結(jié)果

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

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

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

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

圖2 算例1裝載計劃表

圖3 算例1裝箱效果圖

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

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

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

圖4 算例2裝載計劃表

圖5 算例2裝箱效果圖

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

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

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

圖6 算例3裝載計劃表

圖7 算例3裝箱效果圖

6 結(jié)束語

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

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

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

[13]王亞英，邵惠鶴，田雅杰.一種平板車裝載問題的啟發(fā)式算法[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）；浙江省教育廳科研項目（No.Y201017000）。

魏平（1965—），女，副教授，主要研究方向：進化計算，計算智能等；熊偉清（1966—），男，教授，主要研究方向：進化計算，計算智能，軟件工程等。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.