基于混合遺傳算法的雜貨船裝載優(yōu)化問題

朱瑩，向先波，楊運(yùn)桃

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

2中國(guó)船舶工業(yè)系統(tǒng)工程研究院，北京100094

基于混合遺傳算法的雜貨船裝載優(yōu)化問題

朱瑩1，向先波1，楊運(yùn)桃2

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

2中國(guó)船舶工業(yè)系統(tǒng)工程研究院，北京100094

雜貨船的裝載問題屬于典型的三維裝箱問題，在分析雜貨船裝載問題的特點(diǎn)的基礎(chǔ)上，以船艙空間利用率最大為目標(biāo)，建立雜貨船裝載問題的數(shù)學(xué)模型。針對(duì)模型特點(diǎn)，提出一種結(jié)合啟發(fā)式算法和遺傳算法的混合遺傳算法，設(shè)計(jì)一種新的三空間劃分方法，并對(duì)此算法進(jìn)行仿真試驗(yàn)驗(yàn)證。以文獻(xiàn)［3］的一組經(jīng)典測(cè)試數(shù)據(jù)為實(shí)例，經(jīng)與同類裝箱問題中的同類型算法進(jìn)行對(duì)比分析，發(fā)現(xiàn)空間利用率達(dá)到了92.94%，與其他算法的結(jié)果相比具有明顯的優(yōu)勢(shì)，驗(yàn)證了優(yōu)化算法的有效性。

雜貨船；三維裝箱；啟發(fā)式算法；遺傳算法

0 引 言

雜貨船是一種運(yùn)載包裝、箱裝、捆裝、桶裝貨物的貨船，其裝載效率與運(yùn)輸成本直接相關(guān)，提高船艙的利用率可以在很大程度上節(jié)約運(yùn)輸成本?？梢詫㈦s貨船的裝載問題簡(jiǎn)化成一般的裝箱問題。

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

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

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

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

1 裝載模型建立

1.1 問題描述

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

1.2 約束條件和目標(biāo)函數(shù)

雜貨船裝載優(yōu)化的思路是根據(jù)不同的約束條件和目標(biāo)函數(shù)構(gòu)建不同的模型，然后再根據(jù)這些模型設(shè)計(jì)合適的算法進(jìn)行求解，完成裝載問題的優(yōu)化。所以，要優(yōu)化雜貨船的裝載問題，首先需要分析其約束條件和目標(biāo)函數(shù)。

1.2.1 約束條件

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

1.2.2 目標(biāo)函數(shù)

雜貨船裝載問題的目標(biāo)可選用1個(gè)或多個(gè)，一般選用的目標(biāo)函數(shù)如下：

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

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

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

4）運(yùn)輸成本最低。

本文以船艙的空間利用率最大為目標(biāo)函數(shù)。

1.3 模型假設(shè)

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

1）所有貨物都可裝入。

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

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

4）貨物無優(yōu)先級(jí)。

5）貨物包裝箱體的強(qiáng)度足夠。

6）貨物的外形為規(guī)則矩形。

7）忽略裝載對(duì)雜貨船穩(wěn)定性的影響。

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

1.4 模型的建立

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

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

圖1 坐標(biāo)系Fig.1 The coordinate system

模型的相關(guān)參數(shù)設(shè)定如表1所示。

表1 模型主要參數(shù)Tab.1 The main parameters of model

模型的目標(biāo)函數(shù)為

模型的約束條件為

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

2 模型求解及算法分析

2.1 啟發(fā)式規(guī)則

2.1.1 定序規(guī)則

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

2.1.2 定位規(guī)則

圖1已經(jīng)確定了本文的坐標(biāo)系，本文的定位規(guī)則采用占角策略，貨物擺放在靠近原點(diǎn)的位置。

2.1.3 空間劃分規(guī)則

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

1）當(dāng)前待裝貨物為層中的第1個(gè)裝入貨物，即Y-Z-X方式；

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

3）當(dāng)前待裝貨物不是條中第1個(gè)裝入貨物，即X-Z-Y方式。

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

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

2.1.4 空間合并規(guī)則

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

1）裝載前，當(dāng)存在廢棄空間時(shí)，對(duì)廢棄空間進(jìn)行搜索。

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

3）若共XZ面，則將該廢棄空間與當(dāng)前空間進(jìn)行左右合并；若共XY面，則將該廢棄空間與當(dāng)前空間進(jìn)行上下合并；若共YZ面，則將該廢棄空間與當(dāng)前空間進(jìn)行前后合并。

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

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

2.2 遺傳算法

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

2.2.1 編 碼

