許歡，劉偉，劉詩(shī)

上海海事大學(xué)交通運(yùn)輸學(xué)院，上海 201306

◎工程與應(yīng)用◎

低碳經(jīng)濟(jì)下的港口泊位分配模型及其算法實(shí)現(xiàn)

許歡，劉偉，劉詩(shī)

上海海事大學(xué)交通運(yùn)輸學(xué)院，上海 201306

航運(yùn)公司正在進(jìn)行前所未有的努力以減少船舶的燃油消耗量及碳排放量，而港口所制定的泊位分配計(jì)劃對(duì)于船舶的油耗量和碳排放量有著直接的影響。由于船舶的到港時(shí)間是港方制定泊位分配計(jì)劃的關(guān)鍵參數(shù)，因此將船舶到港時(shí)間作為決策變量引入傳統(tǒng)的泊位分配（BAP）模型中，設(shè)計(jì)了港口與船方協(xié)調(diào)調(diào)度的新的泊位分配策略——VAT（Variable Arrival Time）策略，同時(shí)將船舶油耗和碳排放量融入BAP模型的目標(biāo)函數(shù)中，建立了船舶油耗量最小和船舶離港延遲時(shí)間最短的雙目標(biāo)優(yōu)化模型。采用多目標(biāo)遺傳算法對(duì)該模型進(jìn)行求解，并用仿真算例驗(yàn)證了該策略的有效性。計(jì)算結(jié)果表明，VAT策略可以大大削減航運(yùn)公司的燃油消耗和船舶的碳排放，同時(shí)可以提高港口的服務(wù)水平，縮短船舶在港等待時(shí)間。

低碳經(jīng)濟(jì)；泊位分配；遺傳算法；可變的到港時(shí)間（VAT）策略

1 引言

研究報(bào)告顯示，航運(yùn)業(yè)目前每年排放的二氧化碳超過(guò)12億噸，約占全球碳排放總量的4%[1]。為了減輕對(duì)環(huán)境的負(fù)面影響，在過(guò)去十年中國(guó)際社會(huì)已加強(qiáng)對(duì)于船舶排放的立法。與此同時(shí)，船用燃油價(jià)格在過(guò)去幾年中飛漲，燃油成本已成為航運(yùn)公司經(jīng)營(yíng)成本中的絕大部分。基于這兩方面的原因，航運(yùn)公司正在進(jìn)行前所未有的努力以減少船舶的燃油消耗及碳排放量，從技術(shù)上和管理層面上嘗試各種可能的措施來(lái)減少燃油消耗。例如，減緩船舶航速。目前航運(yùn)公司普遍采用低于20節(jié)的船舶經(jīng)濟(jì)航速[2]。不論是從經(jīng)濟(jì)上還是從環(huán)境上來(lái)考慮船舶油耗以及碳排放的問(wèn)題，其對(duì)于航運(yùn)公司的策略選擇的影響是深遠(yuǎn)的，包括營(yíng)銷(xiāo)策略，船舶配置及調(diào)度，航線選擇等。

船舶進(jìn)港時(shí)機(jī)的選擇及港口所制定的泊位分配計(jì)劃對(duì)于船舶的油耗量和碳排放量有著直接的影響，不論是在船舶駛近港口期間還是船舶在港停泊期間。通過(guò)采用船舶航行優(yōu)化系統(tǒng)，以及制定更好的船舶靠泊計(jì)劃，對(duì)船舶的進(jìn)港時(shí)機(jī)進(jìn)行優(yōu)化，既能縮短船舶在港口外等待進(jìn)港的時(shí)間和其在港口的周轉(zhuǎn)時(shí)間，又能減少溫室氣體的排放量。然而，現(xiàn)實(shí)的情況是船舶往往以一個(gè)較高的航速行駛至港口，港口擁堵，船舶無(wú)法靠泊，只能在錨地等待，這既增加了船舶等待期間的燃料消耗和碳排放，也增加了船舶在港口附近海域航行時(shí)的燃料消耗和碳排放。如果港口在制定泊位分配計(jì)劃時(shí)就考慮到船舶的油耗及碳排放的問(wèn)題，港口和航運(yùn)公司之間努力合作，并進(jìn)行充分的信息共享，情況就會(huì)有所改變。

