考慮泊位疏浚的連續型泊位和動態岸橋聯合調度

焦小剛， 鄭斐峰， 徐寅峰， 劉 明

(1.東華大學 旭日工商管理學院，上海 200051; 2.寧夏大學 信息工程學院，寧夏 銀川 750021; 3.同濟大學 經濟與管理學院，上海 200092)

0 引言

全球經濟一體化進程和國際貿易的迅速發展，推動了作為世界經濟紐帶的航運業迅猛增長。為了在激烈的國際航運業競爭中獲得優勢和追求規模經濟效益，各航運公司近年來競相建造了許多超大型船舶。船舶大型化趨勢勢必給航運業終端的港口帶來巨大壓力和影響。為了能夠適應這種趨勢，吸引這些“巨無霸”靠泊，給港口帶來更大的經濟效益，港口勢必要改造和升級現有的基礎設施以提供優質的服務保障。港口泊位水深是港口的重要技術指標之一，它決定了港口的船舶接納能力。由于潮汐、臺風、泥沙和地質等原因造成的回淤使港口泊位在使用過程中不斷淤積泥沙，減少了泊位水深，從而降低了泊位的靠泊能力和靠泊安全性。為此，港口需要定期地進行海事測量和泊位疏浚工作。以天津港為例,天津港深水泊位眾多且大多數分布在泥沙回淤嚴重的口門附近, 泊位回淤速率達1.5～3.4米/年，設計備淤深度為1米，為此每年需要進行2至4次常規維護疏浚[1]。根據在上海洋山港的實地走訪調研得知，洋山深水港泊位大約一至兩年就需要疏浚一次，每次耗時約一周，而且僅直接費用往往就要幾百萬元，具體時間長度還受到疏浚船只的工作效率、數量以及天氣情況等多種因素的影響。

為了在泊位疏浚工作期間，最大可能地保留港口靠泊裝卸服務能力以減少對正常工作的影響，這是每個港口都值得思考的問題，這也是本研究的出發點。針對集裝箱港口泊位進行疏浚工作時部分泊位陸續不能使用的現實情況，對如何更好地協調碼頭前沿泊位和岸橋這兩個重要關鍵資源開展了聯合調度，旨在降低船舶周轉時間，提升港口服務水平。本文創新之處在于：(1)考慮了泊位疏浚對泊位-岸橋聯合調度的影響；(2)考慮了每艘船舶裝卸期間岸橋數可變的岸橋調度情形，提高了岸橋的利用率進一步縮短船舶服務時間；(3)為了防止岸橋頻繁移動影響其工作效率，限定服務每艘船舶的岸橋數變化不超過1，即僅允許位于船舶最前端或最后端的岸橋在當前船舶任務未完成的情況下移動至相鄰船舶進行服務；(4)設計了三個啟發式算法進行求解并對它們的性能進行了比較。

1 文獻綜述

集裝箱港口作業區域主要分為碼頭前沿和后方堆場兩大部分，其中碼頭前沿是港口運營和管理中最為重要的場所。泊位和岸橋是設置在碼頭前沿的兩種重要稀缺資源，它們的工作效率在很大程度上影響著客戶滿意度和港口運營成本。因此，關于泊位和岸橋的優化調度問題引起了國內外眾多學者的關注。為了更好地了解這方面內容，可以參見Bierwirth[2,3]和Carlo[4]等人的綜述性文獻。這些文獻將泊位與岸橋的調度研究劃分了層次，形成了三個子問題：泊位分配問題(BAP: Berth Allocation Problem)，岸橋分配問題(QCAP: Quay Crane Assignment Problem)和岸橋調度問題(QCSP:Quay Crane Scheduling Problem)。近年來學術界對這些子問題及其聯合問題進行了廣泛的研究，以下將對國內外一些相關文獻作一個簡要的介紹。

