基于作業鏈的泊位與岸橋協同調度研究

敖 丹，楊勇生

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

隨著集裝箱化的發展，海上運輸已經成為一種主要的運輸方式，全球貿易的80%以上及中國對外貿易的90%左右都是由海運進行處理，集裝箱碼頭在國際運輸中發揮著巨大的作用。

整個集裝箱碼頭包括三個區域，即岸邊區域、運輸區域以及堆場區域。本文研究碼頭的岸邊區域，岸邊操作面臨的主要問題是泊位分配問題（berth allcation problem，BAP）、岸橋分配問題（quay crane allcation problem，QCAP）和岸橋調度問題（quay crane scheduling problem，QCSP）。泊位分配與岸橋調度具有高度相關性，一方面，泊位分配能夠影響到岸橋的調度，船舶的靠泊位置和靠泊時間影響到分配給船舶的岸橋數量以及岸橋的作業時間；另一方面，分配給船舶的岸橋數量以及每臺岸橋的裝卸效率直接影響到船舶的靠港、離港時間。泊位分配受到岸橋調度的影響，而岸橋調度又依賴于泊位分配的結果，因此，需要對泊位與岸橋進行協同調度研究。

針對泊位與岸橋協同調度問題，國內外學者已經做了大量的研究，主要分為兩類：一是泊位與岸橋分配問題（BACAP）；二是泊位岸橋分配與岸橋調度問題（BACAP-QCSP）。關于泊位與岸橋分配問題，Han等[1]考慮船舶到達時間以及集裝箱裝卸時間不確定的情況下，建立混合整數規劃模型，采用基于仿真的遺傳算法進行求解。楊春霞等[2]將泊位與岸橋分配問題分為兩個子模型并采用遺傳算法進行求解，以船舶裝卸時間作為耦合變量構建一個外循環將兩個子模型耦合起來進行分析。He[3]為了達到節能和省時的平衡，以最小化船舶延遲離港時間和能源消耗為目標建立混合整數規劃模型，提出仿真和優化相結合的方法進行求解。Karam等[4]提出了功能集成方法，將問題分為兩個子模型進行求解，用反饋回路將模型銜接起來，數值實驗驗證了此方法的有效性。梁承姬等[5]考慮船舶偏離偏好泊位產生的懲罰時間，通過添加緩沖時間的方法來吸收不確定因素帶來的影響。郝楊楊等[6]考慮船舶等待裝卸的容忍度約束建立相應模型，用仿真進行分析。Iris等[7]考慮岸橋邊際生產率下降以及船舶偏離偏好靠泊位置等問題，通過改進一些約束條件建立模型，采用自適應大鄰域搜索（adaptive large neighborhood search，ALNS）啟發式算法求解。史立等[8]考慮潮汐對泊位岸橋分配的影響，以最小化船舶延遲成本和岸橋移動成本為目標建立混合整數模型，用CPLEX軟件求解。楊劼等[9]考慮離散泊位岸橋調度問題，以最小化船舶總服務成本為目標建立模型，用遺傳算法進行求解。焦小剛等[10]考慮了泊位疏浚對泊位岸橋分配的影響，分別用混合遺傳、混合粒子群、混合模擬算法進行求解。

關于泊位岸橋分配與岸橋調度問題相關研究，張小莉[11]考慮岸橋混合裝卸以及船舶甲板的約束建立泊位岸橋調度模型，設計嵌套式遺傳算法進行求解。文獻[12]以最小化岸邊碼頭服務成本提出一種新的混合整數規劃模型，采用割平面法對模型進行求解。鄭紅星等[13]考慮大型船需乘潮進出港及岸橋作業約束，構建泊位-岸橋分配主模型以及岸橋調度子模型，設計三階段混合遺傳算法進行求解。毛敏俐等[14]考慮船時效率對泊位分配與岸橋配置的影響，以最小化碼頭總成本為目標建立模型，用遺傳算法求解。Abou Kasm等[15]提出碼頭作業一體化的數學公式，考慮任務優先級與岸橋動態、靜態配置不同組合場景下的岸橋操作策略對碼頭作業進度的影響。Tasoglu等[16]首次考慮混合泊位布局、船舶動態到港、裝卸作業時間不確定以及岸橋作業無沖突等因素建立仿真優化模型，用仿真與模擬退火相結合的方法進行求解。文獻[17]考慮了船舶的水深、潮汐條件以及岸橋之間的安全距離，建立泊位與岸橋聯合調度混合整數規劃模型，采用基于環狀拓撲粒子群算法對大規模問題進行求解。