船舶的到港時(shí)間是港口制定泊位分配計(jì)劃的關(guān)鍵參數(shù)，在以往的泊位分配計(jì)劃制定過(guò)程中，通常將船舶到港時(shí)間作為一個(gè)已知的參數(shù)，港口根據(jù)由船期所確定的船舶到港時(shí)間來(lái)制定泊位分配計(jì)劃。同時(shí)，港口所關(guān)注的問(wèn)題主要在于在保持客戶(hù)服務(wù)水平的情況下，盡可能減少船舶在港等待的時(shí)間和船舶在港口停泊時(shí)產(chǎn)生的碳排放，這與航運(yùn)公司所關(guān)切的整個(gè)航次的燃油消耗量以及碳排放量有所不同。低碳經(jīng)濟(jì)下的泊位分配不再將船舶到港時(shí)間看作一個(gè)已知的參數(shù)，而是作為一個(gè)決策變量，同時(shí)要求港口在掌握了即將靠泊的船舶的有關(guān)資料的基礎(chǔ)上，在綜合考慮碼頭和航運(yùn)公司所關(guān)注的問(wèn)題的情況下制定泊位分配計(jì)劃。然后，港口給即將到達(dá)的船舶發(fā)送其建議，船方根據(jù)港方的建議選擇一個(gè)合適的速度航行至港口。也就是說(shuō)，港方應(yīng)考慮到其客戶(hù)——航運(yùn)公司的效率，而不是孤立地制定其作業(yè)計(jì)劃。當(dāng)然這需要雙方之間進(jìn)行充分的信息共享，船方必須事先將船舶的基本信息（船舶長(zhǎng)度，裝載/卸載量，所要求的出發(fā)時(shí)間，距港口的距離，船舶的最大/最小航速等）向港口主動(dòng)傳達(dá)。

由以上分析可知，低碳經(jīng)濟(jì)下的泊位分配計(jì)劃應(yīng)該是港方和船方共同決策的結(jié)果，雙方合作的潛力在于協(xié)調(diào)控制駛近船舶的航速，以確定其靠港時(shí)間。這就要求船舶加速或減速航行以確定特定的裝載、卸載時(shí)段，避免港口擁堵，同時(shí)最大限度地減少船舶在港區(qū)附近航行和在港停泊期間的油耗和碳排放量，以達(dá)到港口資源和航運(yùn)企業(yè)利益與大氣環(huán)境之間的微妙平衡。這種平衡可以通過(guò)改進(jìn)傳統(tǒng)的泊位分配模型（Berth Allocation Problem，BAP）來(lái)實(shí)現(xiàn)。

2 文獻(xiàn)綜述

自20世紀(jì)90年代以來(lái)，泊位分配問(wèn)題被廣泛研究，關(guān)于其最新研究的詳細(xì)回顧，可以參考Bierwirth[3]和Meisel[4]所著文章，這里不再贅述。