Park和Kim[5]開創性地研究了連續型靜態泊位和岸橋聯合調度問題，該問題被劃分為二個階段進行求解，第一階段采用次梯度優化方法給出了船舶的靠泊位置和時間以及分配的岸橋數量，在此基礎上第二階段用動態規劃方法確定了岸橋的調度方案。Giallombardo等[6]首次提出了QCAssignment Profiles概念，用于解決泊位和岸橋聯合調度的策略層問題。 Meisel和Bierwirth[7]建立了一個解決泊位和岸橋聯合調度問題的完整框架并分解為三個階段逐步求解。Hu等[8]為了對船舶燃油消耗，溫室氣體排放和船舶服務時間進行權衡把連續型動態泊位問題和岸橋分配問題進行了集成，構建了一個非線性多目標混合整數規劃模型，為了降低求解復雜度該模型被轉化為一個二階混合整數錐規劃模型并設計了對應算法進行求解。Zhen[9]研究了周期性到達的集裝箱班輪裝卸時長具有隨機性的策略級(tactical-level)泊位分配問題。針對裝卸時長概率分布已知和未知兩種情形分別建立了隨機規劃模型和魯棒優化模型并對這兩個模型進行了分析和比較。Turkogullari等[10]將岸橋分配數量可變的泊位和岸橋聯合問題分解為主次兩個子問題，并開發了精確算法進行求解。Zhen等[11]針對具有流量控制和潮汐影響航道的集裝箱港口制定每日操作級(operational-level)生產計劃的現實問題建立了一個整數規劃模型，為了克服問題復雜性帶來的求解難度，該模型被轉化為一個集合劃分問題并利用列生成方法進行求解。Wang等[12]將碼頭前沿泊位-岸橋分配問題和后方堆場存放空間分配問題集成到一個混合整數線性規劃模型中并基于問題特性設計了一個基于列生成方法的啟發式算法，通過對大量實際問題算例的求解驗證了算法的有效性。Jiao等[13]研究了考慮潮汐航道的連續型泊位和動態岸橋聯合調度問題，設計了遺傳算法、混合粒子群算法和混合模擬退火算法分別進行求解并對其性能進行了比較，最后通過模擬試驗分析了潮汐對泊位和岸橋利用率的影響。

周鵬飛和康海貴[14]建立了考慮船舶到港時間和服務時間隨機性的泊位和岸橋聯合調度問題并設計了一種改進的遺傳算法進行求解。董盼等[15]以船舶在港總成本最小化為目標建立了離散型泊位與岸橋集成分配混合整數規劃模型，通過實例分析了不同等待成本與裝卸成本比率以及不同可用岸橋數量設置對在港總成本的影響，并得出了最佳的等待成本與裝卸成本比率和最合適的岸橋配置數量。樂美龍和劉秀玲[16]將船舶實際靠泊位置與最優靠泊位置的偏差以及岸橋同時工作時的相互干擾這兩個因素加入到泊位-岸橋聯合調度問題中，以船舶在港時間最短為目標建立了一個混合整數線性規劃模型。模型以寧波某集裝箱港口實際數據為輸入用Gurobi軟件和一個兩階段啟發式算法進行了測試并給出了一些對企業的生產有實際價值的建議。楊華龍和滕川川[17]構建了以最大化岸橋利用率和最小化船舶在港時間為目標的非線性模型，并設計了一種啟發式自適應算法-擠壓算法進行優化求解。郝楊楊等[18]從考慮船舶等待和岸橋分配兩者公平性為出發點，擴充了現有的泊位與岸橋聯合分配模型并設計了一個三階段領域搜索算法。鄭紅星等[19]將潮汐的因素加入到泊位和岸橋聯合調度問題中，以岸橋作業成本，岸橋移動成本和船舶滯期成本之和最小化為目標建立了一個混合整數規劃模型，并用一個嵌入啟發式規則的遺傳算法進行算例求解。

2 問題描述與建模

2.1 問題描述

為了不中斷港口對外業務，集裝箱碼頭泊位疏浚工作通常按照分段分時的原則進行開展，以最大程度地使用泊位，如圖1所示，坐標系橫軸和縱軸分別代表調度時間和岸線，按照相關文獻[7,10,23]方法本文同樣將時間和岸線劃分為若干個時間段(time step)和泊位段(berth segment)，其中每個時間段為1小時，每個泊位段為50米；船舶的裝卸工作量采用Liu等[24]文中的岸橋單位時間段的裝卸量(QC-time-step)為單位進行衡量。在泊位疏浚期間船舶動態到達，到達后船舶將被分配足夠多的泊位段和岸橋工作時間段以盡快完成其裝卸任務，其中靠泊泊位段和靠泊時間不能與任何泊位段的疏浚工作沖突，岸橋分配采用動態分配模式既岸橋可以在各靠泊船舶間移動。

圖1 考慮泊位疏浚的船舶調度示意圖

本文研究將基于以下幾點基本假設：(1)船舶在泊位疏浚期間動態到達；(2)船舶對靠泊位置沒有偏好，靠泊后不能改變位置；(3)每條船舶可分配岸橋數量應在預先設定好的范圍內；(4)岸橋可以在靠泊的船舶間移動服務，但在同一個時間段內不得移動；(5)為了不影響岸橋在岸線上的布局和減少岸橋工作準備時間，限定船舶在各服務時間段間岸橋的數量變化不超過1；(6)由于物理上的限制，岸橋不能跨越式移動。

