考慮中轉的集裝箱碼頭多資源集成調度

王曉光，王宏宇，劉博宇

1.上海海事大學物流科學與工程研究院，上海 201306

2.上海立信會計金融學院工商管理學院，上海 201209

全球集裝箱航運網絡呈輪輻式結構，轉運港作為航運運輸網絡的關鍵節點，在全球供應鏈中發揮著重要作用，負責長途服務的干線船舶（母船）與負責連接周邊小型港口的船舶（支線船）通過轉運港碼頭進行集裝箱轉換[1]。先到港的船舶將集裝箱暫存于碼頭堆場側，等待后續船舶裝載出港。然而新冠肺炎疫情突然暴發，暴露了樞紐港管理的系統性問題，如碼頭資源分配不均、船舶裝卸作業時間增加等。這些問題不僅影響到樞紐港的整體運行效率造成港口擁堵，同時阻礙了船舶間轉運作業的順利進行，對全球貿易發展造成不利影響。

隨著新冠肺炎疫情的持續傳播，樞紐港碼頭管理變得越發復雜，導致碼頭規劃混亂。學者們對如何提高港口運營效率進行了深入研究，主要方法包括碼頭泊位、堆場調度以及規劃船舶到港時間。本文收集了相關研究并對相關文獻進行了比較分析。

碼頭資源分配主要包括戰術泊位分配與戰術堆場分配。由于泊位和堆場分配相互影響，近年來泊位-堆場等一體化規劃正在興起。Wang 等[2]開發了一種同時優化泊位和堆場決策的列生成算法，提出結合泊位、碼頭起重機和堆場存儲空間三種資源分配的集成優化問題。Guo等[3]研究了堆場和泊位分配之間的多期相互作用，設計了一種禁忌遺傳算法以獲得來訪船舶的靠泊位置和出口集裝箱的堆場存放位置。韓笑樂等[4]針對戰術層面的泊位—堆場資源聯合分配問題，提出不確定性環境下的魯棒性模板決策，通過松弛時間的啟發式調整規則優化啟發式算法，為集裝箱碼頭多資源協同分配提供了有效決策思路。針對泊位和堆場進出口同步作業協同分配（BYCA-ⅠESOs）問題，Li 等[5]提出基于計算物流同步或異步集成調度策略的BYCA-ⅠESO 研究模型，通過實驗結果的分析，驗證了模型和策略的可行性。郭文文等[6]分析了出口箱裝船過程中泊位與堆場分配的相互影響關系，建立了以集卡行駛路徑最短為目標，以?？坎次?、出口箱堆存位置及堆存在子街區的數量為決策變量的泊位與堆場協調分配模型，并設計了禁忌遺傳算法求解。

伴隨著研究的不斷深入，學者們發現平衡船舶的到港時間對泊位分配具有重要意義，可以避免同時段到達船舶過多造成泊位擁堵，于是將時間窗約束引入研究中。De等[7]引入時間窗口約束限制船舶到達時間，并提出考慮調度、路徑約束、裝卸約束和船舶約束的混合整數非線性規劃模型，最后通過粒子群優化-差分進化算法（PSO-DE）求解，提高了港口服務水平。隨后提出了一個考慮時間窗口概念的新型可持續船舶航線問題，并提出一種新的粒子群優化算法（BVNS-PSO）對其進行求解[8]。Jiang 等[9-10]提出通過結合港口時間窗口來解決班輪航線和船期設計同時優化的問題，構建了混合整數非線性模型，將其轉化為整數線性優化模型進行求解得到最佳船舶到港時間，緩解了港口擁堵。

此外，為提高碼頭作業效率，集裝箱裝卸和轉運作業也受到學者們的廣泛關注。Liu等[11]定義了兩種船舶間轉運模式，即直接轉運模式和間接轉運模式，并設計了一種雙目標方法解決集裝箱碼頭綜合規劃復雜的問題。Emde 等[12]考慮直接轉運模式，特別關注到支線船和母船之間的集裝箱交換，通過支線船的碼頭空間和服務時間分配，實現支線船舶交付的集裝箱數量不超過母船給定上線。常祎妹等[13]建立了以裝卸總完成時間最短為目標的混合整數規劃模型，考慮了裝卸同步等現實約束和集卡堵塞問題，設計了改進的多層遺傳算法求解模型。唐夢宇等[14]采用滾動窗策略方法研究轉運進口集裝箱作業問題，并建立了以列車在港停留時間和集裝箱在堆場的堆存時間最小為目標的整數規劃模型，結果表明，增加裝卸線數和軌道起重機工作能力可以提高集裝箱轉運效率。