待裝貨物的裝載順序已經(jīng)由啟發(fā)式定序規(guī)則確定，裝載方式也由啟發(fā)式定位規(guī)則和空間劃分規(guī)則確定，目前，影響裝載的決策變量?jī)H剩下貨物的放置狀態(tài)，即貨物的各個(gè)面與船艙各個(gè)面的位置關(guān)系（存在6種位置關(guān)系）。在編碼中存儲(chǔ)決策變量的信息，即貨物的放置狀態(tài)。待裝貨物有k種，編號(hào)為i=1，2，…，k，每種貨物的數(shù)量為ni，編碼表示為

si為種類編號(hào)為i的貨物的放置狀態(tài)，取值范圍為｛1，2，3，4，5，6｝。為盡可能減少?gòu)U棄空間，同一種貨物的放置狀態(tài)需相同。種類編號(hào)為i的貨物的原始放置狀態(tài)為si=1，表示貨物的長(zhǎng)、寬、高與船艙的長(zhǎng)、寬、高一一平行對(duì)應(yīng)放置，即li∥L，wi∥W，hi∥H。由于貨物的放置狀態(tài)可以任意旋轉(zhuǎn)，故形成了6種可影響總體空間的放置狀態(tài)，如表2所示。

表2 編碼值對(duì)應(yīng)表Tab.2 Encoding values

2.2.2 解 碼

由啟發(fā)式定序規(guī)則確定貨物的裝填順序，啟發(fā)式定位規(guī)則和空間劃分規(guī)則確定貨物放置的位置，編碼確定待裝貨物的放置狀態(tài)，繼而確定一種裝載結(jié)果。解碼是將編碼轉(zhuǎn)化成裝載結(jié)果的過程。解碼后，可以確定每種貨物能裝入船艙的數(shù)量和放置狀態(tài)。設(shè)種類編號(hào)為i的貨物能裝入mi個(gè)，解碼表示為

2.2.3 適應(yīng)度函數(shù)

一般的遺傳算法適應(yīng)度函數(shù)由目標(biāo)函數(shù)變化而成，本文的適應(yīng)度函數(shù)也參考目標(biāo)函數(shù)空間利用率，定義如下：

2.2.4 選擇操作

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

1）計(jì)算出群體中每個(gè)個(gè)體的適應(yīng)度總和。

2）計(jì)算出每個(gè)個(gè)體的相對(duì)適應(yīng)度大小，即各個(gè)個(gè)體被選擇為遺傳父代的概率。第j個(gè)個(gè)體的選擇概率

3）計(jì)算各個(gè)個(gè)體的累積概率

4）生成一個(gè)［0，1］隨機(jī)數(shù)，判斷隨機(jī)數(shù)所在的取值區(qū)間，若隨機(jī)數(shù)取值在之間，則Pj被選中，如圖4所示。

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

5）重復(fù)第4）步，得到M個(gè)個(gè)體組成的新群體

2.2.5 交叉操作

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

2）生成一個(gè)［0，1］隨機(jī)數(shù)，若隨機(jī)數(shù)大于Pc，則不交叉，若隨機(jī)數(shù)小于Pc，則對(duì)行后續(xù)交叉操作。

3）在［1，k］之間生成2個(gè)隨機(jī)整數(shù)a，b（a＜b）作為交叉點(diǎn)，交換位于ab之間的基因段，如圖5所示。

圖5 簡(jiǎn)單兩點(diǎn)交叉Fig.5 Simple two-point crossover

4）對(duì)剩余個(gè)體重復(fù)第2）步和第3）步，得到M個(gè)個(gè)體組成的新群體

2.2.6 變異操作

根據(jù)本文的編碼方式，采用兩點(diǎn)順序逆轉(zhuǎn)方式進(jìn)行變異。變異概率為Pm，準(zhǔn)備進(jìn)行變異操作的群體為變異步驟如下：

2）生成一個(gè)［0，1］隨機(jī)數(shù)，若隨機(jī)數(shù)大于Pm，則不變異，若隨機(jī)數(shù)小于Pm，則對(duì)進(jìn)行后續(xù)的變異操作。

3）通過隨機(jī)數(shù)生成函數(shù)在［1，k］之間的2個(gè)整數(shù)a，b（a＜b）作為變異點(diǎn)，逆轉(zhuǎn)位于ab之間的基因段，如圖6所示。

圖6 順序逆轉(zhuǎn)變異Fig.6 Order reversal mutation

4）對(duì)剩余個(gè)體重復(fù)第2）步和第3）步，得到M個(gè)個(gè)體組成的新群體

2.2.7 最優(yōu)保存策略

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

