基于混合遺傳算法的雜貨船裝載優化問題

朱瑩，向先波，楊運桃

1華中科技大學船舶與海洋工程學院，湖北武漢430074

2中國船舶工業系統工程研究院，北京100094

基于混合遺傳算法的雜貨船裝載優化問題

朱瑩1，向先波1，楊運桃2

1華中科技大學船舶與海洋工程學院，湖北武漢430074

2中國船舶工業系統工程研究院，北京100094

雜貨船的裝載問題屬于典型的三維裝箱問題，在分析雜貨船裝載問題的特點的基礎上，以船艙空間利用率最大為目標，建立雜貨船裝載問題的數學模型。針對模型特點，提出一種結合啟發式算法和遺傳算法的混合遺傳算法，設計一種新的三空間劃分方法，并對此算法進行仿真試驗驗證。以文獻［3］的一組經典測試數據為實例，經與同類裝箱問題中的同類型算法進行對比分析，發現空間利用率達到了92.94%，與其他算法的結果相比具有明顯的優勢，驗證了優化算法的有效性。

雜貨船；三維裝箱；啟發式算法；遺傳算法

0 引 言

雜貨船是一種運載包裝、箱裝、捆裝、桶裝貨物的貨船，其裝載效率與運輸成本直接相關，提高船艙的利用率可以在很大程度上節約運輸成本。可以將雜貨船的裝載問題簡化成一般的裝箱問題。

裝箱問題屬于NP-Hard問題，研究的重點在于要根據特定的問題建立數學模型和尋求有效的求解算法。在實際應用中，精確數值計算方法的探討已逐漸消失，取而代之的是啟發式算法、模擬退火算法、禁忌搜索算法和遺傳算法等各種智能算法在該問題求解過程中的大量應用［1］。本文擬采用混合遺傳算法的啟發式算法對雜貨船的裝載問題進行優化。

國內外對裝箱問題已有一些研究，但主要針對的是二維裝箱問題，有關三維裝箱問題方面的研究較少。國外最有代表性的就是George和Robinson［2］提出的啟發式算法，并且首先引入了層的概念。Loh和Nee［3］研究的啟發式算法主要針對的是弱異類問題，其采用裝填密度作為目標函數，構建水平層來由下至上裝載，此外，其給出的15組測試數據經常被后人作為檢驗算法的經典數據。Bischoff等［4］提出的啟發式算法主要針對的是貨物裝盤的問題，但和裝箱問題有很多的相通之處。Bischoff和Ratcliff［5］提出的啟發式算法考慮了多目的地運送的情況，其不是構建層而是通過構建柱來實現裝載。Gehring和Bortfeldt［6］提出了一種比較典型的混合遺傳算法，其將啟發式算法與遺傳算法相結合，提出了塔的概念，并將二維裝填問題的思路引入到了三維裝載問題中。國內比較有代表性的是何大勇等［7］提出的遺傳算法，其通過權重系數變化法來處理多目標問題，通過罰函數法處理約束，并對多目標多約束裝箱問題進行了研究。翟鈺等［8］提出的啟發式算法中，是由完全相同的貨物組成塊，然后用塊自底向上依次填充的方式來完成裝載，裝載過程中，采用樹搜索策略尋找最優的裝載方式。陳德良等［9］設計了一種智能啟發式算法，通過模擬人們在實際裝箱時總是盡量保證每一層裝的比較“平直”的思想，借以克服一般啟發式算法依賴“經驗”的不足。

啟發式算法憑借實踐經驗建立搜索策略和搜索規則，并以此規則在搜索空間中求解，該算法被大量應用于裝載問題中。但啟發式算法在同一問題的不同實例中會產生不同的效果，這種不穩定性使得計算結果變得不可信。為了降低這種不穩定性，本文擬將遺傳算法作為搜索算法來改進啟發式算法，通過啟發式算法確定裝載規則來產生可行解，然后應用遺傳算法在解空間中搜索令人滿意的優質解。一般的優化算法［10］往往是直接利用決策變量的實際值來進行優化計算，而遺傳算法則是以決策變量構造的編碼為運算對象，更適合很難有數值概念的裝載問題。遺傳算法同時使用多個搜索點的搜索信息進行群體優化，這種特有的并行性使其搜索效率高于一般算法。遺傳算法屬于一種概率搜索技術，其選擇、交叉和變異運算都是以一定的概率發生的，增加了搜索的靈活性。

