具有承載能力約束的裝箱問題的蟻群算法

張曉蕊，劉向東

(大連民族學(xué)院計算機科學(xué)與工程學(xué)院，遼寧大連116605)

三維集裝箱問題［1］是將一系列規(guī)則的長方體以最佳方式裝入到集裝箱的過程，是貨物運輸過程中重要的環(huán)節(jié)。過去的幾十年中，在處理集裝箱裝入方面已經(jīng)取得了很大的進步，人們已經(jīng)研究出了能夠解決集裝箱裝入問題的一些方法，比如模擬退火算法［2，3］、遺傳算法［4，5］、禁忌搜索算法［6，7］、樹搜索算法［8，9］等等?；谶@些算法在裝入貨物的時候，人們通常是將集裝箱的整體空間劃分成一些規(guī)則的空間，然后再將其余的貨物進行裝入，使得裝入貨物后的剩余空間繼續(xù)劃分成更小的規(guī)則空間。但是在實際的運輸過程中，裝箱問題還會受到許多實際條件的約束［10］和影響，比如貨物擺放的方向要受到限制、貨物所承受的最大壓力要受到限制、貨物的底面要有足夠的支撐、相同類型的貨物或同一批次的貨物要放在一起等等，這些約束都影響著運輸?shù)馁|(zhì)量和貨物的裝箱率。

本文以裝箱系統(tǒng)為研究背景，目的是在裝箱過程中減少貨物的破損率和提高貨物的裝箱率，設(shè)計出尋優(yōu)能力很強的蟻群算法，將運輸過程中較重要的穩(wěn)定性約束和承載力約束加入到其中。該算法與實際裝箱問題相結(jié)合，能夠滿足貨物裝入過程中所需要的約束條件，具有很強的實用性。

1 問題定義

本文采用的是單箱問題，集裝箱是右側(cè)開口的規(guī)則長方型，將其定義在一個三維坐標(biāo)系下，其中，坐標(biāo)系的原點為集裝箱的左-前-下頂點，集裝箱的長、寬、高分別沿著坐標(biāo)系的X軸、Y軸、Z軸的正方向。

問題可以簡單描述為:在一個長、寬、高分別為L、W、H的長方體集裝箱內(nèi)，裝入長、寬、高分別為li、wi、hi(i=1，2…m)的 m 種貨物。其中，每類貨物都是由尺寸相同的多個長方體組成。目的是使裝入貨物的總體積最大，集裝箱的空間利用率最高，但是該問題還需要滿足三種基本約束［10］:

(1)待裝貨物必須都能裝入集裝箱內(nèi)部;

(2)貨物之間互不重疊;

(3)已裝入的貨物邊緣要與集裝箱的邊緣平行。

2 空間處理

2.1 空間劃分

由于不同的空間劃分將會影響到集裝箱的空間利用率。因此，在解決集裝箱裝入問題中，空間劃分是一個重要因素。為了滿足裝入過程中的各個約束條件，不規(guī)則的裝入空間需要劃分成規(guī)則的裝入空間。當(dāng)貨物被裝入到剩余空間后，該空間被拆分成三個子空間，即前面的空間、上面的空間、右面的空間。兩種基于穩(wěn)定性的空間劃分方法如圖 1［11］。

圖1 穩(wěn)定性空間劃分

2.2 空間合并

隨著貨物的裝入，零碎空間變得越來越多，使得大尺寸的貨物無法裝入?？臻g的劃分采用虛擬切割原理，實際上剩余空間還是相通的。因此，有必要對剩余空間進行合并。采用隊列結(jié)構(gòu)來存儲已裝不下任何貨物的廢棄空間?？紤]分別對剩余空間和廢棄空間這兩類空間進行合并處理。

根據(jù)兩種穩(wěn)定性空間劃分方法能夠保證貨物的穩(wěn)定性要求，對于空間合并，我們只需要考慮相同高度即可。合并原則是使合并后的空間底面積要比合并前的任一空間的底面積都要大［3］。

3 承載力約束

本文主要實現(xiàn)關(guān)聯(lián)約束、穩(wěn)定性約束和承載能力約束，目前大多的研究方法都未將貨物的承載能力約束考慮進去，只有少數(shù)的將承載力約束考慮在內(nèi)［11］。本文采用第一種和第二種空間劃分方法就可以保證貨物的穩(wěn)定性。對于關(guān)聯(lián)約束，將相同類型的貨物以組合塊的形式進行裝入，這樣就保證了貨物的關(guān)聯(lián)性。而對于較難實現(xiàn)的承載力約束，本文提出了一個將承載能力約束與空間劃分相結(jié)合的新方法。隨著貨物的不斷裝入，每個劃分的空間都帶有了一個承載力值，通過空間的承載力值來判斷剩余的貨物是否能夠放入?？臻g承載力的產(chǎn)生和變化都是隨著貨物的不斷裝入而產(chǎn)生和變化的?？梢?，貨物承載力的表示是解決空間承載力的基礎(chǔ)。本文采用貨物單位面積所能承受的最大重量來表示貨物的承載力，表示為:

