整數遺傳算法求解下的泊位形狀問題研究

張 璠

（遼寧省交通高等?？茖W校物流管理系，沈陽,110122）

0 引言

隨著經濟全球化的發展，跨地域、跨國家之間的貿易往來越來越頻繁，與之相應的船舶的運輸業也日益發展。目前，大型船（載箱量超過1 萬TEU）每天到港和離港的船只數與日俱增，港口泊位越來越擁擠，到港船舶等待時間加長，這無形中也增加了船運費用。因此，合理的泊位分配對港口運營而言顯得尤為重要。泊位分配問題（Berth Allocation Problem，簡稱BAP）是指船舶到達集裝箱碼頭后或之前，根據各個泊位的空閑情況和物理條件（如泊位長度、前沿水深等）的約束，碼頭調度人員為船舶安排合理的停泊泊位、靠泊順序以及確定合適的靠泊時間。合理的泊位分配能夠有效縮短船舶在港時間，從而降低碼頭的運營成本、提高客戶的滿意度。

圖1 給出了，目前全球采用的兩種形狀不同的港口。左邊這種我們稱為直線型樞紐港，（以下，簡稱為LT），右邊這種我們稱為凹槽型樞紐港（以下簡稱為，IT）。

1 問題描述與數學建模

圖1 兩種形狀的樞紐港

在不影響目標函數值的情況下，為了方便建立模型，我們規定：船舶的裝卸作業時間段=離泊準備時刻-作業準備時刻。于是，本BAP 模型中將會出現以下幾個時間參數：船舶到港時刻、船舶進泊開始作業時刻、船舶裝卸箱時間段和船舶離港時刻。依據參考大量國內外文獻[1,2]，本研究考慮兩種形狀的碼頭，如圖2 所示的直線型（簡稱L 型）和凹槽型（簡稱I 型）。白色橢圓代表大型船以外的船，灰色的橢圓代表大型船。

那么，BAP 模型目標函數與約束條件如下所示。

目的函數：Min（所有船舶的（開始服務時刻-到港時刻+裝卸箱時間））

約束條件：

（1）每條船必須且僅服務一次；

圖2 兩種類型的碼頭

圖3 I 型泊位停靠非大型船時會產生的出港制約

（2）船到達后被服務；

（3）船長不超過泊位長；（4）泊位水深不小于船的吃水深；

（5）在船長總和不超過泊位長度的情況下，可以安排這兩艘 船同時進行裝卸作業；

（6）大型船優先度高，到港后可立即進行裝卸作業；

（7）在I 型碼頭，大型船必須使用I 型泊位從船舶的兩舷同時進行作業。

（8）如圖3 所示，I 型泊位里面船舶即便裝卸作業完畢，也得等待外部船舶作業完畢出港后才可以出港。

2 遺傳算法

本研究在港口服務系統時以所有船舶的總在港時間最短為目標，建立了BAP 數學模型，根據模型特點導出必須滿足的約束條件，為了使該模型能夠更加反映船舶泊位實際情況，我們采用整數編碼的遺傳算法（Genetic Algorithm，簡稱GA）來求解。我們采用圖4 的編碼方式進行編碼設計。即8 號船在1 號泊位第2個進行裝卸作業，5 號船在1 號泊位第3 個進行裝卸作業，7 號船在2 號泊位第2 個進行裝卸作業；6 號船在2 號泊位待1 號船走后進行裝卸作業的這種表現方法將船、泊位、裝卸作業順序這3 個信息表現了出來。根據既往的研究，本研究也采用以下適應度函數：

適應度=100000/目的函數值

關于遺傳操作，根據文獻[1]本研究采用輪盤賭選擇法進行選擇操作，兩點交叉法進行交叉，換位變異法進行變異操作。

GA 參數選定：在求解BAP 時，控制參數的不同選擇會對遺傳算法的性能產生很大影響。根據文獻[3]和GA 選定實驗結果我們將群體規模規定為50，變異概率為0.09，進化代數為3000。

3 數值實驗

3.1 數值試驗

（1）數據生成及情況假定

大型船到港頻度我們規定三種：計劃周期內不到港（M0），到港1 次（M1），到港2 次（M2）。船長設定為400m。根據文獻[1,2]，我們規定大型船在L 型泊位裝卸作業時間為57 小時，在I 型泊位上規定為40 小時。

圖4 染色體編碼設計

圖5 總在港時間比較

大型船以外的船舶的到港時刻、裝卸作業時間以及船舶長度均由亂數隨機生成。本研究主要針對樞紐港的形狀進行對比研究，所以回避了2 艘船舶在同一泊位內同時進行裝卸作業的復雜情況。因此，我們將大型船以外的船舶長度設定在201～400m 之間。并且，設定一個泊位的長度為400m。船舶到港時刻間隔分別按照2,3,4 小時一艘的頻率按指數分布狀況來寄港。