從上述文獻中可以發現，泊位岸橋協同調度問題已有廣泛研究，其中大多數學者主要研究泊位與岸橋之間的分配問題，而關于岸橋如何裝卸集裝箱的作業調度問題研究較少。本文不僅研究泊位岸橋分配問題，還考慮岸橋間的相關約束以及岸橋任務之間的均衡，進一步研究岸橋裝卸作業調度問題，建立泊位岸橋分配和岸橋調度兩個模型，關注兩個模型之間的反饋，并設計嵌套式循環算法求解。此外，本文采用作業鏈的方法，引入“鏈式優化”思路，用鏈單元、鏈環節、鏈上界面與鏈下界面等概念來理解泊位岸橋協同調度問題。

1 問題描述

對于陸續進港的船舶，港口規劃者需要根據給定的船舶信息以及碼頭的實際情況為船舶安排泊位時間、泊位位置，根據船舶的裝載量安排合理的岸橋數量。如圖1是一個泊位計劃時空圖，圖中的矩形表示相應的船舶，矩形中的數字分別表示船舶編號和分配給此船的岸橋數量。

圖1 泊位計劃時空圖Fig.1 Space time diagram of berth planning

當船舶靠港后，需要安排岸橋對船舶進行裝卸作業，岸橋調度決定了岸橋進行裝卸作業的順序，岸橋調度將每艘船劃分為一組貝位，每個貝位上都載裝集裝箱，港口規劃者需要將船舶的貝位任務分配給相應的岸橋組，考慮到岸橋相互干擾以及各個貝位任務的時間窗等因素來確定岸橋的裝卸作業順序。只有當岸橋全部裝卸完集裝箱后船舶才能離港，船舶離港后岸橋閑置，可以安排為其他船舶進行服務。

作業鏈是指相互聯系的一系列作業活動組成的鏈式結構。集裝箱裝卸作業環節包括泊位分配、岸橋作業、AGV作業、場橋作業、外集卡作業等，每個作業環節都是相對獨立的鏈單元，每個鏈單元都由鏈上界面、鏈環節和鏈下界面組成。在優化鏈單元時，不僅要注重鏈單元內的優化，也要考慮到作業鏈的整體性能。

本文只考慮卸船作業，故泊位與岸橋協同調度問題中所涉及到的作業鏈主要由泊位鏈單元和岸橋卸船作業鏈單元組成，其中泊位鏈單元主要為動態到港船舶分配靠泊時間、靠泊位置和岸橋數量，對此擬采取資源節點優化策略進行分析；岸橋卸船作業鏈單元主要是將船舶貝位任務分配給相應的岸橋組以及確定每臺岸橋的裝卸作業順序，對此擬采取任務節點優化策略進行分析?？紤]到作業鏈的整體性能，采用嵌套循環算法對模型求解，確定最佳的泊位岸橋協同調度方案。

2 模型建立

泊位岸橋協同調度問題涉及的變量和參數眾多，為更好地優化泊位和岸橋的性能指標，本文將此問題分為泊位岸橋分配問題和岸橋調度問題，建立兩個模型分別進行優化，然后用岸橋數量作為公用變量將模型連接起來進行協同優化。

2.1 泊位岸橋分配模型

采用資源節點優化策略，將泊位作為作業鏈的開始鏈單元，其中泊位上界面由船舶確定，船舶的到港時間、吃水深度、船時效率要求分別對應泊位上界面的靠泊時間、水深條件、泊位作業能力；鏈環節為船舶制定靠泊計劃，包括靠泊順序和靠泊位置；泊位下界面受岸橋、堆場等影響，岸橋所在位置決定泊位的作業能力，進口箱對應的堆場位置決定船舶的偏好靠泊位置。如圖2表示的是泊位鏈單元結構圖。

