遺傳算法在碼頭泊位調(diào)度的研究與應(yīng)用

官培堃　畢明彥

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

關(guān)鍵詞：泊位調(diào)度；背包問題；遺傳算法

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

0 引言

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

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

1 當(dāng)前泊位計劃中存在的問題

當(dāng)前泊位計劃編排的依據(jù)主要是根據(jù)船公司對碼頭的重要程度，也就是所謂的“重點客戶重點服務(wù)”策略；再有就是采用所謂的“先進先出”原則，這樣會導(dǎo)致出現(xiàn)物化消耗過大，服務(wù)效率低下，客戶滿意度不高等問題；除此之外，碼頭泊位計劃安排的好與壞，則主要體現(xiàn)在計劃員本身對于碼頭業(yè)務(wù)的理解程度、作業(yè)經(jīng)驗是否豐富等方面，而這些則可能導(dǎo)致作業(yè)線路安全隱患或者資源岸線泊位浪費等情況出現(xiàn)?？傊狈Ρ匾睦碚撝С趾拖到y(tǒng)分析，從而導(dǎo)致泊位計劃的隨機性較大，這是目前泊位計劃制定過程中存在的一個比較普遍的問題。

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

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

背包問題是一個典型的組合優(yōu)化問題，在計算理論中屬于NP-完全問題， 其計算復(fù)雜度為，傳統(tǒng)上采用動態(tài)規(guī)劃來求解。

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

3 問題描述

3.1 背包問題概述

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

該問題的模型可以表示為下述0/1整數(shù)規(guī)劃模型：

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

3.2 遺傳算法概述

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

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

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

（1）基因編碼：

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

（2）編碼修復(fù)：

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

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

（3）適應(yīng)度函數(shù)：

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

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

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

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

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

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

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

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

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

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

5 結(jié)論

5.1 作業(yè)效果

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

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

5.2 產(chǎn)生效益

實踐證明，系統(tǒng)地推廣應(yīng)用，有效規(guī)范集裝箱碼頭作業(yè)流程，優(yōu)化碼頭生產(chǎn)工藝，增強碼頭作業(yè)的安全管理能力，提升作業(yè)效率及資源的有效利用率，降低碼頭的作業(yè)成本，不僅提高了港口作業(yè)效率和服務(wù)質(zhì)量，更極大提高了港口管理水平和服務(wù)能力，實現(xiàn)了良好的經(jīng)濟效益和社會效益。

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

6 結(jié)束語

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

參 考 文 獻

[1] 宋海濤，張連鋼，竇亮.集裝箱碼頭泊位優(yōu)化措施[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] 張燕濤.基于遺傳算法的泊位調(diào)度問題優(yōu)化研究及仿真[D].武漢：武漢理工大學(xué)，2005.