周期環(huán)境下集裝箱碼頭資源分配的動態(tài)干擾管理

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

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

在集裝箱進(jìn)出口碼頭，泊位堆場作為關(guān)鍵資源相互制約又緊密聯(lián)系，因此如何有效分配成為提升碼頭作業(yè)效率的關(guān)鍵.在研究初期，眾多學(xué)者關(guān)注于單類資源的調(diào)度分配.Bierwirth等[1-2]及Carlo等[3]分別對海側(cè)和堆場方面的現(xiàn)有研究進(jìn)行了綜述整理.隨著研究的發(fā)展，多資源協(xié)同調(diào)度逐漸成為研究的趨勢[4-8].

為了方便集裝箱的運(yùn)輸管理，船運(yùn)公司往往會定期訪問相關(guān)碼頭(一般按周)，即船舶的到港具備周期性的特征.依據(jù)船舶到港的周期性特征，碼頭依照船運(yùn)公司所給定的預(yù)計到港時間對船舶進(jìn)行作業(yè)資源預(yù)安排，即制定中長期模板，其具有周期重復(fù)性及穩(wěn)定性的特征.模板的周期重復(fù)性指的是模板計劃在一定周期內(nèi)重復(fù)，簡化執(zhí)行過程中周期與周期間的資源分配變動；穩(wěn)定性體現(xiàn)在每個周期的模板均與上一周期相同，便于碼頭提前安排作業(yè).通常情況下，碼頭會依據(jù)模板的資源安排對到港船舶進(jìn)行作業(yè)分配.而實(shí)際作業(yè)中各種不確定因素不可避免，如惡劣天氣，作業(yè)故障，設(shè)備停機(jī)等.一旦干擾事件發(fā)生，會擾亂模板的執(zhí)行情況，使得碼頭管理人員不得不對現(xiàn)有計劃進(jìn)行調(diào)整，甚至重新安排，造成實(shí)際執(zhí)行的計劃與模板的相差過大，原有的作業(yè)計劃意義降低，增加了碼頭的作業(yè)負(fù)擔(dān).

干擾管理是對干擾事件發(fā)生后的應(yīng)急處理方式，保證以盡量小的擾動恢復(fù)系統(tǒng)的正常運(yùn)作.與重調(diào)度相比更注重于減小與原有模板之間的偏差.干擾管理作為實(shí)時處理干擾事件的方法逐漸受到學(xué)術(shù)界的關(guān)注.Zeng等[9]在集裝箱碼頭的泊位分配問題的基礎(chǔ)上，建立干擾管理模型，并采用仿真優(yōu)化的方式進(jìn)行求解.Zeng等[10]通過岸橋重調(diào)度及泊位重分配應(yīng)對突發(fā)的中斷現(xiàn)象，以最小化延遲成本以及最優(yōu)泊位的懲罰成本作為目標(biāo)函數(shù).Li等[11]對集裝箱碼頭的泊位與岸橋建立干擾管理模型，采用反應(yīng)恢復(fù)策略，在這種策略下，泊位被限制在一定的空間范圍內(nèi)，岸橋能夠在船舶之間轉(zhuǎn)移，目的在于使得碼頭的服務(wù)質(zhì)量最大化的前提下降低調(diào)整成本.Liu等[12]將干擾恢復(fù)的重調(diào)度問題分為兩部分執(zhí)行，包括第一部分泊位位置、靠泊時間以及岸橋數(shù)量的分配和第二部分對每個岸橋的具體調(diào)度.Gui等[13]研究由于船舶的延遲或者計劃到港但取消到港或者未在計劃中的船舶臨時到港等干擾因素對泊位調(diào)度的影響，提出了基于人機(jī)交互的鄰域搜索，依照干擾的類型影響程度等生成初始解，并且在迭代過程中進(jìn)行修正.針對于集裝箱碼頭，Li等[14]考慮由于船舶延遲造成的干擾因素，基于干擾管理提出了調(diào)整框架，并采用自適應(yīng)的遺傳算法以及計算機(jī)仿真優(yōu)化的方式進(jìn)行求解.Umang等[15]以散貨港作為研究對象，在已知泊位調(diào)度模板的前提下，從干擾恢復(fù)的角度，對泊位分配的實(shí)時恢復(fù)進(jìn)行研究.Umang等[16]考慮船舶的到港時間以及作業(yè)時間不確定性，假設(shè)船舶預(yù)計到港信息隨著時間動態(tài)更新，以滾動計劃的形式求解泊位分配問題,目標(biāo)函數(shù)是最小化實(shí)時的計劃成本，提出了基于集合劃分和智能貪婪算法的優(yōu)化恢復(fù)算法對問題進(jìn)行實(shí)時的求解.