圖2 泊位鏈單元結構示意圖Fig.2 Schematic diagram of berth chain unit structure

2.1.1 假設條件

（1）時間周期劃分為相等的時間段，泊位劃分為同等的泊位段；

（2）船舶一旦停泊，泊位位置固定；

（3）每艘船都只有一個偏好靠泊位置；

（4）岸橋之間不能相互跨越，都有一定的安全距離；

（5）船舶裝卸作業不能在中途停止，每艘船舶接受服務的岸橋數目有最大最小數量限制。

2.1.2 參數設置

集合：

V為到港船舶集合，i,g∈V={1,2,…,n}；B為泊位段集合，k∈B={1,2,…,L}；

T為時間段集合，t∈T={1,2,…,H}；

Ri為第i艘船的岸橋數量集合

參數：

n為船舶總數；

L為泊位段總數；

H為時間段總數；

q為岸橋總數；

a i為第i艘船的預計到達時間；

d i為第i艘船的預計離港時間；

b i為第i艘船的偏好靠泊位置；

mi為第i艘船的岸橋需要工時數量；

l i為第i艘船的長度；

c1i為每單位等待時間成本率；

c2i為每單位延遲離港時間成本率；

c3i為每單位偏離理想泊位位置的成本率；

c4為岸橋運營的每小時成本率；

α為岸橋之間的干擾指數；

β為泊位偏差系數；

M為一個足夠大的數。

決策變量：

S i為整數，第i艘船的開始靠泊時間；

Ei為整數，第i艘船的實際離港時間；

P i為整數，第i艘船的實際靠泊位置；

ΔBi為整數，當第i艘船靠泊在b i位置時與其偏好靠泊位置之間的偏差；

M it為0-1變量，第i艘船在t時間段內有岸橋分配則為1，否則為0；

Ritr為0-1變量，第i艘船在t時間段內分配r臺岸橋則為1，否則為0；

G itk為0-1變量，第i艘船在t時間段內靠泊在第k個泊位則為1，否則為0；

Y ig為0-1變量，如果第i艘船泊位在第g艘船的下方則為1，否則為0，如b i+l i≤b g；

Z ig為0-1變量，如果第i艘船的結束時間不晚于第g艘船的開始時間則為1，否則為0。

2.1.3 目標函數及約束條件

式（1）是目標函數，即最小化船舶總的服務成本，包括等待靠泊的時間成本、延遲離港的時間成本、偏離偏好靠泊位置的懲罰成本以及岸橋作業成本；式（2）和（3）分別表示等待時間和延遲時間決策變量；式（4）和（5）表示船舶靠泊位置的偏差變量；式（6）表示考慮到岸橋干擾造成的效率損失以及船舶靠泊位置的偏差，確保每艘船都能獲得所需的岸橋工時；式（7）表示分配的岸橋數量與船舶靠泊之間的關系；式（8）表示船舶i的在泊時間應等于該船舶進行岸橋作業的所有靠泊時間之和；式（9）和（10）表示船舶i開始靠泊和離港時間的界限；式（11）表示每艘船只能在一個時間段內靠泊；式（12）表示船舶i在未到達港口之前不能靠泊；式（13）表示船舶i離港后船舶g才能靠泊在此處；式（14）表示船舶i需靠泊在船舶g的下方；式（15）避免船舶在時間和空間上重疊；式（16）表示分配給船舶的岸橋數量的約束；式（17）～（19）是定義相關變量的取值范圍。

2.2 岸橋調度模型

對于進口箱卸船作業環節，該環節的上、下作業環節分別為船舶靠泊作業和AGV作業，因此岸橋卸船作業的時間窗的最早開工時間為泊位的最晚完工時間，時間窗的最晚完工時間為AGV的最早開工時間。

2.2.1 假設條件

（1）只考慮進口箱卸船作業；