一般的啟發式規則多參考George和Robinson的思路［2］，引入層的概念，把裝載過程當作一層一層的裝入，這種思路與實際的裝載過程非常契合。一旦空間中裝入一個貨物后，貨物的周圍就產生了三個剩余的空間，然后以一定的遍歷方式選取優先級較高的貨物進行裝填，先是在層中擺滿一條，再擺另一條，直至形成一個層。本文的啟發式規則將參考George和Robinson［2］的思路并給予一些改進。本文擬將同種貨物采用同一種放置狀態，并盡量放在一起，以避免同種貨物放在一起因放置狀態不一致而產生空隙，從而提高一定的裝箱效率；采用一種多樣化的空間劃分方式，針對不同的放置位置設計不同的空間劃分方式，以有效避免一定的空間損失。同時，還將待裝空間與相鄰的廢棄空間進行合并，使廢棄空間得到再利用，從而提高空間利用率。

1 裝載模型建立

1.1 問題描述

雜貨船的裝載問題可以描述為：將具有一定重量、體積、價值的不同種類、不同數量的物品按照一定的規則裝入具有一定載重和容積限制的船艙內的過程，在滿足運量限制的情況下實現箱內物品價值總和最大化。

1.2 約束條件和目標函數

雜貨船裝載優化的思路是根據不同的約束條件和目標函數構建不同的模型，然后再根據這些模型設計合適的算法進行求解，完成裝載問題的優化。所以，要優化雜貨船的裝載問題，首先需要分析其約束條件和目標函數。

1.2.1 約束條件

在雜貨船裝載問題的描述過程中，一般具有以下幾種約束條件：體積約束、載重約束、方向約束、承載能力約束、配裝優先級約束和穩定性約束。本文主要考慮體積約束條件下的裝載問題優化。

1.2.2 目標函數

雜貨船裝載問題的目標可選用1個或多個，一般選用的目標函數如下：

1）船艙的載重量利用率最大。

2）船艙的空間利用率最大。

3）船艙的面積利用率最大。

4）運輸成本最低。

本文以船艙的空間利用率最大為目標函數。

1.3 模型假設

本文僅考慮單個船艙裝載時的優化，不考慮特殊約束條件下的裝載問題，并將以船艙的空間利用率最優為目標，構造雜貨船裝載問題的模型。為方便研究，做以下假設：

1）所有貨物都可裝入。

2）雜貨船的載重量足夠大。

3）貨物均可以任意擺放。

4）貨物無優先級。

5）貨物包裝箱體的強度足夠。

6）貨物的外形為規則矩形。

7）忽略裝載對雜貨船穩定性的影響。

8）貨物之間的空隙用填充物填充以保證穩定，忽略裝載中貨物的穩定性因素。

1.4 模型的建立

雜貨船的裝載問題模型可以描述為：在滿足船艙容積約束的條件下，確定各貨物在船艙中的裝載位置和放置狀態，以使船艙的空間利用率最優。

本模型采用的坐標系是三維笛卡爾坐標系，如圖1所示。該坐標系的X軸表示船艙的長度方向，Y軸表示船艙的寬度方向，Z軸表示船艙的高度方向。船艙的左下角為坐標系原點。

圖1 坐標系Fig.1 The coordinate system

模型的相關參數設定如表1所示。

表1 模型主要參數Tab.1 The main parameters of model

模型的目標函數為

模型的約束條件為

式中：F為船艙的空間利用率；mi為貨物的裝入數量。

2 模型求解及算法分析

2.1 啟發式規則

2.1.1 定序規則

