基于遺傳算法的港口裝箱問題的研究

摘要:隨著港口之間的競爭不斷白熱化，如何提高港口的工作效率一直是研究港口問題的熱點(diǎn)問題。裝箱問題作為港口運(yùn)作的重要組成部分，在港口體系中具有舉足輕重的作用。該文利用遺傳算法，對港口裝箱問題進(jìn)行了優(yōu)化，改善了裝箱的方法，提高了裝箱的效率。

關(guān)鍵詞:遺傳算法;港口;裝箱

中圖法分類號:TP311文獻(xiàn)標(biāo)識碼:A文章編號:1009-3044(2009)36-10242-02

Reserch on the Port-Packing Problem Based on Genetic Algorithm

ZHOU Chun-liang

(Ningbo Dahongying college， Ningbo 315157， China)

Abstract: With the rapid development of the economy globalization， the competition among the manufacturing enterprises has been more and more fierce. How to increase the efficiency of the port is always a hot issue in the research of the port problem. And packing problem is an important component for the Port operation， which makes great importance to the port system. this article perfects the port-packing problem， improve the way of packing and also increase the packing efficiency with the genetic algorithm.

Key words: genetic algorithms; port; packing

在眾多的物流運(yùn)輸方式中，港口運(yùn)輸以其便捷性和穩(wěn)定性，一直是物流行業(yè)的主流運(yùn)輸方式。港口作為海運(yùn)的重要運(yùn)輸部分，在整個(gè)海運(yùn)體系中具有重要的地位。因此如何提高港口的工作效率，對于整個(gè)物流體系有著至關(guān)重要的作用。

我們本次走訪了寧波港三期碼頭，了解了碼頭整個(gè)運(yùn)作過程。就如何提高提高港口的工作效率和工作人員進(jìn)行了深入的探討。我們一致認(rèn)為裝箱問題作為港口運(yùn)輸中的一個(gè)重要環(huán)節(jié)，對于提高整個(gè)港口貨物的利用率和調(diào)動速度，有著舉足輕重的作用。

1 什么是裝箱問題

裝箱問題指的是將不同類型的物品，放入到一個(gè)容器的過程。這是一個(gè)典型的NP難問題，可以通過建立相關(guān)的線性規(guī)劃問題進(jìn)行精確解。但是由于這類問題過于復(fù)雜，需要耗費(fèi)大量的時(shí)間和CPU資源，對于規(guī)模比較大的裝箱問題，線形規(guī)劃往往束手無策。于是有了許多的啟發(fā)式算法，其中比較著名的有全匹配算法，部分匹配算法。但大多數(shù)的算法都是啟發(fā)式算法，往往容易產(chǎn)生個(gè)體的局部解，而脫離整個(gè)解的空間，不能達(dá)到最佳的裝箱效果。

于是我們采用了遺傳算法和啟發(fā)式算法結(jié)合的方法，避免了啟發(fā)式算法的收發(fā)性，大大降低了算法的冗余度，且總能收斂到全局最優(yōu)解，從而彌補(bǔ)了啟發(fā)式算法的收斂問題。

2 裝箱問題的基本特征

根據(jù)裝箱問題的自身特點(diǎn)，不同的學(xué)者制度了研究了裝箱問題的不同方面，總結(jié)起來，它的基本特征如下:

1) 裝箱過程遵循先放入大件的物品，后放入小件的物品。

2) 面積較大的矩形裝入后產(chǎn)生的空洞較大，面積較小的矩形裝入后產(chǎn)生的空洞較小;

3) 面積較大的矩形裝入后產(chǎn)生的空洞常常可以裝入面積較小的矩形;

4) 裝入過程中產(chǎn)生的輪廓線越規(guī)整，即組成輪廓線的水平線數(shù)量越少，就越有利于后期矩形的裝入。

3 裝箱問題的描述和數(shù)學(xué)模型

裝箱問題的一般描述:有n個(gè)物品要裝入k個(gè)箱子(k≤n)中。每個(gè)物品有重量(wj)，每個(gè)箱子有重要限制(cj>0)。目標(biāo)是尋找最優(yōu)的將物品分配到箱子的方案，使每個(gè)箱子中物品的重量之和不超過其重量限制，且使用的箱子數(shù)量最少。