2.2 模型構建

集合類參數：

I:調度周期內所有船舶的集合，I={1,2,3,…,|I|}；Q:集裝箱碼頭岸線上所有岸橋的集合，Q={1,2,3,…,|Q|}；B:泊位段的集合，B={1,2,3,…,|B|}；K:調度周期內實施疏浚工作的泊位段序號集合，K={1,2,3,…,|K|}；T:調度周期內時間段的集合，T={1,2,3,…,|T|}。

指標類參數：

i,i′：表示船舶，i,i′∈I；q,q′：表示岸橋，q,q′∈Q；b,b′:表示泊位段，b,b′∈B；k：表示泊位疏浚位置的序號，k∈K；t,t′：表示時間段，t,t′∈T。

輸入參數：

決策變量：

(1)優化目標函數：

目標函數為最小化所有船舶的周轉時間總和。

(1)

(2)服務時間約束條件:

ai≤si,?i∈I

(2)

(3)

(4)

(5)

(6)

?i∈I,?t∈[2,|T|]

(7)

?i∈I,?t∈[1,|T|-1]

(8)

Pit≥1-M(1-Sit),?i∈I,?t∈T

(9)

Pit′+Pi,t-1-Pit≤1,?i∈I,?t∈[2,|T|),

?t′∈[t+1,|T|]

(10)

(11)

ei=si+pi-1,?i∈I

(12)

不等式(2)指船舶到達后才可以開始服務。等式(3)和(4)分別計算船舶服務的開始和結束時間。等式(5)和(6)保證船舶i只能在某一個時段t開始或結束服務。不等式(7)和(8)保證船舶i在服務開始之前或服務結束之后，均處于非服務狀態，即Pit=0。不等式(9)表示如果船舶i在t時段開始服務，則馬上處于服務狀態。不等式(10)保證船舶被服務的連續性。等式(11)和(12)分別計算船舶i的服務時長和結束時間。

(3)泊位分配約束條件:

(13)

(14)

(15)

(16)

(17)

?i∈I,?t∈T,?b∈[2,|B|),?b′∈[b+1,|B|]

(18)

yi+li-1≤|B|+M(1-Pit),?i∈I,?t∈T

(19)

(20)

(21)

?i∈I,?b∈B,?t∈[1,|T|-1]

(22)

?i∈I,?b∈B,?t∈[1,|T|-1]

(23)

?i∈I,?b∈B,?t∈[1,|T|-1]

(24)

?i∈I,?b∈B,?t∈[1,|T|-1]

(25)

(26)

yi+li-1

(27)

Yii′+Yii′≤1+M(2-Pit-Pi′t),

?i,i′∈I,i≠i′,?t∈T

(28)

Yit′+Yi′i≥1-M(2-Pit-Pi′t),

?i,i′∈I,i≠i′,?t∈T

(29)

不等式(13)表示在t時刻所有靠泊船舶的總長度不超過岸線長|B|。等式(14)表示如果t時刻船舶i在服務，其船頭一定處在某個位置。不等式(15)和(16)確定船舶i的船頭位置。等式(17)保證船舶靠泊時給其分配足夠多的泊位段。不等式(18)確保泊位分配的連續性。不等式(19)保證任意船舶的船尾不超出岸線。不等式(20)和(21)確定船舶i的船體位置范圍。不等式(22)至(25)保證船舶在服務期間不改變靠泊位置。不等式(26)表示任意泊位段在任一時刻只能分配給一艘船既保證船舶的靠泊位置不沖突。不等式(27)表示在時間-岸線圖中如果船舶i在船舶i′下方，則船舶i的船尾位置小于船舶i'的船頭位置。不等式(28)和(29)保證在時間-岸線圖中船舶i和船舶i'只能有一個在另一個的下方。

(4)岸橋分配約束條件：

(30)

(31)

(32)

(33)

(34)

(35)

?q∈[2,|Q|),?q′∈[q+1,|Q|]

(36)

?i,i′∈I,i≠i′,t∈T,?q,q′∈Q,q≠q′,

(37)

?i∈I,?t,t′∈T,t≠t′

(38)

?i∈I,?t,t′∈T,t≠t′

(39)

(5)泊位疏浚約束條件:

(44)

