考慮船舶碳排放的集裝箱船舶進港靠泊調度問題研究

曾慶光，董明望，辜 勇

（武漢理工大學，湖北 武漢 430063）

1 引言

溫室氣體排放引起全球變暖，作為其最主要的發生來源，二氧化碳成為環境領域關注的重點。預計到2050年，航運業碳排放量將達到18%。考慮低碳因素，對港口內部機械作業流程優化，尋求港口資源的合理配置，對于實行節能減排、發展綠色港口航運、提升港口群整體的競爭力等具有重要價值[1]。

許歡等以船舶到港時間作為決策變量，區別于傳統的泊位分配問題，提出基于港口與船方協調調度的新的泊位分配策略（Variable Arrival Time，VAT），以船舶油耗量最小和船舶離港延遲時間最短為目標函數，建立了雙目標優化模型[2]；韓曉龍等分別建立了船舶到港時間可變（VAT）和到港時間固定策略（CAT）下的泊位—岸橋聯合調度模型，以最小化船舶延遲離港時間、航行油耗和整個碼頭碳排放為目標進行多方面多層次對比分析，VAT相較于CAT，不僅可保證船舶的服務水平。而且還可以大幅度減少船公司航行油耗和整個碼頭的碳排放[3]；靳玉基于船舶的偏好停泊泊位，考慮碳排放成本對碼頭作業的影響，以提升碼頭服務質量和降低碼頭作業成本兩方面為目標，建立泊位岸橋聯合配置多目標優化模型，并運用改進的自適應遺傳算法求解[4]；王旭等以最小化船舶碳排放和平均延遲時間為目標，考慮到港時間不確定性和集卡運輸能力受限等約束，建立多目標非線性混合整數規劃模型，采用高效非支配排序的遺傳算法求解[5]；彭云等通過系統仿真的方法計算出船舶、岸橋、集卡等碳排放量，結果顯示船舶的總排放占比80%，且港內航行占50%左右[6]。

本文研究基于船舶碳排放最小的集裝箱碼頭調度問題，先對船舶計劃到港時間進行有效預測，形成合理的船舶到港時間統計表。考慮船舶船長、集裝箱裝卸量、連續型泊位分配情況、岸橋分配調度過程約束等條件，建立以船舶在港時間最小化和船舶港內油耗最小為目標的雙目標函數模型，在此基礎上，進一步考慮船舶到港時間可協調情況下的作業調度計劃，并用遺傳算法求解該模型，進而比較不同策略下船舶港內油耗情況，為降低船舶港內排放提供理論基礎。

2 船舶進港靠泊作業調度問題分析

2.1 船舶進港排放分析

船舶作為港口內主要的排放源，其中港內航行的排放占到船舶總排放的60%—80%，航行時船舶的主機和輔機一同運轉，主機功率通常為輔機十幾倍，因此，港內航行的排放占據較大部分，而船舶除外的集卡、岸橋和場橋，加起來僅僅占到20%—30%，從能耗上來看，船舶依然是能耗主體，根據以上描述，船舶航行時，主機與輔機同時運轉，其油耗見式（1）。

根據式（1）可知，選取天津港某段時間的15艘船，具體數據見表1，假設為單輔機作業，航行距離設置為30海里，通過Matlab編寫函數尋優，繪制油耗和航速之間的關系，如圖1所示，該船舶的最佳航速約為11.3節，油耗約為3 411.2kg，而以航速為30節行駛時，油耗量可達到7 500kg以上，由此可見，以經濟航速可以大幅度減少油耗。

表1 某港口入港船舶信息表

圖1 船舶1航速與油耗關系分布圖

2.2 泊位分配和裝箱理論

連續泊位問題是指無固定泊位，船舶可根據實際岸線和與其他船舶的約束，在任意岸線坐標上靠泊，該問題就如同裝箱問題。鑒于連續型泊位不僅提高泊位利用率，還可以減少船舶總在港時間，本文采用連續型泊位分配。圖2表示15艘船的連續型泊位動態作業調度，在不考慮岸橋數量分配和調取情況下而衍生出二維裝箱問題，橫軸表示岸線固定長度，以50m為一個船區進行劃分，分為30個船區，縱軸表示時間維度，圖中N1—N15表示15艘船舶的作業計劃，根據二維矩形的長度大致判斷其作業時間段和所在岸線的坐標。

圖2 船舶靠泊問題裝箱圖

