低碳經(jīng)濟(jì)下港口泊位—岸橋分配問(wèn)題

王致遠(yuǎn)，范元偉 WANG Zhi-yuan, FAN Yuan-wei

（上海理工大學(xué) 管理學(xué)院，上海200093）

(College of Management, University of Shanghai for Science and Technology, Shanghai 200093, China)

0 引 言

泊位和岸橋是港口的稀缺資源，正因?yàn)槿绱?，合理的泊位—岸橋資源分配對(duì)于碼頭和船舶運(yùn)營(yíng)成本降低及客戶滿意度的提高都至關(guān)重要[1]。同時(shí)，合理的泊位—岸橋分配計(jì)劃和船舶進(jìn)港時(shí)間的選擇對(duì)于船舶的油耗成本和二氧化碳的排放量有著直接的關(guān)系。但是隨著集裝箱運(yùn)輸量的持續(xù)增長(zhǎng)，船舶往往高速駛?cè)敫劭?，造成碼頭擁擠，船舶只能在錨地等待靠泊，這大大增加了船舶等待的成本以及燃油消耗和二氧化碳的排放，造成環(huán)境的污染，不利于綠色航運(yùn)和節(jié)省燃油成本的目標(biāo)。研究報(bào)告表明，每年航運(yùn)業(yè)二氧化碳的排放量超過(guò)12 億噸，約占全球碳排放總量的4%[2]。由于近年來(lái)燃油價(jià)格的突飛猛漲，如何降低燃油成本已經(jīng)成為了所有航運(yùn)公司所關(guān)注的焦點(diǎn)，例如，減少ballast/盡量多裝貨，控制船舶航運(yùn)速度，設(shè)計(jì)最佳耗油轉(zhuǎn)速提高燃油使用率。這就需要港口與航運(yùn)公司之間相互配合，協(xié)同合作，信息共享，才能緩解港口擁擠以及航運(yùn)公司燃油成本過(guò)高的嚴(yán)峻情況。

許多文獻(xiàn)在研究港口泊位—岸橋分配計(jì)劃時(shí)，往往把船舶到港時(shí)間作為一個(gè)已知的參數(shù)來(lái)制定船舶泊位—岸橋分配計(jì)劃[3-5]，并且它們所關(guān)注的問(wèn)題主要在于保持客戶服務(wù)水平的情況下，減少船舶在港口等待時(shí)間和船舶停泊時(shí)產(chǎn)生的二氧化碳排放量，這與航運(yùn)公司所關(guān)切的整個(gè)航次的燃油消耗量以及二氧化碳排放量有所不同。本文研究的是在低碳經(jīng)濟(jì)下的港口泊位—岸橋問(wèn)題，不再把船舶到港時(shí)間看作是已知的參數(shù)，而是作為一個(gè)決策變量。同時(shí)，對(duì)于到港船舶，通過(guò)港口與航運(yùn)公司雙方信息的共享，船舶公司根據(jù)即將到港船舶的基本信息（船舶長(zhǎng)度，船舶裝卸箱量，船舶靠泊位置，距離港口的距離，船舶航行的最大和最小航速） 進(jìn)行泊位—岸橋資源分配，使港口整體資源得到充分利用，為到港的船舶指定其較為偏好的停泊位置，以此為基礎(chǔ)，岸橋分配用于確定服務(wù)于每艘船舶的岸橋數(shù)量。通過(guò)優(yōu)化分析提高停泊時(shí)的工作效率，降低船舶在港時(shí)間，以此彌補(bǔ)船舶由于降低速度駛?cè)敫劭谒斐傻碾x港延遲。在緩解港口擁擠的情況下，降低船舶在港時(shí)的燃油消耗和二氧化碳的排放，以達(dá)到低碳經(jīng)濟(jì)下綠色航運(yùn)的目標(biāo)。

1 模型建立

本文建立的低碳經(jīng)濟(jì)下泊位—岸橋分配模型是由低碳經(jīng)濟(jì)下的泊位分配和港口的岸橋分配兩部分建立而成，不僅能夠?qū)崿F(xiàn)低碳經(jīng)濟(jì)下船舶油耗量最小和船舶離港延遲時(shí)間最短的目標(biāo)，同時(shí)能夠?qū)崿F(xiàn)港口岸橋分配總量最小，從而節(jié)省港口的資源分配，提高港口生產(chǎn)作業(yè)系統(tǒng)的整體性能。

