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

張 璠

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

0 引言

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

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

1 問題描述與數(shù)學(xué)建模

圖1 兩種形狀的樞紐港

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

那么，BAP 模型目標(biāo)函數(shù)與約束條件如下所示。

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

約束條件：

（1）每條船必須且僅服務(wù)一次；

圖2 兩種類型的碼頭

圖3 I 型泊位?？糠谴笮痛瑫r(shí)會產(chǎn)生的出港制約

（2）船到達(dá)后被服務(wù)；

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

（5）在船長總和不超過泊位長度的情況下，可以安排這兩艘 船同時(shí)進(jìn)行裝卸作業(yè)；

（6）大型船優(yōu)先度高，到港后可立即進(jìn)行裝卸作業(yè)；

（7）在I 型碼頭，大型船必須使用I 型泊位從船舶的兩舷同時(shí)進(jìn)行作業(yè)。

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

2 遺傳算法

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

適應(yīng)度=100000/目的函數(shù)值

關(guān)于遺傳操作，根據(jù)文獻(xiàn)[1]本研究采用輪盤賭選擇法進(jìn)行選擇操作，兩點(diǎn)交叉法進(jìn)行交叉，換位變異法進(jìn)行變異操作。

GA 參數(shù)選定：在求解BAP 時(shí)，控制參數(shù)的不同選擇會對遺傳算法的性能產(chǎn)生很大影響。根據(jù)文獻(xiàn)[3]和GA 選定實(shí)驗(yàn)結(jié)果我們將群體規(guī)模規(guī)定為50，變異概率為0.09，進(jìn)化代數(shù)為3000。

3 數(shù)值實(shí)驗(yàn)

3.1 數(shù)值試驗(yàn)

（1）數(shù)據(jù)生成及情況假定

大型船到港頻度我們規(guī)定三種：計(jì)劃周期內(nèi)不到港（M0），到港1 次（M1），到港2 次（M2）。船長設(shè)定為400m。根據(jù)文獻(xiàn)[1,2]，我們規(guī)定大型船在L 型泊位裝卸作業(yè)時(shí)間為57 小時(shí)，在I 型泊位上規(guī)定為40 小時(shí)。

圖4 染色體編碼設(shè)計(jì)

圖5 總在港時(shí)間比較

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

（2）數(shù)值試驗(yàn)及結(jié)論

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

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

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

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

4 小結(jié)

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

（1）在參考了國內(nèi)外大量文獻(xiàn)后了解了目前國內(nèi)外出現(xiàn)的兩種形狀的集裝箱港口，建立了與之相對應(yīng)的數(shù)學(xué)建模，包括目標(biāo)函數(shù)與約束函數(shù)。并運(yùn)用亂數(shù)隨機(jī)生成等方法造出與目前我國港口實(shí)際情況較符合的船舶相關(guān)數(shù)據(jù)。

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

（3）通過大量的數(shù)據(jù)結(jié)果表明，I 型集裝箱港口不論是大型船是否寄港都比L 型集裝箱港口更加效率化。因此，在條件允許的情況下，建設(shè)或修建成I 型集裝箱港口更加適應(yīng)當(dāng)前集裝箱船大型化的現(xiàn)狀。

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

（1）大型船是否寄港，以及寄港頻度顯然對船舶停靠計(jì)劃以及顧客等待時(shí)間長短起到很大的作用。計(jì)劃周期內(nèi)大型船的寄港頻度有待繼續(xù)的深入研究，怎樣個頻度才能是顧客滿意度最大化是需要被研究的。

（2）進(jìn)一步調(diào)查我國各港口船舶情況，根據(jù)不同類型的港口量身設(shè)計(jì)更適合的數(shù)學(xué)模型及數(shù)據(jù)。

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

（4）船舶的到港時(shí)間間隔也是造成等待時(shí)間過長的一個因素。因此。在計(jì)劃周期內(nèi)，時(shí)間間隔定位多少才能使顧客等待時(shí)間以及港口運(yùn)營收入兩者關(guān)系最為協(xié)調(diào)，這也是下一個需要考慮的問題。

[1] 西村悅子,コンテナバース共同利用のためのバース最適割當(dāng)に関する研究,京都大學(xué)博士論文,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] 服部真洋、コンテナバース共同利用のためのバース最適割當(dāng)に関する研究、神戸大學(xué)修士論文、2006.1.