然而，很少有研究考慮到中轉港船舶間的集裝箱轉運服務，以及船舶間轉運服務對碼頭作業效率的影響。特別是新冠疫情爆發以來，港口擁堵、船舶在港外排起長隊的新聞屢見不鮮，隨之帶來的一系列連鎖反應暴露了船期表、轉運流量以及碼頭資源的相互關聯性[15-16]?；诖?，本文以樞紐港集裝箱碼頭為背景，研究碼頭多資源集成調度，并綜合考慮船舶間轉運流管理、船舶服務時間分配、泊位調度和堆場分配因素的內在聯系，進行多資源協同優化，旨在高效利用碼頭資源，實現碼頭集裝箱轉運作業時間最小化。

1 問題描述與建模

1.1 多資源集成調度問題

碼頭運營商的一個主要決策是到港船舶的時間安排，由于母船有更高的泊位權且到港時間穩定，所以碼頭運營商時間調度主要是遵循母船工作時間請求，設計支線船服務時間表。支線船舶服務時間表需要滿足兩點要求，第一，周期內支線船對母船有轉運需求時，支線船要早于母船到達泊位或與母船同時到達泊位。當母船對支線船有轉運需求時，支線船最晚在下一個周期結束前將堆場內貨物運出，避免堆場集裝箱積壓。如圖1所示，當母船1 對支線船1 有轉運需求但支線船本周期服務時間已過時，支線船需要在下一周期同一班次到港時將轉運流貨物運出。第二，調整船舶的?？繒r間以平衡碼頭的工作量。一方面船舶服務時間最好在周期內呈均勻分布。另一方面船舶靠泊時間決定了周期內同一時段堆場內集裝箱轉運流量的多少，這與泊位和堆場模板設計緊密相連，而良好地泊位和堆場規劃可以有效管理集裝箱轉運流，提高碼頭整體作業效率。船舶服務時間表設計周期為1周，每8小時為一個工作班次，共包含21 個工作班次，支線船在每個周期內按照規定時間服務，服務班次一旦確定，在整個規劃期內不能輕易更改。

圖1 船舶服務時間的說明性示例Fig.1 Ⅰllustrative examples of ship service hours

碼頭運營商的另一個主要決策為空間規劃，即為轉運船舶規劃停泊位置，對船舶間轉運流進行管理（母船和支線船間進行轉運的集裝箱被稱為“轉運流”），確定轉運流貨物在堆場停留期間的存儲區塊。由于轉運流方向不同，在同一節點或路段運輸時存在相互干擾，導致堆場存在多轉運服務擁堵的情況[17]。所以，通過調整船舶的停泊位置和集裝箱的堆場存儲區域來均衡堆場內的轉運流，實現同時均衡轉運流、泊位和堆場分配。此外，堆場發生多業務擁堵時，最短路徑可能不是最有效的運輸路徑，支線船的停泊位置和堆場的存放區域由最小化轉運流集裝箱的運輸時間確認。為了更直觀地構建碼頭多資源分配數學模型，本文將船舶間集裝箱運輸看作如圖2所示的節點-網絡圖，其中堆場塊節點為單向節點，碼頭泊位節點為雙向節點，車道節點分為垂直節點和交叉節點，其中交叉節點為雙向節點。

圖2 碼頭集裝箱運輸節點-鏈路圖Fig.2 Terminal transportation node-link diagram

1.2 模型構建

（1）假設

①由于母船裝卸作業量大，優先?？吭谥鞑次?；

②碼頭運營商在班輪公司給定的船舶可用時間窗內可以決定支線船的?？繒r間。

（2）參數設置

本文的符號定義如表1～表3所示。

表1 集合符號定義Table 1 Collection of symbols definition

