集裝箱裝入問(wèn)題的研究

摘要:集裝箱裝載問(wèn)題是一種有廣泛應(yīng)用背景的組合優(yōu)化問(wèn)題，它屬于NP-hard問(wèn)題。禁忌搜索算法(TS)是求解組合問(wèn)題的一種主要方法，有很強(qiáng)的全局搜索能力。集裝箱裝入屬于有多種約束的空間資源優(yōu)化問(wèn)題。約束條件多，求解困難。根據(jù)同類(lèi)型貨物一次性裝載的思想，提出了一種新的基于空間劃分的啟發(fā)式算法。

關(guān)鍵字:集裝箱裝載;禁忌搜索;組合;啟發(fā)式;NP-hard問(wèn)題

中圖分類(lèi)號(hào):TP391 文獻(xiàn)標(biāo)識(shí)碼:A 文章編號(hào):1009-3044(2009)15-3999-01

Study on Container Loading Problem

YOU Ying， WANG Jing-wei

(School of Fundamental Education， ShenYang University of Technology， Shenyang 110178， China)

Abstract: The container loading problem with wide practical application is a combinatorial optimization problem， and is NP-hard problem. Tabu Search (TS) has the ability to search globally as an effective approach to solving the combinatorial problems.Container loading problem is a combinatorial optimization problem with a broad application background. It involves complicated constraints， therefore， it's difficult to obtain the solution. Accordance with the idea of The same type of goods in a one-time loading， put forward a new space-based division of the heuristic algorithm.

Key words: container loading; tabu search; combinatorial heuristic; NP-hard problem

1 引言

集裝箱裝載問(wèn)題是指將一批待布入小物體(長(zhǎng)方體貨物)裝入到長(zhǎng)方體容器(集裝箱)中， 目標(biāo)是優(yōu)化排布使容器的體積利用率和(或)重量利用率最高，同時(shí)要求滿(mǎn)足一定的目標(biāo)約束條件，如貨物搬運(yùn)的難易性;某些貨物的隔離性;貨物裝載的穩(wěn)定性;集裝箱的承重性等。裝箱問(wèn)題是一個(gè)具有復(fù)雜約束條件的組合優(yōu)化問(wèn)題， 在理論上屬NP-hard 問(wèn)題[1] ， 其求解是極為困難的。 在實(shí)際應(yīng)用中， 往往采用一些啟發(fā)式算法來(lái)求解。由于實(shí)際應(yīng)用約束條件很復(fù)雜， 所以具有多約束條件的裝箱問(wèn)題的求解也是困難的。

對(duì)于集裝箱裝載問(wèn)題，國(guó)內(nèi)工作多采用逐個(gè)、優(yōu)先放入大物體的策略[2-3]，考慮的優(yōu)化因素較少;國(guó)外文獻(xiàn)中提到了物體組合的啟發(fā)式方法，如按層(Layer)和塊(Block)等方式組合物體[1，4-7]。Pisinger[1]提出了按層和條的方式來(lái)裝箱。Eley[7]采用同質(zhì)塊(由相同物體組成)填充集裝箱。上述方法在物體種類(lèi)繁多，尺寸差異大的時(shí)候不適用。在采用現(xiàn)代啟發(fā)式算法求解集裝箱裝載問(wèn)題方面，國(guó)內(nèi)研究集中在使用遺傳算法，何大勇等[8]提出的方法收斂速度慢，且允許物體出現(xiàn)不完全支撐，導(dǎo)致不穩(wěn)定排放，需用填充物固定。

本文以實(shí)際的集裝箱自動(dòng)裝載系統(tǒng)為研究背景，設(shè)計(jì)出一種基于多種約束的裝箱方案。該方案以空間利用率的優(yōu)化以及運(yùn)算效率的提高為目標(biāo)，根據(jù)裝載過(guò)程中的實(shí)際約束條件，采用三叉樹(shù)結(jié)構(gòu)裝載思想以及空間劃分合并原則，結(jié)合啟發(fā)式算法和禁忌搜索算法。該方案緊密結(jié)合了裝載操作實(shí)際情況，能滿(mǎn)足實(shí)際裝箱過(guò)程中的多種約束條件，具有較強(qiáng)的適用性。

2 基于重量約束的啟發(fā)式算法

在裝入物體時(shí)，可以通過(guò)物體之間關(guān)系判斷是否滿(mǎn)足物體的承載能力。為了減小搜索物體 的范圍，設(shè)置了鄰域算子，生成鄰域解集，使物體在鄰域解集內(nèi)進(jìn)行判斷。

2.1 物體以組合方法裝填空間