通常，所有箱子有相同的重量限制(c>0)。顯然，將每個(gè)物品放入一個(gè)箱子是一個(gè)可行解，但不是最優(yōu)解。裝箱問題的數(shù)學(xué)表達(dá)式如下:

公式中yi=1箱子i被裝入物品，反之則表示箱子i是空的。xij=1表示物品j放入箱子i，反之表示物品j未放入箱子i。

4 遺傳算法的設(shè)計(jì)

基本遺傳算法可定義為一個(gè)八元組:GA=(S，E，P0，M，Φ ，F(xiàn)，Ψ，T)，式中S表示個(gè)體的編碼方法;E表示個(gè)體適應(yīng)度評價(jià)函數(shù);P0表示初始群體;M表示群體大小;Φ表示選擇算子;F表示交叉算子;Ψ表示變異算子;T表示遺傳算子終止條件。

4.1 初始種群

假定裝箱順序中所有集裝箱箱號組成的一個(gè)列表記為S，給每個(gè)集裝箱分配一個(gè)1到n之間的序號，可分別與箱號對應(yīng)，將這個(gè)序號的排列也表示為S，即:S=(s1，s2，s3，…，sn)，在此范圍，將隨機(jī)取出一個(gè)順序?yàn)槌跏既后w中的一個(gè)裝箱順序。初始群體，允許重復(fù)。

4.2 編碼方式

采用Grefenstette等提出的編碼方法，該方法能夠使得任意的基因型個(gè)體都能夠?qū)?yīng)于一條具有實(shí)際意義的裝箱順序。

對于一個(gè)集裝箱裝箱順序問題的集裝箱序號列表W，各個(gè)箱子的配載順序?yàn)镾:S=(s1，s2，s3，…，sn)，規(guī)定每配載完一個(gè)箱子，就從列表W中將該箱子序號去掉，則用第i個(gè)(i=1，2，3，…，n)所配載的箱子si在所有未訪問列表W {s1，s2，s3，…，si-1}中的對應(yīng)位置序號gi(1≤gi≤n-i+1)就可表示具體配載哪個(gè)箱子，如此這樣直到處理完W中所有的箱子。將全部順序排列在一起所得到的一個(gè)列表:G=(g1，g2，g3，….，gn)，就可表示一個(gè)集裝箱裝箱的配載順序，它即為遺傳算法中一個(gè)個(gè)體的基因型。

4.3 選擇算子

采用最優(yōu)保存策略進(jìn)化模型(Elitist Mode1)來進(jìn)行優(yōu)勝劣汰操作，當(dāng)前群體中適應(yīng)度最高的個(gè)體不參與交叉運(yùn)算和變異運(yùn)算。

操作過程是:1) 找出當(dāng)前群體中適應(yīng)度最高的個(gè)體和適應(yīng)度最低的個(gè)體。2) 若當(dāng)前群體中最佳個(gè)體的適應(yīng)度比總的目前為止的最好個(gè)體的適應(yīng)度還要高，則以當(dāng)前群體中的最佳個(gè)體作為新的目前為止的最好個(gè)體。3) 用目前為止的最好個(gè)體替換掉當(dāng)前群體中的最差個(gè)體。

4.4 交叉算子

配對策略是優(yōu)劣配對，即將群體中的個(gè)體，評估函數(shù)評估后，分出優(yōu)劣等級組成LM/2J對配對個(gè)體組，交叉操作是在這些配對個(gè)體組中的兩個(gè)個(gè)體之問進(jìn)行的。對每一對相互配對的個(gè)體，隨機(jī)設(shè)置某一基因座之后的位置為交叉點(diǎn)。若染色體的長度為n，則共有(n-1)可能的交叉點(diǎn)位置。對每一對相互配對的個(gè)體，根據(jù)設(shè)定的交叉概率，在其交叉點(diǎn)處相互交換兩個(gè)個(gè)體的部分染色體，從而產(chǎn)生出兩個(gè)新的個(gè)體，只交換載位匹配的箱子。

4.5 變異算子

依次指定個(gè)體編碼串中的每個(gè)基因座為變異點(diǎn)。對每一個(gè)變異點(diǎn)，以變異概率P從對應(yīng)基因的取值范圍內(nèi)取隨機(jī)數(shù)來替代原有基因值。

