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

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

關鍵詞:遺傳算法;港口;裝箱

中圖法分類號:TP311文獻標識碼: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

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

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

1 什么是裝箱問題

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

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

2 裝箱問題的基本特征

根據裝箱問題的自身特點，不同的學者制度了研究了裝箱問題的不同方面，總結起來，它的基本特征如下:

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

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

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

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

3 裝箱問題的描述和數學模型

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

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

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

4 遺傳算法的設計

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

4.1 初始種群

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

4.2 編碼方式

采用Grefenstette等提出的編碼方法，該方法能夠使得任意的基因型個體都能夠對應于一條具有實際意義的裝箱順序。

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

4.3 選擇算子

采用最優保存策略進化模型(Elitist Mode1)來進行優勝劣汰操作，當前群體中適應度最高的個體不參與交叉運算和變異運算。

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

4.4 交叉算子

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

4.5 變異算子

依次指定個體編碼串中的每個基因座為變異點。對每一個變異點，以變異概率P從對應基因的取值范圍內取隨機數來替代原有基因值。

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

5 仿真實驗

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

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

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

通過比較，可以總結出，在傳統裝箱問題中，GBR有以下優點:

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

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

6 結束語

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

參考文獻:

[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] 張新艷.港口集裝箱物流系統規則與仿真建模方法的研究與實現[D].武漢:武漢理工大學，2003.

[4] 王小平，曹立明.遺傳算法-理論、應用與軟件實現[M].西安:西安交通大學出版社，2003.