1）計(jì)算父代群體{P1，P2，P3，…，PM}中所有個(gè)體的適應(yīng)度，找出父代中適應(yīng)度最高的個(gè)體，即最優(yōu)父代，其適應(yīng)度為Fmax。

2.3 仿真程序設(shè)計(jì)

基于上文對(duì)啟發(fā)式規(guī)則和遺傳算法的描述，借助Matlab仿真軟件進(jìn)行算法實(shí)現(xiàn)，程序流程如圖7所示。

3 算例分析

3.1 測(cè)試數(shù)據(jù)

Loh和Nee［3］研究的問題與本文十分相似，他們?cè)谘芯恐薪o出了多組經(jīng)典的測(cè)試數(shù)據(jù)。之后，Bischoff和Ratcliff等［4-5］、Gehring和Bortfeldt［6］先后使用這組數(shù)據(jù)對(duì)自己的算法進(jìn)行了測(cè)試。本文也采用該組數(shù)據(jù)進(jìn)行了算法測(cè)試，測(cè)試數(shù)據(jù)如表3所示。

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

表3 測(cè)試數(shù)據(jù)Tab.3 Test data

3.2 測(cè)試結(jié)果

本文的各項(xiàng)參數(shù)取值分別為：

群體規(guī)模M60

遺傳代數(shù)GEN0.95

交叉概率Pc0.01

變異概率Pm0.95

針對(duì)這組測(cè)試數(shù)據(jù)進(jìn)行仿真試驗(yàn)，得到了16組試驗(yàn)結(jié)果，試驗(yàn)結(jié)果分布如圖8所示。

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

3.3 對(duì)比分析

圖8 仿真試驗(yàn)結(jié)果分布Fig.8 Distribution of simulation results

表4 測(cè)試結(jié)果Fi=92.94%Tab.4 Test results Fi=92.94%

對(duì)同一組測(cè)試數(shù)據(jù)，Bischoff等［4］算法的空間利用率為89.7%，Bischoff和Ratcliff［5］算法的空間利用率為90.3%，Gehring和Bortfeldt［6］算法的空間利用率為89.8%，而本文算法的空間利用率可達(dá)92.94%。通過與這些算法試驗(yàn)結(jié)果的比較，發(fā)現(xiàn)在解決同類問題時(shí)，本文的算法具有顯著的優(yōu)勢(shì)。

4 結(jié) 語

本文分析了一般雜貨船裝載問題的配載特點(diǎn)，構(gòu)建了雜貨船裝載問題的一般模型，并提出了一種新的空間劃分方式下的混合遺傳算法，用以彌補(bǔ)以往啟發(fā)式算法對(duì)閑置空間再利用的不足。借助Matlab仿真軟件，對(duì)文獻(xiàn)［3］的經(jīng)典測(cè)試數(shù)據(jù)進(jìn)行了仿真試驗(yàn)，仿真結(jié)果達(dá)92.94%，驗(yàn)證了本文算法對(duì)雜貨船裝載問題優(yōu)化結(jié)果的有效性。

［1］ 徐麗麗.集裝箱單箱三維裝載優(yōu)化研究［D］.濟(jì)南：山東大學(xué)，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］ 何大勇，查建中，姜義東.遺傳算法求解復(fù)雜集裝箱裝載問題方法研究［J］.軟件學(xué)報(bào)，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］ 翟鈺，孫小明.多種物品三維裝箱問題的一種啟發(fā)式算法［J］.上海交通大學(xué)學(xué)報(bào)，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］ 陳德良，陳治亞.三維裝箱問題的智能啟發(fā)式算法［J］.中南林業(yè)科技大學(xué)學(xué)報(bào)，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］ 徐寧，李春光，張健，等.幾種現(xiàn)代優(yōu)化算法的比較研究［J］.系統(tǒng)工程與電子技術(shù)，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］.計(jì)算機(jī)工程與設(shè)計(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］ 李書全，孫雪，孫德輝，等.遺傳算法中的交叉算子的述評(píng)［J］.計(jì)算機(jī)工程與應(yīng)用，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.

［責(zé)任編輯：盧圣芳］

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期刊網(wǎng)址：www.ship-research.com

朱瑩，向先波，楊運(yùn)桃.基于混合遺傳算法的雜貨船裝載優(yōu)化問題［J］.中國(guó)艦船研究，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"> 網(wǎng)絡(luò)出版時(shí)間：

時(shí)間：2015-11-10 10:26

湖北省自然科學(xué)基金資助項(xiàng)目（2014CFB253）；高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研基金資助項(xiàng)目（20120142120045）；中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)基金資助項(xiàng)目（2015TS006）

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