在以往的文獻(xiàn)中，通常將船舶到港時(shí)間作為已知的參數(shù)來(lái)建立泊位分配模型，并且常以提高港口作業(yè)效率作為優(yōu)化目標(biāo)，如減少船舶起航延誤，縮短船舶的等待時(shí)間和在港作業(yè)時(shí)間等，而考慮到船舶油耗和碳排放問(wèn)題的文獻(xiàn)較少。Golias[5]等人于2009年認(rèn)為：在建立BAP模型時(shí)，應(yīng)將船舶到達(dá)時(shí)間作為決策變量，而不是已知的參數(shù)。他們嘗試通過(guò)減少船舶等待時(shí)間來(lái)達(dá)到減少船舶燃料消耗和碳排放的目的。然而，其目標(biāo)僅僅是減少船舶在港口停泊時(shí)的碳排放。事實(shí)上，相比于在港停泊期間，船舶在駛近港口的過(guò)程中的碳排放更多[6]，因此，應(yīng)給予更多的關(guān)注。Lang和Veenstra[7]在2010年也考慮將船舶到達(dá)時(shí)間作為決策變量，并最大限度地減少船舶駛近港口過(guò)程中的油耗。他們的研究首次對(duì)船舶燃油消耗進(jìn)行了直接的定量分析，并闡明將船舶到達(dá)時(shí)間作為決策變量引入BAP模型可以為港口運(yùn)營(yíng)商和航運(yùn)公司之間提供潛在的協(xié)調(diào)機(jī)會(huì)，這將會(huì)節(jié)省船舶在航行期間的燃油消耗。這個(gè)基本思想也被本文的研究所采用。然而，其研究無(wú)法處理船舶燃油消耗量與航速之間的非線性函數(shù)關(guān)系，他們只是簡(jiǎn)單地把非線性回歸以線性回歸來(lái)代替。此外，并沒(méi)有考慮船舶碳排放的問(wèn)題。Alvarez[8]等人在2010年進(jìn)行了有關(guān)泊位分配和船舶航速控制的混合優(yōu)化問(wèn)題的研究，并開(kāi)發(fā)了一個(gè)離散事件仿真工具，提出了既能節(jié)省燃料又能提高港口生產(chǎn)率的新泊位分配策略。通過(guò)將船舶航速的可行域離散化，避開(kāi)了燃油消耗與航速之間的非線性關(guān)系，但這種離散化方法可能會(huì)使計(jì)算不夠精確。此外，也沒(méi)有考慮船舶碳排放的問(wèn)題。本文將船舶到達(dá)時(shí)間作為決策變量引入BAP模型中，同時(shí)將船舶油耗和碳排放量融入BAP模型的目標(biāo)函數(shù)，試圖彌補(bǔ)此項(xiàng)空白。

3 模型建立

3.1 傳統(tǒng)的泊位分配模型

在傳統(tǒng)的泊位分配（BAP）模型中，船舶隨著時(shí)間的推移不斷到達(dá)港口，港口計(jì)劃人員為每艘船舶分配岸線泊位和靠泊時(shí)間，以使船舶能夠盡快駛離碼頭。

模型參數(shù)：

V為到港船舶集合（包含n艘船舶）；L為岸線長(zhǎng)度；ai為船舶i的到港時(shí)間；li為船舶i的船長(zhǎng)（考慮了船舶靠泊的安全距離）；hi為船舶i的作業(yè)時(shí)間；M為一個(gè)足夠大的常數(shù)。

決策變量：

xi為船舶i的靠泊位置；yi為船舶i的靠泊時(shí)間。

輔助決策變量：

σ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。

傳統(tǒng)的泊位分配模型[9]如下：

在這個(gè)模型中，目標(biāo)函數(shù)式（1）是最小化船舶平均在港時(shí)間，它是衡量集裝箱碼頭服務(wù)水平的一個(gè)具有代表性的指標(biāo)，也是碼頭作業(yè)計(jì)劃制定者經(jīng)常采用的決策目標(biāo)；約束條件式（2）保證所有船舶都在給定岸線內(nèi)靠泊；約束條件式（3）～（5）保證任意兩艘船舶在占用碼頭岸線和在港作業(yè)時(shí)間上不相互重疊；約束條件式（6）表明船舶只有到港后才能靠泊；約束條件式（7）定義了從屬變量。

值得注意的是，在這個(gè)傳統(tǒng)的BAP模型中，碼頭作業(yè)計(jì)劃制定者是根據(jù)船舶的預(yù)計(jì)抵達(dá)時(shí)間來(lái)分配船舶靠泊位置和靠泊時(shí)間的，也就是說(shuō)，碼頭作業(yè)計(jì)劃制定者把每艘船舶的到達(dá)時(shí)間看成是一個(gè)已知的恒定的參數(shù)。把這個(gè)泊位分配策略稱(chēng)為CAT（Constant Arrival Time）策略。然而，把船舶到港時(shí)間作為決策變量，將為優(yōu)化船舶燃料消耗和減少碳排放提供可能。這個(gè)新的泊位分配策略可以稱(chēng)之為VAT（Variable Arrival Time）策略。在VAT策略中，把船舶的燃料消耗量和碳排放量融入BAP模型的目標(biāo)函數(shù)中進(jìn)行優(yōu)化。

3.2 低碳經(jīng)濟(jì)下的泊位分配模型

