摘要：至今三維裝箱已經誕生出了很多優(yōu)秀的研究結果，這其中包含有啟發(fā)式算法，遺傳算法，蟻群算法，以及模擬退火算法等解決方法。近幾年來隨著物流行業(yè)的飛速發(fā)展，成本控制在物流行業(yè)中顯得尤為重要，因此，針對三維裝箱這一類典型NP-complete問題有了更高的要求。在此，對三位裝箱近幾年來幾種典型的研究算法進行了相應的詳細介紹，并通過對各種算法進行比對分析，總結了多約束三維裝箱過程現階段所存在的一些問題，最后展望了該問題的發(fā)展方向。

關鍵詞：三維裝箱；裝箱策略；自由落體算法；遺傳算法；條形裝箱；NP完全問題；啟發(fā)式規(guī)則；多目標優(yōu)化；模擬退火算法；禁忌搜索算法；組合優(yōu)化；交互式算法；預分配策略；現實約束

中圖分類號：TP301.6 文獻標識碼：A 文章編號：1007-9599 （2012） 17-0000-03

1 引言

近些年來隨著物流行業(yè)的快速發(fā)展，在激烈的競爭下，物流企業(yè)在控制成本的方面提出了越來越高的要求。在物流公司的運營成本中，集裝箱裝載成本已成為最重要的一項內容。因此，在最大程度上的提高集裝箱裝載水平，降低集裝箱裝載成本，已成為當務之急。

在問題求解的早期階段，大多采用單獨設計一組啟發(fā)式規(guī)則來滿足某一種通用的裝箱問題求解方案。George在A Heuristic for Packing Boxes into a Vontainer一文中提出將箱體分層的策略之后，很多研究人員均采用了這一原則。啟發(fā)式策略在解決裝箱問題時的確具有其獨到之處，但在規(guī)?；潭壬仙龝r，重復的使用啟發(fā)式算法不能在有限的時間內得出比較理想的結果。之后，更多的人逐漸意識到具有全局搜索能力的遺傳算法（GA）去解決裝箱問題具有獨特的優(yōu)勢，隨后關于GA解決裝箱問題的算法逐漸涌現。與單一的啟發(fā)式算法比較，通過引入遺傳算法，無論在設計的可擴展性，規(guī)范性還是在求解問題效率方面都得到了很大的改善。最后，一種新的協同進化計算方法也被應用到裝箱問題的過程中，相信隨著各類算法的進一步的深入研究，可以得到更好的裝箱的解決方法。

2 三種代表性算法在三維裝箱問題中的研究

2.1 啟發(fā)式算法解決方案

首先介紹一下國外的具有代表性的啟發(fā)式算法，George和Robinson算法的主要思想是通過建立容器寬度層，結合空間平整規(guī)劃，使得剩余空間外表面平整，來提高容器的利用率。Bischoff和Dowsland方法同George和Robinson方法相類似，也是基于通過建立容器寬度層進行填充的。Bischoff和Dowsland方法和George和Robinson方法相比較還有著明顯的不同：第一，箱體內各個層的物品種類單一；第二，單體層內的布局采用二維布局過程，將單個容器的寬*高面積的利用率最大化。這兩種方法共同點是：在物品的種類單一，數量很大的情況下，可以得到較好的解。

David Pisinger提出了基于墻壁支撐理論的容器啟發(fā)式裝載方法，該方法是把空間先分層然后劃條的方式來分割。采用分枝定界法來規(guī)劃層和條的劃分，該方法針對Hetrogeneous類和Homogeneous類的具體問題進行了測試，結果表明較大規(guī)模的問題所獲得的較優(yōu)解的質量更好。

Michael Eley提出了建立同一個方向上的同質塊算法，首先，將物品在相同的方向上進行排放，然后將堆放好的物品繼續(xù)放入集裝箱。這種裝箱方式使裝入容器中的物品裝卸方便，擺放穩(wěn)定。

國內具有代表性的是陳治亞提出的啟發(fā)式算法：在模擬實際裝箱的過程中，總是盡量使得每一層裝箱效果比較“平直”，從而設計了一種智能啟發(fā)式算法，用來克服一般啟發(fā)式算法對于經驗的依賴，該算法的主要思想是對人工智能思路的模擬，在裝箱的過程中人們總是在經驗的指導下挑選與已經裝入的箱體尺寸相差較小的一只箱子裝入，在這種方式的指導下可以確保每一層裝的相對平直，例如，我們可以在一個坐標方向進行選擇，然后通過目測所選尺寸與已裝入尺寸相差不大的物品來裝入，假如某個方向上有缺口，那么通常的做法采用尋找一件物品來把缺口填平，直到沒有合適的物品為止，然后在該方向上繼續(xù)裝入新物品。