本文基于碼頭的實(shí)際作業(yè)特性，從動態(tài)干擾管理的角度出發(fā)，借鑒并使用針對復(fù)雜多階段隨機(jī)優(yōu)化過程的、基于二階段近似優(yōu)化模型的決策框架[17]，提出泊位-堆場的協(xié)同動態(tài)干擾恢復(fù)模型，基于滾動周期的動態(tài)決策框架，且在各周期決策點(diǎn)，提出兩階段決策框架.一方面預(yù)先考慮不確定因素，對后續(xù)若干周期的作業(yè)進(jìn)行隨機(jī)場景下的預(yù)調(diào)度，增強(qiáng)當(dāng)前周期執(zhí)行計劃的魯棒性；另一方面充分利用不斷更新的確定性信息和最新掌握的不確定信息，將部分調(diào)度決策延遲，并保留前述預(yù)調(diào)度在下一決策點(diǎn)修改的權(quán)利，提高決策的靈活性.

1 問題描述與決策框架

1.1 周期性泊位堆場資源協(xié)同分配

基于碼頭的實(shí)際作業(yè)，現(xiàn)對問題做如下設(shè)定：考慮連續(xù)型泊位；船舶動態(tài)到港并具有周期性，且模板已定；其他資源不受限制，所有船舶均能以預(yù)定的速度進(jìn)行作業(yè)，堆場內(nèi)集裝箱數(shù)量的改變可以瞬間完成；船舶到港前出口箱需要提前在堆場預(yù)留，船舶離港后進(jìn)口箱需要留存一定時間，且設(shè)定預(yù)留與留存時間相等；時間軸和泊位長度分別作離散化處理，離散單位分別為4 h和50 m.如表1所示為參數(shù)及決策變量.

表1 參數(shù)及決策變量Tab.1 Parameters and decision variables

依照以上定義的參數(shù)與決策變量及周期性環(huán)境下的泊位堆場資源分配在時間上的關(guān)聯(lián)，將“泊位-時間”與“堆場-時間”置于同一張圖，具體如圖1所示.在“泊位-時間”分配圖中，中間白色矩形表示船舶的作業(yè)時間及泊位占用，如果兩個矩形之間相互重疊，表示這兩艘船在時間或空間上存在一定的沖突，在實(shí)際作業(yè)過程中不允許發(fā)生的；而淺灰色矩形的長度表示船舶作業(yè)開始時間與到達(dá)時間之差，即船舶的作業(yè)延遲等待時間；深灰色矩形分別表示船i需要提前或延后占用堆場的時間.而在“堆場-時間”分配圖中，描述了本周期內(nèi)由于船舶的裝卸載作業(yè)，堆場集裝箱庫存的變化情況，包括出口箱提前存放到堆場到進(jìn)口箱留存時間結(jié)束離開堆場整個過程中堆場集裝箱數(shù)量的波動情況.

此外,由于周期性的存在，在實(shí)際作業(yè)中每個周期均可能存在尚未完成作業(yè)的船舶，這將占用部分下一周期的資源，即還需要考慮其他周期船舶對本周期資源占用的情況，因此設(shè)置虛擬船舶應(yīng)對這些跨周期船舶的資源占用問題.虛擬船舶當(dāng)前周期的調(diào)度計劃中并非真實(shí)存在，而只用作碼頭資源的提前占用.圖中虛線部分即為本周期內(nèi)的虛擬船舶，其資源占用包括上一周期未完成作業(yè)以及下一周期需要提前存放的集裝箱的船舶造成的.

圖1 周期性泊位堆場分配示意圖Fig.1 Interrelationship between berth-yard resourceallocation in periodic environment

1.2 干擾環(huán)境下動態(tài)決策框架