小物體組合成大的矩形體放入可以避免剩余空間零碎劃分，同時(shí)有利于機(jī)械裝入，另外，由于一次性放入多個(gè)小物體，避免了傳統(tǒng)算法中放入一個(gè)小物體就要對(duì)當(dāng)前布局空間全面分析的低效率做法，大大提高了算法的效率。組合裝入的示意圖如圖1。

根據(jù)待裝入空間的大小和方向，小物體組合裝填剩余空間，在裝填過(guò)程中會(huì)出現(xiàn)一組物體橫跨在幾個(gè)物體之上，為了避免下面的物體被壓壞，考慮物體之間的承載能力是必要的。

2.2 編碼與解碼

用禁忌搜索算法求解集裝箱裝載問(wèn)題，首先要將原問(wèn)題的可行解空間轉(zhuǎn)化到禁忌搜索算法所能處理的搜索空間。編碼就是這個(gè)抽象過(guò)程的實(shí)現(xiàn)步驟之一。編碼之后將問(wèn)題的解表示成數(shù)字串的形式，再用鄰域算子對(duì)數(shù)字串進(jìn)行操作，從而求得新解。

根據(jù)給定解的編碼串，按照實(shí)際過(guò)程裝一遍箱，即為解碼的過(guò)程。解碼是編碼的逆過(guò)程，將搜索空間中的解轉(zhuǎn)換到原問(wèn)題的可行解空間，然后在再對(duì)得到的可行解求出評(píng)價(jià)參數(shù)。對(duì)于集裝箱裝入問(wèn)題就是按照得到的裝入順序把物體按照一定規(guī)則實(shí)際裝入一遍，評(píng)價(jià)參數(shù)就是按照這種裝入方式得到的空間利用率。對(duì)物體承載能力的計(jì)算和檢查都是在解碼過(guò)程中，即解的可行性及優(yōu)化程度的驗(yàn)證上。

2.3 評(píng)價(jià)函數(shù)

對(duì)于單箱裝入問(wèn)題，將裝箱體積利用率作為解的評(píng)價(jià)函數(shù)，其定義如下形式:

其中，f為評(píng)價(jià)函數(shù)，νi表示i種裝入的小物體的體積，V表示集裝箱的體積，n為裝入的小物體數(shù)目。

2.4 計(jì)算過(guò)程

1) 設(shè)定算法參數(shù)，包括鄰域解個(gè)數(shù)、候選解個(gè)數(shù)、禁忌表長(zhǎng)度和迭代次數(shù)r等。

2) 將小物體按體積降序排列，然后對(duì)其按升序編號(hào)形成當(dāng)前初始解。

3) 根據(jù)當(dāng)前解和鄰域算子，生成鄰域解集。

4) 解碼過(guò)程。計(jì)算鄰域解，對(duì)滿(mǎn)足要求的裝填結(jié)果，計(jì)算它們的評(píng)價(jià)函數(shù)，生成候選解集。

5) 依據(jù)候選解集及禁忌表，更新當(dāng)前解、當(dāng)前最優(yōu)解及禁忌表。

6) 迭代計(jì)數(shù)器t加1，判斷終止條件，若t小于r，轉(zhuǎn)(3);若t大于r，則以此刻的當(dāng)前最優(yōu)解作為最優(yōu)解輸出，終止計(jì)算。

7) 判斷最優(yōu)解是否滿(mǎn)足要求?若是，則算法結(jié)束，否則，轉(zhuǎn)(1)設(shè)定參數(shù)，重新計(jì)算。

3 實(shí)例圖

圖2-a為透視的線框圖，圖2-b為對(duì)應(yīng)的實(shí)體圖。

4 結(jié)束語(yǔ)

本文提出了一種基于重量約束的集裝箱裝入算法，本算法的特點(diǎn)是考慮了物體的承載能力。

參考文獻(xiàn):

[1] Pisinger D. Heuristics for the container loading problem[J].European Journal of Operational Research，2002，141(2): 382~392.

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

[3] 樊建華，黃有群，劉嘉敏.集裝箱裝入算法的研究[J].沈陽(yáng)工業(yè)大學(xué)學(xué)報(bào)，2002，24(4):306-308.

[4] Bischoff E， Dowsland W B. An application of the microcomputer to product design and distribution[J].Journal of the Operational Research Society，1982，33(3):271-280.

[5] Dowsland K A， Dowsland W B. Packing problems[J].European Journal of Operational Research， 1992， 56(1):2-14.

[6] George J A， Robinson D F.A heuristic for packing boxes into a container[J].Computers and Operations Research，1980，7(3):147-156.

[7] Eley M. Solving container loading problem by block arrangement[J]. European Journal of Operational Research，2002，141(2):393-409.

[8] 何大勇，查建中，姜義東.遺傳算法求解復(fù)雜集裝箱裝載問(wèn)題方法研究[J].軟件學(xué)報(bào)，2001，12(9):1380-1385.