等式(40)表示泊位段在疏浚時不能分配給任何船舶。不等式(41)指在某泊位段疏浚工作之前開始服務的船舶若占用該泊位段，則要在該泊位段疏浚開始前結束服務。不等式(42)表示在某泊位段疏浚工作之后結束服務的船舶若占用該泊位段，則該船舶的服務開始時間一定在該泊位段疏浚完成之后。不等式(43)和(44)指當船舶i在某泊位段疏浚時還在進行服務，則其只能靠泊在該疏浚泊位段的上方或下方。

(6)決策變量取值約束:

(45)

?i,i′∈I,i≠i′,?b∈B,?t∈T,?q∈Q,?k∈K

(46)

3 算法設計

Lim[25]在1998年已經證明了泊位分配問題屬于NP-難，因此，本文所研究的考慮泊位疏浚的連續型泊位和動態岸橋聯合調度問題也是NP-難，因為它可以退化至泊位分配問題。為此，本文在被廣泛應用于組合優化問題中的遺傳算法(GA)、粒子群算法(PSO)和模擬退火算法(SA)基礎上，結合本文問題特點設計出相應的混合遺傳算法(HGA)、混合粒子群算法(HPSO)和混合模擬退火算法(HSA)。接下來本文將詳細闡述算法具體原理和解決問題的思路。

3.1 解編碼

圖2 一個6艘船舶解編碼示意圖

3.2 解編碼目標函數值計算

在本文提出的三個啟發式算法最優解搜索過程中，為了比較解的好壞，需要計算解編碼所對應的目標函數值。為此，需要完成以下3個步驟：

Step1通過BAP貪婪算法確定每艘船舶靠泊的時間和位置；

Step2通過QCAP貪婪算法為每艘船舶靠泊服務期間的每個時間段分配岸橋并判斷當前的解是否可行；

Step3如果該解可行，那么通過式(1)計算其對應的目標函數值，否則，將其目標函數值設置為充分大的正整數M，這意味著該解將在算法的迭代過程中淘汰。

3.2.1 BAP貪婪算法

為了確定每艘船舶的靠泊時間和位置，本文將泊位分配問題抽象為一個二維空間的裝箱問題，如圖1所示，可以根據泊位疏浚工作的時間和位置將它們抽象為若干個矩形先行擺放在時間-岸線空間中。根據船舶的長度和解編碼中預先生成的靠泊服務時長可以刻畫出代表每艘船舶的矩形大小，接下來為每艘船舶按照編碼中的靠泊順序依次搜尋合適的位置使其盡可能早地靠泊，以最大可能地減少船舶的周轉時間，其具體步驟如算法1所示，其中關于找尋船舶所有可能被放置的位置時本文參考了Chazelle[26]的算法。在圖3中，船舶5的到達時間為a5，其所有可能的停放位置被找到并按照從下到上從左到右的順序依次編號并嘗試停靠，最終確定位置4為符合約束的最早靠泊位置。

圖3 泊位分配示意圖

圖4 岸橋分配示意圖

3.2.2 QCAP貪婪算法

上一小節的算法確定了每艘船舶的靠泊位置和時間，接下來本文設計了一個貪婪算法確定每艘船舶在每一個服務時間段中的岸橋分配情況。如算法2中所示，每個船舶每個時間段內的岸橋數目由該時間段內所有船舶的任務緊迫程度決定，既其剩余任務量和剩余服務時間的比值在該時間段內所有船舶中所占的比重越高則給其分配的岸橋數也越多，但同時還需要滿足模型中關于岸橋分配時的一些約束。為了更好地理解該算法，圖4和表1給出一個示意圖和相應的求解過程。其中，船1～5的工作量為{8,9,15,16,19}，最大岸橋數量為{2,3,3,4,4}，distr{t,3}列中括號內為算法第24行直接求得的船舶岸橋分配數目，由于其超出了船舶可使用岸橋數目的范圍，算法又對其進行了調整。

表1 岸橋分配算法實例

算法2 求解岸橋數目可變岸橋分配問題的貪婪算法輸入:船舶靠泊時間si和位置yi輸出:船舶的岸橋分配方案和解的可行性f1f=true; 2for t=1 to|T|3 distr{t,1}=?,distr{t,2}=0,distr{t,3}=?; 4 for i =1 to|I|5 if船舶i在時間段t正在靠泊服務中6 distr{t,1}=distr{t,1}∪{i};7 distr{t,2}=distr{t,2}+1;8 endif9 endfor10endfor11for t=1 to|T|12 sum=0,avg=?,percnt=?;13 for j=1 to distr{t,2}14 i=distr{t,1}(j) ;15if船舶i在t時刻開始靠泊服務16remainconi=Ui, remaintimi=pi;//其中pi是解編碼中為船舶i預設的靠泊服務時長17endif18avgj=remainconi/remaintimi;19sum=sum+avgj;20endfor21for j=1 to distr{t,2}22 i=distr{t,1}(j) ;23percntj=avgj/sum;24distr{t,3}(j)=round(|Q|?percntj);25if distr{t,3}(j)Qmaxi29 distr{t,3}(j)=Qmaxi;30endif31調整distr{t,3}(j)使其滿足約束(38)和(39);32remainconi=remainconi-distr{t,3}(j);33remaintimi=remaintimi-1;34if remaintimi==0 and remainconi>035 f=false;36 break;37 endif38endfor39endfor