待裝貨物在裝入船艙時，其裝載的先后順序直接影響裝載結果。由于貨物沒有配裝優先級約束，故待裝貨物的裝載順序主要參考對船艙空間利用率的影響。本文的裝填思路是最大限度地填滿空間，但隨著空間分解的進行，空間會越來越狹小，而如果大尺寸貨物的裝載順序靠后，極有可能造成大尺寸貨物無法裝載，最終降低船艙空間利用率的情況。故裝填時應優先裝入尺寸較大的貨物，本文采用按待裝貨物最短邊邊長遞減的順序。

2.1.2 定位規則

圖1已經確定了本文的坐標系，本文的定位規則采用占角策略，貨物擺放在靠近原點的位置。

2.1.3 空間劃分規則

本文對雜貨船裝載問題的優化主要體現在空間劃分規則上。George和Robinson［2］最先提出了三空間劃分原則，即將第1個貨物放入當前空間左下角后，就形成了上方、右方、前方3個子空間（圖2（a）），然后后面的貨物就按照上空間、右空間和前空間的順序進行裝載。George和Robinson［2］還引入了“層”的概念，他們使用的是YZ-X層，每次裝載都會產生3個子空間，按照Z-Y-X的遍歷方式裝載，直到所有剩余的貨物不能裝入任意一個剩余子空間，裝載便結束。本文采用一種新的三空間劃分方法，構建YZ-X層，在每一個YZ層內再構建Y-Z條，裝載由角到條到層再到整個空間的順序，空間劃分方式按以下3種情況進行：

1）當前待裝貨物為層中的第1個裝入貨物，即Y-Z-X方式；

2）當前待裝貨物為條中第1個裝入貨物但不是層中的第1個裝入貨物，即X-Y-Z方式；

3）當前待裝貨物不是條中第1個裝入貨物，即X-Z-Y方式。

在一般問題中，所有情況均按如圖2（b）所示的Y-Z-X方式分解空間，本文僅在第1種情況下采用此種劃分方法。當裝箱為第2種情況時，當前空間X方向的長度由層中第1個裝入的貨物決定，若X方向尺寸較小，在后續劃分空間時，前空間會較狹窄，而過狹窄的前空間極易成為無法裝入任一貨物的廢棄空間。當裝箱為第3種情況時，當前空間X方向的長度由層中第1個裝入的貨物決定，當前空間Y方向的長度由條中第1個裝入的貨物決定，若X，Z方向尺寸較小，在后續劃分空間時，前空間和上空間都會較窄，易成為廢棄空間。針對這類情況，本文提出一種新的空間分配方式，即考慮將狹窄的空間提前視為廢棄空間，分情況采用相應的空間劃分規則，加大可用空間的體積，進而提高整體空間利用率。當處于第2種情況時，將空間劃分為前方、右方和上方3個子空間（圖2（c）），按照X-Y-Z的遍歷方式裝載；當為第3種情況時，將空間劃分為前方、上方和右方3個子空間（圖2（d）），按照X-Z-Y的遍歷方式裝載。

圖2 空間劃分方式Fig.2 Three-space partition method

2.1.4 空間合并規則

每次裝載前，若存在廢棄空間，則將當前裝載空間與廢棄空間合并，以使廢棄空間再利用?？臻g合并有3個方向上的空間合并，分別為左右合并（圖3（a））、上下合并（圖3（b））和前后合并（圖3（c））。空間合并的步驟如下：

1）裝載前，當存在廢棄空間時，對廢棄空間進行搜索。

2）依次判斷廢棄空間與當前空間是否共XZ面、是否共XY面、是否共YZ面。

3）若共XZ面，則將該廢棄空間與當前空間進行左右合并；若共XY面，則將該廢棄空間與當前空間進行上下合并；若共YZ面，則將該廢棄空間與當前空間進行前后合并。

4）將合并后的空間作為新的裝載空間。

圖3 空間合并方式Fig.3 Spaces consolidation method

2.2 遺傳算法