式中，li、wi是第i種貨物的長和寬，Gi是貨物的重量。

當(dāng)有一個貨物需要裝入時，需要判斷當(dāng)前貨物的重量是否小于或等于下面貨物的承載能力，根據(jù)當(dāng)前空間承載力來判別貨物是否能裝入該空間，其裝入條件判別可以表示為:

式中，Bspace表示當(dāng)前空間的承載力。

當(dāng)多個貨物裝入到空間后，空間的承載力會發(fā)生變化，而上面空間的承載能力等于該空間的承載力值減去貨物本身的承載力值，即:

由于貨物裝入時會出現(xiàn)分層的現(xiàn)象，為了避免貨物被壓壞，空間承載力的大小則要選取空間承載力和貨物本身的承載力中的最小值，即:

當(dāng)進行空間合并時，承載力也會發(fā)生變化，此時合并后的空間承載力要選取合并前空間承載力的最小值，即:

式中，Bspace1、Bspace2是兩個空間的承載力。

本文貨物是以組合的方式進行裝入的，這樣就要求貨物要以相同的擺放方式進行組塊，以便于計算出裝入空間中的貨物個數(shù)。當(dāng)貨物被裝入前，需要判斷組合塊的承載力是否小于等于空間的承載力，組合塊的承載力可以表示為:

式中，m是組合塊的層數(shù)。

4 蟻群算法

4.1 初始解

為了提高體積利用率，優(yōu)先裝入大尺寸貨物。在蟻群算法中，一個好的初始解能夠加快尋優(yōu)速度。按貨物最長邊排序;按貨物的底面積排序。本文將貨物按體積從大到小進行排序。

貨物編碼是蟻群算法應(yīng)用成功與否的關(guān)鍵。貨物種類按1到n進行編號，同類貨物編號相同，不同種類的貨物編號不相同。此時n種貨物對應(yīng)放在n個節(jié)點上，這樣把待裝貨物編成了一個解的序列，即:

式中，n為待裝貨物的種類數(shù);bi是每種貨物的編號，該值為整數(shù)。通過信息素對其進行操作實際上就是改變待裝貨物的排放順序，從而產(chǎn)生不同的解序列。

4.2 參數(shù)設(shè)置

(1)信息量

依據(jù)每個貨物上所留下的信息素的量來確定將會被選擇的貨物。通過更新信息素來更新螞蟻的路徑。當(dāng)螞蟻完成從貨物i到貨物j的搜索或者遍歷完所有種類的貨物后，每種貨物上的信息素將會揮發(fā)。

蟻群覓食時，信息量越多距目標(biāo)越近。在貨物j上留下的信息素的量代表著貨物j被選擇的可行性概率，它決定了螞蟻的移動方向。

當(dāng)螞蟻完成從貨物i到貨物j的一次搜索后，就會在貨物i和貨物j上釋放信息素。信息量影響著螞蟻的搜索路徑。在初始時刻，將ant_m只螞蟻隨機的放到n類貨物上，

此刻每種貨物上的信息量是相同的，即τi(0)=C(C為常數(shù))。當(dāng)螞蟻完成對每類貨物的遍歷后，每種貨物上的信息量按式(7)進行更新。

(2)概率轉(zhuǎn)移函數(shù)

第k只螞蟻根據(jù)每種貨物上的信息量來確定其移動的方向(k=1，2，…，ant_m)。用來表示第k只螞蟻移動到貨物i時，選擇貨物j的概率。概率轉(zhuǎn)移函數(shù)按式(10)進行表示:

式中，τj是在貨物j上的信息量，τs是刻遍歷一次所有螞蟻在該貨物上留下的信息素的總量。

(3)評價函數(shù)

蟻群算法的可行性接是通過一個評價函數(shù)獲得的。一般情況下，對于啟發(fā)式算法的評價函數(shù)能夠處理多目標(biāo)，多約束問題。在本課題中，蟻群算法的評價函數(shù)將集裝箱的空間利用率作為唯一目標(biāo)，同時，貨物的穩(wěn)定性將考慮在這個裝入過程中。評價函數(shù)表示為:

式中，L×W×H是集裝箱的容量，n為貨物的種類數(shù)，ai為每種類型的貨物裝入數(shù)，mi為每種類型的貨物數(shù)。

4.3 貨物裝入