（2）所有岸橋的工作效率、移動速度相同；

（3）貝位和岸橋的順序索引從船頭到船尾依次遞增；

（4）岸橋在給定時間內只能在一個貝位作業，只有完成當前貝位任務才能移動到下個貝位；

（5）不考慮裝卸過程中船舶平衡問題和岸橋等待AGV的時間；

（6）岸橋初始作業時刻、初始位置已知。

2.2.2 參數設置

集合：

Z為集裝箱集合，u,v∈Z={1,2,…,z}；

E為貝位集合，m,o∈E={1,2,…,e}；

Q為岸橋集合，j,p∈Q={1,2,…,q}。

參數：

z為待處理的集裝箱數量；

e為貝位總數；

q為岸橋總數；

I為虛擬開始任務I∈{0}；

F為虛擬結束任務F∈{E+1}；

L u為集裝箱u所在貝位的編號；

c jmo為相鄰貝位移動時間；

k jm為岸橋j處理貝位m的時間；

p jmo為岸橋j處理貝位m和貝位o之間的時間間隔。

決策變量：

X ju為0-1變量，岸橋j處理集裝箱u則為1，否則為0；

S jmo為0-1變量，岸橋j在處理完貝位m之后立即處理貝位o則為1，否則為0；

Z jm為0-1變量，岸橋j處理貝位m則為1，否則為0；

h jm為整數變量，岸橋j開始處理第m個貝位的時刻；

r j m為整數變量，岸橋j處理完第m個貝位的時刻；

為整數變量，岸橋j在T時期的位置。

2.2.3 目標函數及約束條件

式（20）是目標函數，即最小化岸橋最大完工時間；式（21）表示岸橋j在t時期所在的貝位位置；式（22）表示每個集裝箱只能由一臺岸橋處理；式（23）表示每個貝位只能由一臺岸橋處理；式（24）表示同一貝位的集裝箱由同一岸橋服務；式（25）和（26）表示每個岸橋必須處理一個開始任務和一個結束任務；式（27）和（28）表示每個貝位任務只有一個前序任務和一個后序任務；式（29）表示每個任務的完成時間；式（30）表示岸橋的開始時間；式（31）表示岸橋的結束時間；式（32）表示岸橋之間不能交叉；式（33）表示岸橋開始時間與岸橋完工時間的關系；式（34）和（35）定義決策變量。

3 算法設計

基于上述模型相互作用的特點，采用嵌套循環算法[2]進行求解，首先將泊位岸橋分配模型和岸橋調度模型看作兩個內循環，用遺傳算法分別求解，遺傳算法流程如圖3所示；然后為了提高作業鏈的整體性能，構建一個外循環對兩個模型同時優化求解，用岸橋數量作為公用變量進行傳遞和反饋。嵌套循環的主要過程如圖4所示，首先設置初始岸橋數量得到泊位岸橋分配解，帶入到岸橋調度模型中得到岸橋調度解，然后將此解反饋到泊位岸橋分配模型中，對泊位岸橋分配計劃進行調整，通過反復迭代和反饋，不斷改進解的質量，從而得到最佳的泊位岸橋協同調度方案。

圖3 遺傳算法流程圖Fig.3 Flow chart of genetic algorithm

圖4 嵌套循環算法流程圖Fig.4 Flow chart of nested loop algorithm

3.1 泊位岸橋分配模型求解

（1）染色體編碼與初始化種群

采用實數編碼的形式，按照船舶的到港時間順序進行編碼。如圖5所示，染色體包括三部分：一是隨機生成的船舶靠泊順序；二是船舶的靠泊位置，在[0，L-l i]之間生成；三是分配給船舶的岸橋數量，介于最小和最大岸橋數量之間，并且不超過碼頭總岸橋數量。

圖5 染色體構造Fig.5 Chromosome structure

（2）適應度函數設置

為避免陷入局部最優，引入岸橋移動啟發式規則計算適應度，適應度函數值取目標函數的倒數，fitness=1/f，即最小化船舶在港服務總成本的倒數。

（3）選擇操作與交叉操作