裝箱問題是一種復雜的離散組合優化問題，也是一種NP-Hard問題。裝箱問題是隨著計算機技術而產生的，可應用于汽車、造船、貨物裝載和大規模集成電路等行業，也應用于運籌學、人工智能等領域，在物流生產領域中，集裝箱的配載問題較為明顯。

2.3 船舶作業與岸橋分配調度

岸橋作為集裝箱碼頭岸邊作業系統中實現集裝箱垂直和水平位移的機械作業工具，是泊位之外的另一項核心資源。通常岸橋數量的確定由岸線長度來決定，船舶進入港汊內，成功靠泊并完成相關準備作業工作后，岸橋開始對船舶上的集裝箱進行裝卸操作。分配給某船舶的岸橋數量對作業時間影響很大，通常需要考慮船舶集裝箱貝位數量以及不同岸橋作業人員的裝卸技能指數，有時某些岸橋在作業中途出現故障，甚至無法行動，那么該岸橋下的貝位集裝箱無法作業，將會導致該船舶因為該貝位區域未完成作業而大大延期，如果嘗試船舶沿岸線進行泊位移動，將會增加船舶本身與岸線之間碰撞的可能性而帶來安全隱患，因此，船舶通常不進行移動泊位。

3 作業調度模型建立

3.1 船舶到港時間固定調度模型

模型假設：

（1）每艘船到港時間可提前預知；

（2）船舶港內行駛航速滿足最大最小值約束；

（3）每艘船舶有且僅有一次停泊機會，并且停泊后坐標不能改變；

（4）每艘船的岸橋作業數量滿足其約束；

（5）不考慮潮汐對船舶吃水深度的約束；

（6）不考慮其他類型船舶和集裝箱船舶的避讓影響；

（7）船舶作業完畢后，按照經濟航速進行行駛，不計入排放范圍；

（8）集卡數量充足且能夠完全配合岸橋實現堆場轉運；

（9）船舶到港時間為船舶從港外水域到達錨地時間，入港時間是從錨地出發向港內水域行駛時的時間。

使用數學符號如下：

V ：到港船舶集合（i=1，2，…，N）；T ：作業最大期限；ATi：船舶i預計到港時間；LVi：船舶i的長度；Ci：船舶i的集裝箱裝卸量；vi：船舶i錨地至泊位航速；QZ：碼頭岸橋總數；BL：泊位總長度；F：船舶在港總油耗；LD：錨地至泊位航線路程；F1i：船舶i主機在港油耗；F2i：船舶i輔機在港油耗：船舶i岸橋作業數量上限；：船舶i岸橋作業數量下限；qv：單個岸橋裝卸速度；M：足夠大的整數；T2i：船舶作業完畢離泊時間；TDi：船舶錨地等待時間。

決策變量：

TVi：船舶i的靠泊時間；ZVi：船舶i的靠泊岸線坐標；Wi：船舶i的裝卸作業時間；qi：船舶i的實際分配岸橋數。

式（3）表示船舶總靠泊作業時間最小；式（4）表示船舶總油耗最小；式（5）和式（6）分別表示船舶靠泊作業過程中主機和輔機的油耗；式（7）表示船舶從錨地至泊位港內航行時段的航速范圍；式（8）表示靠泊坐標的約束范圍；式（9）表示靠泊時間與到港時間的約束關系；式（10）表示每艘船的作業調度岸橋數的約束范圍；式（11）—式（13）表示任意兩艘船之間存在的時間空間上的約束關系；式（14）表示遍歷任意時刻的岸橋數總和不超過總岸橋數；式（15）表示作業時間與作業量、岸橋數量、岸橋裝卸速度的關系；式（16）與（17）表示選取的判定因子為0-1變量；式（18）表示裝卸作業時間與靠泊時間、離開泊位時間的關系。

3.2 到港時間可協調機制下的作業調度模型

針對船舶到港時間可協調情況下的作業調度問題，其決策變量新增船舶到港時間，目標函數新增船舶離港延遲時間，新增數學符號：LTi：船舶i預計離港時間（完成裝卸作業后立刻離開的時刻）。

決策變量：

ASTi：船舶i協調機制下的到港時間；TVi：船舶i的靠泊時間；ZVi：船舶i的靠泊岸線坐標；Wi：船舶i的裝卸作業時間；qi：船舶i的實際分配岸橋數

到港時間可協調情況下的建模與非協調機制下的建模大體相似，只需要將式（19）替換式（3），式（20）替換式（6），式（21）替換式（9）。

當目標函數為船舶離港延遲時間時，目標函數見式（22），其中單個船舶離港延遲時間為見式（23）。