由于船舶的到港時間及市場需求的不確定是大多數(shù)干擾事件的源頭，且其不確定性隨著時間的推移準(zhǔn)確度越高，越靠近船舶的期望到達(dá)時間，碼頭對其掌握的信息越準(zhǔn)確.一旦船舶離開上個港口，其集裝箱的裝卸載量已定，但與模板制定時會有一定差異.而到港時間的不確定僅存在于部分船舶中，其余到港時間與所制定的模板相同，且船舶的準(zhǔn)確到港時間能夠提前一天準(zhǔn)確獲得.

依據(jù)已知參數(shù)以及所需決策的變量，將一定時間內(nèi)到港的船舶分為以下3類(其中周期k的是從時間點(diǎn)k到時間點(diǎn)k+1的時間段),如圖2所示.

(1)A類：在決策點(diǎn)k時已經(jīng)開始但未完成作業(yè).(船0、船1)

(2)B類：在決策點(diǎn)k尚未開始作業(yè)，但將在k周期內(nèi)到達(dá).包括某些會在周期k內(nèi)開始作業(yè)(船3、船4、船5), 某些預(yù)計會延遲到下一周期(船6、船2).

(3)C類：在k+1～k+TL(k+3)周期內(nèi)到達(dá)(船7、船8、船9、船10、船11、船12、船13).

圖2 周期k碼頭決策示意圖Fig.2 An example of vessel scheduling planning at k

不同類型船舶將執(zhí)行不同的決策方式：A類船的作業(yè)已經(jīng)開始，因此不需要進(jìn)行決策，按照其上一周期所分配的資源繼續(xù)作業(yè).B類船引入決策延遲判斷因子ui，用于判斷該船舶是否需要被延遲到下一周期重新做決策，若延遲則令ui=1，否則ui=0.依照ui的取值，將B類船分為B0和B1兩類，對于B0類船，需要進(jìn)行第一階段的固定性決策，決策量包括作業(yè)開始時間si、作業(yè)結(jié)束時間ei、泊位位置bi和進(jìn)口箱堆場留存截止時間gi.而B1類船和C類一樣，在本階段需要進(jìn)行各場景下的可調(diào)整預(yù)決策，并且在后續(xù)階段保留修正的權(quán)利.

1.3 各階段滾動機(jī)制

假設(shè)圖2為周期k時碼頭管理人員所做的決策示意圖，在決策點(diǎn)時，船0和船1已經(jīng)開始作業(yè)，因此在本周期內(nèi)不需要對其決策，將被分為A類船.船2、3、4、5、6作為能夠在該周期內(nèi)到達(dá)的船舶，并不是所有船都能夠在本周期內(nèi)被安排開始作業(yè).按照該優(yōu)先級列表進(jìn)行作業(yè)安排，2、6號船將被延遲到下周期重新決策.其余預(yù)計在k+4前到港的船舶將被分為C類，將于B1類船一起決策，但并不在該周期內(nèi)執(zhí)行.

在周期k+1開始前，周期k所做的決策已經(jīng)執(zhí)行完畢，相關(guān)信息也已經(jīng)更新.假設(shè)圖3是周期k+1碼頭管理人員所做的決策示意圖.圖2與圖3的對比，可以明確的了解滾動的機(jī)制，具體如表2所示.

為了更好描述干擾情況下的動態(tài)更新過程，現(xiàn)以以下4船作為例子進(jìn)行說明，各參數(shù)如表3所示.船2由于干擾事件，其到港時間需要延遲13h，導(dǎo)致其不能按照模板開始作業(yè)，針對如上干擾，分別對時刻0及時刻24的作業(yè)安排如表4所示.

表2 動態(tài)更新機(jī)制Tab.2 Dynamic update mechanism

圖3 周期k+1碼頭決策示意圖Fig.3 An example of vessel scheduling planning at k+1表3 示例船舶參數(shù)Tab.3 Parameters of example vessels

船舶編號預(yù)計到港時間點(diǎn)模板開始時間點(diǎn)真實(shí)到港時間點(diǎn)模板作業(yè)時間/h真實(shí)作業(yè)時間/h11313138922020331010323252398430303078

2 二階段近似優(yōu)化模型

基于前述參數(shù)和決策的動態(tài)性分析，建立決策點(diǎn)k的二階段優(yōu)化模型，以最小化與模板的偏差作為計劃調(diào)整成本作為目標(biāo)函數(shù)，包括對應(yīng)的第一階段固定性成本以及第二階段各場景下的可調(diào)整期望成本.在各個場景ω中補(bǔ)充參數(shù)，并對決策變量進(jìn)行更新.修正后的參數(shù)及變量設(shè)置如表5所示.