采用輪盤賭法進行選擇操作。采取順序交叉的方法進行交叉操作，如圖6所示，從種群中選取兩個父代個體，隨機選擇兩個交叉列，按照船舶的編號順序進行對應部分的交叉操作。

圖6 交叉操作Fig.6 Cross operation

（4）變異操作

隨機選擇父代個體的兩個基因值，將這兩個值進行互換，產生新的個體，變異操作過程如圖7所示。

圖7 變異操作Fig.7 Variation operation

3.2 岸橋調度模型求解

（1）染色體編碼

采用矩陣式編碼，染色體由m行n列的矩陣表示，其中m表示分配的岸橋數量，n表示船舶的貝位數。染色體中的基因值表示分配給此臺岸橋的貝位上的集裝箱數量，0表示沒有可處理的集裝箱。如圖8為染色體構造，有3臺岸橋和12個貝位。

圖8 染色體構造Fig.8 Chromosome structure

（2）適應度函數設置

目標函數為最小化岸橋最大完工時間，適應度函數取該目標函數的倒數。

（3）選擇操作與交叉操作

采用精英保留策略，在種群中選取適應度函數值較好的個體直接保留到下一代。

采用算術交叉的方法產生新的染色體，參考文獻[18]提出的交叉策略方法，交叉過程如下：off spring=φ×parent1+(1-φ)×parent2，本文設置φ=0.8，交叉過程如圖9所示。

圖9 交叉操作Fig.9 Cross operation

（4）變異操作

與泊位岸橋分配中的變異操作一致。

4 算例結果與分析

4.1 初始數據

碼頭岸線總長1 200 m，50 m為1個泊位段，共24個泊位段；船舶計劃周期為24 h；10臺可用岸橋；岸橋的作業效率為1 TEU/min；岸橋在相鄰貝位之間的移動時間為1 min，安全距離為1個貝位；岸橋的干擾系數為0.9；泊位偏差系數為0.2；單個集裝箱偏離偏好泊位每米的成本為0.01元；船舶的成本參數分別為：c1i=100，c2i=100，c3i=100，c4j=150。初始岸橋數是根據船舶集裝箱數和岸橋的工作效率計算所得，并符合最小和最大岸橋數的約束。

船舶的相關信息見表1所示，船舶的到港時間、偏好靠泊位置、船舶貝位數都是隨機生成的，每個貝位的作業量生成的范圍介于[30，100]之間。

表1 船舶信息表Table 1 Ship information table

4.2 結果分析

內循環中遺傳算法的參數設置如下：泊位岸橋分配模型中種群規模為100，迭代次數為300，交叉和變異概率分別為0.8和0.1；岸橋調度模型中種群規模100，迭代次數200，交叉和變異概率分別為0.9和0.2。外循環中的最大迭代次數為500，用MATLAB軟件進行編程對模型求解，泊位岸橋分配模型中算法收斂如圖10所示，可以看出算法迭代至125代時目標函數值趨于收斂至最優解。得出泊位岸橋分配最優解，如表2所示，并繪制了泊位岸橋分配計劃圖，如圖11所示，此圖更加形象直觀地表達了計劃周期內各到港船舶的靠泊時間、靠泊位置、分配的岸橋數量以及船舶的離港時間。

圖11 泊位岸橋分配計劃Fig.11 Berth quay crane allocation plan

表2 泊位岸橋分配結果Table 2 Berth quay crane allocation results

圖10 結果收斂圖Fig.10 Result convergence graph

根據泊位岸橋分配的結果，可以計算出每艘船舶所花費的成本，見表3，從表中可知6艘船舶在港期間所花費的總成本為12 303元。

表3 船舶成本分析Table 3 Ship cost analysis 元

在泊位岸橋分配的基礎上，結合表4中到港船舶的貝位作業量以及岸橋相關信息，對岸橋調度模型求解，得出如圖12所示的岸橋調度圖，圖中橫軸表示岸橋作業時間，縱軸表示船舶貝位，此圖表示了計劃周期內岸橋的作業調度過程，包括每臺岸橋的開工時間、作業時間以及完工時間，從圖可知6艘船舶各自的開工時間分別為0、0、165、300、520和728 min，完工時間分別為195、258、312、650、885和913 min。