下面勾勒出VAT策略的基本思路，并將船舶油耗和碳排放融入BAP模型的目標(biāo)函數(shù)。一般來(lái)說(shuō)，對(duì)于船舶i，航運(yùn)公司可以通過(guò)調(diào)整其航速來(lái)控制其到達(dá)港口的時(shí)間，即把a(bǔ)i作為決策變量，而不再將其看成恒定的參數(shù)。ai的取值應(yīng)介于[aˉi]，和aˉi分別由船舶的最高航速和最低航速確定。

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

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

由于船舶到港時(shí)間ai成為決策變量，而不再是恒定不變的參數(shù)，因此原目標(biāo)函數(shù)值可以通過(guò)調(diào)整ai和yi的取值而實(shí)現(xiàn)最小化。然而必須要考慮的一個(gè)問(wèn)題是，船舶通過(guò)改變其靠近港口時(shí)的航行速度來(lái)控制其到港時(shí)間，雖然可以最小化其等待時(shí)間及在港作業(yè)時(shí)間，但是會(huì)影響到其離港時(shí)間，進(jìn)而影響到船期。為防止出現(xiàn)所有船舶都以最低航速駛近港口進(jìn)而減少燃料消耗和碳排放，并同時(shí)縮短在港作業(yè)時(shí)間的優(yōu)化結(jié)果，需對(duì)原目標(biāo)函數(shù)進(jìn)行改進(jìn)，即將船舶平均在港作業(yè)時(shí)間最小化的目標(biāo)函數(shù)修改為船舶平均離港延遲時(shí)間最小化。

用di表示船舶預(yù)計(jì)離港時(shí)間，原目標(biāo)函數(shù)修改為：

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

目標(biāo)函數(shù)式（11）為最小化船舶駛近港口期間的燃油消耗。由于船舶二氧化碳排放量與用油量成正比，因此該目標(biāo)與最小化船舶航行期間的碳排放量是一致的。船舶二氧化碳排放量與用油量之間的比例系數(shù)在各文獻(xiàn)中有微小差別，本文采用政府間氣候變化專(zhuān)門(mén)委員會(huì)（Intergovernmental Panel on Climate Change，IPCC）的比例，即一噸船用油的燃燒產(chǎn)生3.17噸的二氧化碳[11]。目標(biāo)函數(shù)式（12）為最小化船舶平均離港延遲時(shí)間，這個(gè)時(shí)間也可作為港口服務(wù)水平的一個(gè)衡量指標(biāo)。

4 基于遺傳算法的低碳經(jīng)濟(jì)下的泊位分配模型求解

不包括約束條件式（19），該模型由5n2/2+n/2個(gè)約束條件和2n2+n個(gè)變量組成，其中2n2-2n個(gè)變量是二進(jìn)制的。同時(shí)，目標(biāo)函數(shù)f1和f2都是非線性的，這給用分支定界法來(lái)求解模型帶來(lái)了極大的挑戰(zhàn)。考慮到研究模型與約束條件的復(fù)雜性，本文采用了一種模擬生物進(jìn)化機(jī)制的智能隨機(jī)優(yōu)化算法——遺傳算法。遺傳算法屬于進(jìn)化類(lèi)優(yōu)化算法的一種，是一種啟發(fā)式算法，它把自然遺傳機(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)解[12]。遺傳算法因其優(yōu)化性能在多目標(biāo)優(yōu)化問(wèn)題中有較為廣泛的應(yīng)用[13-14]。

本文結(jié)合具體問(wèn)題對(duì)傳統(tǒng)的遺傳算法進(jìn)行了改進(jìn)，具體求解步驟如下。

4.1 染色體編碼

在前述泊位分配優(yōu)化模型中有三個(gè)決策變量x、y、a，其中變量a為船舶的到港時(shí)間，其取值與決策變量y

圖1 染色體的基因表述

4.2 種群初始化

為保證多樣性，采用隨機(jī)生成初始種群的方法。假設(shè)種群的大小為M，在算法開(kāi)始時(shí)隨機(jī)生成M條染色體。每條染色體有兩條子染色體，見(jiàn)圖1中的染色體編碼。子染色體1根據(jù)船舶的數(shù)量隨機(jī)生成排序序列；子染色體2，在滿(mǎn)足式（17）及式（18）的情況下，隨機(jī)生成靠泊時(shí)間。

4.3 目標(biāo)函數(shù)值計(jì)算