表4 各時刻作業(yè)安排表Tab.4 Scheduling planning at each time point

依據(jù)以上更新的參數(shù)及決策變量，同時結(jié)合問題的描述及已知的周期性模板，對決策點(diǎn)k建模如下：

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

(1)

約束條件：

-Mui≤si,ω-si,1≤Mui,?i∈VB,ω∈Ω

(2)

M(ui-1)≤si,ω-Tk+1≤Mui,?i∈VB,ω∈Ω

(3)

-Mui≤bi,ω-bi,1≤Mui,?i∈VB,ω∈Ω

(4)

si,ω=sR,i,?i∈VA,ω∈Ω

(5)

fi,ω=fR,i,?i∈V,ω∈Ω

(6)

bi,ω=bR,i,?i∈VA,ω∈Ω

(7)

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

(8)

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

(9)

fi,ω≤tyL,it,ω+M(1-yL,it,ω),

?i∈V,t∈T,ω∈Ω

(10)

ei,ω≥tyL,it,ω,?i∈V,t∈T,ω∈Ω

(11)

si,ω≤tyD,it,ω+M(1-yD,it,ω),?i∈V,t∈T,ω∈Ω

(12)

gi,ω≥tyD,it,ω,?i∈V,t∈T,ω∈Ω

(13)

(14)

表5 修正參數(shù)及變量設(shè)置Tab.5 Modified parameters and decision variables

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

(15)

(16)

(17)

(18)

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

(19)

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

(20)

(21)

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

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

(22)

(23)

γD,it,ω=yD,it,ωND,i,?i∈V,t∈T,ω∈Ω

(24)

γL,it,ω=yL,it,ωNL,i,?i∈V,t∈T,ω∈Ω

(25)

(26)

(27)

si,ω,ei,ω∈{Ai,…,T},?i∈V,ω∈Ω

(28)

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

(29)

gi,ω∈{Ai,…,T},?i∈V,ω∈Ω

(30)

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

(31)

xit,ω,yD,it,ω,yL,it,ω,wij,ω,αijt,ω∈{0,1},

?i∈V,t∈T,ω∈Ω

(32)

ui∈{0,1},?i∈VB

(33)

為了保持碼頭作業(yè)安排的穩(wěn)定性，在每個決策周期考慮目標(biāo)函數(shù)(1)最小化與已知模板的偏差，包括時間及空間上的偏差值.由于在模板制定以及真實(shí)執(zhí)行過程中存在市場需求的不確定性，其作業(yè)時間會存在一定的偏差，因此以作業(yè)結(jié)束時間的偏差作為時間偏差的衡量，而空間上的偏差則以泊位差異來體現(xiàn)，依據(jù)Umang[16]，時間與空間偏差的比例為500 m相當(dāng)于1 h，因此按照現(xiàn)有的單位精度λ=0.025.

3 雙層嵌套禁忌搜索算法

在決策點(diǎn)k上的二階段近似優(yōu)化問題可以看作是基于場景的混合整數(shù)規(guī)劃模型，依照該模型的特點(diǎn)及決策邏輯，提出了雙層嵌套動態(tài)禁忌搜索(Tabu Search，TS)框架，包括在第一階段需執(zhí)行的固定性決策ξk及第二階段各場景下的可調(diào)整決策ξk+1，其步驟如下：

獲取初始優(yōu)先級列表L0:L*∶=L0

TS1開始

構(gòu)建集合N(L*)：隨機(jī)更換B類船在列表的順序?[L](首個循環(huán)包括L*)

對所有的L∈N(L*)，若Π(L)未禁忌

對于所有場景ω

TS2 開始

TS2結(jié)束，返回ξk當(dāng)前場景下的成本

重復(fù)所有場景，返回ξk的期望成本

找出l∈N(L*)，具有最小成本

找出L*∶=l，更新禁忌表1，迭代，再次構(gòu)建N(L*)

TS1結(jié)束

3.1 TS1：第一階段固定性決策

依據(jù)1.2中對船舶的分類，生成優(yōu)先級列表L，如圖4所示.

圖4優(yōu)先級列表L

Fig.4PrioritylistLforvessels

不同類型的船舶，其在TS1中所需的決策不同，因此位于列表的位置不同.