3.3 三個啟發式算法設計

本文將遺傳算法、粒子群算法和模擬退火算法的基本原理和研究問題自身特點相結合設計了相應的混合遺傳算法(HGA)、混合粒子群算法(HPSO)和混合模擬退火算法(HSA)。混合遺傳算法將上文中的兩個貪婪算法加入到適應度值的衡量中。在混合粒子群算法中，引入了遺傳算法的交叉基因操作用于每一個粒子與其自身和全種群最佳位置的信息交換過程中。混合模擬退火算法的迭代過程中需要產生新的解，本算法采用了遺傳算法中的基因變異操作。以上兩個算法在解的質量衡量時依然需要上一小節中的兩個貪婪算法。由于篇幅的原因，三種算法的基本原理不在這里贅述，請讀者參考相關文獻[27～29]。

4 仿真實驗

為了驗證本文模型的正確性并衡量求解算法的性能，本部分將進行數值模擬測試。本文的問題是一個復雜的NP-難問題，算法求解時間會隨著問題的規模呈指數級增長，CPLEX能在可接受的時間內得到小規模問題的精確解但無法解決大規模問題，所以本文分兩個部分進行測試。首先，用CPLEX和本文設計的三個算法對小規模數據進行測試；其次，針對大規模數據對三個算法進行測試并比較其各自的性能。

數值模擬測試在Intel Core i7 4790K 4.0GHz CPU，16G內存的Windows 7 個人計算機上進行，CPLEX12.6 在MATLAB 2014b中調用，三個算法也均用MATLAB 2014b編制測試。

4.1 參數設定

如2.1節所述，本文設定每個時間段為1小時，每個泊位段為50米，全部泊位段依次進行疏浚，每個泊位段的疏浚工作時長均設置為5個時間段。參照Rodriguez-Molins等[30]，船舶到港時間的間隔服從參數為2的指數分布；船舶以相同比例分為小型、中型和大型，相應的船舶參數列于表2，其中船舶長度和工作量分別以一個泊位段(berth segment)長度和一個岸橋單個時間段工作量(QC-time-step)為單位。

算法的參數設定如下：(1)混合遺傳算法種群規模為200，進化代數為150，通過實驗比較選取交叉率和變異率為0.9和0.1；(2)混合粒子群算法種群規模和迭代次數分別設置為200和150；(3)混合模擬退火算法的初始溫度和終止溫度分別設定為1000和0.001，其中每個溫度下的鏈長設置為200，降溫速率為0.9，新解接受與否的依據選擇Metropolis準則。由于三個算法具有不同的解搜索策略，為了更公平地對算法進行比較，進行大規模數據測試時不再指定相應的迭代次數而是將它們的運算時間全部設置為2000秒。另外，由于這三種算法解搜索的隨機性，下文表格中列出的解均為算法5次運行結果中的最佳解。

表2 船舶參數

4.2 小規模數據測試

表3 未考慮泊位疏浚小規模數據計算結果

表4 考慮泊位疏浚小規模數據計算結果

4.3 大規模數據測試

表5 未考慮泊位疏浚大規模數據計算結果

表6 考慮泊位疏浚大規模數據計算結果

5 結論

本文研究了泊位疏浚情況下泊位和岸橋聯合分配問題，為了更符合真實生產環境，泊位采用連續型的分配方式，岸橋允許在相鄰的船舶間進行移動。該問題被刻畫為一個以船舶周轉時間最小為目標的整數線性規劃模型并設計了混合遺傳算法(HGA)、混合粒子群算法(HPSO)和混合模擬退火算法(HSA)進行求解。通過分別對小規模和大規模數據的數值模擬測試，驗證了模型正確性并比較了三個算法的性能。

集裝箱碼頭生產調度問題十分復雜，本文在泊位岸橋聯合分配問題中并未考慮岸橋的調度優化問題以及集卡的聯合調度，這將是今后進一步的研究拓展方向。