解決約束三維裝箱問題的混合粒子群算法

摘 要：針對約束條件下三維裝箱問題復雜性，為提高裝箱利用率，本文提出了混合粒子群算法，該算法采用BF啟發(fā)式算法配合改進的自適應權重粒子群算法實現(xiàn)。通過仿真試驗，結(jié)果表明該混合粒子群算法對解決部分約束條件下裝箱問題較之傳統(tǒng)研究遺傳算法利用率和準確率更高，具有不同程度的可行性。

關鍵詞：裝箱問題；約束條件；啟發(fā)式算法；混合粒子群算法

中圖分類號：TP301.6

裝箱問題在現(xiàn)實生活中具有廣泛的應用背景，如在實際工程優(yōu)化問題中集裝箱貨物裝載、內(nèi)存調(diào)度分配，金屬制造業(yè)下料問題等。隨著物流業(yè)的發(fā)展，在物流作業(yè)中，三維裝箱問題更是得到了大量研究。Falkenauer提出的HGGA算法用于解決裝箱問題優(yōu)化[1]，將每個待裝物品所裝入的箱子編號，編碼為染色體，交叉算子采用貪婪分割交叉算子改進，優(yōu)化質(zhì)量較高；何大勇，查建中等采用遺傳算法對復雜集裝箱裝載問題求解，對其進入了深入的方法研究與探索[2]；吳斐等在集裝箱布局問題中進行了基于啟發(fā)式結(jié)果的模擬退火算法的研究與應用[3]。

顯然，由于裝箱問題復雜性高，各種約束條件限制，考慮組合優(yōu)化層面自然很多，是典型的NP-Hard問題[4]。隨著裝箱組合優(yōu)化研究的進行，各種啟發(fā)式算法配合遺傳算法、模擬退火算法的設計不斷涌現(xiàn)。而配合采用混合粒子群算法的研究卻少之又少。遺傳算法和粒子群算法都是解決全局搜索尋優(yōu)的算法，但局部搜索能力不足。因此現(xiàn)實裝箱中多約束條件下，配合采用啟發(fā)式算法解決局部搜索效率有所提高。此外，采用粒子群算法過程中改進權重來增加局部搜索能力。本文采用自適應權重結(jié)合BF算法的混合粒子群算法進行研究，通過仿真試驗，探索混合粒子群算法相比基本遺傳算法解決多約束條件下三維裝箱效率問題。

1 問題描述與約束定義

多種貨物三維裝箱問題描述為：給定k個寬為W，長為L，高為H，最大承載質(zhì)量為M的箱體和n種不同類的貨物a1，a2，...，an，第i（i=1，2，..，n）種貨物參數(shù)寬為w，長為l，高為h，質(zhì)量為m。滿足約束條件下，集裝箱裝載要達到的目標為：最大化體積裝載率，以提高集裝箱利用率，獲得最佳的效益。最大化目標函數(shù)為： 其中，該算法考慮的集裝箱裝載約束定義有：（1）最基本的約束：空間約束，被放入的任何貨物邊界不能超出長寬高限制的范圍；（2）載重能力約束，對于每個箱體加一個載重能力的標識Sign用以記錄容器的最大承重重量；（3）物品方向約束，貨物擺放可以以六個面中的任意一個面最為底面。

2 混合粒子群算法優(yōu)化

混合粒子群算法是本文提出的核心算法，該算法通過抽取BF啟發(fā)式算法思想，結(jié)合已有的基本粒子群算法，通過改進慣性權重得來。對三維裝箱問題優(yōu)化求解的混合粒子群算法基本思想描述如下。

2.1 BF啟發(fā)式算法

對于以上問題的描述，在各種約束條件限制的情況下，目前，解決三維裝箱的近似求解算法有Next-Fit（NF近似算法）、Firsts-Fit（FF近似算法）、Best-Fit（BF近似算法）、First-Fit-Decreasing（FFD近似算法）[5]。本文采用啟發(fā)式算法中BF算法即最佳適應啟發(fā)式算法求解裝箱優(yōu)化問題。

BF算法設計基本思想如下：將箱子分為兩類：空箱和已用箱。對于裝箱物品，按照最佳適配算法先從已用箱子中找合適的箱子；若沒有合適箱體，則選擇空箱，找到后修改該箱體數(shù)據(jù)，并將該箱子置為已用箱中，直至所有物品裝完。該算法摒棄了利于最小下標順序箱子放入的思想，是從FF算法改進而來。在時間復雜度和空間復雜度上性能較優(yōu)。

2.2 自適應權重的粒子群算法優(yōu)化

基本粒子群算法由Eberhart博士和Kennedy博士發(fā)明，起源于對鳥類群體捕食行為的研究[6]。算法中，每個優(yōu)化問題的解均指搜索空間中的一只鳥，被抽象為無質(zhì)量和體積屬性的微粒，并將其延伸到多維空間。所有粒子都有由被優(yōu)化的函數(shù)決定的適應值，每個粒子還有一個速度決定飛翔的方向和距離矢量。