表2 參數設置Table 2 Parameter setting

表3 0～1變量說明Table 3 0～1 variable description

（3）模型構建

在周期h內轉運流F對應的裝卸路線是確定的，其中泊位節點集合B以i為索引，堆場塊節點K以j為索引，運輸路線表示以(i,j) 為索引，裝卸時間為tij。假設共享路段(i,j) 上轉運服務數量為gh，考慮到共享路段多條轉運流之間相互干擾對堆場運輸造成影響。本文改進了Zhen[18]提出的基于概率的堆場擁堵公式，構建了集裝箱運輸時間受共享鏈路多轉運流同時服務影響的預期行程時間公式，決策變量為共享節點或鏈路中同時作業的轉運流數量。將tij(c)定義為鏈路(i,j)上發生了c次運輸中斷，預期行程時間tij如式（1）所示，式（2）定義為鏈路(i,j)發生c次運輸中斷的概率Pij(c)。

式（3）中cˉ是受轉運流量影響造成多服務擁堵的平均次數，式（3）、（4）中a表示卡車運行時的加/減速度；lii表示鏈接(i,j)的距離；hi,j表示鏈路(i,j)中的通道數；Ey表示堆場起重機處理單元集裝箱的平均時間長度；v表示堆場卡車的正常速度；和分別代表卡車在鏈接間的初始速度和終止速度，綜上轉運流f在鏈路(i,j)上的預期行程時間為式（5）：

其中，式（6）、（7）中的參數已知，式（6）的決策變量為gh，即路段( )i,j上的轉運流干擾程度影響集裝箱轉運流作業時間。但gh受碼頭運營商船舶服務時間、泊位和堆場分配的共同影響，所以可以通過調整碼頭決策實現最小化預期鏈路行程時間。在不考慮轉運流量過大造成的堆場擁堵時，碼頭決策受船舶到港時間和碼頭容量限制，但堆場擁堵情況下，轉運流的管理受泊位和堆場塊的具體分配影響。

目標函數：

式（8）是模型的目標函數，表示為母船到支線船的裝卸時間和母船到支線船的裝卸時間之和。

約束條件：

式（9）表示每條轉運流貨物需存放在同一堆場存儲塊，不能拆分到多個堆場存儲區域，式（10）和（11）分別表明每艘船只在一個泊位停泊。

式（12）表明船只在一個周期內只?？恳淮?。式（13）表明當支線船對母船有轉運需求時，與轉運流相關聯的支線船應比母船更早或同時到達。式（14）表明，任何時期的轉運流量都不應超過分配貨場區段的能力上限。式（15）表明，任何時期的總集裝箱工作量都不應超過總泊位工作量的上限。

式（16）和（17）表明轉運流集裝箱在堆場停留時間不超過一個周期，確保貨物在周期內裝上到港或離港船舶。

式（18）、（19）、（20）表明當轉運流貨物對母船有轉運需求時，轉運流早于母船的到港時間提前到達港口，同時對決策變量δft進行約束。

2 基于禁忌搜索的人工免疫算法設計

由于本文設計的模型是非線性整數規劃模型構造復雜，一些商用求解器（例如CPLEX 求解器）很難直接求解，所以針對該問題選擇采用元啟發式算法，一些元啟發式方法經常用于解決與本文類似的港口、碼頭優化問題，例如，人工免疫算法（ⅠA）。然而人工免疫算法在求解優化過程中存在“早熟”問題，為克服早熟現象，提高算法的全局收斂性、穩定性和尋找極值點能力，本文基于人工免疫算法，借鑒禁忌搜索算法的機制，提出基于禁忌搜索的人工免疫算法，在算法中引入禁忌搜索程序以豐富解決方案的多樣性。

2.1 編碼

本文設計的人工免疫算法中，抗原表示上述的碼頭規劃問題，抗體表示針對該問題的決策方案。本文通過所構建的模型進行編碼求解。以隨機生成的方式，生成一組初始抗體組，每個抗體包含子船及所連接轉運流的堆場、泊位和服務時間窗決策。

（1）抗體與抗原的親和度計算

