王致遠(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 引 言

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

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

1 模型建立

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

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

設(shè)V：到港船舶集合（包含n艘船舶）；L：岸線長度；li：船舶的船長（考慮了船舶靠泊的安全距離）；hi：船舶i的作業(yè)時間；xi：靠泊位置；M：一個足夠大的常數(shù)。決策變量：yi：船舶的靠泊時間。ai：船舶i的到港時間，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è)泊位分配計劃從零時刻開始，此時船舶距離港口mi（海里）。由趙剛的《國際航運管理》[4]，船舶i每航行天的燃油消耗fi與所采用的航速vi之間的函數(shù)關(guān)系可以用式（1） 表示。

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

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

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

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

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

2 模型求解

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

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

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

表1 染色體的基因表述

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

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

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

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

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

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

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

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

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

表2 染色體的基因表述

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

3 試驗算例

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

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

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

4 結(jié) 論

本文將船舶到港時間作為決策變量引入傳統(tǒng)泊位分配模型中，同時將船舶油耗和碳排放量融入傳統(tǒng)泊位分配模型的目標(biāo)函數(shù)中，建立了船舶油耗最小和船舶離港延遲時間最短的雙目標(biāo)優(yōu)化模型，并且加入岸橋分配模型，使得港口整體優(yōu)化，在滿足能夠完成船舶裝卸任務(wù)的情況下，避免不必要的岸橋分配，提高港口的工作效率。然而研究仍然存在很多的局限性，首先，沒有考慮船舶在港停泊時的排放量問題；其次，模型只考慮了一個碼頭及其客戶，而實際問題可能會延伸到涉及多個碼頭，甚至多個港口?？朔@些限制，并優(yōu)化模型將是未來進(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ì)對我國海運業(yè)的影響及應(yīng)對措施[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)用與軟件實現(xiàn)[M]. 西安：西安交通大學(xué)出版社，2002:78-79.

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

[8] 王海峰，白佳玉. 國際海運溫室氣體排放的量化分析及中國對策研究[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]. 北京：國防工業(yè)出版社，2006:45-48.