1.1 低碳經(jīng)濟(jì)下的泊位分配。與傳統(tǒng)泊位分配模型不同，本文將船舶到港時(shí)間作為決策變量，將船舶燃料消耗量和二氧化碳排放量融入傳統(tǒng)泊位分配模型的目標(biāo)函數(shù)中進(jìn)行優(yōu)化。然而不能忽視的一個(gè)問(wèn)題是船舶通過(guò)改變靠港時(shí)的航速來(lái)控制到港時(shí)間，雖然可以最小化其等待時(shí)間，但是會(huì)影響到船舶的離港時(shí)間，進(jìn)而影響船期。為了防止出現(xiàn)所有船舶都以最低航速駛近港口進(jìn)而減少燃料消耗和二氧化碳排放量，并同時(shí)縮短在港作業(yè)時(shí)間的優(yōu)化結(jié)果，本文將船舶平均在港時(shí)間最小化的目標(biāo)函數(shù)修改為船舶平均離港延遲時(shí)間最小化。

設(shè)V：到港船舶集合（包含n艘船舶）；L：岸線長(zhǎng)度；li：船舶的船長(zhǎng)（考慮了船舶靠泊的安全距離）；hi：船舶i的作業(yè)時(shí)間；xi：靠泊位置；M：一個(gè)足夠大的常數(shù)。決策變量：yi：船舶的靠泊時(shí)間。ai：船舶i的到港時(shí)間，ai的取值應(yīng)介于分別由船舶的最高航速和最低航速確定。輔助決策變量：σij：σij=1 表示船舶i在船舶j的左側(cè)靠泊；否則σij=0；i,j∈V,i≠j； δij：δij=1 表示船舶i在船舶j之前靠泊；否則δij=0；i,j∈V,i≠j。

假設(shè)泊位分配計(jì)劃從零時(shí)刻開(kāi)始，此時(shí)船舶距離港口mi（海里）。由趙剛的《國(guó)際航運(yùn)管理》[4]，船舶i每航行天的燃油消耗fi與所采用的航速vi之間的函數(shù)關(guān)系可以用式（1） 表示。

船舶i從距離港口mi海里處行駛至港口過(guò)程中的燃油消耗量Fi可以表示為：

由此可得低碳經(jīng)濟(jì)下的BAP 模型如下：

目標(biāo)函數(shù)（11） 為最小化船舶駛近港口期間的燃油消耗。由于船舶二氧化碳排放量與用油量成正比，因此該目標(biāo)與最小化船舶航行期間的碳排放量是一致的。船舶二氧化碳排放量與用油量之間的比例系數(shù)在各文獻(xiàn)中有微小差別，本文采用政府間氣候變化專門委員會(huì)（IPCC: Intergovernmental Panel on Climate Change） 的比例，即1 噸船用油的燃燒產(chǎn)生3.17 噸的二氧化碳[5]。目標(biāo)函數(shù)（4） 為最小化船舶平均離港延遲時(shí)間，需要注意的是本文不考慮沒(méi)有延遲的船舶，而只考慮延遲離港的船舶進(jìn)行優(yōu)化，所以這里的參數(shù)n為延遲船舶的總數(shù)量。

1.2 港口的岸橋分配。設(shè)T為時(shí)間段集合，為可利用岸橋集合，為船舶的裝卸箱量；etbi為船舶i的預(yù)計(jì)靠泊時(shí)間；etui為船舶i的預(yù)計(jì)離港時(shí)間；Cmini為船舶i的最少可分配岸橋數(shù)目，由船公司與碼頭公司的協(xié)議決定；Cmaxi為船舶i的最多可分配岸橋數(shù)目，由船舶長(zhǎng)度和岸橋安全距離決定；v0為單個(gè)岸橋作業(yè)效率（TEU/h）；決策變量nci為分配給船舶i的作業(yè)岸橋數(shù)目；從屬變量thi為船舶i的作業(yè)開(kāi)始時(shí)間，本文假定只有當(dāng)所需岸橋全準(zhǔn)備好后才能開(kāi)始作業(yè)；從屬變量tfi為船舶i的作業(yè)完成時(shí)間；如果岸橋k在時(shí)間段j服務(wù)船舶i；則從屬變量θijk=1，否則θijk=0；岸橋分配子模型如下:

