集裝箱裝入問題的研究

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

關鍵字:集裝箱裝載;禁忌搜索;組合;啟發式;NP-hard問題

中圖分類號:TP391 文獻標識碼:A 文章編號: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 引言

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

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

本文以實際的集裝箱自動裝載系統為研究背景，設計出一種基于多種約束的裝箱方案。該方案以空間利用率的優化以及運算效率的提高為目標，根據裝載過程中的實際約束條件，采用三叉樹結構裝載思想以及空間劃分合并原則，結合啟發式算法和禁忌搜索算法。該方案緊密結合了裝載操作實際情況，能滿足實際裝箱過程中的多種約束條件，具有較強的適用性。

2 基于重量約束的啟發式算法

在裝入物體時，可以通過物體之間關系判斷是否滿足物體的承載能力。為了減小搜索物體 的范圍，設置了鄰域算子，生成鄰域解集，使物體在鄰域解集內進行判斷。

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

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

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

2.2 編碼與解碼

用禁忌搜索算法求解集裝箱裝載問題，首先要將原問題的可行解空間轉化到禁忌搜索算法所能處理的搜索空間。編碼就是這個抽象過程的實現步驟之一。編碼之后將問題的解表示成數字串的形式，再用鄰域算子對數字串進行操作，從而求得新解。

根據給定解的編碼串，按照實際過程裝一遍箱，即為解碼的過程。解碼是編碼的逆過程，將搜索空間中的解轉換到原問題的可行解空間，然后在再對得到的可行解求出評價參數。對于集裝箱裝入問題就是按照得到的裝入順序把物體按照一定規則實際裝入一遍，評價參數就是按照這種裝入方式得到的空間利用率。對物體承載能力的計算和檢查都是在解碼過程中，即解的可行性及優化程度的驗證上。

2.3 評價函數

對于單箱裝入問題，將裝箱體積利用率作為解的評價函數，其定義如下形式:

其中，f為評價函數，νi表示i種裝入的小物體的體積，V表示集裝箱的體積，n為裝入的小物體數目。

2.4 計算過程

1) 設定算法參數，包括鄰域解個數、候選解個數、禁忌表長度和迭代次數r等。

2) 將小物體按體積降序排列，然后對其按升序編號形成當前初始解。

3) 根據當前解和鄰域算子，生成鄰域解集。

4) 解碼過程。計算鄰域解，對滿足要求的裝填結果，計算它們的評價函數，生成候選解集。

5) 依據候選解集及禁忌表，更新當前解、當前最優解及禁忌表。

6) 迭代計數器t加1，判斷終止條件，若t小于r，轉(3);若t大于r，則以此刻的當前最優解作為最優解輸出，終止計算。

7) 判斷最優解是否滿足要求?若是，則算法結束，否則，轉(1)設定參數，重新計算。

3 實例圖

圖2-a為透視的線框圖，圖2-b為對應的實體圖。

4 結束語

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

參考文獻:

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

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

[3] 樊建華，黃有群，劉嘉敏.集裝箱裝入算法的研究[J].沈陽工業大學學報，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] 何大勇，查建中，姜義東.遺傳算法求解復雜集裝箱裝載問題方法研究[J].軟件學報，2001，12(9):1380-1385.