楊會(huì)志

摘要：針對(duì)集裝箱裝載問題中混合禁忌搜索算法雖然滿足集裝箱重心平衡約束但存在裝載率較低的缺點(diǎn)，從采用基于矩陣的空間約束表達(dá)形式、基于簡單塊構(gòu)造裝載方案、根據(jù)禁忌搜素算法的編碼次序選擇裝載貨物種類以及設(shè)計(jì)新的裝載方案的評(píng)價(jià)函數(shù)等方面對(duì)G2LA算法進(jìn)行改進(jìn)，并把改進(jìn)后的G2LA算法作為混合禁忌搜索算法中的基礎(chǔ)啟發(fā)式裝載算法。實(shí)驗(yàn)結(jié)果表明了本算法的有效性。

關(guān)鍵詞：集裝箱裝載；重心平衡約束；禁忌搜索；編碼；G2LA算法

中圖分類號(hào)：TP391.72 文獻(xiàn)標(biāo)識(shí)碼 A 文章編號(hào)：1009-3044（2015）08-0220-03

Abstract： This paper presents a novel hybrid tabu search approach to the container loading problem to provide a better space utilization in the case of satisfying the constraint of weight distribution. An improved G2LA algorithm， which covers the spatial representation system based on matrices， using simple blocks to construct loading plan， using encoding order of tabu search to load blocks， as well asnew evaluation function of loading solutions， is devised as a loading heuristic to incorporate tabu search. Experimental results with benchmark data show that the new approach is effective.

Key words： container loading problem； weight distribution； tabu search； encoding； G2LA algorithm

1 前言

在集裝箱的實(shí)際裝載過程中，除了考慮最大化空間利用率之外，往往需要考慮多種約束，如：貨物的擺放方向；某些貨物的隔離性；貨物的承載能力；貨物裝載的穩(wěn)定性；裝載的優(yōu)先級(jí)；集裝箱的承重性等。目前，針對(duì)具有重心平衡約束的集裝箱裝載問題的研究成果還比較少，主要有H. GEHRING等人【1】提出的方法，首先把貨物根據(jù)一定的規(guī)則組成多個(gè)塔（box tower），然后基于某種優(yōu)化標(biāo)準(zhǔn)來優(yōu)化這些塔在集裝箱中的位置，進(jìn)而可以調(diào)整貨物的重心在集裝箱長度和寬度方向上的位置；Michael Eley【2】把集裝箱在長度方向上分成相等大小的3個(gè)子空間，然后把貨物分別裝載到這3個(gè)子空間，最后通過交換這3個(gè)子空間中的貨物來達(dá)到集裝箱重心平衡的目的；E.E. Bischoff【3】提出的方法是在集裝箱裝載貨物的過程中用具有權(quán)重系數(shù)的5個(gè)標(biāo)準(zhǔn)來進(jìn)行裝載空間和貨物組合的選擇，通過把其中第五個(gè)標(biāo)準(zhǔn)改變?yōu)樨浳镅b載后重心在水平面的變化量，然后通過優(yōu)化規(guī)則的權(quán)重系數(shù)達(dá)到控制重心位置的目的，該方法避免了前面兩種方法控制重心位置精度不高的缺點(diǎn)，但是該標(biāo)準(zhǔn)的公式作者并沒有明確給出；我國學(xué)者劉嘉敏等人【4】提出的混合禁忌搜索算法，設(shè)計(jì)了貨物裝載過程的基礎(chǔ)啟發(fā)式方法，并根據(jù)貨物種類進(jìn)行禁忌搜索算法的編碼，該算法可以在同時(shí)滿足集裝箱裝載總重量約束的同時(shí)，精確地控制貨物重心在三維空間中的位置，但該算法的體積利用率較低。G2LA算法【5】是集裝箱裝載領(lǐng)域非常優(yōu)秀的算法，集裝箱裝載的體積利用率非常高。本文從采用基于矩陣的物體空間約束表達(dá)形式、基于簡單塊構(gòu)造裝載方案策略、根據(jù)禁忌搜素算法的編碼次序選擇裝載貨物等方面對(duì)G2LA算法進(jìn)行改進(jìn)，改進(jìn)后的G2LA算法作為混合禁忌搜索算法中的基礎(chǔ)啟發(fā)式裝載算法，并基于新算法在國際標(biāo)準(zhǔn)測試數(shù)據(jù)集上進(jìn)行了計(jì)算實(shí)驗(yàn)。