抗體親和度是通過計算期望繁殖率對抗體質量進行評價，期望繁殖率越大則被選中的概率越大。本文設候選抗體為σ，全部種群數量為N，抗原親和力與抗體親和力分別為A(σ)與C(σ)，則該抗體的期望繁殖率為式（21）：

變量ε用于確定A(σ)與C(σ)的各自權重，兩種親和力相互拮抗既能使得高適應度的個體繁殖，又能保證種群的多樣性。式（22）為抗體親和力計算公式，f(σ)代表目標函數值，抗體的親和力越大，目標函數值越小。

（2）抗體濃度計算

抗體濃度反映了抗體之間的相似程度，濃度越高則說明抗體相似度越高，種群的多樣性越低。通過平均信息熵來衡量個體間差異，擁有L個基因的染色體每個基因的信息熵H(a) 計算如式（23）所示：

式中，a為抗體個數，表示a條抗體的平均信息熵，一般取值為2。式（24）中pji是j出現在i位點的比率，pji=(the total number ofjth symbols oni)/a

（3）抗體相似度與抗體濃度計算

本文采用R位連續方法計算抗體之間的親和力，即對于抗體x與y，若二者的編碼有超過R位相同，則表示這兩個抗體近似“相同”，否則表示二者不同，構造邏輯判別函數如下：

式（25）、（26）中，Hσ,μ( 2 )表示σ和μ兩條染色體的平均信息熵，為了計算抗體相似性，本文引入中間變量S(σ,μ)，其中L為抗體的長度，k表示抗體σ與抗體μ中相同的位數，R代表親和度的閾值，S為抗體是否“相同”的邏輯判別?？贵w濃度本文用C(σ)表示，指群體中與抗體σ相似的抗體數量的比率，對于抗體x，若設全部種群數量為N，則其抗體濃度為公式（27）：

2.2 免疫操作

免疫操作基本原理是在解集中選擇抗體進行變異操作，指改變染色體上的一個或多個基因，得到親和力更高的染色體，并在迭代過程中逐漸逼近最優解的過程。免疫操作具體包括選擇操作、交叉操作和突變操作。本文通過輪盤賭法進行抗體選擇，即抗體σ被選擇留下的概率為Pσ，且σ的預期繁殖率E( )σ越高，被選中的概率Pσ越大，計算公式如下：

變異操作是相鄰抗體信息交互的重要步驟，以確保全部種群中優秀基因被長期保存。對于每次迭代操作，種群進行隨機配對并進行統一的交叉操作。給定交叉參數ρ和0 到1 之間的隨機數r，若r≤ρ，則執行交叉操作。由于抗體包含三個決策，所以具體操作為隨機選定一個位點，交換該位點對應的三個基因。變異操作是保持種群多樣性，避免“早熟”的重要手段，除了位點選擇后的基因會產生突變外，其他與交叉操作相同。

2.3 基于禁忌搜索的免疫突變操作

避免算法陷入“早熟”的同時提高搜索效率，本文在抗體突變過程中結合禁忌搜索程序來改進后代個體，擴大抗體群種類。首先，通過鄰域搜索隨機選擇抗體的某個因素替代后生成鄰域解。在禁忌迭代過程中，若鄰域解中的最優解親和力高于原解，則原解被更優的鄰域解替換，反之則保留原解。圖3 展示了鄰域解的生成過程。如圖所示，通過鄰域搜索隨機選擇左側原解中的某個因素變異后生成右側的鄰域解。原解Gene3中Y5突變為Y6 后生成第一個鄰域解，同樣方式，在突變T1次后，共生成T1個鄰域解。本文將鄰域解中最佳方案與原方案更換元素的位置記錄在禁忌列表中，遵循先進先出的規則進行存儲，記錄在緊急列表中的元素不再進行變異。禁忌列表長度設置為T1，當最佳解決方案通過最高迭代限度C次后沒有得到改進，則禁忌搜索過程終止。

2.4 算法編碼過程

算法的具體編碼及數據處理過程如下所示。

算法1基于禁忌搜索的人工免疫算法

3 數值實驗與方法評估

3.1 案例研究