對(duì)于給定的任一染色體個(gè)體，包含兩條子染色體，即船舶服務(wù)序列和船舶靠泊時(shí)間。通過(guò)染色體個(gè)體變量可以求解出對(duì)應(yīng)的從屬變量，進(jìn)而計(jì)算出對(duì)應(yīng)的目標(biāo)函數(shù)值fk，k∈{1，2}，將其作為各個(gè)體的適應(yīng)度值。

4.4 交叉操作

交叉操作是以隨機(jī)的方式將種群個(gè)體的信息在種群成員之間進(jìn)行交換，從而產(chǎn)生新的染色體，增加種群的多樣性。交叉操作的方式很多，采用何種方式需要根據(jù)染色體的編碼形式。由于本文在一個(gè)染色體中，采用了兩種不同的編碼形式，因此相應(yīng)地采用了兩種不同的方式進(jìn)行交叉操作。

對(duì)于子染色體1，采用的是整數(shù)的編碼形式，在交叉時(shí)采用兩點(diǎn)交叉的方式。如果交叉后得到的子代不可行，即不同船舶存在相同的靠泊順序，則需要進(jìn)一步采取交換策略和調(diào)整策略。圖2以6艘船舶的交叉操作為例，A、B為父代，交叉后得到中間代C1、D1。查看C1可知，船舶1和船舶3的靠泊順序重復(fù)，為保證船舶靠泊順序是個(gè)排序序列，即不重復(fù)，需要對(duì)重復(fù)的位置進(jìn)行交換。為保存交叉操作的成果，在交換策略中，交叉區(qū)域的基因不進(jìn)行變化，僅僅變換交叉區(qū)域外的基因。交換策略共分為三步：（1）從左至右查找C1交叉區(qū)域內(nèi)出現(xiàn)過(guò)兩次的靠泊順序編號(hào)（如順序1），并找到D1內(nèi)對(duì)應(yīng)基因位置的靠泊順序編號(hào)（如順序4）；（2）在C1交叉區(qū)域外找到順序1對(duì)應(yīng)的船舶決策變量，在D1交叉區(qū)域外找到靠泊順序4對(duì)應(yīng)的船舶決策變量，兩者進(jìn)行交換；（3）重復(fù)（1）、（2）直至交叉區(qū)域查找完畢。交換操作所得結(jié)果還可能出現(xiàn)不滿(mǎn)足約束條件式（18）的情況，則需要進(jìn)行調(diào)整。調(diào)整策略的規(guī)則是把不符合約束條件的船舶服務(wù)時(shí)間用可行的船舶服務(wù)時(shí)間進(jìn)行替換，即人為縮小搜索空間以避免多余的交換，最終可確定父代A、B的子代為C、D。

圖2 子染色體1的兩點(diǎn)交叉操作

對(duì)于子染色體2，采用的是小數(shù)的編碼形式，采用正交交叉的方式進(jìn)行交叉操作。設(shè)參與重組的Q個(gè)父代個(gè)體為p1，p2，…，pQ，其中pi=(pi1，pi2，…，piN)且i∈{1，2，…，Q}，其正交交叉操作具體步驟如下：將每一個(gè)參與重組的父代個(gè)體看作是正交交叉操作的一個(gè)水平，即N水平；然后將每一個(gè)父代個(gè)體分成F個(gè)片段，每個(gè)片段作為正交交叉操作的一個(gè)因素，即F個(gè)因素。這樣就將Q個(gè)父代個(gè)體的重組問(wèn)題轉(zhuǎn)化為Q水平、F因素的交叉問(wèn)題，最后構(gòu)造正交表LM(QF)，進(jìn)行正交交叉操作產(chǎn)生M個(gè)子代個(gè)體。圖3顯示了子染色體2的正交交叉操作過(guò)程（以Q=3，M=9，F(xiàn)=3為例），其具體交叉過(guò)程見(jiàn)參考文獻(xiàn)[15]，這里不再贅述。

圖3 子染色體2的正交交叉操作

4.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è)滿(mǎn)足式（18）的隨機(jī)數(shù)，用其取代當(dāng)前位置上的基因信息。

4.6 選擇操作

