集裝箱進出口碼頭泊位-堆場協同分配的動態(tài)決策

韓笑樂， 鞠留紅， 錢麗娜， 陸志強

(同濟大學 機械與能源工程學院， 上海 201804)

隨著海上運輸業(yè)的快速發(fā)展，集裝箱碼頭在全球物流業(yè)中的作用越來越重要.碼頭中泊位和堆場等核心資源的有效分配已成為提升其服務水平的關鍵.現有文獻大多將泊位和堆場視為相互獨立的資源進行研究[1-2]，而在碼頭的實際運營過程中，泊位與堆場間存在相互聯系和相互制約的關系，因此，近年來不少研究者開始考慮泊位與堆場資源的協同作用[3-4].另一方面，在碼頭的實際運營過程中還存在各種不確定性因素，其中船舶到港時間是最普遍的不可控因素[5-6]，其會導致碼頭作業(yè)無法準確安排、資源無法合理利用和船舶到港時間延長.Moorthy等[5]針對船舶到港時間的不確定性，將泊位分配問題與堆場問題相結合，運用模擬退火算法進行求解；Xu等[7]和Zhen等[8]在研究泊位分配問題的過程中考慮了船舶到港時間與作業(yè)時間的不確定因素；Zhen[9]在對轉運港的堆場模板進行求解的過程中考慮了時間與空間的不確定性，包括泊位位置以及在泊時間；Xiang等[10]針對到港時間及作業(yè)時間不確定條件下的泊位分配問題，考慮經濟效用及客戶滿意度，并采用自適應灰狼算法進行求解；Schepler等[11]以多終端、多模式海運集裝箱碼頭為研究對象建立了雙目標模型，以最小化集裝箱碼頭的運輸時間及船舶到港時間，并采用基于混合整數規(guī)劃分解的啟發(fā)式算法進行滾動求解；Zhen[12]從海運市場的不確定性出發(fā)，針對到港船舶裝、卸載量的波動，研究了碼頭核心資源的有效分配.在干擾環(huán)境下，為了最小化與原調度方案的偏差，Zeng等[6]采用岸橋重調度、泊位重分配的方法解決突發(fā)的干擾問題，采用局部重搜索與禁忌搜索相結合的算法進行求解；Liu等[13]將干擾恢復的重調度問題分為泊位位置、靠泊時間以及岸橋數量的分配和對每個岸橋具體調度的問題.

總之，針對不確定環(huán)境下的決策有2種方式，即前攝-反應式[8]與滾動周期式[14].前攝-反應式決策預先考慮不確定性因素，注重相對較長決策期間內決策的魯棒性；而滾動周期式決策是利用最新的信息在較短決策期間內進行滾動決策，具有更強的靈活性.區(qū)別于現有文獻，本文主要針對集裝箱進出口碼頭的泊位-堆場資源的協同分配，并兼顧決策的魯棒性與靈活性，借鑒針對復雜多階段隨機優(yōu)化過程、基于兩階段近似的決策框架[15]，將第1階段固定性決策與第2階段各場景下的可調整決策進行區(qū)分與結合，提出了定制化的動態(tài)決策方法，并驗證其有效性.

1 問題建模與分析

1.1 泊位-堆場資源的協同分配模型

圖1 泊位-堆場資源分配的相互關系Fig.1 Interrelationship of berth allocation and yard allocation

目標函數為

(1)

約束條件分別為

si≤txit+M(1-xit), ?i∈V,t∈T

(2)

ei≥txit, ?i∈V,t∈T

(3)

(4)

(5)

(6)

(7)

fi=Ai-TL, ?i∈V,t∈T

(8)

gi=ei+TD, ?i∈V,t∈T

(9)

(10)

(11)

(12)

bi≤jwij+M(1-wij), ?i∈V,j∈J

(13)

bi+Li-1≥jwij, ?i∈V,j∈J

(14)

(15)

(xit+wij-1)/2≤αijt≤(xit+wij)/2

(16)

?i∈V,j∈J,t∈T

(17)

(18)

(19)

(20)

(21)

si,ei∈{Ai,Ai-1,…,T}, ?i∈V

(22)

fi∈{-TL,TL,…,0,…,T}, ?i∈V

(23)

gi∈{Ai,Ai-1,…,T}, ?i∈V

(24)

bi∈{1,2,…,J-Li+1}, ?i∈V

(25)

(26)

?i∈V,j∈J,t∈T

目標函數(式(1))以常用的船舶總在港時間為衡量標準.式(2)～(9)定義了與船i相關的各時間決策變量，并限定其相互關系；式(10)～(12)確保了船舶及其集裝箱在港時段的連續(xù)性；式(13)～(15)定義了船i的靠泊位置決策，并確保了占用泊位區(qū)段的連續(xù)性；式(16)～(17)基于xit、wij定義了αijt，并且確保任意時段泊位區(qū)段的被占用量上限為1；式(18)～(20)基于船舶在港定義了堆場資源占用量，并確保任意時段的堆場被占用量不超過其上限；式(21)確保了各船的累計作業(yè)量滿足集裝箱裝卸需求；式(22)～(26)為決策變量的定義域.