圖12 岸橋調度圖Fig.12 Quay crane dispatching chart

表4 任務船舶貝位以及集裝箱數量Table 4 Number of mission vessels and containers

4.3 單獨調度與協同調度對比分析

泊位與岸橋調度問題能單獨優化，也可以協同優化，為了說明協同調度的有效性，對此問題進行單獨調度，即將泊位岸橋分配和岸橋調度當成兩個獨立的階段進行考慮，只單方面考慮泊位岸橋分配對岸橋調度的影響，目標函數成本比較如表5所示。

表5 成本比較Tab.5 Cost comparison

從表中可看出，協同調度的優化效果主要表現在岸橋運營總成本上，這是因為本文將岸橋調度問題一起考慮，確定了最佳的岸橋裝卸作業順序，提高了岸橋的裝卸效率，從而減少了船舶在港總成本。

4.4 不同規模算例結果

為了驗證模型和方法的有效性和普適性，隨機選取6個算例進行實驗，每個算例運行10次取平均值，與單獨調度進行對比，實驗結果見表6，其中n表示船舶數量，e表示貝位數，q表示岸橋數。

表6 算例結果對比Table 6 Comparison of calculation results

由算例1和2可知，岸橋數量不變時，船舶數量越多，船舶在港總成本和算法求解時間會逐漸增加；由算例3和4可知，船舶規模一定時，分配的岸橋數量越多，算法求解時間越久，船舶在港總成本并沒有減少，這說明岸橋數量不是越多越好。此外，與單獨調度相比，協同調度在求解時間上要更久，但其優化效果更好，平均可以達到10.28%的優化效果。

4.5 算法對比

為了驗證遺傳算法的有效性，隨機選取6個不同規模的算例分別與粒子群算法（PSO）、蟻群算法（ACO）和蜂群算法（ABC）進行對比分析，考慮到隨機誤差，每個算例運行10次取其平均值，實驗結果見表7。

表7 算法對比結果Table 7 Algorithm comparison results

從表7中可知，中小規模下這些算法都能得到最優解，隨著問題規模變大，算法求解時間變長，與其他智能算法相比，遺傳算法在求解時間上花費的時間相對更少，說明遺傳算法求解效率要更高。從圖13可看出，目標函數值的變化幅度隨問題規模變大而增加，粒子群算法與蜂群算法變化幅度稍大，而遺傳算法變化趨勢較平穩，說明遺傳算法求解質量更好，適合大規模問題求解。由此可知，遺傳算法在求解質量和效率上都更優，從而驗證了遺傳算法在求解此類問題中的有效性和穩定性。

圖13 算法表現分析Fig.13 Analysis of algorithm performance

5 結束語

本文從作業鏈的角度對泊位與岸橋協同調度問題進行研究，首先將泊位計劃看作一個鏈單元，采用資源節點優化策略分析，建立泊位岸橋分配模型；然后將岸橋卸船作業看作一個鏈單元，采用任務節點優化策略分析，建立岸橋調度模型?？紤]作業鏈的整體性能，采用嵌套循環算法對模型同時求解，內循環用于求解兩個模型，外循環通過兩個模型之間的反饋得到協同調度最優解。為了驗證本文提出的模型和算法的有效性，擴大問題規模，設計不同的算例進行分析，實驗結果表明：（1）與單獨調度相比，協同調度平均可達到10.28%的優化效果，通過合理利用泊位與岸橋資源，顯著降低了岸橋成本，進而減少船舶在港總成本。（2）通過與粒子群、蟻群算法、蜂群算法進行對比，結果表明遺傳算法在求解質量和求解效率上都更優，證明了遺傳算法適合求解此類問題。

本文只考慮了卸船作業，未來可與裝船作業結合起來進行研究，使其更加符合碼頭實際的生產作業；對于問題求解，采用遺傳算法，未來可以對遺傳算法進行改進或采取其他更加高效的算法進行求解。