集裝箱進(jìn)出口碼頭泊位-堆場(chǎng)協(xié)同分配的動(dòng)態(tài)決策

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

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

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

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

1 問(wèn)題建模與分析

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

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

1.2 動(dòng)態(tài)性分析與船舶分類(lèi)

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

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

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

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

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

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

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

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

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

(27)

約束條件的數(shù)學(xué)表述可通過(guò)泊位-堆場(chǎng)資源協(xié)同分配模型的約束在各場(chǎng)景ω下擴(kuò)充得到.另外，對(duì)于A類(lèi)船舶和決策所得的B0類(lèi)船舶，還需增加以下約束，以確保各場(chǎng)景下決策的一致性：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)語(yǔ)

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