1.2 動態(tài)性分析與船舶分類

在信息層面，碼頭和船運公司對于到港時間預估的準確性會隨時間的推移而逐漸提高.船舶的真實到達時間通常能夠提前1 d獲得；而距離更遠的船舶則只能預估到港時間的期望值，其隨機分布信息可以由場景ω描述.

在操作層面，所提出的動態(tài)決策方法是基于滾動周期機制并以1 d作為決策點的間隔的.定義周期K是從決策點k到決策點k+1的時間段.一方面，在任意周期K開始時，該周期內的到港船舶都已經確認到港時間，周期K以外的后續(xù)船舶到港時間尚不確定；而在周期K結束時，周期K+1內的到港船舶都將確認到港時間，依次類推.在一個決策周期內，新的信息將不斷被確認，但已決策的計劃不會被立即修改，而必須等到下一個決策點再次更新決策.另一方面，對于已經離港但其進口箱仍留存在堆場，以及尚未到港但其出口箱已預存堆場的船舶，其到港時間不屬于當前周期，但仍會影響當前周期內的堆場占用決策.

基于上述動態(tài)性分析，在各個滾動決策點k上，將待決策船舶分為3類，其信息和操作特性表述如下：

(1) A類.在決策點k已經開始但未完成作業(yè)，包括某些在周期K-1前到港和在周期K-1內到港.A類船舶不需要進行決策，直接按照已有計劃繼續(xù)作業(yè).

(2) B類.在決策點k尚未開始作業(yè)但會在周期K內到達.對B類船舶引入0或1的決策變量ui作為延遲判定因子，因其中某些船會在周期K內開始作業(yè)(ui=1，歸入B1子類)，某些船會延遲到下一周期重新做出決策(ui=0，歸入B0子類).B0類船舶需要決策其資源分配并予以執(zhí)行，而B1類船舶則與C類船舶進行同樣操作.

(3) C類.在周期K+1至K+[TL/24 h]內到達.C類船舶與B1類船舶一起可決策場景ω下的資源分配，但其在周期K內不需要執(zhí)行，并保留在周期K+1內調整的權利.

2 決策框架與優(yōu)化算法

2.1 基于兩階段近似的動態(tài)決策框架

各決策點k的兩階段近似優(yōu)化模型的邏輯架構如圖2所示.其中，將現有參數作為第1階段的確定信息和第2階段不確定場景下的隨機參數.在決策對象中，第1階段的固定性決策ξk需要在本周期內執(zhí)行，而第2階段的可調整決策ξk+1,ω用于輔助評估第1階段決策的預決策，不需要在本周期內執(zhí)行，后續(xù)周期隨著信息的不斷更新而確認，仍可做出相應地調整.因此，決策點k的目標函數也包括了第1階段的固定成本z(ξk)，以及第2階段各場景下可調整成本的期望值EΩ[z(ξk+1,ω|ξk)].

圖2 兩階段近似優(yōu)化模型的邏輯架構Fig.2 Logic structure of two-stage approximation model

目標函數沿用式(1)的船舶總在港時間，但綜合第1階段的固定性時間以及第2階段各場景下的可調整期望時間，即

(27)

約束條件的數學表述可通過泊位-堆場資源協同分配模型的約束在各場景ω下擴充得到.另外，對于A類船舶和決策所得的B0類船舶，還需增加以下約束，以確保各場景下決策的一致性：

(28)

(29)

(30)

-Mui≤si,ω-si,1≤Mui

(31)

?i∈VB,ω∈Ω

M(ui-1)≤si,ω-Tk+1≤Mui

(32)

?i∈VB,ω∈Ω

-Mui≤bi,ω-bi,1≤Mui

(33)

?i∈VB,ω∈Ω

2.2 各決策點的兩階段禁忌搜索

由于各決策點的兩階段近似優(yōu)化模型包含隨機場景，在實際算例規(guī)模下很難使用商用求解軟件(如Cplex軟件)直接求解，所以本文基于圖2的邏輯架構提出兩階段禁忌搜索(TS)算法，其框架如圖3所示.其中，外層TS1和內層TS2(ω)分別搜索第1階段的固定性決策ξk和第2階段各場景ω下的可調整決策ξk+1,ω.在編碼和搜索中，均采用待決策船舶優(yōu)先級來編碼；鄰域生成通過互換(Swap)操作進行，禁忌對象為上一步移動的互換操作，禁忌次數在禁忌上限與禁忌下限之間隨機生成，并循環(huán)進行禁忌搜索直至最大循環(huán)次數.在解碼和評價中，均采用首個適合(First fit)的解碼方式，按照當前優(yōu)先級的順序，依次為船舶分配最早可用的資源；以TS1層的當前決策作為TS2(ω)層的輸入，TS2(ω)層的當前決策則用于TS1層的評價.