(1)A類：作業(yè)已安排，不需要在該階段決策，因此位于編碼列表的最高優(yōu)先級位置.

(2)B類：其準(zhǔn)確到港時間已知，在本階段需執(zhí)行固定性決策，因此其位于編碼列表的第二優(yōu)先級位置.

(3)C類：到港時間存在干擾的可能性，在第一階段不進(jìn)行決策.因此位于列表的最后.

初始列表L0采用經(jīng)驗(yàn)式生成方式：以EDD原則排序A類船，隨后按照FCFS的原則排序剩余B、C.

在本階段需要做決策的主要是B類船，因此第一階段的領(lǐng)域生成方式為對B類船進(jìn)行單項(xiàng)互換操作，即初始列表L0的基礎(chǔ)上隨機(jī)選取兩艘B類船更換其在列表上的位置，生成搜索領(lǐng)域N(L).禁忌對象為上一步移動的互換操作，禁忌次數(shù)在上限tabu_max和下限tabu_min間隨機(jī)生成.循環(huán)進(jìn)行禁忌搜索直至最大循環(huán)次數(shù)Iter_max.

解碼過程中，依照優(yōu)先級順序，以首次適應(yīng)(First Fit)原則，考慮剩余可用泊位位置以及堆場的容量，依次將船舶添加到當(dāng)前的部分計劃中.在解碼過程中，B類船會被劃分為兩類：B0類計劃能夠在當(dāng)前決策周期內(nèi)安排并開始作業(yè)(令ui=0)；而B1類船無法在該周期內(nèi)安排作業(yè)，將被延遲到下一周期重新決策(令ui=1).對于B0類船來說，在該階段已經(jīng)做了固定性的決策，包括其船舶靠泊位置，作業(yè)開始時間等關(guān)鍵決策變量，需要在該階段實(shí)際執(zhí)行，該計劃一旦決策，則無法更改.而B1類船由于將被延遲到下一周期重新做決策，因此在該周期B1類船相當(dāng)于C類船，需進(jìn)行在各個場景下的第二階段調(diào)整性決策，具體解碼過程如下：

TS1：

對于所有L中的船

(1)A類：保留si，ei，bi，fi，gi，并從k點(diǎn)開始繼續(xù)作業(yè)

(2)B類：保留fi，并且在k～k+1之間，尋找最早開始時間s，確定對應(yīng)的e，g，保證在s～g之間內(nèi)堆場資源能夠滿足；以及找到可行且最小的泊位b，若能找到，則令ui=0,si=s,ei=e,bi=b,gi=g，否則ui=1.

(3)C類：跳過

3.2 TS2(ω)：第二階段可調(diào)整決策

第二階段主要基于場景ω對B1及C類船進(jìn)行調(diào)整性預(yù)決策.其優(yōu)先級列表L2(ω)由B1和C類船構(gòu)成，如圖5所示，且基于單項(xiàng)互換操作生成搜索鄰域N(ξk+1,ω).

圖5場景ω下優(yōu)先級列表L2(ω)

Fig.5PrioritylistL2(ω)forvesselsinscenarioω

在場景ω下，采用首次適應(yīng)原則依次按照優(yōu)先級列表將B1與C類船添加到已有的計劃中.在各個場景下補(bǔ)充ξk得到第二階段的鄰域解ξk+1.在本階段中，B1與C類船的決策量均獨(dú)立于各場景ω，但均補(bǔ)充自同一個第一階段固定性決策.第二階段禁忌的對象仍為上一步移動的操作，禁忌次數(shù)在上限tabu_max和下限tabu_min間隨機(jī)生成.

TS2

對所有場景ω所有L2中的船

(1)B1類，保留fi，從時間k+1找最早開始時間sω，確定對應(yīng)的eω，gω，保證在s～g之間內(nèi)堆場資源能夠滿足，以及找到可行且最小的泊bω.

令si,ω=sω，ei,ω=eω，bi,ω=bω，gi,ω=gω.

(2)C類，保留fi，從Ai,ω開始，尋找最早開始時間sω，確定對應(yīng)的eω，gω，保證在s～g之間內(nèi)堆場資源能夠滿足，以及找到可行且最小的泊位bω.

令si,ω=sω，ei,ω=eω，bi,ω=bω，gi,ω=gω.

4 數(shù)值實(shí)驗(yàn)