為了評估綜合規劃方法在解決實際的問題時的求解效果，本文基于上海港最大的集裝箱碼頭上海盛東國際集裝箱碼頭（SSⅠCT）生成實驗案例。SSⅠCT是位于上海東南部洋山島上的洋山深水港（YDP）的一部分，擁有3 000 m 長的直線型碼頭和15 公頃的集裝箱堆場，每個月為550多艘深海和支線船提供服務，平均吞吐量為45萬標箱[19]。在此基礎上，本文生成集裝箱碼頭仿真案例，頭堆場布局如圖4 所示，碼頭全場3 000 m，最多有8 個泊位48 個堆場存儲區，堆場橫向和縱向超車道的寬度分別設置80 m和30 m，泊位到堆場區域距離為55 m，每個堆場存儲塊容量為1 200 TEU[11]。該碼頭所有堆場和泊位空間均可服務于到港的船舶及轉運流，本文在船舶服務時間的約束下隨機生成船舶間轉運流方向及數量，并施加了轉運流總數限制，與母船相關的轉運流不超過六條，支線船則不超過三條。每條轉運流的集裝箱量在100 到500 間呈均勻分布，每條轉運流存放在同一堆場存儲區塊，此外，模型結合相關研究[18]，其他參數設置如表4所示，表中數據均源于上海港專家研究的數據估算結果[20-21]。其中泊位處理能力實際上取決于船舶數量、船舶類型、分配的碼頭起重機數量等，本文側重戰術規劃僅施加限制每個泊位處理的最大集裝箱數量。

表4 模型參數設置Table 4 Model parameter setting

圖4 碼頭實驗平面圖Fig.4 Terminal experimental plan

3.2 算法評估

為了驗證本文提出的基于禁忌搜索的人工免疫算法（TS-ⅠA）解決問題的能力，本文采用當前求解效果較好且具有一定公信力的兩種啟發式算法，遺傳算法（GA）、人工免疫算法（ⅠA），進行算法對比實驗。這兩種算法廣泛應用于各類研究中，Junqueira等[22]研究了集裝箱搬遷和港口碼頭裝卸船舶通港的聯合規劃問題，并應用模擬遺傳算法描述了一種優化方法，測試結果表明，能夠在6 min 內解決上百個集裝箱分配實例給出有效優異的集成方案。Wu 等[23]提出了解決自主水面車輛（ASV）需要遵守擁擠海域海上避碰規則的問題，并設計了一個改進的遺傳算法進行的仿真研究，結果表明，提出的智能遺傳算法可以有效避讓與其他船只碰撞。劉剛[24]將堆場裝卸作業時間成本和堆場空間成本作為優化目標，并采用貪心算法改進遺傳算法并和原來的遺傳算法作對比實驗，有效證明了改進后具有較好的效果。程玉龍等[25]與遺傳算法做對比，來證明提出的免疫遺傳算法對個體的選擇和評價更為全面與合理。Xu等[26]在研究中提到免疫算法已被證明在許多實際優化問題中是有效的，具有高效的收斂性和搜索效率。上述各研究均表明，用遺傳算法和人工免疫算法做為對比實驗算法是具有一定公信力且求解結果較好的算法，在解決相關問題上具有一定的優越性和有效性。

基于文獻中所提到的遺傳算法和人工免疫算法思想，本文針對碼頭多資源集成調度問題設計了具體的兩種智能算法，進而作對比實驗。兩種智能算法與基于禁忌搜索的人工免疫算法（TS-ⅠA）共進行了6組不同規模的實驗，實驗數據如表5 所示，其中Set1 和Set6 分別為最小和最大規模實驗。以Set6為例，表示該碼頭每周有30艘母船和50條支線船（21個工作班次）和110條轉運流到訪碼頭。本文通過3 個維度對比了3 種算法的性能，對比結果顯示TS-ⅠA 的求解質量、迭代效率和魯棒性均高于其他兩種啟發式算法。

表5 實驗案例參數設置Table 5 Experimental case parameter setting

（1）算法的求解結果比較

