多約束三維裝箱問(wèn)題的研究綜述

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

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

中圖分類(lèi)號(hào)：TP301.6 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9599 （2012） 17-0000-03

1 引言

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

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

2 三種代表性算法在三維裝箱問(wèn)題中的研究

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

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

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

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

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

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

2.2 遺傳式算法解決方案

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

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

國(guó)內(nèi)在求解基于遺傳算法的三維裝箱問(wèn)題方案中，具有代表性的是曹先彬，他提出了采用免疫遺傳算法對(duì)裝箱問(wèn)題來(lái)進(jìn)行求解，下面具體介紹一下他提出的相關(guān)算法：

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

具體的裝箱步驟如下：

Step1：針對(duì)當(dāng)前裝箱的墻面，對(duì)R求出相應(yīng)的子集R’，并且R’中的元素的總長(zhǎng)度盡量小于F的總長(zhǎng)度L，且具體的高與寬應(yīng)當(dāng)盡量接近。

Step2：將R’的寬按照具體的寬度來(lái)進(jìn)行排列。

Step3：將排好的元素逐個(gè)放入裝箱頁(yè)面中，其中R’寬度較大的對(duì)應(yīng)當(dāng)前較窄的一段，依據(jù)當(dāng)前裝箱的凹凸度來(lái)具體判斷箱體是否下移。

Step4：在R=R- R’時(shí)，假如R已經(jīng)為空，算法結(jié)束，否則進(jìn)行下一步。

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

Step6：若R不為空，同時(shí)F還有剩余空間時(shí)，轉(zhuǎn)到第二步對(duì)上一層進(jìn)行裝箱，否則結(jié)束算法。

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

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

（2）初始化隨即種群；

（3）具體產(chǎn)生種群的操作如下所示：

·在種群中對(duì)每個(gè)個(gè)體的適應(yīng)度進(jìn)行評(píng)價(jià)，將空間利用率作為適應(yīng)度的函數(shù)。

·通過(guò)輪盤(pán)選擇算法來(lái)選擇個(gè)體。

輪盤(pán)選擇的具體思想是：生成隨即數(shù)γ∈[0，1]，同時(shí)計(jì)算相對(duì)適應(yīng)值pi=fi/∑fi，假如，p0+p1+…+pi-1<γ≤p0+p1+…+pi，則相應(yīng)個(gè)體被選擇至下一代。由此可見(jiàn)，個(gè)體的適應(yīng)度值大的個(gè)體被選至下一代中的幾率相應(yīng)較高。

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

·對(duì)交叉后的個(gè)體進(jìn)行變異操作，按第三步中的方法決定是否接收變異后的解；

（4）若在收斂條件得到滿(mǎn)足時(shí)，結(jié)束進(jìn)化過(guò)程；否則Tk+1=α，轉(zhuǎn)（3）。

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

2.3 一種新的協(xié)同進(jìn)化計(jì)算方法

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

下面對(duì)CoopcompEA協(xié)同進(jìn)化算法做進(jìn)一步具體介紹：

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

Step2：種群內(nèi)的子群采用合作方式，在種群S1，S2的子群向量采用目標(biāo)函數(shù)合作計(jì)算的方式得出個(gè)體適應(yīng)度。依據(jù)適應(yīng)度值來(lái)組成全局最優(yōu)解。若在當(dāng)前的過(guò)程中得出滿(mǎn)意結(jié)果或者超出進(jìn)化代數(shù)的限制而結(jié)束。

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

Step4：對(duì)測(cè)試集向量T=（ T1，T2）采用種群競(jìng)爭(zhēng)的方式進(jìn)行計(jì)算。

Step5：將反饋因子以競(jìng)爭(zhēng)結(jié)果的方式來(lái)獎(jiǎng)勵(lì)給個(gè)體，并對(duì)適應(yīng)值進(jìn)行修改。

Step6：將最佳個(gè)體逐個(gè)保存，并對(duì)種群中的子群向量Si=（Si1， Si2， Si3…， Sin）依據(jù)適應(yīng)度數(shù)值來(lái)采用GA操作，并轉(zhuǎn)至Step2。

3 對(duì)比分析

在比較中，本文中包含了Bischoff在文獻(xiàn)[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都是在滿(mǎn)足C1的條件下進(jìn)行裝箱的，此外HAS，TS_BG，GA_GB，H_BR算法的裝箱結(jié)果均滿(mǎn)足C2的約束，并屬于完全支撐的類(lèi)型。在問(wèn)題需要滿(mǎn)足越來(lái)越多約束的條件下，求解的過(guò)程也相對(duì)較為困難。

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

4 結(jié)論

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

參考文獻(xiàn)

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

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

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

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

[5]江娜，丁香乾，劉同義等.集裝箱裝載問(wèn)題的模擬退火遺傳算法[J].電子技術(shù)應(yīng)用，2005，10.

[6]張新征.用CoopcompEA解決三維裝箱問(wèn)題[J].計(jì)算機(jī)工程與應(yīng)用，2005，（15）：82-85.

[7]黃文琪.基于A2算法的裝箱問(wèn)題求解[J].小型微型計(jì)算機(jī)系統(tǒng)，2000，21（4）：273-279.