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

魏 平，熊偉清

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

魏 平，熊偉清

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

集裝箱裝載；蟻群優化算法；啟發式規則；整數規劃

1 引言

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

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

考慮到蟻群算法在求解組合優化問題上的優勢，本文嘗試利用蟻群優化算法求解強異類集裝箱裝載問題。

2 集裝箱裝載問題數學模型

假設集裝箱的長、寬、高分別為L、W、H，最大裝載質量為G，貨物的種類數為n，第i(i=1，2，…，n)類貨物的長、寬、高、數量分別為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類貨物裝入集裝箱的個數，其中0≤numi≤ki。

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

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

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

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

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

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

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

3.1 空間三叉樹定義

為了確保貨物沒有懸空現象，對空間采用三叉樹分割法。當貨物放入集裝箱后，該集裝箱被分割成前、右、上三個空間，每個子空間在裝填貨物過程中，在放入貨物后同樣被繼續分割為三個空間[1]。空間劃分如圖1所示。

圖1 空間劃分示意圖

空間三叉樹定義如下：

空間三叉樹

{

數據對象D：D表示可利用的空間

數據關系R：R是如下二元關系：

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

若D≠Φ，則R={H}，H是如下二元關系：

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

若 Dt≠Φ，則 Dt中存在唯一的元素 xt，＜root，xt＞∈H，且存在 Dt上的關系Ht?H；若Dr≠Φ，則Dr中存在唯一的元素xr，＜root，xr＞∈H，且存在Dr上的關系Hr?H；若Df≠Φ，則Df中存在唯一的元素 xf，＜root，xf＞∈H，且存在Df上的關系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的葉子結點，設GS表示未裝入集裝箱的貨物集，V表示結點e代表的空間，GV表示能裝入V的貨物集(GV={g|g∈GS，V≥g})，若GV≠Φ，選擇其中一件貨物裝入V，并為結點e產生三個子結點；否則結點e為最終生成三叉樹的葉子結點。

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

}

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

3.2 裝載策略

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

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

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

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

4 混合蟻群算法設計

4.1 目標函數

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

各參數含義見第2章。

4.2 編碼和解碼

（1）編碼

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

貨物狀態定義如下：

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

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

（2）解碼

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

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

步驟2若S中還有可利用的空間，取出棧頂的空間作為當前待裝空間V；否則結束。

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

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

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

4.3 算子設計

（1）序列選擇

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

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

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

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

（2）交叉操作

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

序交叉具體操作如下：

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

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

（3）信息素更新

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

其中，ρ1、ρ2為兩種揮發系數，ρ2＞ρ1。

后繼貨物信息素更新：

貨物狀態信息素更新：

其中，ρ′1、ρ′2為兩種揮發系數，ρ′2＞ρ′1。

4.4 算法步驟

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

步驟1初始化貨物序列信息素和貨物狀態信息素、迭代次數loop、螞蟻個數m，揮發系數ρ1,ρ2,ρ′1,ρ′2。

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

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

4.5 算法時間復雜度分析

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

5 實驗結果

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

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

表1 算例1貨物數據

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

圖2 算例1裝載計劃表

圖3 算例1裝箱效果圖

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

表2 算例2貨物數據

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

圖4 算例2裝載計劃表

圖5 算例2裝箱效果圖

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

表3 算例3貨物數據

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

圖6 算例3裝載計劃表

圖7 算例3裝箱效果圖

6 結束語

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

[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]許光濘，俞金壽.應用自適應遺傳算法解決集裝箱裝載問題[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].計算機工程與應用，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].鐵道學報，2002，22（6）：13-18.

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

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

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

WEI Ping,XIONG Weiqing

寧波大學 電子商務與物流研究所，浙江 寧波 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

浙江省自然科學基金（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.