采用Zhang[18]和Zhen[19]研究中的算例用于數(shù)值實(shí)驗(yàn)測試.將船舶分為三類，包括小船(Feeder)、中船(Medium)、大船(Jumbo)，分別占總量的三分之一.假設(shè)岸橋資源不構(gòu)成瓶頸，各船分配的岸橋數(shù)取其平均值，大中小船分別設(shè)置為2、3、4.5.設(shè)置小、中、大三種規(guī)模算例，其每周到港船舶數(shù)分別為20、30、40，基于Zhen[20]設(shè)置不同規(guī)模下碼頭可用資源量.同時考慮到進(jìn)出口港與轉(zhuǎn)運(yùn)港運(yùn)作上存在差異，設(shè)置堆場的名義利用率在50%左右，即小、中、大規(guī)模下堆場容量分別設(shè)置為27 000、39 000、54 000TEU(Twenty foot Equivalent Unit，20英尺標(biāo)準(zhǔn)集裝箱)；并設(shè)置各船的進(jìn)口箱占比服從均勻分布U[0.2,0.8].

船舶的周期性作業(yè)模板已定，且假設(shè)每個周期內(nèi)隨機(jī)選取發(fā)生干擾的船舶占總船舶數(shù)量的20%.設(shè)定除干擾船舶到港時間存在不確定性，其余船舶準(zhǔn)確到港時間已知.通過生成隨機(jī)到港時間場景體現(xiàn)干擾現(xiàn)象，其延遲時間在[20 h，30 h]內(nèi)隨機(jī)選取，且隨著時間的接近其準(zhǔn)確度越高，不同時間段的到港時間分別與其準(zhǔn)確到港時間偏差分布服從均勻分布[-12 h,12 h]，[-8 h,8 h]，[-4 h,4 h]，針對出現(xiàn)的干擾現(xiàn)象，設(shè)置場景池，場景池的大小為2 000，每個算例從中選取30個場景(Ω=30)并取其期望值作為目標(biāo)函數(shù).由于市場需求的不確定性，所有船舶的實(shí)際作業(yè)時間與模板中的作業(yè)時間存在一定偏差，其服從均勻分布[-4 h,4 h].

由于船舶本身的到港具有周期性，在每個周期均會存在部分船舶作業(yè)需要延續(xù)到下周期，針對這些“跨周期”的船舶，在實(shí)際調(diào)度過程中需要將其資源考慮到當(dāng)前周期的資源分配中.在首個決策周期中，將模板中的跨周期船舶設(shè)置為虛擬船舶作為A類船，其不參與決策過程，但是在本周期有一定的資源占用.

現(xiàn)設(shè)置測試環(huán)境如下：

(1)部分后驗(yàn)信息下，考慮周期性模板，以最小化加權(quán)偏差為目標(biāo)函數(shù)，采用商用求解軟件CPLEX滾動求解近似二階段優(yōu)化模型.

(2)干擾環(huán)境下，考慮周期性模板，以最小化加權(quán)偏差為目標(biāo)函數(shù)，基于隨機(jī)場景信息，使用動態(tài)決策框架，滾動求解二階段近似優(yōu)化模型，在各決策周期內(nèi)采用雙層嵌套禁忌搜索.

(3)干擾環(huán)境下，不考慮周期性模板，以最小化船舶在港時間為目標(biāo)函數(shù)，使用提出的動態(tài)決策框架，滾動求解二階段近似優(yōu)化模型，在各決策周期內(nèi)采用雙層嵌套禁忌搜索.

(4)干擾環(huán)境下，基于周期性模板，保持泊位位置不變的前提下，以最小化船舶在港時間為目標(biāo)函數(shù)，采用右移策略(right shift)應(yīng)對干擾事件.

其中由于周期性模版是已知的，因此在數(shù)據(jù)測試中，小規(guī)模的模板由CPLEX求解3 h獲得的最優(yōu)解或者高界.而中大規(guī)模由于CPLEX無法獲得較理想的可行解，因此，采用確定環(huán)境下的簡化TS獲得.

每組實(shí)驗(yàn)均通過10組隨機(jī)數(shù)組進(jìn)行測試，在C#(Visual Studio 2013)語言環(huán)境下編程，測試平臺為Intel Xeon E5-1650 v3處理器，3.50GHz主頻，16G內(nèi)存，實(shí)驗(yàn)結(jié)果見表6.其中“-”表示無法求得可行解.Obj=Δe+Δb0.025；差異=(Obj2-Obj1)/Obj1；改善1=(Obj3-Obj2)/Ob3j；改善2=(Obj4-Obj2)/Obj4.