另一種比較有代表性的啟發(fā)式算法是由國內張德富教授提出的組合啟發(fā)式算法：在日常的生活中，采用擬人的思想來解決實際問題通常是很有效的。在砌墻的過程中，人們一般會先放置一塊參考磚，并且將參考磚的高度作為基準，設定每塊物體的高度均不能超過參考高度，當物體不再能放入箱體時則提高參考高度，受此類思想的啟發(fā)，我們在解決三維裝箱問題的過程中，在垂直和水平方向上均引入參考高度來指導裝填的過程，采用了記錄可放置特殊點的方式來查找裝填位置，此方法的不同之處在于不需要裝填結構作為特定的條件，從而使裝填過程比較靈活，并且通過垂直水平參考線和水平參考線來指導裝填的全過程，最終與模擬退火算法相結合來改變箱子的裝填方向與裝填順序。結果表明，此方法可以獲得較高的填裝效率。但是在箱子種類較少的情況下，解空間比較有限，改進效果不明顯；而在箱子種類較多的情況下，算法的運行時間較長。

2.2 遺傳式算法解決方案

遺傳算法（GA）本身作為一種隨機搜索的算法，具有非常強的全局搜索能力，特別針對求解問題的近似最優(yōu)過程，用遺傳算法來解決裝箱問題具有可行性。但遺傳算法本身存在著許多的不足，尤其在針對解群分布不均勻的時候容易出現未成熟的收斂，陷入局部最優(yōu)。目前針對基本遺傳算法仍有很多需要改進的工作，為避免未成熟的收斂，以及提高群體多樣性是改進的主要方面之一。

國外首先提出遺傳算法應用于三維裝箱領域的是Gehring H。在解決三維裝箱的問題上采用建立多維模型的遺傳算法，并且在當時具有很大程度的創(chuàng)新性。之后，相關的國內文獻中，大多數均會涉及到該算法的核心思想。

國內在求解基于遺傳算法的三維裝箱問題方案中，具有代表性的是曹先彬，他提出了采用免疫遺傳算法對裝箱問題來進行求解，下面具體介紹一下他提出的相關算法：

已有待裝箱的一個組合R={R1，R2，R3……，RN}，Ri代表第i個箱體，其中ai，bi，ci表示箱體的長，寬，高。F=L*W代表將要填充的箱子。對R求出相應的子集，將其中的各個元素互不重疊的對方在F中，最終可達到較高的空間利用率。

具體的裝箱步驟如下：

Step1：針對當前裝箱的墻面，對R求出相應的子集R’，并且R’中的元素的總長度盡量小于F的總長度L，且具體的高與寬應當盡量接近。

Step2：將R’的寬按照具體的寬度來進行排列。

Step3：將排好的元素逐個放入裝箱頁面中，其中R’寬度較大的對應當前較窄的一段，依據當前裝箱的凹凸度來具體判斷箱體是否下移。

Step4：在R=R- R’時，假如R已經為空，算法結束，否則進行下一步。

Step5：假如已裝入元素的頂點坐標已經在方向上大于W，則超出寬度剩余的元素一同放回至R中，若當前裝箱完全處理結束時，進行下一步，否則轉到第二步繼續(xù)執(zhí)行。

Step6：若R不為空，同時F還有剩余空間時，轉到第二步對上一層進行裝箱，否則結束算法。

此外，江那提出的關于遺傳模擬退火算法的港口裝箱研究，同樣代表了一種新的解決方案。將模擬退火算法與遺傳算法相結合，生成一種創(chuàng)新的優(yōu)化算法。雖然遺傳算法具有很多優(yōu)點，比如：應用范圍廣，魯棒性強，使用簡單等。但其本身也有許多的不足，尤其在過早的收斂上，容易陷入到局部最優(yōu)解中，所以將模擬退火算法引入至遺傳算法中，過程如下：

（1）針對控制參數進行初始化：α為溫度冷卻參數；T。為退火初始溫度；Pm為變異概率；N為群體規(guī)模；

（2）初始化隨即種群；

（3）具體產生種群的操作如下所示：

·在種群中對每個個體的適應度進行評價，將空間利用率作為適應度的函數。

·通過輪盤選擇算法來選擇個體。

輪盤選擇的具體思想是：生成隨即數γ∈[0，1]，同時計算相對適應值pi=fi/∑fi，假如，p0+p1+…+pi-1<γ≤p0+p1+…+pi，則相應個體被選擇至下一代。由此可見，個體的適應度值大的個體被選至下一代中的幾率相應較高。

·對復制的個體進行交叉操作，分別選擇兩個個體xi和xj進行交叉操作，相應計算個體的適應函數值f（x'i）和f（x'j）；生成具體在[0，1]之間的隨機數，記為random，以min{1，exp（-Δf/Tk）}>random[0，1]概率得出的新解，作為新個體。

·對交叉后的個體進行變異操作，按第三步中的方法決定是否接收變異后的解；

（4）若在收斂條件得到滿足時，結束進化過程；否則Tk+1=α，轉（3）。

首先模擬退火算法利用輪盤選擇法淘汰了較低適應度的個體，而遺傳算法的核心是交叉操作，從而實現了進一步的尋優(yōu)過程。在這一思想的指導下，模擬退火算法在選擇后代的過程中均采用交叉操作，將編譯與交叉后的父代與子代充分競爭，不但對保留優(yōu)良個體有利，同時預防了過早收斂等問題。隨著進化過程，逐漸溫度下降，接受劣質解的概率同時也逐漸下降，充分利用了模擬退火算法的特性，提高了收斂的速度。