由于裝箱順序問題，使用由Grefenstette等所提出的編碼方法來表示個(gè)體時(shí)，每個(gè)個(gè)體經(jīng)過遺傳運(yùn)算后所得到的任意的一個(gè)基因型個(gè)體都對應(yīng)于一條具有實(shí)際意義的裝箱順序。所以變異基因Si(i=1，2，3，…，n)所對應(yīng)的等位基因值只能從f1，2，3，…，n-i中選取，并且載位匹配的箱子。

5 仿真實(shí)驗(yàn)

現(xiàn)有500個(gè)不同重量的物品(重量為0~1的隨機(jī)數(shù))，要裝入若干個(gè)箱子中，每個(gè)箱子的重量限制為1。一個(gè)箱子可以裝一個(gè)物品，也可以同時(shí)裝幾個(gè)物品，但每個(gè)箱子所裝入的物品重量總和不能超過其限制。試確定如何裝箱才能使500個(gè)物品全部裝箱，并使得所需要的箱子數(shù)量最少。

利用Matlab程序來實(shí)現(xiàn)上述問題的GBR的混合遺傳算法，其運(yùn)行參數(shù)設(shè)置為:交叉概率=0.2，變異概率=0.1，適應(yīng)值函數(shù)中=2。運(yùn)行次數(shù)為100代，每一代群體的規(guī)模為100。各代的進(jìn)化結(jié)果如圖2所示。圖1中，第1條曲線表示每代個(gè)體中最差裝箱方案所需的箱子數(shù)，第2條曲線表示每代所有個(gè)體所需的平均箱子數(shù)，第3條曲線表示每代個(gè)體中最好裝箱方案所需的箱子數(shù)。

為了和GBR的混合遺傳算法進(jìn)行比較，用同樣的運(yùn)行參數(shù)和相同的初始箱子重量對OBR的混合遺傳算法也進(jìn)行了測試，其結(jié)果如圖2所示。

通過比較，可以總結(jié)出，在傳統(tǒng)裝箱問題中，GBR有以下優(yōu)點(diǎn):

1) 收斂快。由于OBR只對物品的排序進(jìn)行編碼，這種編碼方式可能出現(xiàn)不同的染色體代表相同的解，從而導(dǎo)致其冗余度隨著問題規(guī)模的增加而指數(shù)上升，使得遺傳算法的能力受到嚴(yán)重影響。而GBR 只對群體部分進(jìn)行操作，從一開始就不會出現(xiàn)冗余現(xiàn)象，從而大大提高了效率。

2) 在進(jìn)化過程中，保留了父代中較優(yōu)個(gè)體的信息。OBR無法在進(jìn)化過程中維持從父代繼承的信息，這樣會造成父代中較優(yōu)個(gè)體的信息丟失，從而導(dǎo)致只能收斂到局部最優(yōu)解。而GBR 每代都保留了父代中較優(yōu)個(gè)體的信息，這樣能使每只箱子裝得盡量滿，從而能找到全局的最優(yōu)的裝箱方案。

6 結(jié)束語

該文實(shí)地參觀了寧波港三期碼頭的運(yùn)作情況，對于如何提高港口的裝箱問題進(jìn)行了研究，文章分析了裝箱問題的基本特征，設(shè)計(jì)了符合港口裝箱問題的種群編碼，通過選擇算子，交叉算子和變異算子，篩選出優(yōu)質(zhì)的后代。通過一系列的遺傳操作，改善了裝箱的方法，提高了裝箱的效率。最后通過實(shí)驗(yàn)，驗(yàn)證了該算法的有效性。

參考文獻(xiàn):

[1] Ebru K，Bish.A multiple-crane-constrained scheduling problem in a container terminal. European Journal of Operational Research， 2005，144(1):83-107.

[2] Zhang C.Dynamic crane deployment in container storage yards:[PhD thesis].Hong Kong:Department of Industrial Engineering and Engineering Management， Hong Kong University of Science and Technology，2003.

[3] 張新艷.港口集裝箱物流系統(tǒng)規(guī)則與仿真建模方法的研究與實(shí)現(xiàn)[D].武漢:武漢理工大學(xué)，2003.

[4] 王小平，曹立明.遺傳算法-理論、應(yīng)用與軟件實(shí)現(xiàn)[M].西安:西安交通大學(xué)出版社，2003.