目標(biāo)函數(shù)（12） 表示船舶等待作業(yè)平均所需岸橋總量最小，這里需要注意的是，岸橋的利用是可以重復(fù)，也就是說(shuō)假設(shè)停泊位置相近或者相同的前后兩艘船可以分配到相同編號(hào)的岸橋；約束條件（13） 表示各船舶所分配岸橋數(shù)目的取值范圍；約束條件（14） 表明船舶作業(yè)時(shí)間與船舶裝卸箱量成正比，與所分配岸橋數(shù)目成反比；約束條件（15） 保證所有裝卸作業(yè)需在指定時(shí)間窗內(nèi)完成；約束條件（16） 表明在船舶作業(yè)過(guò)程中，作業(yè)岸橋數(shù)目保持不變；約束條件（17） 和（18） 說(shuō)明沒(méi)有岸橋在指定時(shí)間窗外對(duì)船舶進(jìn)行作業(yè)；約束條件（19） 表明一臺(tái)岸橋在每個(gè)時(shí)間段內(nèi)最多可以服務(wù)一艘船舶；約束條件（20） 保證各時(shí)段內(nèi)所有作業(yè)岸橋數(shù)不能超過(guò)岸橋總數(shù)；約束條件（21） 定義了從屬變量。

2 模型求解

本文模型分為兩部：低碳經(jīng)濟(jì)下的泊位分配以及港口的岸橋分配，利用多目標(biāo)遺傳算法求出全局最優(yōu)解，達(dá)到本文研究的目的。

2.1 低碳經(jīng)濟(jì)下的泊位分配算法。本文模型第一部分為低碳經(jīng)濟(jì)下的泊位分配，泊位分配問(wèn)題為NP 難題。本文采用了一種模擬生物進(jìn)化機(jī)制的智能隨機(jī)優(yōu)化算法—遺傳算法，它把自然遺傳機(jī)制和計(jì)算機(jī)科學(xué)結(jié)合起來(lái)，按照個(gè)體對(duì)環(huán)境的適應(yīng)程度進(jìn)行概率搜索。因其搜索最優(yōu)解的過(guò)程具有指導(dǎo)性，因此不容易陷入局部最優(yōu)，即使所定義的適應(yīng)函數(shù)是不連續(xù)的、非規(guī)則的，它也能以很大的概率找到全局最優(yōu)解[6]。遺傳算法因其優(yōu)化性能在多目標(biāo)優(yōu)化問(wèn)題中有較為廣泛的應(yīng)用[7-8]。本文結(jié)合具體問(wèn)題對(duì)傳統(tǒng)的遺傳算法進(jìn)行了改進(jìn)，具體求解步驟如下。

（1） 染色體編碼。本文用兩個(gè)基因片組成一個(gè)染色體個(gè)體。子染色體1 表示船舶靠泊順序，用自然數(shù)的編碼形式，區(qū)別于船舶在碼頭的具體位置。由于碼頭和船長(zhǎng)是固定的，所以一種靠泊順序就對(duì)應(yīng)著一個(gè)靠泊位置。子染色體2 為靠泊時(shí)間，采用小數(shù)的編碼形式。如表1 所示。

表1 染色體的基因表述

（2） 種群初始化。為保證多樣性，采用隨機(jī)生成初始種群的方法。假設(shè)種群的大小為M，在算法開(kāi)始隨機(jī)生成M條染色體。

（3） 目標(biāo)函數(shù)計(jì)算。任一染色體個(gè)體，包含兩條子染色體，即船舶靠泊順序和靠泊時(shí)間，通過(guò)染色體個(gè)體變量可以求解出對(duì)應(yīng)的從屬變量，進(jìn)而計(jì)算出對(duì)應(yīng)的目標(biāo)函數(shù)值，將其作為各個(gè)體的適應(yīng)度值。

（4） 交叉操作。將種群個(gè)體的信息在種群成員中進(jìn)行交換，從而產(chǎn)生新的染色體，增加種群的多樣性。本文的一個(gè)染色體中有兩種不同編碼形式，因此對(duì)于子染色體1（整數(shù)編碼形式），在交叉時(shí)采用兩點(diǎn)交叉的方式。對(duì)于子染色體2（小數(shù)編碼形式），采用正交交叉的方式。

（5） 變異操作。在一個(gè)種群中，每個(gè)個(gè)體以概率Pm進(jìn)行變異，生成新的變異群體。在每個(gè)變異的個(gè)體中，對(duì)于染色體1，采用隨機(jī)選取兩個(gè)不同的位置進(jìn)行交換的方式來(lái)進(jìn)行變異操作。對(duì)于染色體2，采用基于取代的方法即隨機(jī)的選取一個(gè)取代位置，并且隨機(jī)的生成一個(gè)滿足式（18） 的隨機(jī)數(shù)，用其取代當(dāng)前位置上的基因信息。