實(shí)驗(yàn)1在部分后驗(yàn)的前提下，已知決策當(dāng)天及后續(xù)3 d的船舶準(zhǔn)確到港時間，并采用CPLEX進(jìn)行滾動求解，在實(shí)際中是無法實(shí)現(xiàn)的理想情況.在中小規(guī)模下能夠基本上求得相應(yīng)最優(yōu)解，但在大規(guī)模CPLEX在某一循環(huán)周期中無法在5 h內(nèi)獲得可行解.總的來說運(yùn)算時間較長，中小規(guī)模下平均求解時間分別在150 min、694 min.

實(shí)驗(yàn)2在存在干擾的前提下，滾動調(diào)用所提出的TS求解二階段近似優(yōu)化模型，相比較于實(shí)驗(yàn)1在部分后驗(yàn)前提下采用CPLEX滾動求解，中小規(guī)模下平均差異均為10%，其差異的差值體現(xiàn)了第二階段準(zhǔn)確信息的價值及重要性，側(cè)面體現(xiàn)抽樣場景與真實(shí)值之間的差異.由于實(shí)驗(yàn)1是基于部分后驗(yàn)信息且采用CPLEX求解精度較高，相比較于實(shí)驗(yàn)2的第二階段采用抽樣樣本，其10%的差異在可接受范圍內(nèi).同時由于CPLEX針對各規(guī)模的求解時間較長，

表6 數(shù)值實(shí)驗(yàn)匯總表Tab.6 Results of numerical experiments

實(shí)驗(yàn)2在求解質(zhì)量可接受的前提下提升了求解速度，在各規(guī)模下的平均求解時間分別為：0.22 min，1.87 min，18.75 min.同時CPLEX在大規(guī)模問題無法在5 h之內(nèi)滾動求得可行解，體現(xiàn)了所提出求解框架與算法在求解效率上的優(yōu)勢.

為了證明周期性模板在作業(yè)執(zhí)行中的穩(wěn)定作用，設(shè)計實(shí)驗(yàn)3進(jìn)行驗(yàn)證.實(shí)驗(yàn)3在不考慮模板的前提下，以作業(yè)效率最小化總在港時間為目標(biāo)，最后將作業(yè)計劃與模板進(jìn)行偏差比較，各規(guī)模下與實(shí)驗(yàn)2的改善分別為14%，4%，8%，顯示周期性模板在維持船舶作業(yè)穩(wěn)定性上的作用.分別從時間與空間單角度偏差出發(fā)，其各規(guī)模平均均比實(shí)驗(yàn)2(采用周期性模板)差異值大，兩者在各規(guī)模下時間偏差值在16%，2%，5%，其空間偏差值分別為30%，24%，24%.無論從整體偏差還是時間空間單角度偏差上均充分體現(xiàn)了考慮周期性模板能夠在存在干擾的前提下使作業(yè)執(zhí)行更加穩(wěn)定.

實(shí)驗(yàn)4與實(shí)驗(yàn)2基于相同的干擾環(huán)境，使用傳統(tǒng)的右移策略充分考慮模板，保持泊位位置不變，按照先到先服務(wù)的原則對到港船舶安排作業(yè).相比而言，采用動態(tài)的決策框架在各規(guī)模下的改進(jìn)分別為42%，41%和43%，體現(xiàn)了動態(tài)決策框架在應(yīng)對干擾事件時的優(yōu)勢性，也體現(xiàn)了第二階段隨機(jī)場景信息的重要性.雖然在右移策略下泊位的偏差均為0，但是由于船舶干擾因素主要體現(xiàn)在到港時間及需求市場的不確定性上，傾向性的保證空間上的穩(wěn)定性會造成時間上存在較大的偏差，這也是兩者差距在40%以上的原因之一.

5 總結(jié)