選取當(dāng)前種群中的所有個(gè)體，包括交叉后的新個(gè)體，變異后的新個(gè)體，進(jìn)行4.3節(jié)中的目標(biāo)函數(shù)值計(jì)算，即計(jì)算每個(gè)染色體個(gè)體的適應(yīng)度值fk，k∈{1，2}。然后根據(jù)適應(yīng)度值對(duì)當(dāng)前群體進(jìn)行升序排序，即把適應(yīng)度值fk，k∈{1，2}比較小的排在前面，適應(yīng)度值fk，k∈{1，2}比較大的排在后面，最后從種群中選出排在前面的M個(gè)個(gè)體，作為下一代的新種群。

4.7 終止準(zhǔn)則

以進(jìn)化代數(shù)作為終止判斷條件，如果進(jìn)化代數(shù)小于設(shè)定值，則返回到步驟4.3；否則輸出結(jié)果。

5 仿真計(jì)算與分析

5.1 數(shù)據(jù)

本文使用寧波市某著名的國(guó)際集裝箱碼頭的實(shí)際數(shù)據(jù)進(jìn)行研究。其碼頭岸線長(zhǎng)L=1 600 m，以此集裝箱碼頭2011年7月14日到港船舶的信息數(shù)據(jù)為例，具體數(shù)據(jù)見(jiàn)表1。

5.2 CAT策略下的泊位分配方案

按照傳統(tǒng)的泊位分配模型，即采用CAT策略，得到的泊位分配方案如圖4所示。其求解過(guò)程可參照文獻(xiàn)[16]，這里不再贅述，而是直接給出求解結(jié)果。

經(jīng)計(jì)算可得，在CAT策略下，各船舶從零時(shí)開(kāi)始至其到達(dá)碼頭期間的燃油消耗總和為=763 t，排放的二氧化碳總量為2 418.8 t，船舶平均在港時(shí)間為7 h，17艘船舶總共等待時(shí)間為其中第6、 10、11、12、13、15、16、17號(hào)船舶的等待時(shí)間分別為4、1、5、3、5、1、1、2 h，其余船舶的等待時(shí)間為0。各船舶的離港延遲時(shí)間均為0，即=0。

表1 到港船舶數(shù)據(jù)

圖4 CAT策略下的泊位方案示意圖

5.3 VAT策略下的泊位分配方案

取零時(shí)作為碼頭泊位分配計(jì)劃開(kāi)始的時(shí)刻，不考慮計(jì)劃期前靠泊的船舶，根據(jù)各船舶目前所采用的航速及其最高、最低航速，可以計(jì)算出各船舶在碼頭泊位分配計(jì)劃開(kāi)始時(shí)刻與碼頭的距離mi(nmile)及各船舶的最快到港時(shí)間和最慢到港時(shí)間，如表2所示。

本文采用C#語(yǔ)言編寫(xiě)算法程序，運(yùn)行機(jī)器配置為Pentium D CPU 2.80 GHz。通過(guò)實(shí)驗(yàn)確定多目標(biāo)遺傳算法各參數(shù)如下：種群大小pop=40；遺傳迭代次數(shù)G= 1 024；交叉概率Pc=0.8，變異概率Pm=0.1，所耗時(shí)間為1 min 7 s。通過(guò)前述優(yōu)化算法，將相關(guān)數(shù)據(jù)輸入所編程序，能求得低碳經(jīng)濟(jì)下泊位分配模型的多個(gè)Pareto最優(yōu)解，即Pareto最優(yōu)解集，如表3所示（由于篇幅限制只隨機(jī)地列出六種方案）。

表2 零時(shí)刻各船舶與碼頭的距離mi及最快、最慢到港時(shí)間

由表3后兩列的對(duì)比結(jié)果可知，VAT策略在減少燃油消耗、減排二氧化碳這一目標(biāo)上明顯優(yōu)于CAT策略；同時(shí)VAT策略可以減少船舶等待作業(yè)的時(shí)間，進(jìn)而減少船舶平均在港時(shí)間。但VAT策略在目標(biāo)二上劣于CAT策略，即船舶的平均離港延遲時(shí)間在VAT策略下多于CAT策略。船舶平均離港延遲時(shí)間越長(zhǎng)，節(jié)省的燃油量越多。對(duì)于同一個(gè)Pareto最優(yōu)解，目標(biāo)一的優(yōu)化程度要明顯高于目標(biāo)二的被影響程度。綜合考慮，VAT策略既能提高港口的服務(wù)水平（船舶平均在港時(shí)間縮短），又能減少船舶的燃料消耗和碳排放，在目前的高油價(jià)下，為船公司節(jié)省了大量的燃油成本，即既有經(jīng)濟(jì)效益又有環(huán)境效益，并且對(duì)各方都有益?；蛘哒f(shuō)，VAT策略從不同程度上平衡了兩個(gè)相互矛盾的目標(biāo)，能獲得更大的綜合效益。