所謂遺傳算法，就是模擬生物進化優勝劣汰的過程搜索最優解。一個編碼P即一個生物個體，對應雜貨船裝載問題中的一種裝載方案。由多個個體組成一個生物種群，群體大小M對應于裝載方案的數量。適應度代表了個體適應生存環境的能力，對應于裝載問題中的船艙空間利用率，個體適應度越高，其編碼代表的裝載方案越優秀，其裝載信息保留下來的概率越大。繁殖進化要經歷選擇、交叉和變異。選擇裝載方案中對船艙空間利用率較高的方案作為父代群體，在這些空間利用率較高的裝載方案之間交換裝載信息或調整部分自身裝載信息，以此來產生空間利用率更高的裝載方案，也就是子代群體，然后不斷重復這種過程，以使得到的裝載方案的空間利用率越來越高，最終獲得空間利用率令人滿意的裝載方案。

2.2.1 編 碼

待裝貨物的裝載順序已經由啟發式定序規則確定，裝載方式也由啟發式定位規則和空間劃分規則確定，目前，影響裝載的決策變量僅剩下貨物的放置狀態，即貨物的各個面與船艙各個面的位置關系（存在6種位置關系）。在編碼中存儲決策變量的信息，即貨物的放置狀態。待裝貨物有k種，編號為i=1，2，…，k，每種貨物的數量為ni，編碼表示為

si為種類編號為i的貨物的放置狀態，取值范圍為｛1，2，3，4，5，6｝。為盡可能減少廢棄空間，同一種貨物的放置狀態需相同。種類編號為i的貨物的原始放置狀態為si=1，表示貨物的長、寬、高與船艙的長、寬、高一一平行對應放置，即li∥L，wi∥W，hi∥H。由于貨物的放置狀態可以任意旋轉，故形成了6種可影響總體空間的放置狀態，如表2所示。

表2 編碼值對應表Tab.2 Encoding values

2.2.2 解 碼

由啟發式定序規則確定貨物的裝填順序，啟發式定位規則和空間劃分規則確定貨物放置的位置，編碼確定待裝貨物的放置狀態，繼而確定一種裝載結果。解碼是將編碼轉化成裝載結果的過程。解碼后，可以確定每種貨物能裝入船艙的數量和放置狀態。設種類編號為i的貨物能裝入mi個，解碼表示為

2.2.3 適應度函數

一般的遺傳算法適應度函數由目標函數變化而成，本文的適應度函數也參考目標函數空間利用率，定義如下：

2.2.4 選擇操作

本文是采用輪盤賭注法進行遺傳算法中的選擇操作［11］。已知群體大小為M，父代群體為輪盤賭注法的操作步驟如下：

1）計算出群體中每個個體的適應度總和。

2）計算出每個個體的相對適應度大小，即各個個體被選擇為遺傳父代的概率。第j個個體的選擇概率

3）計算各個個體的累積概率

4）生成一個［0，1］隨機數，判斷隨機數所在的取值區間，若隨機數取值在之間，則Pj被選中，如圖4所示。

圖4 輪盤賭注法Fig.4 Roulette betting method

5）重復第4）步，得到M個個體組成的新群體

2.2.5 交叉操作

在裝箱問題中，常用的交叉方法為部分映射交叉［12］，本文選用的編碼方式不適用于部分映射交叉，故選用簡單的兩點交叉。交叉概率為Pc，準備進行交叉操作的群體為交叉步驟如下：

2）生成一個［0，1］隨機數，若隨機數大于Pc，則不交叉，若隨機數小于Pc，則對行后續交叉操作。

3）在［1，k］之間生成2個隨機整數a，b（a＜b）作為交叉點，交換位于ab之間的基因段，如圖5所示。

圖5 簡單兩點交叉Fig.5 Simple two-point crossover

4）對剩余個體重復第2）步和第3）步，得到M個個體組成的新群體

2.2.6 變異操作

根據本文的編碼方式，采用兩點順序逆轉方式進行變異。變異概率為Pm，準備進行變異操作的群體為變異步驟如下：

2）生成一個［0，1］隨機數，若隨機數大于Pm，則不變異，若隨機數小于Pm，則對進行后續的變異操作。

