遺傳算法在碼頭泊位調度的研究與應用

官培堃　畢明彥

摘 要：為更好地優化碼頭泊位分配，提高泊位利用率，以實現碼頭泊位利用率最大化為目標，借鑒背包問題的解決方案，將船舶在港時間、作業順序、泊位安排、機械配置、堆場安排等時空因素，結合遺傳算法得出泊位資源安排的最優解。實踐證明，該算法能有效緩解人工制訂泊位計劃所造成的考慮不周全、計劃不合理等現象，有效避免了泊位沖突、極大提高了碼頭泊位利用率，提升了碼頭作業效益和服務水平。

關鍵詞：泊位調度；背包問題；遺傳算法

中圖分類號： U691 文獻標識碼： A 文章編號： 1673-1069（2016）25-179-2

0 引言

現代港口是國際物流供應鏈的主要環節，能夠提供快速、可靠、靈活的綜合物流經營服務是現代港口的重要標志。泊位是決定港口碼頭的一個關鍵因素，相對于港口其他設施的投資來說，建造一個新的泊位的費用是非常昂貴的，所以，如何在已有泊位數量的基礎上，合理的分配泊位已經成為制約當前港口發展的重要因素。

作為碼頭重要的作業資源，泊位、泊位計劃是碼頭作業的基礎，合理的泊位計劃是提高作業效率、縮短船舶在港時間的關鍵因素?，F在全球吞吐量排名前十的港口，其24小時內數量達到幾十艘次，因此如何合理安排船舶靠泊順序和位置，決定了碼頭岸線資源及堆場、設備、人力資源的合理應用程度，提高泊位計劃的合理性對提升整個碼頭的通過能力和服務水平，有著至關重要的意義[1]。

1 當前泊位計劃中存在的問題

當前泊位計劃編排的依據主要是根據船公司對碼頭的重要程度，也就是所謂的“重點客戶重點服務”策略；再有就是采用所謂的“先進先出”原則，這樣會導致出現物化消耗過大，服務效率低下，客戶滿意度不高等問題；除此之外，碼頭泊位計劃安排的好與壞，則主要體現在計劃員本身對于碼頭業務的理解程度、作業經驗是否豐富等方面，而這些則可能導致作業線路安全隱患或者資源岸線泊位浪費等情況出現。總之缺乏必要的理論支持和系統分析，從而導致泊位計劃的隨機性較大，這是目前泊位計劃制定過程中存在的一個比較普遍的問題。

2 通過基于背包問題的遺傳算法解決組合優化問題

遺傳算法已經成為組合優化問題的近似最優解的一把鑰匙[2][3]。它是一種模擬生物進化過程的計算模型[4]，作為一種新的全局優化搜索算法，它具有簡單、魯棒性強、適應并行處理廣等特點，非常適合N-P問題的求解。

背包問題是一個典型的組合優化問題，在計算理論中屬于NP-完全問題， 其計算復雜度為，傳統上采用動態規劃來求解。

如上所述，我們可以將碼頭岸線長度作為橫軸，時間為縱軸，兩者相乘所得面積作為背包大小，其他如泊位水深、船舶吃水、裝卸箱量等參數作為約束條件，從而將船舶泊位調度問題，轉化為背包問題最優解的求解問題。

3 問題描述

3.1 背包問題概述

背包問題（ Knapsack Problem）的一般提法是：已知n個物品的重量（weight）及其價值（或收益profit）分別為wi>0和pi>0，背包的容量（contain）假設設為ci>0，如何選擇哪些物品裝入背包，可以使得在背包的容量約束限制之內所裝物品的價值最大？

該問題的模型可以表示為下述0/1整數規劃模型：

式中xi為0-1決策變量，xi=1時表示將物品i裝入背包中，xi=0時則表示不將其裝入背包中。

3.2 遺傳算法概述

遺傳算法（ Genetic Algorithms，GA） 是在1975 年首次由美國密西根大學的D。J。Holland 教授和他的同事們借鑒生物界達爾文的自然選擇法則和孟德爾的遺傳進化機制基礎之上提出的。經過40多年的研究、應用，遺傳算法已被廣泛地應用于函數優化、機器人系統、模式識別、圖像處理、工業優化控制等多個領域。

4 背包問題的遺傳算法求解

遺傳算法具有“生成+檢測”的特點。其基本流程描述如下：

（1）基因編碼：

基因編碼將n個Xi的值順序排列，可簡單理解為，將符合要求的物品放入背包中，其他的物品則不放入。

（2）編碼修復：

利用遺傳算法的思想進行修復。修復的基本思想為：