（2）數值試驗及結論

根據如上所述的假定情況，我們得到了如圖7 所示的結果。依圖所得：

（1）從M0、M1、M2 三種情況下的對比比較來看，大型船寄港與否，船舶在IT 比在LT 的總在港時間短。目前，大型船已經成為船舶使用趨勢。集裝箱碼頭的岸線是由一定的地理、水深、潮汐和航道等因素唯一確定的，是作為集裝箱碼頭公司最寶貴的不可再生資源。建設投資巨大不說，資源還有不可再生以及唯一的性質。因此，在條件允許的情況下，大力搭建或改建成凹槽式樞紐港或者是碼頭更加適應當前船舶大型化的發展。同時，隨著大型船寄港頻率的增加，船舶在L 型或者在I 型的總在港時間之間的差距愈加變小。這一點是可以解釋通的。當大型船寄港頻率過大時，使得凹槽泊位被大型船以外的船舶利用率低導致這些船舶只能用凹槽泊位以外的直線泊位，此時的L 型便等同于I 型。因此，隨著大型港寄港頻度的增加，船舶在L 型和I 型的總在港時間愈加接近。

（2）從到港時間間隔2 小時、3 小時和4 小時上來看，船舶的總在港時間會隨著到港時間間隔的增大而變小。到港時間間隔的增大，也可以理解為船舶之間的等待時間及幾率減少，由于總等待時間的減少、船舶裝卸作業時間還不變，兩者相加的總在港時間勢必會變少。由此也可以看出，不管是I 型樞紐港也好L 型樞紐港也好，適度的船舶數量以及到港時間間隔會降低客戶等待時間，從而提高客戶滿意度，提高港口回轉效率。

（3）隨著船舶數量的增加，總在港時間也隨之變長，1 艘船的平均在港時間也可判斷出應在不斷增長。由于裝卸作業時間長短固定，可推出隨著船舶數量的增加，每搜船舶的等待時間也隨之增加。

4 小結

本文針對目前全球擁有的兩種形狀的碼頭，采用遺傳算法對集裝箱港口泊位優化問題進行了建模與研究。主要成果如下：

（1）在參考了國內外大量文獻后了解了目前國內外出現的兩種形狀的集裝箱港口，建立了與之相對應的數學建模，包括目標函數與約束函數。并運用亂數隨機生成等方法造出與目前我國港口實際情況較符合的船舶相關數據。

（2）參考了幾種不同的優化方法，最終選擇用整數編碼的遺傳算法來解決本研究的BAP 模型。通過實例說明優化后的結果能使所有船舶的總在港時間最短，編制了通用的優化程序，為以后更進一步的研究BAP 模型提供了一個高效有用的工具。

（3）通過大量的數據結果表明，I 型集裝箱港口不論是大型船是否寄港都比L 型集裝箱港口更加效率化。因此，在條件允許的情況下，建設或修建成I 型集裝箱港口更加適應當前集裝箱船大型化的現狀。

BAP 是一個復雜而且離散的隨機系統，本研究在數學模型的建立、算法上取得了一定的進展，但是，由于時間和其他方面的限制，本研究還存在著不足之處，有待更進一步的研究與改進。主要在以下3 個方面需要進行改善：

（1）大型船是否寄港，以及寄港頻度顯然對船舶?？坑媱澮约邦櫩偷却龝r間長短起到很大的作用。計劃周期內大型船的寄港頻度有待繼續的深入研究，怎樣個頻度才能是顧客滿意度最大化是需要被研究的。

（2）進一步調查我國各港口船舶情況，根據不同類型的港口量身設計更適合的數學模型及數據。

（3）繼續深入研究遺傳算法，特別是基于染色體遺傳方式的不同考慮選擇優化結果的影響。

（4）船舶的到港時間間隔也是造成等待時間過長的一個因素。因此。在計劃周期內，時間間隔定位多少才能使顧客等待時間以及港口運營收入兩者關系最為協調，這也是下一個需要考慮的問題。

[1] 西村悅子,コンテナバース共同利用のためのバース最適割當に関する研究,京都大學博士論文,2002.12.

[2] Imai A.,Nishimura E.,Hattori M.,Papadimitriou S. Berth allocation at indented berths for megacontainerships,European Journal of Operational Research 179(2007) 579-593.

[3] 服部真洋、コンテナバース共同利用のためのバース最適割當に関する研究、神戸大學修士論文、2006.1.