（6） 選擇操作。選取當(dāng)前種群中的所有個(gè)體，包括交叉后和變異后的新個(gè)體，計(jì)算每個(gè)染色體個(gè)體的適應(yīng)值，并進(jìn)行排序，適應(yīng)值小的排前面，適應(yīng)值大的排后面，最后從種群前排選出M個(gè)個(gè)體，作為下一代的新種群。

（7） 終止準(zhǔn)則。以進(jìn)化代數(shù)作為終止判斷條件，如果進(jìn)化代數(shù)小于設(shè)定值，則返回（3），否則輸出結(jié)果。

2.2 岸橋分配模型算法。模型第二部分為港口的岸橋分配，也采用基于啟發(fā)式算法的遺傳算法進(jìn)行求解。具體步驟如下。

染色體編碼：采用自然數(shù)編碼形式進(jìn)行編碼，如表2 所示，染色體長(zhǎng)度表示船舶數(shù)目；基因位置為船舶ID；基因值為船舶分配的岸橋數(shù)目nc，該數(shù)目由約束條件（13） 隨機(jī)生成。

遺傳操作：選擇操作為輪盤賭法，交叉操作為2 點(diǎn)交叉法, 變異操作為交換變異法。

表2 染色體的基因表述

終止條件：到達(dá)最大迭代次數(shù)。

3 試驗(yàn)算例

3.1 基礎(chǔ)數(shù)據(jù)。本文使用寧波市某著名的國(guó)際集裝箱碼頭的實(shí)際數(shù)據(jù)進(jìn)行研究。其碼頭岸線長(zhǎng)L=1 500 米，取時(shí)間為1 天，以小時(shí)分段。初始時(shí)刻各岸橋均勻分布在碼頭岸線上。E從（600TEU～2 300TEU）；V0=40TEU/h。設(shè)定船舶作業(yè)時(shí)間初始值set-其中，vr為港口的平均船時(shí)效率。采用MATLAB R2013a 編寫算法程序，運(yùn)行機(jī)器配置為Pentium（R） D CPU 2.80GHZ。試驗(yàn)確定：初始種群popsize=10，交叉概率pc=0.6，變異概率pm=0.01，迭代次數(shù)g=50。我們的目標(biāo)是：（1） 確定優(yōu)化目標(biāo)為船舶離港延遲時(shí)間最小，且最小化船舶駛近港口期間的燃油消耗（2） 在完成總工作量的情況下，最小化安排給船舶工作的岸橋總數(shù)目。

3.2 結(jié)果分析。從圖1 中可以看出，第三行和第五行表示的是10 艘船舶的最佳到港時(shí)間。Bestfitness 的值為低碳經(jīng)濟(jì)下泊位分配的兩個(gè)目標(biāo)函數(shù)，即離港時(shí)間最小化和燃料消耗、二氧化碳排放量最小化的加權(quán)和的最優(yōu)解。Positionx 的值表示的是10 艘船舶最佳的停泊位置。圖2 縱坐標(biāo)表示模型第一部分低碳經(jīng)濟(jì)下泊位分配的兩個(gè)目標(biāo)函數(shù)，即離港時(shí)間最小化、燃料和二氧化碳排放最小化的加權(quán)和，橫坐標(biāo)表示的是種群個(gè)體通過(guò)交叉變異的迭代數(shù)值，本文設(shè)定迭代數(shù)為50，紅色曲線表示的是每一代兩個(gè)目標(biāo)函數(shù)的加權(quán)和的平均值，藍(lán)色曲線表示的是從各代中挑選出來(lái)的最優(yōu)的目標(biāo)函數(shù)加權(quán)值。從圖2 中可以看出，隨著種群進(jìn)化迭代數(shù)的不斷增加，代表各代種群目標(biāo)函數(shù)平均加權(quán)和的紅色曲線逐漸趨近于代表各代種群目標(biāo)函數(shù)最佳加權(quán)和的藍(lán)色曲線，從而可以得出滿足在低碳經(jīng)濟(jì)下離港時(shí)間最小化且燃料、二氧化碳排放量最小化雙目標(biāo)的最佳加權(quán)和，從圖1 可知最佳加權(quán)和值為63.7479，實(shí)現(xiàn)本文模型第一部分低碳經(jīng)濟(jì)下泊位分配的目標(biāo)。