3）通過隨機數生成函數在［1，k］之間的2個整數a，b（a＜b）作為變異點，逆轉位于ab之間的基因段，如圖6所示。

圖6 順序逆轉變異Fig.6 Order reversal mutation

4）對剩余個體重復第2）步和第3）步，得到M個個體組成的新群體

2.2.7 最優保存策略

最優保存策略可以避免父代中的優秀個體在遺傳迭代的過程中消失。最優保存的步驟為：

1）計算父代群體{P1，P2，P3，…，PM}中所有個體的適應度，找出父代中適應度最高的個體，即最優父代，其適應度為Fmax。

2.3 仿真程序設計

基于上文對啟發式規則和遺傳算法的描述，借助Matlab仿真軟件進行算法實現，程序流程如圖7所示。

3 算例分析

3.1 測試數據

Loh和Nee［3］研究的問題與本文十分相似，他們在研究中給出了多組經典的測試數據。之后，Bischoff和Ratcliff等［4-5］、Gehring和Bortfeldt［6］先后使用這組數據對自己的算法進行了測試。本文也采用該組數據進行了算法測試，測試數據如表3所示。

圖7 程序流程圖Fig.7 Program flow chart

表3 測試數據Tab.3 Test data

3.2 測試結果

本文的各項參數取值分別為：

群體規模M60

遺傳代數GEN0.95

交叉概率Pc0.01

變異概率Pm0.95

針對這組測試數據進行仿真試驗，得到了16組試驗結果，試驗結果分布如圖8所示。

試驗結果表明，本文算法的空間利用率均分布在93%～88%之間，空間利用率可達92.94%，其具體的裝載方案如表4所示。

3.3 對比分析

圖8 仿真試驗結果分布Fig.8 Distribution of simulation results

表4 測試結果Fi=92.94%Tab.4 Test results Fi=92.94%

對同一組測試數據，Bischoff等［4］算法的空間利用率為89.7%，Bischoff和Ratcliff［5］算法的空間利用率為90.3%，Gehring和Bortfeldt［6］算法的空間利用率為89.8%，而本文算法的空間利用率可達92.94%。通過與這些算法試驗結果的比較，發現在解決同類問題時，本文的算法具有顯著的優勢。

4 結 語

本文分析了一般雜貨船裝載問題的配載特點，構建了雜貨船裝載問題的一般模型，并提出了一種新的空間劃分方式下的混合遺傳算法，用以彌補以往啟發式算法對閑置空間再利用的不足。借助Matlab仿真軟件，對文獻［3］的經典測試數據進行了仿真試驗，仿真結果達92.94%，驗證了本文算法對雜貨船裝載問題優化結果的有效性。

［1］ 徐麗麗.集裝箱單箱三維裝載優化研究［D］.濟南：山東大學，2008.

［2］ GEORGE J A，ROBINSON D F.A heuristic for pack?ing boxes into a container［J］.Computers&Operations Research，1980，7（3）：147-156.

［3］ LOH T H，NEE A Y C.A packing algorithm for hexahe?dral boxes［C］//Conference of Industrial Automation. Singapore，1992.

［4］ BISCHOFF E E，JANETZ F，RATCLIFF M S W.Load?ing pallets with non-identical items［J］.European Jour?nal of Operational Research，1995，84（3）：681-692.

［5］ BISCHOFF E E，RATCLIFF M S W.Issues in the de?velopment of approaches to container loading［J］.Ome?ga，1995，23（4）：377-390.

［6］ GEHRING H，BORTFELDT A.A genetic algorithm for solving the container loading problem［J］.International Transactions in Operational Research，1997，4（5/6）：401-418.

［7］ 何大勇，查建中，姜義東.遺傳算法求解復雜集裝箱裝載問題方法研究［J］.軟件學報，2001，12（9）：1380-1385. HE Dayong，ZHA Jianzhong，JIANG Yidong.Research on solution tocomplexcontainer-loadingproblem based on genetic algorithm［J］.Journal of Software，2001，12（9）：1380-1385.