2 基于G2LA算法的基礎(chǔ)啟發(fā)式方法

Zhu Wenbin等【5】通過分析多個(gè)優(yōu)秀的基于塊裝載的集裝箱裝載算法，提出了由6個(gè)關(guān)鍵部分組成的此類算法的分析框架，并在此基礎(chǔ)上提出來一度成為此類問題最優(yōu)秀算法的G2LA算法。本文通過對(duì)G2LA算法進(jìn)行改進(jìn)，使它能夠作為混合禁忌搜索算法的基礎(chǔ)啟發(fā)式方法，下面從6個(gè)方面對(duì)算法進(jìn)行描述：

（K1）集裝箱中空間約束的表達(dá)形式，采用基于矩陣的空間約束表達(dá)形式，而沒有采用G2LA算法的cover representation，目的是方便以后對(duì)該算法進(jìn)行擴(kuò)展。

（K2）把G2LA算法的采用復(fù)合塊構(gòu)造裝載方案策略改變?yōu)椴捎煤唵螇K構(gòu)造裝載方案的策略，目的是能夠適應(yīng)混合禁忌搜索算法的編碼方式。

（K3）修改G2LA算法的選擇具有最小anchor distance的可用空間作為待裝載空間的方法，把定義集裝箱通過原點(diǎn)的底面寬度的兩個(gè)點(diǎn)作為計(jì)算anchor distance的依據(jù)，然后選擇具有最小anchor distance的可用空間作為待裝載空間，目的是能夠適應(yīng)混合禁忌搜索算法的編碼方式來按照貨物類型的次序裝載貨物。示意圖如圖1所示。

（K4）簡單塊選擇算法采用G2LA算法的2LA算法。2LA算法示意圖如圖2所示。

根節(jié)點(diǎn)代表當(dāng)前的搜索狀態(tài)。當(dāng)要裝載一個(gè)貨物塊時(shí)，利用評(píng)價(jià)函數(shù)檢查最好的w個(gè)貨物塊所生成的裝載方案，對(duì)w個(gè)貨物塊中的每一個(gè)所生成的部分裝載方案，再次檢查最好的w個(gè)貨物塊所生成的裝載方案，這樣每次迭代要總共檢查w2個(gè)裝載方案。對(duì)w2個(gè)部分裝載方案，采用基于最大體積的貪婪算法得到一個(gè)完整裝載方案。然而，基于最大體積的評(píng)價(jià)函數(shù)沒有反應(yīng)當(dāng)裝載一個(gè)貨物塊時(shí)造成的浪費(fèi)空間的大小（例如，那些不能被任何以后裝載的貨物塊使用的空間）。因此，對(duì)一個(gè)可裝載空間s和一個(gè)貨物塊b，采用如下的評(píng)價(jià)函數(shù)：

改進(jìn)后的G2LA算法的偽代碼如圖3所示。

3 基于混合禁忌搜索算法和改進(jìn)G2LA算法的具有重心平衡約束的集裝箱裝載算法

我國學(xué)者劉嘉敏等人提出的混合禁忌搜索算法可以在同時(shí)滿足集裝箱裝載總重量約束和重心平衡約束的同時(shí)最大化集裝箱的裝載率，但裝載率較低，因此，把該算法的裝載過程所用的基礎(chǔ)啟發(fā)性方法改變?yōu)榍懊骊U述的改進(jìn)后的基于G2LA算法的基礎(chǔ)啟發(fā)式方法，并采用該算法原來的編碼和解碼方法。新算法的主要步驟如下：

1）采用前面說明的改進(jìn)后的基于G2LA算法的基礎(chǔ)啟發(fā)式方法生成初始解。采用禁忌搜索算法產(chǎn)生多個(gè)可行解。

