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

干擾管理是對干擾事件發(fā)生后的應(yīng)急處理方式，保證以盡量小的擾動(dòng)恢復(fù)系統(tǒng)的正常運(yùn)作.與重調(diào)度相比更注重于減小與原有模板之間的偏差.干擾管理作為實(shí)時(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í)間以及岸橋數(shù)量的分配和第二部分對每個(gè)岸橋的具體調(diào)度.Gui等[13]研究由于船舶的延遲或者計(jì)劃到港但取消到港或者未在計(jì)劃中的船舶臨時(shí)到港等干擾因素對泊位調(diào)度的影響，提出了基于人機(jī)交互的鄰域搜索，依照干擾的類型影響程度等生成初始解，并且在迭代過程中進(jìn)行修正.針對于集裝箱碼頭，Li等[14]考慮由于船舶延遲造成的干擾因素，基于干擾管理提出了調(diào)整框架，并采用自適應(yīng)的遺傳算法以及計(jì)算機(jī)仿真優(yōu)化的方式進(jìn)行求解.Umang等[15]以散貨港作為研究對象，在已知泊位調(diào)度模板的前提下，從干擾恢復(fù)的角度，對泊位分配的實(shí)時(shí)恢復(fù)進(jìn)行研究.Umang等[16]考慮船舶的到港時(shí)間以及作業(yè)時(shí)間不確定性，假設(shè)船舶預(yù)計(jì)到港信息隨著時(shí)間動(dòng)態(tài)更新，以滾動(dòng)計(jì)劃的形式求解泊位分配問題,目標(biāo)函數(shù)是最小化實(shí)時(shí)的計(jì)劃成本，提出了基于集合劃分和智能貪婪算法的優(yōu)化恢復(fù)算法對問題進(jìn)行實(shí)時(shí)的求解.

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

1 問題描述與決策框架

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

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

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

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

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

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

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

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

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

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

(2)B類：在決策點(diǎn)k尚未開始作業(yè)，但將在k周期內(nèi)到達(dá).包括某些會在周期k內(nèi)開始作業(yè)(船3、船4、船5), 某些預(yù)計(jì)會延遲到下一周期(船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è)開始時(shí)間si、作業(yè)結(jié)束時(shí)間ei、泊位位置bi和進(jìn)口箱堆場留存截止時(shí)間gi.而B1類船和C類一樣，在本階段需要進(jìn)行各場景下的可調(diào)整預(yù)決策，并且在后續(xù)階段保留修正的權(quán)利.

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

假設(shè)圖2為周期k時(shí)碼頭管理人員所做的決策示意圖，在決策點(diǎn)時(shí)，船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ù)計(jì)在k+4前到港的船舶將被分為C類，將于B1類船一起決策，但并不在該周期內(nèi)執(zhí)行.

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

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

表2 動(dòng)態(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ù)計(jì)到港時(shí)間點(diǎn)模板開始時(shí)間點(diǎn)真實(shí)到港時(shí)間點(diǎn)模板作業(yè)時(shí)間/h真實(shí)作業(yè)時(shí)間/h11313138922020331010323252398430303078

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

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

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

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

3 雙層嵌套禁忌搜索算法

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

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

TS1開始

構(gòu)建集合N(L*)：隨機(jī)更換B類船在列表的順序?[L](首個(gè)循環(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)確到港時(shí)間已知，在本階段需執(zhí)行固定性決策，因此其位于編碼列表的第二優(yōu)先級位置.

(3)C類：到港時(shí)間存在干擾的可能性，在第一階段不進(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).禁忌對象為上一步移動(dòng)的互換操作，禁忌次數(shù)在上限tabu_max和下限tabu_min間隨機(jī)生成.循環(huán)進(jìn)行禁忌搜索直至最大循環(huán)次數(shù)Iter_max.

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

TS1：

對于所有L中的船

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

(2)B類：保留fi，并且在k～k+1之間，尋找最早開始時(shí)間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類船添加到已有的計(jì)劃中.在各個(gè)場景下補(bǔ)充ξk得到第二階段的鄰域解ξk+1.在本階段中，B1與C類船的決策量均獨(dú)立于各場景ω，但均補(bǔ)充自同一個(gè)第一階段固定性決策.第二階段禁忌的對象仍為上一步移動(dòng)的操作，禁忌次數(shù)在上限tabu_max和下限tabu_min間隨機(jī)生成.

TS2

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

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

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

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

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

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

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

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

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

(4)干擾環(huán)境下，基于周期性模板，保持泊位位置不變的前提下，以最小化船舶在港時(shí)間為目標(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)確到港時(shí)間，并采用CPLEX進(jìn)行滾動(dòng)求解，在實(shí)際中是無法實(shí)現(xiàn)的理想情況.在中小規(guī)模下能夠基本上求得相應(yīng)最優(yōu)解，但在大規(guī)模CPLEX在某一循環(huán)周期中無法在5 h內(nèi)獲得可行解.總的來說運(yùn)算時(shí)間較長，中小規(guī)模下平均求解時(shí)間分別在150 min、694 min.

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

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

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

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

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

5 總結(jié)

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