表3 Pareto最優(yōu)解集

VAT策略的另一個(gè)好處是碼頭作業(yè)計(jì)劃制定者可以在船舶離港延遲最小化和燃油消耗最小化這兩個(gè)目標(biāo)之間進(jìn)行權(quán)衡，根據(jù)實(shí)際情況選擇合適的方案。并且對(duì)于每種方案，所編寫(xiě)的算法程序都可以導(dǎo)出對(duì)應(yīng)的變量取值EXCEL表和泊位分配甘特圖，這里由于篇幅的限制，沒(méi)有具體列出。

6 結(jié)論

本文將船舶到港時(shí)間作為決策變量引入BAP模型中，設(shè)計(jì)了港口與船方協(xié)調(diào)調(diào)度的新的泊位分配策略——VAT（Variable Arrival Time）策略，同時(shí)將船舶油耗和碳排放量融入BAP模型的目標(biāo)函數(shù)中，建立了船舶油耗量最小和船舶離港延遲時(shí)間最短的雙目標(biāo)優(yōu)化模型。采用多目標(biāo)遺傳算法對(duì)該模型進(jìn)行求解，并用仿真算例驗(yàn)證了該策略的有效性。研究結(jié)果表明，VAT策略可以大大削減船舶的燃油消耗和碳排放量，同時(shí)可以提高港口的服務(wù)水平，縮短船舶在港等待時(shí)間。換句話說(shuō)，VAT策略，建立了一個(gè)協(xié)調(diào)機(jī)制，它可以為港口和航運(yùn)公司帶來(lái)雙贏的經(jīng)濟(jì)效益和環(huán)境效益。必須指出的是，港口與航運(yùn)公司之間的信息共享是實(shí)施VAT策略的先決條件。

VAT策略也有一定的局限性。首先，在這項(xiàng)研究中，沒(méi)有考慮碼頭裝卸機(jī)械的分配，它會(huì)對(duì)船舶在港作業(yè)時(shí)間和等待作業(yè)時(shí)間產(chǎn)生影響。第二，雖然船舶在航行時(shí)的廢氣排放量相對(duì)于在港口停泊時(shí)的排放量來(lái)說(shuō)更多，但是后者是一個(gè)比較敏感的話題，并受到廣泛的關(guān)注。因?yàn)榇霸谕２雌陂g其輔機(jī)所產(chǎn)生的廢氣是港口污染物的主要來(lái)源。船舶排放物如氮氧化物（NOx），硫氧化物（SOx）和顆粒物（PM）等，造成了港區(qū)大氣環(huán)境的惡化，甚至對(duì)港口城市和沿海社區(qū)居民的健康產(chǎn)生了巨大且明顯的影響。該模型僅考慮了船舶在駛近港口期間的油耗和碳排放，而船舶在港停泊期間產(chǎn)生的碳排放沒(méi)有考慮在內(nèi)。第三，沒(méi)有考慮連續(xù)的動(dòng)態(tài)泊位分配問(wèn)題。船舶靠泊港口是一個(gè)連續(xù)的動(dòng)態(tài)的過(guò)程，但本文僅考慮了一個(gè)時(shí)間段內(nèi)的靜態(tài)泊位分配問(wèn)題。最后，該模型只考慮了一個(gè)碼頭及其客戶(hù)，而實(shí)際問(wèn)題可能會(huì)延伸到多個(gè)碼頭，甚至涉及多個(gè)港口。克服這些限制，并優(yōu)化模型將是未來(lái)進(jìn)一步的研究方向。

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

[2]劉寶亮.減速航行正在成為航運(yùn)業(yè)趨勢(shì)[J].中國(guó)船檢，2008（10）：60-61.

