韓笑樂， 鞠留紅， 錢麗娜， 陸志強(qiáng)

(同濟(jì)大學(xué) 機(jī)械與能源工程學(xué)院， 上海 201804)

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

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

1 問題建模與分析

1.1 泊位-堆場資源的協(xié)同分配模型

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

目標(biāo)函數(shù)為

(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

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

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

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

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

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

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

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

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

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

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

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

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

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

(27)

約束條件的數(shù)學(xué)表述可通過泊位-堆場資源協(xié)同分配模型的約束在各場景ω下擴(kuò)充得到.另外，對于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 各決策點(diǎn)的兩階段禁忌搜索

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

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

3 數(shù)值實(shí)驗(yàn)與結(jié)果

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

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

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

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

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

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

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

表1 數(shù)值實(shí)驗(yàn)結(jié)果Tab.1 Results of numerical experiments

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

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

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

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

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

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

表2 大規(guī)模下的數(shù)值實(shí)驗(yàn)結(jié)果Tab.2 Results of large scale numerical experiments

4 結(jié)語

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