2.3 一種新的協同進化計算方法

由國內張新征提出了一種創(chuàng)新型協同進化算法CoopcompEA與某種啟發(fā)式規(guī)則相結合來解決典型的NP-complete問題。在用該策略求解的過程中，通過利用CoopcompEA算法將個體層的合作進化過程添加到種群競爭的行列中。在該過程中，即對合作進化的求解質量進行了優(yōu)化，又為競爭的收斂效果增加了融合度；此外，裝箱過程的啟發(fā)式規(guī)則得到了完善，實驗結果表明，這種求解方式，無論在進化速度還是在求解效果上都優(yōu)于傳統CCGA方法和GA方法。

下面對CoopcompEA協同進化算法做進一步具體介紹：

Step1：該問題由n個小問題組成。算法隨即的初始化個體，子群和種群。其中種群中子群的向量Si=（Si1， Si2， Si3…， Sin），種群向量S=（S1，S2），種群i的第j個子群個數即為子群大小為|Sij|。

Step2：種群內的子群采用合作方式，在種群S1，S2的子群向量采用目標函數合作計算的方式得出個體適應度。依據適應度值來組成全局最優(yōu)解。若在當前的過程中得出滿意結果或者超出進化代數的限制而結束。

Step3：將種群的向量S中的每個個體組成全局解，進行采樣并放入向量集T=（T1，T2）中。

Step4：對測試集向量T=（ T1，T2）采用種群競爭的方式進行計算。

Step5：將反饋因子以競爭結果的方式來獎勵給個體，并對適應值進行修改。

Step6：將最佳個體逐個保存，并對種群中的子群向量Si=（Si1， Si2， Si3…， Sin）依據適應度數值來采用GA操作，并轉至Step2。

3 對比分析

在比較中，本文中包含了Bischoff在文獻[2]中所提及的啟發(fā)式算法H_BR，Gehring[9]提出的GA_GB算法以及Bortfeldt所采用的禁忌搜索算法TS_BG，Bortfeldt等提出的混合遺傳算法HGA_BG以及并行遺傳算法，Bortfeldt等提出的并行禁忌搜索算法PTSA，Kim提出的MFB算法，Biles等提出的GRASP算法，Bischoff提出的新啟發(fā)算法H_B以及Bortfeldt等提出的啟發(fā)式算法SPPBBL-CC4，張德富等提出的組合啟發(fā)式算法CH，模擬退火算法HSA以及黃文琪等提出的A2算法。

表1和表2都是在滿足C1的條件下進行裝箱的，此外HAS，TS_BG，GA_GB，H_BR算法的裝箱結果均滿足C2的約束，并屬于完全支撐的類型。在問題需要滿足越來越多約束的條件下，求解的過程也相對較為困難。

此外，表2的最后兩行中都是在不采用其他算法的輔助下，表示混合模擬退火算法基礎啟發(fā)中的填充率和組合啟發(fā)式算法你人啟發(fā)中的填充率，他們均在默認輸入下計算。擬人啟發(fā)式序列以體積從大到小排序，而基礎啟發(fā)式則更多考慮約束條件C1和C2得到滿足。在這種情況下，由表2可知，基礎啟發(fā)式的計算結果實際過程中均超出擬人啟發(fā)式策略，填充率的平均值高出約1.5%。在組合啟發(fā)式策略下的平均填充率高出約2.0%。結果充分證明了初始啟發(fā)式算法，具有很大的優(yōu)勢。由上可見，啟發(fā)式算法的優(yōu)劣對提升領域搜索算法在復雜三維裝箱問題上有著舉足輕重的作用。

4 結論

本文主要介紹了關于啟發(fā)式算法，遺傳算法以及其他混合算法來解決復雜三維裝箱中裝箱效率的問題，隨后對這些算法的優(yōu)劣程度進一步進行了歸納，并通過1000個測試的計算結果來分析實際裝箱過程中裝箱算法的效率問題。由以上分析得出，在領域搜索技術緊密結合的啟發(fā)式算法是求解復雜三維裝箱問題的一種有效解決方案。

參考文獻

[1]陳德良，陳治亞.三維裝箱問題的智能啟發(fā)式算法[J].中南林業(yè)科技大學學報 Vol.29 No.3.

[2]閻威武，邵惠鶴，田雅杰.集裝箱裝載的一種啟發(fā)式算法[J].信息與控制，2002，31（4）：353-356.

[3]張德富，魏麗軍，陳青山，陳火旺.三維裝箱問題的組合啟發(fā)式算法[J].軟件學報，2007，9.

[4]周明，孫樹棟.遺傳算法原理及應用.北京：國防工業(yè)出版社，2000.

[5]江娜，丁香乾，劉同義等.集裝箱裝載問題的模擬退火遺傳算法[J].電子技術應用，2005，10.

[6]張新征.用CoopcompEA解決三維裝箱問題[J].計算機工程與應用，2005，（15）：82-85.

[7]黃文琪.基于A2算法的裝箱問題求解[J].小型微型計算機系統，2000，21（4）：273-279.