編碼表示一種裝入順序，每種裝入順序產(chǎn)生一種布局。在裝入過程中，對剩余空間進行排序，采用棧結(jié)構(gòu)來存儲剩余空間，棧的初始狀態(tài)是空的集裝箱，彈出的棧頂元素為每次貨物要裝入的空間。初次裝入的剩余空間是整個空的集裝箱空間，當(dāng)貨物裝入時，將其放在當(dāng)前剩余空間的左-下-后角，此時該剩余空間被分成三個子空間，按照前面空間，上面空間，右面空間這個順序壓入剩余空間的棧中，此次裝入結(jié)束;下次裝入貨物時，棧頂元素彈出，作為新的裝入空間，重復(fù)上述過程，直至集裝箱沒有可利用的剩余空間或是貨物已全部裝入。在此過程中，每次要裝入一個貨物時，都要判斷該貨物是否滿足當(dāng)前空間的最大承載力。如果滿足，則裝入該貨物;如果不滿足，就裝入下一貨物。每次剩余空間都要與廢棄空間進行合并。

表1 待裝貨物尺寸

表2 貨物裝入位置數(shù)據(jù)

5 測試結(jié)果比較

本文算法采用文獻［12］中提出的一組測試數(shù)據(jù)見表1。布局空間為國際標(biāo)準(zhǔn)集裝箱，尺寸為L=589.9 cm，W=238.8 cm，H=235.2 cm。在考慮承載能力約束和穩(wěn)定性約束的情況下，與文獻［13］采用的禁忌搜索算法相比較，禁忌搜索算法得到了82.87%的利用率，而本算法卻得到了85.31%的利用率見表2，裝入效果圖如圖2。由此可見，本算法的性能優(yōu)于禁忌搜索算法。

圖2 裝入效果圖

6 結(jié)束語

對具有承載能力約束的集裝箱裝入問題進行了研究，提出了針對三維裝箱問題的蟻群算法，并給出了承載能力約束的表現(xiàn)形式和定義。在貨物裝入的過程中，判斷貨物的承載能力是否滿足要求來進行貨物裝入，成功的將承載能力約束和蟻群算法相結(jié)合。實驗結(jié)果表明，該算法能夠保證貨物在裝入過程中的穩(wěn)定性，同時還防止了貨物被壓壞的情況，便于實際應(yīng)用。另外，還為基于蟻群算法求解三維裝箱問題提供了基礎(chǔ)和經(jīng)驗。

［1］周昕，紀(jì)穎.三維裝箱問題的遺傳算法研究［J］.電腦學(xué)習(xí)，2010，6(3):117-118.

［2］DERELI T，G S DAS，A hybrid simulated annealing algorithm for multi-objective container loading problems［J］.Applied Artifical Intelligence，2010，24:463-486.

［3］張德富，彭煜，朱文興.求解三維裝箱問題的混合模擬退火算法［J］.計算機學(xué)報，2009，32(11):2147-2156.

［4］邢斌，楊信廷，錢建平，等.基于遺傳算法的規(guī)則包裝農(nóng)產(chǎn)品三維裝箱模型［J］.農(nóng)業(yè)工程學(xué)報，2011，27(8):237-241.

［5］HASNI H，SABRI H.On a hybrid genetic algorithm for solving the container loading problem with no orientation constraints［J］.J Math Modeling Algorithms，2012(11):1032-1041.

［6］劉嘉敏，董宗然，黃有群集裝箱裝箱問題的同質(zhì)塊禁忌搜索算法［J］.高科技通訊，2011，21(8):817-823.

［7］LIU J M，YUE Y，DONG Z R，et al.A novel hybrid tabu search approach to container loading［J］.Comput Oper Res，2011，38:797-807.

［8］陸佳煒，肖剛，高飛.基于裝箱樹算法求解集裝箱裝載問題的研究［J］.浙信息與控制，2007，36(5):644-648.

［9］BORTFELDT A，JUNGMANN S.A tree search algorithm for solving the multi-dimensional strip packing problem with guillotine cutting constraint［J］.Ann Opera Res，2012，196:53-71.

［10］劉曉楠.基于重量約束的集裝箱裝入問題的研究［D］.沈陽:沈陽工業(yè)大學(xué)，2009.

［11］ QUEIRA L J，MORABITO R，YAMASHITA D S.Three dimensional container loading models with cargo stability and load bearing constraints［J］.Computer and Operations Research，2012，39:74～85.

［12］姜義東，查建中，何大勇.集裝箱裝載矩形貨物的布局研究［J］.鐵道學(xué)報，2002，22(6):13-18.

［13］劉嘉敏，劉曉楠，黃有群.具有承載能力約束的集裝箱裝入問題的求解方法［J］.計算機工程與設(shè)計，2009，30(22):5204-5207.