［8］ 翟鈺，孫小明.多種物品三維裝箱問題的一種啟發式算法［J］.上海交通大學學報，2007，41（8）：1244-1247. ZHAI Yu，SUN Xiaoming.A heuristic algorithm for three-dimensionalcontainerloading problem with non-identical items［J］.Journal of Shanghai Jiaotong University，2007，41（8）：1244-1247.

［9］ 陳德良，陳治亞.三維裝箱問題的智能啟發式算法［J］.中南林業科技大學學報，2009，29（3）：134-137. CHEN Deliang，CHEN Zhiya.An intelligent heuristic approach to three-dimensional bin-packing problem［J］.Journal of Central South University of Forestry& Technology，2009，29（3）：134-137.

［10］ 徐寧，李春光，張健，等.幾種現代優化算法的比較研究［J］.系統工程與電子技術，2002，24（12）：100-103. XU Ning，LI Chunguang，ZHANG Jian，et al.Studies on some modern optimization algorithms［J］.Systems Engineering and Electronics，2002，24（12）：100-103.

［11］ 張琛，詹志輝.遺傳算法選擇策略比較［J］.計算機工程與設計，2009，30（23）：5471-5474. ZHANG Chen，ZHAN Zhihui.Comparisons of selec?tion strategy in genetic algorithm［J］.Computer Engi?neering and Design，2009，30（23）：5471-5474.

［12］ 李書全，孫雪，孫德輝，等.遺傳算法中的交叉算子的述評［J］.計算機工程與應用，2012，48（1）：36-39. LI Shuquan，SUN Xue，SUN Dehui，et al.Summary of crossover operator of genetic algorithm［J］.Computer Engineering and Applications，2012，48（1）：36-39.

［責任編輯：盧圣芳］

General cargo ship loading problems based on the hybrid genetic algorithm

ZHU Ying1，XIANG Xianbo1，YANG Yuntao2

1 School of Naval Architecture and Ocean Engineering，Huazhong University of Science and Technology，Wuhan 430074，China

2 Systems Engineering Research Institute，Beijing 100094，China

General cargo ship loading problems belong to general three-dimensional container loading problems.In this paper,based on the analysis of general cargo ship loading problems and taking the goal of maximizing the space utilization,a mathematical model of general cargo ship loading problems is estab?lished.By analyzing the characteristics of the model,a hybrid genetic algorithm combined with the heuris?tic algorithm and the genetic algorithm is presented,and a new type of three-space partition method is de?signed,both of which being realized along with simulation and experimental confirmation.By examining a classic set of test data of Loh&Nee as an example,the space utilization is seen to reach 92.94%,which demonstrates distinct advantages to similar algorithms for the container loading problems.The experimental results show that the hybrid genetic algorithm is feasible on solving general cargo ship loading problems.

general cargo ship；three-dimensional container loading；heuristic algorithm；genetic algorithm

U695.2+5

A

10.3969/j.issn.1673-3185.2015.06.019

http://www.cnki.net/kcms/detail/42.1755.TJ.20151110.1026.036.html期刊網址：www.ship-research.com

朱瑩，向先波，楊運桃.基于混合遺傳算法的雜貨船裝載優化問題［J］.中國艦船研究，2015，10（6）：126-132. ZHU Ying，XIANG Xianbo，YANG Yuntao.General cargo ship loading problems based on the hybrid genetic algorithm［J］.Chinese Journal of Ship Research，2015，10（6）：126-132.

2015-05-28 < class="emphasis_bold"> 網絡出版時間：

時間：2015-11-10 10:26

湖北省自然科學基金資助項目（2014CFB253）；高等學校博士學科點專項科研基金資助項目（20120142120045）；中央高?；究蒲袠I務費專項基金資助項目（2015TS006）

朱瑩，女，1991年生，碩士生。研究方向：艦船系統工程。E-mail：zhuying@hust.edu.cn向先波（通信作者），男，1978年生，博士，副教授。研究方向：航行器/機器人智能控制，艦船系統優化。E-mail：xbxiang@hust.edu.cn