2）由禁忌搜索算法生成的每個(gè)可行解通過基礎(chǔ)啟發(fā)式方法轉(zhuǎn)化為裝載方案。

3）每個(gè)裝載方案采用定義好的評(píng)價(jià)函數(shù)進(jìn)行評(píng)價(jià)，最好的裝載方案作為最優(yōu)解。

4）把上次迭代過程生成的最優(yōu)解作為初始解，通過禁忌搜索算法生成多個(gè)可行解。

5）重復(fù)上述過程直到滿足程序結(jié)束標(biāo)準(zhǔn)（如迭代次數(shù)或者計(jì)算時(shí)間）并得到優(yōu)化解。該過程的偽代碼如圖4所示。

4 算例分析

由于滿足重心平衡約束的集裝箱裝載問題及結(jié)果的完整數(shù)據(jù)還沒有文章發(fā)表，為了分析和比較算法性能，采用集裝箱裝載領(lǐng)域的標(biāo)準(zhǔn)數(shù)據(jù)集對(duì)本文算法進(jìn)行測試。Bischoff和Ratcliff算例，算例分為7組，分別標(biāo)識(shí)為BR1—BR7，每組100個(gè)裝載實(shí)例，在Intel 酷睿2雙核 T7200，2G內(nèi)存計(jì)算機(jī)上每個(gè)實(shí)例運(yùn)行150秒，與其它算法的計(jì)算結(jié)果對(duì)比情況如表1所示【6】，其中混合禁忌搜索算法用HTS標(biāo)識(shí)，本文算法用TS-2LA標(biāo)識(shí)。從表中可以看出，TS-2LA算法在具有HTS算法滿足重心平衡約束的同時(shí)，對(duì)集裝箱裝載領(lǐng)域標(biāo)準(zhǔn)數(shù)據(jù)集的計(jì)算結(jié)果要優(yōu)于HTS算法，從而可以推出滿足重心平衡約束的集裝箱裝載結(jié)果也優(yōu)于HTS算法的結(jié)論。但對(duì)標(biāo)準(zhǔn)數(shù)據(jù)集上的計(jì)算結(jié)果比G2LA算法差，這是由本算法特殊的編碼方式做決定的。

5 結(jié)論

本文針對(duì)集裝箱裝載問題中混合禁忌搜索算法雖然滿足集裝箱重心平衡約束但存在裝載率較低的缺點(diǎn)，從采用基于矩陣的空間約束表達(dá)形式、基于簡單塊構(gòu)造裝載方案策略、根據(jù)禁忌搜素算法的編碼次序選擇裝載貨物以及新的完整裝載方案的評(píng)價(jià)函數(shù)等方面對(duì)G2LA算法進(jìn)行改進(jìn)，并把改進(jìn)后的G2LA算法作為混合禁忌搜索算法中的基礎(chǔ)啟發(fā)式裝載算法。實(shí)驗(yàn)結(jié)果表明了本算法的有效性。今后的主要工作是該算法在多箱裝載問題中的推廣應(yīng)用。

參考文獻(xiàn)：

[1] Gehring H，Bortfeldt A. A genetic algorithm for solving the container loading problem[J]. International Transactions in Operational Research，1997（4）：401-418.

[2] Eley M. Solving container loading problems by block arrangements[J]. European Journal of Operational Research， 2002（141）：393-409.

[3] Bischoff E E. Three-dimensional packing of items with limited load bearing strength[J]. European Journal of Operational Research， 2006（168）：952-966.

[4] Liu J， Yue Y， Dong Z， et al. A novel hybrid Tabu Search approach the container loading[J]. Computers & Operations Research， 2011（38）：797-807.

[5] Zhu W， OonW， LimA， WengY. The six elements to block-building approaches for the single container loading problem[J]. Applied Intelligence， 2012， 37（3）： 1-15.

[6] Araya I， Riff M C. A beam search approach to the container loading problem[J]. Computers & Operations Research， 2014（43）： 100-107.