[3]Bierwirth C，Meisel F.A survey of berth allocation and quay crane scheduling problems in container terminals[J]. Eur J Oper Res，2010，202（3）：615-627.

[4]Meisel F，Bierwirth C.Heuristics for the integration of crane productivity in the berth allocation problem[J].Transport Res E-Logist Transport，2009，45（1）：196-209.

[5]Golias M M，Saharidis G K，Boile M，et al.The berth allocation problem：optimizing vessel arrival time[J].Marit Econom Logist，2009，11（4）：358-377.

[6]Schrooten L，De Vlleger I，Panis L I，et al.Inventory and forecasting of maritime emissions in the Belgian sea territory，an activity-based emission model[J].Atmos Environ，2008，42（4）：667-676.

[7]Lang N，Veenstra A.A quantitative analysis of container vessel arrival planning strategies[J].OR Spectrum，2010，32（3）：477-499.

[8]Alvarez J F，Longva T，Engebrethsen E S.A methodology to assess vessel berthing and speed optimization policies[J]. Marit Econom Logist，2010，12（4）：327-346.

[9]楊春霞，王諾，楊華龍.集裝箱碼頭泊位——岸橋分配耦合優(yōu)化[J].計(jì)算機(jī)集成制造系統(tǒng)，2011（10）：2270-2277.

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

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

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

[13]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.

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

[15]蔡自興，江中央，王勇，等.一種新的基于正交實(shí)驗(yàn)設(shè)計(jì)的約束優(yōu)化進(jìn)化算法[J].計(jì)算機(jī)學(xué)報(bào)，2010（5）：855-864.

[16]樂(lè)美龍，劉菲.基于Memetic算法的泊位和岸橋分配問(wèn)題[J].武漢理工大學(xué)學(xué)報(bào)，2011，33（11）：66-71.

XU Huan,LIU Wei,LIU Shi

College of Transport&Communications,Shanghai Maritime University,Shanghai 201306,China

Shipping companies are making an unprecedented effort to reduce fuel consumption and carbon emissions during the voyage,which are directly effected by port’s berth allocation plan.Considering the ship’s arrival time is a key parameter in the formulation of berth allocation plan for ports,this paper introduces the ship’s arrival time into the traditional BAP（Berth Allocation Problem）model as a decision variable,designs a new berth allocation strategy—VAT（Variable Arrival Time）strategy,which is based on the coordination between the ports and the ship operators,blends the fuel consumption and carbon emission in the BAP model’s target function and builds bi-objective（minimizing fuel consumption and departure delay time）optimization model,uses MOGA（Multi-Objective Genetic Algorithms）to solve the model and validates the strategy by a simulation example.The calculation indicates that VAT strategy can reduce shipping companies’fuel consumption and carbon emission greatly.At the same time,it can also improve the service level of the ports and cut down the waiting time of the ships.

low-carbon economy;berth allocation plan;genetic algorithm;Variable Arrival Time（VAT）strategy

A

F550.62；U691+.3

10.3778/j.issn.1002-8331.1210-0283

XU Huan,LIU Wei,LIU Shi.Berth allocation model under low-carbon economy and its algorithms implementation. Computer Engineering and Applications,2014,50（6）：219-225.

國(guó)家自然科學(xué)基金（No.71272219）；上海市科學(xué)技術(shù)委員會(huì)科研計(jì)劃項(xiàng)目（No.11510501800）；上海海事大學(xué)研究生創(chuàng)新能力培養(yǎng)專(zhuān)項(xiàng)基金資助項(xiàng)目（No.YC2010030）。

許歡（1981—），女，博士研究生，講師，研究領(lǐng)域?yàn)閲?guó)際航運(yùn)現(xiàn)代化管理；劉偉（1954—），男，博士，教授，研究領(lǐng)域?yàn)槲锪飨到y(tǒng)規(guī)劃與設(shè)計(jì)；劉詩(shī)（1989—），男，碩士研究生，研究領(lǐng)域?yàn)閲?guó)際航運(yùn)現(xiàn)代化管理。E-mail：lovely_xuhuan@163.com

2012-10-29

2013-01-08

1002-8331（2014）06-0219-07

CNKI網(wǎng)絡(luò)優(yōu)先出版：2013-01-18，http://www.cnki.net/kcms/detail/11.2127.TP.20130118.1024.001.html