圖3 中，bestpop2 的值表示的是碼頭分配給每艘船最多的岸橋總數(shù)。Bestfitness2 的值表示的是碼頭只需要11 臺(tái)岸橋便可以完成10 艘船舶到港裝卸貨物的任務(wù)。Popindex 每一行的值表示的每艘船舶使用岸橋的編號(hào)，需注意的是0 表示的是沒(méi)有使用岸橋。圖4 為求解港口岸橋分配時(shí)遺傳算法的迭代過(guò)程圖。圖4 橫坐標(biāo)表示的是岸橋使用的總數(shù)量，縱坐標(biāo)表示的是進(jìn)化的迭代數(shù)。本文設(shè)定進(jìn)化代數(shù)為50。紅色曲線表示的是種群個(gè)體每一代岸橋分配總量的平均值，藍(lán)色曲線表示的是種群個(gè)體每一代最佳的岸橋分配總數(shù)量。從圖4 可以發(fā)現(xiàn)，隨著種群進(jìn)化迭代數(shù)目的不斷增加，代表各代種群個(gè)體岸橋分配總量平均值的紅色曲線逐漸趨近于代表各代種群個(gè)體岸橋分配總量最佳值得藍(lán)色曲線，從而可以表示為通過(guò)確定每艘船舶的泊位位置和停靠時(shí)間，而得出港口最佳的岸橋分配總量為11 個(gè)。不僅滿足了低碳經(jīng)濟(jì)下的泊位分配最佳，也滿足了港口岸橋分配總量的最佳。

4 結(jié) 論

本文將船舶到港時(shí)間作為決策變量引入傳統(tǒng)泊位分配模型中，同時(shí)將船舶油耗和碳排放量融入傳統(tǒng)泊位分配模型的目標(biāo)函數(shù)中，建立了船舶油耗最小和船舶離港延遲時(shí)間最短的雙目標(biāo)優(yōu)化模型，并且加入岸橋分配模型，使得港口整體優(yōu)化，在滿足能夠完成船舶裝卸任務(wù)的情況下，避免不必要的岸橋分配，提高港口的工作效率。然而研究仍然存在很多的局限性，首先，沒(méi)有考慮船舶在港停泊時(shí)的排放量問(wèn)題；其次，模型只考慮了一個(gè)碼頭及其客戶，而實(shí)際問(wèn)題可能會(huì)延伸到涉及多個(gè)碼頭，甚至多個(gè)港口。克服這些限制，并優(yōu)化模型將是未來(lái)進(jìn)一步的研究方向。

[1] Meisel F, Bierwirth C. Heuristics for the integration of crane productivity in the berth allocation problem[J]. Transportation Research Part E: Transportation Review, 2009,45(1):196-209.

[2] 袁象. 低碳經(jīng)濟(jì)對(duì)我國(guó)海運(yùn)業(yè)的影響及應(yīng)對(duì)措施[J]. 交通企業(yè)管理，2010(2):1-3.

[3] BIERWIRTH C, MEISEL F. A survey of berth allocation and quay crane scheduling problems in container terminal[J]. European Journal of Operational Research, 2010,202(3):615-627.

[4] STEENKEN D, VOB S, STAHLBOCK R. Container terminal operation and operations research——a classification and literature review[J]. OR Spectrum, 2004,26(1):3-49.

[5] STAHLBOCK R, VOB S. Operations research at container terminals: a literature update[J]. OR Spectrum, 2008,30(1):1-52.

[6] 王小平，曹立明. 遺傳算法——理論、應(yīng)用與軟件實(shí)現(xiàn)[M]. 西安：西安交通大學(xué)出版社，2002:78-79.

[7] 趙剛. 國(guó)際航運(yùn)管理[M]. 大連：大連海事大學(xué)出版社，2006:93-94.

[8] 王海峰，白佳玉. 國(guó)際海運(yùn)溫室氣體排放的量化分析及中國(guó)對(duì)策研究[J]. 海洋環(huán)境科學(xué)，2010(6):923-926.

[9] KALYANMOY D, AMRIT P, SAMEER A, et al. A fast and elitist multi-objective genetic algorithm NSGA-II[J]. IEEE Trans on Evolutionary Computation, 2002,6(2):182-197.

[10] 崔遜學(xué). 多目標(biāo)進(jìn)化算法及其應(yīng)用[M]. 北京：國(guó)防工業(yè)出版社，2006:45-48.