在解碼過程中，B類船舶自然地被劃分為2類：若能夠在當前決策周期內安排并開始作業(yè)，則為B0類；否則，將被延遲到下一個周期重新決策，即為B1類.這種分類作為第1階段的固定性決策，是在解碼過程中自然區(qū)分的.相較于顯式指定類別，這種隱式指定降低了不可行解或較差解出現的可能性.若指定太多的B0類船舶，則部分B0類船舶可能無法被安排在周期K而造成不可行解；反之，則可能導致周期K的資源利用不足與浪費.

3 數值實驗與結果

本文基于Zhen等[16]研究中的參數配置生成隨機算例.生成小、中、大3種問題規(guī)模，對應的每周到港船舶數V分別為20、30、40.考慮到進、出口港與中轉港運營的差異性，設置堆場的名義利用率約為50%，即小、中、大問題規(guī)模下的堆場容量分別為 27 000、39 000、54 000 TEU，并設置各船的進口箱占比服從均勻分布，即U[0.2,0.8].

按照本文所提出的動態(tài)決策框架依次進行連續(xù)7個周期的決策.其中，C類船舶的到港時間延遲量服從分布U[0,10] h，依此生成樣本規(guī)模為30的場景池，即|Ω|=30；船舶真實到港時間獨立于所生成的場景.在小、中、大問題規(guī)模下，分別生成10個隨機算例.對于每個算例，設計如下4個對比實驗：

實驗1(Cplex軟件) 在確定性環(huán)境下，基于完全后驗信息，使用Cplex軟件單次求解第1階段優(yōu)化模型，包含7個周期.

實驗2(禁忌搜索) 在確定性環(huán)境下，基于完全后驗信息，使用簡化的動態(tài)決策框架，即單次求解兩階段近似優(yōu)化模型，其中兩階段禁忌搜索的第1、第2階段決策區(qū)間分別包含第1個周期及6個后續(xù)決策周期.

實驗3(動態(tài)決策) 在不確定性環(huán)境下，基于隨機場景信息，使用動態(tài)決策框架，即按照周期滾動求解兩階段近似優(yōu)化模型，在各周期中采用兩階段禁忌搜索.

實驗4(前攝-反應決策) 在不確定性環(huán)境下，基于無延遲的準點到港信息，采用實驗2的方法生成初始計劃，并采用右移(Right-shift)策略應對執(zhí)行過程中的實際延遲.

實驗2與實驗1采用完全相同的信息進行后驗優(yōu)化，但其簡化了所提動態(tài)決策框架下的兩階段禁忌搜索，各規(guī)模下的p1的均值均在4%以內，其z2值與實驗1中Cplex軟件的最優(yōu)解或低界值很接近，從而驗證了禁忌搜索算法的有效性，且其運算時間具有顯著優(yōu)勢.

表1 數值實驗結果Tab.1 Results of numerical experiments

實驗3采用所提出的動態(tài)決策框架，在各規(guī)模下的p2的均值分別為4%、3%和2%，可見第2階段決策中針對已知的隨機場景信息做出可調整決策，可以有效應對不確定性因素的影響，獲得更好的第1階段固定決策，從而增強多階段決策的后驗優(yōu)化.

實驗4采用與實驗3相同的不確定性環(huán)境，并用典型的前攝-反應決策方式.相比而言，動態(tài)決策框架所獲在各規(guī)模下的p3的均值分別為7%、4%和4%，可見其充分利用了已知隨機場景信息的必要性和有效性.

為了驗證在更大規(guī)模下數值實驗的效果，本文在V=50,60的條件下進行數值實驗，所得結果見表2.其中，p4=(z3-z2)/z2.

由于Cplex軟件在V=40時已經出現較多算例無法在可接受時間內求得精確解的問題，所以在更大規(guī)模下不進行實驗1的求解.實驗2是基于完全后驗信息下采用所提出的簡化兩階段禁忌搜索算法進行求解的，由表1可見其與實驗1所求的解足夠接近，因此，在更大規(guī)模下以實驗2作為對比對象.

在V=60時，實驗3在不確定環(huán)境下采用所提出的動態(tài)決策框架進行求解，所得結果與實驗2的結果基本一致，其p4值均為0；而實驗4與實驗3的不確定環(huán)境相同，采用前攝-反應決策方式，相比而言，所提出的動態(tài)決策框架(實驗3)在V=50，60下對z的改善程度(p3值)分別為7%和4%.

對更大規(guī)模的實驗數據進行分析表明，所提出的基于隨機場景的動態(tài)決策框架及兩階段禁忌搜索算法能夠在各規(guī)模下有效地應對不確定性因素.

表2 大規(guī)模下的數值實驗結果Tab.2 Results of large scale numerical experiments

4 結語

本文針對集裝箱進出口碼頭泊位-堆場的調度問題，提出多階段隨機決策過程的兩階段近似、設計兼顧魯棒性與靈活性的動態(tài)決策框架.一方面，通過判斷并延遲B1類船舶的決策，充分發(fā)揮了準確信息的作用；另一方面，通過隨機場景下的第2階段可調整決策，充分利用了最新獲得的不確定性信息.同時，通過數值實驗中的不同策略對比，驗證了所提方法的有效性.后續(xù)研究將考慮更復雜的不確定性環(huán)境，如裝卸載箱量和天氣等影響的因素.