在粒子群算法的可調(diào)整參數(shù)中，慣性權重w是其中重要參數(shù)，w值較大，則有利于提高算法全局搜索能力，而w較小會增強算法的局部搜索能力，根據(jù)不同的權重變化方法，如線性遞減權重法、自適應權重法、隨機權重法，可以得到不同的粒子群優(yōu)化算法。本文選用自適應權重粒子群算法進行優(yōu)化求解。

自適應權重粒子群算法原理：采用非線性的動態(tài)慣性權重系數(shù)公式，表達式為：

其中，wmax、wmin分別表示w的最大值和最小值，f表示粒子當前目標函數(shù)值，favg和fmin分別表示當前所有微粒的平均目標值和最小目標值。在上式中，慣性權重w隨著微粒的目標函數(shù)值而自動改變，因此稱為自適應權重。

自適應權重粒子群算法基本步驟如下：（1）首先隨機性對種群各粒子位置和速度進行初始化；（2）對單個微粒的適應度進行一一評價，將當前各粒子位置和適應度值存儲在各微粒的pbest中，將所有pbest中適應度值最優(yōu)的個體位置和適應值存儲在gbest中；（3）用上式更新粒子的速度和位移；（4）對每個個體微粒，通過相應適應度值與其經(jīng)歷過的最佳位置相比較，如果較好，則選擇當前最好位置；（5）比較當前各個pbest和gbest的值，對gbest進行更新；（6）若滿足預設的運算精度或迭代次數(shù)值，則停止搜索，繼而輸出結(jié)果；若否，則返回步驟（3）繼續(xù)搜索選擇。

3 仿真試驗

本文結(jié)合啟發(fā)式算法中BF算法對多約束條件的整合操作，解決局部尋優(yōu)問題的局限性約束，此外通過改進權重的自適應粒子群算法進一步解決局部尋優(yōu)問題。該混合粒子群優(yōu)化算法，能夠在全局優(yōu)化問題求得近似解的情況下，針對某些約束條件的限制得到更加有力的分配方案，有效避免了早熟收斂問題。遺傳算法是基于Darwin進化論和Mendel的遺傳學說的一種全局優(yōu)化概率搜索算法[7]，該算法通過對所求解問題的可行解進行編碼，然后對編碼集進行選擇、交叉、變異操作，逐步尋優(yōu)，最終力求得到問題的最優(yōu)解或近似最優(yōu)解。

為了對混合粒子群算法和基本遺傳算法在部分約束條件下的性能進行驗證，利用Matlab仿真軟件對選擇的算例進行試驗。算例中選取了138個不同物品待裝入箱，試驗次數(shù)選擇進行500次仿真，運行結(jié)果見表1。

實例驗證過程是基于.net架構，C#語言實現(xiàn)Web模式下三維裝箱。數(shù)據(jù)從某企業(yè)的裝箱訂單中隨機抽取，實例驗證數(shù)據(jù)及約束見表2。

4 結(jié)束語

對多約束條件下裝箱問題，分別采用基本遺傳算法和混合粒子群算法進行裝箱優(yōu)化，從限制約束條件角度，從裝箱過程中全局尋優(yōu)搜索到局部尋優(yōu)搜索角度比較了這兩種算法的運行結(jié)果，混合粒子群算法有效克服了算法早熟收斂的問題，在實例分析的情況下，得到了行之有效的結(jié)果，尤其對現(xiàn)代物流大批量裝箱問題具有理論指導意義。

參考文獻：

[1]Singh A，Gupta A K. Two heuristics for the one-dimensional bin-packing problem[J].OR Spectrum，2007（29）：765-781.

[2]何大勇，查建中，姜義東.遺傳算法求解復雜裝箱裝載問題方法研究[J].軟件學報，2001（12）：1380-1385.

[3]吳斐，侯云章.基于啟發(fā)式結(jié)果的模擬退火算法在布局問題中的應用[J].物流科技，2005（121）：39-43.

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

[5]王秀清，邱洪澤，徐法升.求解裝箱問題的一種混合分組遺傳算法[J].濟南大學學報（自然科學版），2010（03）.

[6]K.N.V.D.Sarath，Vadlamani Ravi.Association rule mining using binary particle swarm optimization[J].Engineering Application of Artificial Intelligence，2013（08）.

[7]卜雷，蒲云，劉海旭.集裝箱中零擔貨物合理混載的遺傳退火進化算法[J].世界科技研究與發(fā)展，2002（24）：88-91.

作者簡介：杜振（1988-），男，青島人，碩士研究生，研究方向：軟件工程與智能信息等應用；通訊作者：宮會麗（1975-），女，博士，研究方向：計算智能與數(shù)據(jù)挖掘。

作者單位：中國海洋大學 信息科學與工程學院，山東青島 266100；青島海大新星計算機工程中心，山東青島 266071

項目基金：國家科技支撐計劃：城市物流配送服務體系及優(yōu)化技術研究（項目編號：2013BAH17F01）。