本文將TS-ⅠA 算法獲得的目標函數值對比其他兩種算法，表6分別為三種算法在不同規模實驗中的結果比對。由于算法的計算過程具有隨機性，所以選取6組不同規模案例，每個案例運行10次取最優值如2.4節的代碼所示。三種算法在進行小規模Set1 實驗的對比結果表明，ⅠA 與TS-ⅠA 的目標函數值相近目標函數差3.8%左右，但GA的目標函數值與前兩種算法差距更大為9.87%，所以在進行小規模實驗時TS-ⅠA算法最優，ⅠA算法優于GA算法。隨著實驗規模增大，母船和支線船數量增多，轉運流數量增大，三種算法間的目標函數值差距明顯增大。TS-ⅠA 的求解結果在大規模實驗中依舊優于其他算法，而GA 求解結果則優于ⅠA 的目標函數值。

表6 三種算法目標函數值對比Table 6 Comparison of objective function values of three algorithms

（2）算法的性能比較

為進一步展現TS-ⅠA算法的性能優勢，本文以Set6的大規模實驗案例為例，對三種算法進行了收斂效率比較。如圖5所示，GA和ⅠA分別在第154代和第112代收斂，但是本文提出的TS-ⅠA 算法僅需58 代即可收斂，比起其他兩種算法具有過好的收斂效率。

圖5 算法迭代圖Fig.5 Algorithm iteration

（3）算法的魯棒性比較

算法的魯棒性是以波動率為標準判斷算法的穩定程度，即反應初始值逼近最優解的程度，初始值越接近最優解，波動率越小，魯棒性就越好，反之波動率越大，魯棒性越差，式（29）為波動率的計算公式：

式中，Vol 表示算法的波動率，Navg表示算法的平均值，Nopt表示算法的目標函數值。如圖6所示，GA的波動率在8.98%到21.73%之間，ⅠA 的波動率在4.44%到14.06%之間，而TS-ⅠA的波動率在3.03%到6.28%之間，平均值為4.81%，相比其他兩種算法，TS-ⅠA 波動率最小，魯棒性最好。

圖6 算法魯棒性對比圖Fig.6 Comparison chart of algorithm robustness

3.3 情景分析

為了驗證集成調度方法的有效性，設計了三種不同情景決策規則進行對比，決策規則如下：

情景1本文提出方法，集成優化船舶服務時間、船舶間轉運流、泊位模板和堆場模板；

情景2不對船舶間轉運流進行管理，即轉運流貨物在堆場的存儲區域是固定的，僅進行泊位模板優化和船舶服務時間分配；

情景3指定船舶靠泊泊位，對船舶服務時間和船舶間間轉運流進行管理，即分配轉運流在堆場的存儲區域和船舶服務時間；

情景4船舶服務時間固定，集成優化船舶間轉運流的堆場模板和船舶靠泊的泊位模板分配。

本文通過與上述六組實驗規模相似的算例進行對比分析，表7 顯示了不同情景下目標函數值的大小區別，可以看出本文提出的多資源協同規劃方法，無論處理小規模還是大規模問題，求解結果均優于其他情景。

4 結語

本文得到的主要結論如下：

（1）提出了考慮中轉的碼頭集成調度方法，解決了船舶間轉運作業、船舶服務時間分配和碼頭作業規劃關聯決策的綜合性問題，設計了基于禁忌搜索的人工免疫算法進行求解，并利用算例和情景對比實驗證明了模型算法的有效性。

（2）其次，貼合實際情況對轉運流分配造成的堆場多服務擁堵情況進行量化分析，構建了一個充分考慮碼頭轉運作業相關因素的混合整數規劃模型，創新地實現了集裝箱轉運流的分配平衡、船舶靠泊泊位及服務時段資源分配的平衡，避免港口擁堵。

（3）最后，不同情景的對比實驗結果表明，與其他決策方案相比，集成調度模型在預期行程時間上最小縮短4.33%，最大縮短20.19%，可以顯著縮短集裝箱轉運作業時間，提高作業效率，縮短船舶等待時間。

低碳航運是未來港航物流研究的主要問題之一，未來可以在研究中考慮低碳元素，著重碼頭作業與低碳航運的關系，并采用具有更強魯棒性的新型智能算法或混合算法進行求解，實現碼頭資源利用最優化、碳排放量最小化。