4 算法流程

4.1 主流程

遺傳算法一般流程是生成初始種群、參數初始化，而經過種群中個體的選擇交叉變異之后得到新的種群，但是基于船舶作業調度問題，一方面需要規則修復算子，另一方面針對多目標問題，利用快速非支配排序，對多種群中個體進行有效排序，而保留優勢個體。

Step1 初始化參數：將種群初始規模定義為PopSize，種群遺傳代數為Gen，初始種群序列Fi=Φ，擁擠度為Cd，生成隨機初始種群Pop。

Step2 修復算子：初始種群采取隨機生成，極可能產生不可行解，對其進行規則修復。

Step3 合并算子：父代與子代進行合并，形成待排序種群集合PopN，計算PopN中每個個體的目標函數值minT、F。

Step4 快速非支配排序：根據步驟3中的雙目標函數求解，對PopN中個體先計算其目標值，再進行快速非支配排序并生成新的序列Fi（i=1,2,…,L），提取較為合適的個體組成新的種群。

Step5 交叉算子：對Pop中一部分個體兩兩配對，針對兩個個體對應的等位基因進行交叉操作得到Pop’。

Step6 變異算子：對Pop中交叉之外的另一部分個體進行變異操作得到Pop”，然后再將Pop’與Pop”合并為子代MergePop，并且再次通過修復算子對待定解進行規則修復。

Step7 快速非支配排序及計算擁擠度：對MergePop再次進行非支配排序生成新序列F，并計算種群F中每個個體擁擠度Cd。

Step8生成子代：以MergePop中Fi（i=1,2,…,L）和Cd為基礎，提取排序在前Popsize的個體，生成新一代種群數為Pop Size的種群Pop。

Step9 判斷終止條件：若未達到迭代代數Gen，轉到步驟3，否則終止算法得到最優解。

4.2 規則修復算子

針對類似裝箱問題求解過程中存在不可行解，即兩條船之間出現時間或者空間上的沖突，當沖突存在時，啟動適當的調整程序，即規則修復算子，步驟如下：

Step1 檢查靠泊時間是否滿足式（9），如果不滿足，將船舶靠泊時間改為在約束的時間范圍中取隨機整數，檢查靠泊坐標是否滿足式（8），如果不滿足，將靠泊坐標改為船區約束范圍內的隨機整數，檢查分配的岸橋數是否滿足式（10），若不滿足，取某船岸橋約束范圍內的隨機整數。

Step2 檢查遍歷任意整數時刻的裝卸作業岸橋數量是否超過最大限度QZ，即式（14），若不滿足TVi=TVi+1，直到滿足總岸橋數量約束為止。

Step3 檢查分配完畢的船舶是否滿足式（11）—（13），若不滿足，則令ZVi=ZVi+1，直到找到可行的靠泊位置，若到岸線終點依然不滿足，則TVi=TVi+1 。

Step4 如果步驟3中出現TVi=TVi+1，之后立刻通過步驟2檢查分配的岸橋數是否滿足式（14），如果不滿足式（14），TVi=TVi+1，直到滿足為止。

Step5 檢查完所有船舶后，條件滿足，修復結束。

4.3 NSGA-II

1995年，Srinivas和Deb提出了非支配排序遺傳算法（Non-dominated Sorting Genetic Algorithms，NSGA）。這是一種基于Pareto最優概念的遺傳算法，NSGA與簡單的遺傳算法的主要區別在于選擇算子執行之前根據個體之間的支配關系進行了分層。

NSGA-II對第一代算法中非支配排序方法進行了改進：對于每個個體i都設有以下兩個參數n(i)和S(i)，n(i)為在種群中支配個體i的解個體的數量（別的解支配個體i的數量），S(i)為被個體i所支配的解個體的集合（個體i支配別的解的集合）。

（1）首先，找到種群中所有n(i)=0的個體（種群中所有不被其他個體支配的個體i），將它們存入當前集合F(1)（種群中所有未被其他解支配的個體）

（2）然后對于當前集合F(1)中的每個個體j，考察它所支配的個體集S(j)，將集合S(j)中的每個個體k的n(k)減去1，即支配個體k的解個體數減1（因為支配個體k的個體j已經存入當前集F(1)）；

（3）如n(k)-1=0則將個體k存入另一個集H。最后，將F(1)作為第一級非支配個體集合，并賦予該集合內個體一個相同的非支配序i(rank)，然后繼續對H作上述分級操作并賦予相應的非支配序，直到所有的個體都被分級。其計算復雜度為O(mN2)，m為目標函數個數，N為種群大小。