針對集裝箱進(jìn)出口碼頭運(yùn)作層面，考慮周期性船舶到港時間及市場需求的干擾，采用動態(tài)決策框架協(xié)同調(diào)度泊位堆場資源.通過對信息動態(tài)特征分析及船舶分類，同時考慮作業(yè)執(zhí)行的穩(wěn)定性，以最小化與周期性模板的時間空間加權(quán)偏差作為目標(biāo)函數(shù)，提出基于隨機(jī)過程的二階段近似優(yōu)化模型.通過延遲部分決策充分利用準(zhǔn)確信息，增加決策的靈活性，同時通過隨機(jī)場景可調(diào)整預(yù)決策，使決策更具魯棒性.依據(jù)提出的決策框架及模型，設(shè)計雙層嵌套禁忌搜索，驗(yàn)證該框架的有效性.

參考文獻(xiàn):

[1] BIERWIRTH C, MEISEL F. A survey of berth allocation and quay crane scheduling problems in container terminals[J]. European Journal of Operational Research, 2010, 202(3):615.

[2] BIERWIRTH C, MEISEL F. A follow-up survey of berth allocation and quay crane scheduling problems in container terminals[J]. European Journal of Operational Research, 2015, 244(3):675.

[3] CARLO H J, VIS I F A, ROODBERGEN K J. Storage yard operations in container terminals: Literature overview, trends, and research directions[J]. Flexible Services & Manufacturing Journal, 2014, 235(2):412.

[4] MOORTHY R, TEO C P. Berth management in container terminal: the template design problem[J]. OR Spectrum, 2006, 28(4): 495.

[5] JIN J G, LEE D H, HU H. Tactical berth and yard template design at container transshipment terminals: A column generation based approach[J]. Transportation Research Part E: Logistics and Transportation Review, 2015, 73:168.

[6] TAO Y, LEE C Y. Joint planning of berth and yard allocation in transshipment terminals using multi-cluster s9tacking strategy[J] Transportation Research Part E: Logistics and Transportation Review,2015, 83:34.

[7] ROBENEK T, UMANG N, BIERLAIRE M,etal. A branch-and-price algorithm to solve the integrated berth allocation and yard assignment problem in bulk ports[J]. European Journal of Operational Research, 2014, 235(2):399.

[8] HENDRIKS M P M, LEFEBER E, UDDING J T. Simultaneous berth allocation and yard planning at tactical level[J]. OR Spectrum, 2013, 35(2):441.

[9] ZENG Q, HU X, WANG W,etal. Disruption management model and its algorithms for berth allocation problem in container terminals[J]. International Journal of Innovative Computing Information & Control: IJICIC, 2011, 7(5):2763.

[10] ZENG Q, YANG Z, HU X. Disruption recovery model for berth and quay crane scheduling in container terminals[J]. Engineering Optimization, 2011, 43(9):967.

[11] LI M Z, JIN J G, LU C X. Real-Time Disruption Recovery for Integrated Berth Allocation and Crane Assignment in Container Terminals[J]. Transportation Research Record Journal of the Transportation Research Board, 2015, 2479:49.

[12] LIU C, ZHENG L, ZHANG C. Behavior perception-based disruption models for berth allocation and quay crane assignment problems[J]. Computers & Industrial Engineering, 2016, 97:258.

[13] GUI J, YANG C. A Human-computer Interaction-based neighborhood search heuristic for disruption management[C]∥Third International Conference on Intelligent System Design and Engineering Applications. [S.l.]: IEEE, 2013:77-80.

[14] LI Q, TONG S, YANG C,etal. Optimization of operation scheme of container terminal based on disruption management[C]∥International Conference on Transportation Engineering. [S.l.]: 2009:3477-3482.

[15] UMANG N, BIERLAIRE M. Disruption management and re-scheduling in Berth allocation problem in Bulk Ports[R]. [S.l.]: Ecole Polytechnique Federale de Laussane, 2012.

[16] UMANG N, BIERLAIRE M, ERERA A L. Real-time management of berth allocation with stochastic arrival and handling times[J]. Journal of Scheduling, 2017, 20(1):67.

[17] ZHANG G, SMILOWITZ K, ERERA A. Dynamic planning for urban drayage operations[J]. Transportation Research Part E: Logistics and Transportation Review, 2011, 47(5):764.

[18] ZHANG C, LIU J, WAN Y W,etal. Storage space allocation in container terminals[J]. Transportation Research Part B Methodological, 2003, 37(10):883.

[19] ZHEN L, CHEW E P, LEE L H. An integrated model for Berth template and Yard template planning in transishipment Hubs[J]. Transportation Science, 2011, 45(4):483.