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

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

中圖分類號：TP301.6

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

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

1 問題描述與約束定義

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

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

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

2.1 BF啟發(fā)式算法

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

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

2.2 自適應(yīng)權(quán)重的粒子群算法優(yōu)化

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

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

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

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

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

3 仿真試驗(yàn)

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

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

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

4 結(jié)束語

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

參考文獻(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]何大勇，查建中，姜義東.遺傳算法求解復(fù)雜裝箱裝載問題方法研究[J].軟件學(xué)報(bào)，2001（12）：1380-1385.

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

[4]Johnson D S.張立昂，譯.計(jì)算機(jī)和難解性-NP完全性理論導(dǎo)論[M].北京：科學(xué)出版社，1990.

[5]王秀清，邱洪澤，徐法升.求解裝箱問題的一種混合分組遺傳算法[J].濟(jì)南大學(xué)學(xué)報(bào)（自然科學(xué)版），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]卜雷，蒲云，劉海旭.集裝箱中零擔(dān)貨物合理混載的遺傳退火進(jìn)化算法[J].世界科技研究與發(fā)展，2002（24）：88-91.

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

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

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