在Xj=1的所有物品中，將價值重量比（C/W）最小的物品取出，直到滿足背包的容量約束為止。由此可產生一些新的基因編碼串，并且這些新編碼串總是相對來說質量比較好的，特別是它們肯定滿足問題的約束條件。

（3）適應度函數：

由于對每個個體使用遺傳算法修正已保證了不會產生無效染色體，所以在進行個體適應度評價時無須引入度函數項，而是直接用目標函數值作為適應度函數值，即：

（4）選擇： 采用輪盤賭的方式進行選擇。在本算法中，將各基因的適應值事先作處理：

fi（i）=fit（i）-min（fit）+1；以防止適應度函數值出現小于零的情況，并且可以在一定程度上防止適應值差別過大時丟失低適應值基因的有用信息。

（5）交叉： 采用單點交叉方式，隨機選取一點作為基因的交叉點。

（6）變異：定義參數pm作為變異操作的概率，由（5）得到每個個體中的每個基因值都以概率pm進行變異；

（7）演化：經過選擇、交叉和變異操作，得到一個新的種群，對上述步驟經過給定的循環次數的種群演化，遺傳算法終止[5]。

根據上面分析，我們不能看出，該算法成敗的關鍵在于適應度函數的建立，確切地說，就是其中的變量xj，以及對應參數cj。

以本案為例，我們可以將碼頭岸線乘以時間作為背包，單位時間內，碼頭所能承載的船舶數量最大化，或者說泊位利用率最高，作為我們的目標，而泊位水深、船舶吃水、裝卸箱量等參數作為約束條件。

如上所述，解決背包問題的算法有多種，在實踐中，我們采用遺傳算法來解決泊位調度問題，也就是從獲得泊位利用率最高出發，尋找最優解的方法。在絕大多數情況下，尋找最優解的時間復雜度還是比較低的。

在實際生產組織過程中，我們主要通過船公司重要性、碼頭吃水、船舶載重、以及碼頭岸線橋吊、機械配置等四個因素作為變量xj，并且根據實際效果，不斷調整變量的權數cj，來安排現場泊位，最終獲得最佳解，來實現泊位利用率最大化。

5 結論

5.1 作業效果

我們將該算法應用到碼頭泊位計劃系統中，目前該系統已經在青島前灣集裝箱碼頭公司應用，現將其中某一天碼頭船舶的真實數據羅列如表1所示。

通過數據對比，我們發現采用先到先安排原則和本文介紹的算法安排的泊位調度，對應泊位利用率從82%提升到87.2%，尤其對于裝卸箱量較大的大船，依靠本文提出的算法，能夠有效地提高碼頭的泊位利用率。

5.2 產生效益

實踐證明，系統地推廣應用，有效規范集裝箱碼頭作業流程，優化碼頭生產工藝，增強碼頭作業的安全管理能力，提升作業效率及資源的有效利用率，降低碼頭的作業成本，不僅提高了港口作業效率和服務質量，更極大提高了港口管理水平和服務能力，實現了良好的經濟效益和社會效益。

國際國內集裝箱貨運領域信息和營銷服務提供商美國 《JOC》雜志發布《2014年度全球港口和碼頭生產率研究》，在8000TEU以上集裝箱船的碼頭生產率中，青島港以157MPH的成績排名全球第一。

6 結束語

泊位計劃是碼頭的核心計劃，合理的泊位計劃是提高碼頭作業效率，縮短船舶在港時間的關鍵因素，本文根據碼頭實際，提出了基于背包問題的碼頭泊位調度遺傳算法，實踐證明，通過該算法，能有效提高碼頭的泊位利用率，對碼頭的生產作業有著較大的推動作用。下一步，將會結合碼頭岸橋、集卡、天氣、上游港口抵、離港情況等因素，對算法做進一步地優化和改進。

參 考 文 獻

[1] 宋海濤，張連鋼，竇亮.集裝箱碼頭泊位優化措施[J].集裝箱化.2015.9：5-8.

[2] Goldberg D E. Gennitic Algrithms in Search，Optimization and Machine Learning[J]，Adison Wesley Reading.MA，1989.

[3] Khuri s， Back T.Heitkott J，An Evolutionary Approch to Cambinal Optization Problems[J].Proc.of 22st. Annual Computer Science Conference 66-73 Newyork.

[4] Chen Guo-liang，Wang Xu-hua， et.al.Generic Algrithms and its Applications[J].，Beijing Peoples Posts and Telecommunications Press 1996.

[5] 張燕濤.基于遺傳算法的泊位調度問題優化研究及仿真[D].武漢：武漢理工大學，2005.