在原來的NSGA中，采用共享函數以確保種群的多樣性，引入擁擠度這一因子，用id表示，它表示在個體i周圍包含個體i本身但不包含其他個體的最小的長方形，如圖3所示。

圖3 Pareto平面圖

從圖3可以看出，id值較小時表示該個體周圍有較多的其他相鄰個體，說明該個體的擁擠程度比較大。基于個體多樣性的需要，保證留下的個體收斂到一個均勻分布的Pareto面上，當兩個個體非支配排序等級不同時，選擇等級較小的個體；如果排序等級相同，選擇擁擠度較小的個體。

4.4 選擇交叉變異

遺傳算法的一般過程都需要有選擇、交叉、變異算子，而該算法所采取的算子規則如下：

（1）確定交配池中的個體數量popsize。

（2）確定交叉概率為PJ1，任意取1個取值范圍在（0，1）的隨機數，若該數小于PJ1，執行交叉操作，若大于PJ1，小于PJ2執行變異操作。

（3）若執行交叉操作，任意選擇兩個個體作為親代，兩個個體上所有的基因有一半的概率進行交叉，另外一半的概率保留親代基因，產生新一代子代。

（4）若執行變異操作，則隨機從交配池中選擇一個個體作為親代，有關船舶靠泊時間和靠泊坐標上的基因d'ij變化見式（24）。

表示父代個體i的基因位置j，表示子代個體i的基因位置j，r為[0,1]范圍內的隨機數，G表示當前迭代數，gen表示最大迭代數，m表示變異分布指數。

5 算例和結果分析

通過對天津港實地調研，以太平洋國際集裝箱碼頭為例，確定入港船舶時間和裝卸作業量相關數據，岸橋數為23臺，岸線為1 500m，30個船區，裝卸量和入港時間以及其他船舶數據參考實際情況，見表2，遺傳代數為5 000代，種群規模為300，概率PJ1為0.5，概率PJ2為0.9，變異分布指數為0.5，決策變量方面，船舶泊位分配的岸線坐標和岸橋分配數量均以最小至最大范圍內隨機生成整數，而初始解中靠泊時間滿足范圍的不等式見式（25），當以船舶離港時間和船舶油耗作為雙目標進行求解時，每艘船離開泊位時間見式（26），離港延遲時間見式（27）。

表2 天津港某段時間入港船舶信息表

（1）入港時間協調情況（目標函數為油耗和總在港時間）。如圖4所示，Pareto最優解為（767.3，1.088 4×106），運算時間6 534s。（2）非協調機制情況（目標函數為油耗和總在港時間），該算例下不采取協調到港時間作業措施，以預計時間作為實際入港時間，即不將船舶到港時間作為決策變量而作為已知值進行計算。

如圖5所示，Pareto最優解為（805.3，1.110 2×106），運算時間3 663s。（3）入港時間協調情況（目標函數為油耗和總離港延遲時間）。如圖6所示，Pareto最優解為（331.6，1.084 9×106），運算時間7 188s。

圖4 運算結果1

圖5 運算結果2

圖6 運算結果3

比較（1）、（2），容易得出基于船舶到港時間可協調機制下作業調度計劃不僅可以將船舶總在港時間減少5%左右，還能將船舶油耗（碳排放）降低2%，比較（1）、（3），如果將船舶離港延遲時間和油耗作為雙目標函數，要比船舶在港時間和船舶油耗作為雙目標函數，油耗略低，并且求得的解是最優解（兩目標均最優）。因此該算例以船舶離港延遲時間作為評價港口碼頭服務水平的指標，更有利于減少船舶港內排放。

6 結語

本文針對船舶入港靠泊作業調度問題，以船舶碳排放為切入點，一方面考慮船舶港內航行時的油耗和時間，另外也考慮船公司與碼頭之間協調到港時間，以此減少船舶在港時間，有利于作業調度資源的充分利用和船舶等待時間的較小化，從而適當降低船舶港內排放。在算法上，基于調度建立以船舶排放最小和船舶總在港時間（或船舶總離港延遲時間）最小為目標的雙目標作業調度問題，以NSGA—II為基礎，通過比較不同修復算子下的求解狀況，驗證算法的有效性，同時，提出船舶到港時間可協調的作業調度問題，并利用該算法驗證船舶到港時間可協調機制有利于降低船舶港內排放，即協調機制下船舶的港內排放可減少2%，為綠色港口的建設提供理論基礎。