基于魯棒反應(yīng)式策略的集裝箱碼頭堆場和場橋聯(lián)合調(diào)度

徐 亞，張 恒，全雄文，陳秋雙

（1.南開大學(xué) 商學(xué)院，天津 300071；2.南開大學(xué) 計算機與控制工程學(xué)院，天津 300071）

基于魯棒反應(yīng)式策略的集裝箱碼頭堆場和場橋聯(lián)合調(diào)度

徐 亞1，張 恒2，全雄文2，陳秋雙2

（1.南開大學(xué) 商學(xué)院，天津 300071；2.南開大學(xué) 計算機與控制工程學(xué)院，天津 300071）

針對集裝箱碼頭進口堆場的特點，為降低作業(yè)時間的不確定性給堆場作業(yè)帶來的干擾，提高堆場計劃的可執(zhí)行性，提出堆場空間和場橋的魯棒預(yù)調(diào)度模型，采用拉格朗日松弛算法對模型進行求解，利用啟發(fā)式方法對預(yù)調(diào)度方案進行反應(yīng)式再調(diào)度。利用仿真實驗對所提方法在不確定環(huán)境下的有效性進行測試，結(jié)果表明相對單純依靠實時調(diào)整應(yīng)對環(huán)境變化的傳統(tǒng)方法，采用魯棒反應(yīng)式策略可顯著降低客戶到達(dá)時間不確定給堆場計劃帶來的干擾，并可有效減少堆場作業(yè)的延誤。

集裝箱碼頭；堆場計劃；場橋調(diào)度；魯棒反應(yīng)式策略

1 引言

堆場調(diào)度是集裝箱碼頭作業(yè)管理的核心問題之一，對碼頭整體運作效率、服務(wù)水平、作業(yè)成本等有重要影響。由于碼頭堆場空間、場橋數(shù)量等客觀限制，以及客戶取箱時間等不確定因素的干擾，如何動態(tài)地為等待處理的集裝箱分配堆存空間和場橋，充分發(fā)揮其作業(yè)效能，最大限度地提高客戶服務(wù)水平，一直是困擾碼頭管理人員的一個難題，也是碼頭運作服務(wù)的瓶頸環(huán)節(jié)。

通常碼頭中從船上卸下等待貨主取走的進口箱和準(zhǔn)備裝船的出口箱分別堆放在進口堆場和出口堆場，分別由若干箱區(qū)組成。在進口堆場，貨主取箱車輛到達(dá)時間是分散的和不確定的，在堆場計劃階段，對某箱區(qū)某時段有多少集裝箱被取走、需要多少場橋等無法精確控制。作業(yè)實施中，經(jīng)常由于一些箱區(qū)預(yù)留空間、場橋等無法滿足實際需求，而被迫頻繁調(diào)整預(yù)先制定的堆場和

場橋計劃，嚴(yán)重影響作業(yè)效率，甚至造成混亂。

此外，場橋在不同箱區(qū)間進行轉(zhuǎn)場需花費較長時間。若在某時段一些箱區(qū)的實際作業(yè)需求比較集中，而預(yù)分配的場橋更多集中在相對空閑的箱區(qū)，則需對場橋進行轉(zhuǎn)場，造成產(chǎn)能浪費；相反，若此時場橋正好處于繁忙箱區(qū)或其臨近箱區(qū)，則可節(jié)約時間，大大提高作業(yè)效率。實踐中，往往由于無法精確知道未來時段各箱區(qū)實際工作量，進口箱區(qū)場橋調(diào)度存在很大盲目性和短視性，造成場橋疲于轉(zhuǎn)場，作業(yè)效率低下，大量作業(yè)被延誤。

現(xiàn)有研究大多對堆場分配問題和場橋調(diào)度問題分別研究。如：針對堆場分配問題，Bazzazi等［1］和Zhang等［2］分別針對進口堆場和進出口混合堆場，以平衡各箱區(qū)裝卸工作量為目標(biāo)，建立了相應(yīng)的堆場空間分配優(yōu)化模型；Bazzazi等［1］和Zhang等［2］的模型均是基于確定的參數(shù)，王斌在Zhang等［2］的基礎(chǔ)上，假設(shè)各時段進出口箱量為已知分布的隨機量，利用機會約束模型，保證模型所得方案在一定概率下的可行性［3］。針對場橋調(diào)度問題，Linn等［4］，Cheung等［5］，Linn和Zhang［6］以及Zhang等［7］，以最小化各箱區(qū)延誤工作量為目標(biāo)，研究了場橋在堆場中的作業(yè)路徑?jīng)Q策問題。鄭紅星等［8］以最小化集卡等待時間和場橋移動成本為目標(biāo)，研究了箱區(qū)內(nèi)多場橋的協(xié)同調(diào)度問題。

在上述研究的基礎(chǔ)上，本文將堆場分配和場橋調(diào)度結(jié)合在一起，進行協(xié)同決策，使各箱區(qū)工作量與場橋分配相協(xié)調(diào)。考慮取箱車輛到達(dá)時間的不確定性，本文采用魯棒反應(yīng)式策略，在預(yù)調(diào)度階段，利用魯棒優(yōu)化模型［9］，通過控制各箱區(qū)容量約束的違反概率，保證調(diào)度方案在絕大多數(shù)情況下的可行性；在實時再調(diào)度階段，通過對預(yù)調(diào)度方案進行局部調(diào)整，修正預(yù)調(diào)度方案。

2 魯棒預(yù)調(diào)度模型

實際作業(yè)中，為保證碼頭作業(yè)有序進行，提箱車輛需提前向碼頭提出申請，而碼頭會限定各時段安排的總提箱數(shù)（稱預(yù)約提箱量）。通常各時段的預(yù)約提箱量不會超過提出申請的提箱量，未能安排提箱的車輛將延后到下一時段提箱。需指出，在制定預(yù)調(diào)度方案時，尚不知道各時段提箱的具體車輛，因此無法確定相應(yīng)的提箱作業(yè)發(fā)生在哪個箱區(qū)，也就是說，某時段某箱區(qū)的實際提箱量是不確定的。下面以一天為一個計劃期（即晝夜?jié)L動計劃），以4h為一個時段，以各時段預(yù)約提箱量和卸船箱量為依據(jù)，制定進口堆場空間和場橋的聯(lián)合預(yù)調(diào)度方案。

參數(shù)說明：N為進口箱區(qū)總數(shù)；T為總時段數(shù)；H為一個時段的長度（單位min）；ed為卸船時場橋?qū)⒁粋€集裝箱卸入堆場的平均作業(yè)時間；ep為提箱時場橋提取一個集裝箱的平均作業(yè)時間；Ci為箱區(qū)i的容量；tij為場橋由箱區(qū)i轉(zhuǎn)移到箱區(qū)j所需時間；ci0為箱區(qū)i中的初始箱量；xii0為箱區(qū)i中的初始場橋數(shù)；Dt為時段t內(nèi)的總卸船箱量；Pt為時段t內(nèi)的預(yù)約提箱量；

決策變量說明：dit表示時段t放入箱區(qū)i的進口箱量；xijt表示時段t由箱區(qū)i轉(zhuǎn)移到箱區(qū)j的場橋數(shù)；yijt表示時段t由箱區(qū)i轉(zhuǎn)移到箱區(qū)j的場橋在箱區(qū)j的工作量；zijt表示時段t由箱區(qū)i轉(zhuǎn)移到箱區(qū)j的場橋在箱區(qū)i的工作量；wit表示時段t箱區(qū)i中未完成的工作量。

其中εit為箱區(qū)i在時段t的實際提箱量偏離期望提箱量的比例，取εit～N（0,σ2），且?i，εi1,εi2,…,εiT相互獨立。

2.1 標(biāo)稱模型

若不考慮某時段某箱區(qū)提箱量的不確定性，取為pit，則可建立如下模型，即標(biāo)稱模型：

目標(biāo)函數(shù)（3）表示最小化各箱區(qū)在各時段未完成工作量的總和；約束（4）保證時段t放入各箱區(qū)的進口箱量之和等于該時段的總卸船箱量；約束（5）為箱區(qū)i的容量約束；約束（6）用于定義箱區(qū)i在時段t內(nèi)的未完成工作量；約束（7）保證時段t內(nèi)場橋完成的工作量不超過其可能完成的最大工作量；約束（8）保證在不同時段場橋的數(shù)量守恒；約束（9）表示同一時段內(nèi)一個箱區(qū)最多有兩臺場橋工作；約束（12）限定時段t內(nèi)一直在箱區(qū)i工作的場橋不超過2臺，最多有1臺場橋從箱區(qū)i移動到另一箱區(qū)j。

2.2 魯棒預(yù)調(diào)度模型建立

在標(biāo)稱模型基礎(chǔ)上，將不確定因素考慮進來，將約束（5）、（6）中的替換為不確定變量設(shè)α為足夠小的正數(shù)，取置信度為1-α的預(yù)測區(qū)間由可知為標(biāo)準(zhǔn)正態(tài)分布的分布函數(shù)）。進而，根據(jù)Bertsimas和Sim（2003）提出的魯棒優(yōu)化方法［10］，可將標(biāo)稱模型中的約束（5）、（6）替換為：

即得原問題的魯棒優(yōu)化模型。其中參數(shù)Γt用于調(diào)節(jié)箱區(qū)容量約束（13）的違反概率，根據(jù)Bertsimas和Sim［10］，違反概率滿足：

保守程度Γt越高，相應(yīng)約束的違反概率越低，然而保守程度過高，將使所得方案的性能指標(biāo)變差。因此，本文在滿足實際需要的前提下，盡可能降低Γt的取值。給定約束違反概率的上限Pv，取：

即滿足要求的最低保守程度。

約束（13）含有非線性項，為便于求解，需對其線性化。任意給定上述魯棒優(yōu)化模型的解向量X，設(shè)該式等價于：

由強對偶性可知：

于是，可將非線性約束（13），等價替換為以下三個線性約束：

2.3 魯棒預(yù)調(diào)度模型的求解

上述魯棒優(yōu)化模型是一個復(fù)雜的混合整數(shù)規(guī)劃模型，可利用拉格朗日松弛算法對其進行求解。以λ≥0為拉格朗日乘子，對堆場分配與場橋調(diào)度的耦合約束（7）進行拉格朗日松弛，可得上文魯棒優(yōu)化模型的松弛模型，進而可將其分解為兩個相對簡單的子問題（S1）和（S2）：

于是，將原問題中的堆場空間分配和場橋調(diào)度分在了兩個子問題中，其中子問題（S2）產(chǎn)生場橋調(diào)度，與網(wǎng)絡(luò)流問題結(jié)構(gòu)相似；子問題（S1）產(chǎn)生堆場空間分配方

案，除dit外均為連續(xù)變量。由于變量dit數(shù)值較大，本文對模型（S1）中的變量dit進行線性松弛，得到線性模型，分別對兩個子問題進行求解，即得魯棒優(yōu)化模型的松弛問題的解。

進而，可將松弛問題的解可行化為魯棒優(yōu)化模型的解：首先求解子問題（S1）。（S1）目標(biāo)項中包含魯棒優(yōu)化模型的目標(biāo)函數(shù)，所得yijt和zijt是松弛條件下的理想取值。為使場橋調(diào)度盡可能有利于降低魯棒優(yōu)化問題的目標(biāo)值，將（S1）的解yijt和 zijt作為已知量，求解模型（SA）：

其目標(biāo)是在滿足場橋調(diào)度可行性條件下，最小化耦合約束（7）的違反量。將所得解xijt作為可行化后的場橋調(diào)度方案，代入模型（SF）對可行解中的其余變量進行求解。

求解算法的具體步驟如下：

步驟1：初始化。設(shè)UB=M，LB=-M（M為足夠大的正數(shù)），λijt（1）=0（?i,j,t），k=1；

步驟3：可行化。將子問題（S1）的解yijt（k）和zijt（k）代入模型（SA），求解模型（SA）并將所得解xijt（k）作為輸入，代入模型（SF），若其對應(yīng)的目標(biāo)函數(shù)值小于UB，則記錄所得解為當(dāng)前最好解，并令UB為其對應(yīng)的目標(biāo)函數(shù)值。若gap=UB-LB足夠小，則轉(zhuǎn)至步驟5；否則，繼續(xù)；

步驟4：利用次梯度優(yōu)化算法修正拉格朗日乘子。令k=k+1，若k超過最大迭代步數(shù)，則轉(zhuǎn)至步驟5，否則，轉(zhuǎn)至步驟2；

步驟5：整數(shù)化，得到魯棒預(yù)調(diào)度模型的可行解，算法終止。

3 反應(yīng)式再調(diào)度策略實施

上述魯棒方法所得預(yù)調(diào)度方案在執(zhí)行過程中可將不確定環(huán)境下容量約束的違反概率控制在給定上限以內(nèi)，但不能保證在所有情況下預(yù)調(diào)度方案都是可行的。因此，在實施過程中，不可避免地需要根據(jù)當(dāng)時各箱區(qū)的實際提箱量以及堆場空間的實際使用情況，對預(yù)魯棒調(diào)度方案進行反應(yīng)式再調(diào)整。

利用仿真對不確定環(huán)境下的再調(diào)度過程進行模擬，對于給定的預(yù)調(diào)度方案S，其調(diào)整過程如下：

步驟1：初始化，設(shè)t=1；

步驟2：生成時段t各箱區(qū)的實際提箱量。從進口堆場的集裝箱中隨機抽取Pt（即時段t的預(yù)約提箱量）個，作為該時段提走的集裝箱，統(tǒng)計從各箱區(qū)提走的集裝箱數(shù)量，即各箱區(qū)在該時段的實際提箱量。

步驟3：調(diào)整卸船箱的堆放位置。根據(jù)各箱區(qū)實際提箱量，判斷按照預(yù)調(diào)度方案S，在時段t卸入各箱區(qū)的進口箱量是否會超過相應(yīng)的容量約束，如果是，將超出容量約束的箱量堆放到剩余容量最大的箱區(qū)中。

步驟4：若t=T，則根據(jù)各時段各箱區(qū)的實際提箱量和卸入箱量，以及方案S給出的場橋調(diào)度方案，計算各時段各箱區(qū)的實際延誤工作量之和，并統(tǒng)計仿真過程中違反容量約束的次數(shù)和箱量。否則，令t=t+1，轉(zhuǎn)步驟2。

需說明，之所以要將超出容量約束的箱量堆放到剩余容量最大的箱區(qū)中，主要是考慮盡可能減少再調(diào)度發(fā)生的頻率，因為再調(diào)度本身也會對堆場作業(yè)造成擾動，過多地進行再調(diào)度將降低堆場作業(yè)的整體效率。

4 實驗分析

本文以天津港某集裝箱碼頭公司的進口堆場為實驗對象，該碼頭的進口堆場共有17個箱區(qū)，各箱區(qū)的容量見表1。場橋在不同箱區(qū)間的移動時間取值在5～50min不等。

表1 各箱區(qū)的容量（單位：TEU）

本文根據(jù)實際數(shù)據(jù)的取值范圍，隨機產(chǎn)生問題實例，對算法的有效性進行驗證。取進口堆場中場橋數(shù)量為9～12臺，它們在堆場中的初始位置隨機生成，各時段

總卸船箱量為300～900TEU，并限各時段總預(yù)約提箱量為600TEU。根據(jù)碼頭實際，取的置信度為99%的預(yù)測區(qū)間，約束違反概率的上限Pv取為5%，根據(jù)式（15）和（16），保守程度Γt=t，t=1,2,3,4；Γ5=4.77；Γ6=5.27。

4.1 魯棒反應(yīng)式策略的代價與收益

為驗證本文魯棒反應(yīng)式策略的有效性，該實驗?zāi)M實際作業(yè)中各時段提箱車輛所提取的集裝箱位置的隨機性，將魯棒反應(yīng)式策略與碼頭傳統(tǒng)的確定性計劃加實時調(diào)度策略進行比較，考察在不確定環(huán)境下兩者產(chǎn)生的實際延誤工作量以及在執(zhí)行過程中違反容量約束的程度。對10個實例進行測試，對每個實例分別利用兩種調(diào)度策略進行5次仿真。表2給出了兩種調(diào)度策略在5次仿真中得到的實際延誤工作量的平均值、違反容量約束的次數(shù)和箱量（即超容次數(shù)和超容箱量）的平均值。

表2 魯棒反應(yīng)式策略與傳統(tǒng)調(diào)度策略仿真結(jié)果的比較

從表2中平均超容箱量和次數(shù)的比較可以看出，魯棒反應(yīng)式策略在實際執(zhí)行中具有很強的抗干擾能力，對所測10個實例，其平均超容箱量和次數(shù)均為0，而傳統(tǒng)方法在實施過程中很容易超出容量限制。對超出容量限制的箱量的堆放位置進行實時調(diào)整，往往帶有一定的盲目性和短視性，容易造成碼頭作業(yè)的混亂，降低碼頭作業(yè)效率，本文魯棒反應(yīng)式策略有效減少了這種情況的發(fā)生。

由于在魯棒預(yù)調(diào)度階段對各箱區(qū)工作量采取了比較悲觀的估計，且在容量約束中加入了一定的冗余量，其計劃目標(biāo)值比不考慮冗余的確定性模型高46.7%，但這并不代表其在實際執(zhí)行中的延誤工作量會高于基于確定性計劃的傳統(tǒng)方法，因為傳統(tǒng)堆場計劃假定各箱區(qū)提箱量為標(biāo)稱值的情況在實際執(zhí)行中幾乎不可能實現(xiàn)，其得到的理論目標(biāo)值并不具有實際意義。由表2可知，在不確定環(huán)境下，魯棒反應(yīng)式策略的實際延誤工作量低于傳統(tǒng)調(diào)度策略，10個實例的平均實際延誤工作量比采用傳統(tǒng)調(diào)度策略降低了18.5%。

4.2 不同場橋配置的影響

在集裝箱碼頭中，由于優(yōu)先保證出口堆場作業(yè)，通常需要盡可能壓縮進口堆場中的場橋數(shù)量，而若進口堆場中場橋數(shù)量過少，則將使延誤工作量急劇上升，造成提箱車輛嚴(yán)重積壓。為此，需要在進口堆場的場橋配置數(shù)與延誤工作量之間進行權(quán)衡。該實驗隨機生成20個實例分別在場橋數(shù)為9、10、11和12的條件下進行求解。

實驗表明，對于所有實例隨場橋數(shù)量的減少，所得方案的工作延誤率均逐步上升。圖1給出了不同場橋配置下工作延誤率（即總延誤工作量占計劃期內(nèi)全部工作量的比例）的比較。如圖1所示，在場橋數(shù)為11和12的條件下，20個實例的平均工作延誤率分別為4.31%和2.18%，均不超過5%。由于本文模型為魯棒優(yōu)化模型，這意味著在絕大多數(shù)情況下，所得方案在實施時的最大延誤工作量平均不超過總工作量的5%，對于碼頭來說，這樣的結(jié)果是相當(dāng)理想的。當(dāng)場橋數(shù)減少為10時，所得工作延誤率的平均值上升為8.49%，在場橋資源緊張的條件下，該結(jié)果仍然是可以接受的。而當(dāng)場橋數(shù)減少為9時，所得工作延誤率的平均值顯著上升，達(dá)到15.84%，在這種情況下，碼頭調(diào)度人員應(yīng)考慮增加進口堆場中的場橋數(shù)量，否則堆場外積壓的集卡數(shù)量將超出碼頭的承受能力，影響其服務(wù)水平。

圖1 不同場橋配置下的平均延誤率

通過該實驗可以看出，本文方法可為碼頭管理者對進口堆場進行場橋配置提供了決策依據(jù)。在制定計劃時，可以根據(jù)不同場橋配置下的工作延誤率，判斷是否可采用相應(yīng)的場橋配置。實際上，由于本文算法的計算時間相對很短，在實際應(yīng)用時，可采用滾動計劃方法，在

每個時段末根據(jù)最新得到數(shù)據(jù)重新計算下一計劃期（6個時段）的調(diào)度方案，以提高所得方案的實時性。

5 結(jié)論

本文針對集裝箱碼頭進口堆場的特點，研究了堆存空間與場橋集成調(diào)度問題。針對進口堆場中提箱作業(yè)的不確定性，提出了一種魯棒反應(yīng)式調(diào)度策略，利用仿真方法對其在不確定環(huán)境下的實施效果進行了測試，結(jié)果表明采用魯棒反應(yīng)式策略，在預(yù)調(diào)度階段利用魯棒方法對不確定因素進行吸收，在再調(diào)度階段利用啟發(fā)式規(guī)則對預(yù)調(diào)度方案進行局部調(diào)整，比事先不考慮不確定因素的影響而單純依靠在執(zhí)行過程中進行實時調(diào)整得到的實際效果要好，采用該策略有利于提高碼頭的作業(yè)效率。

［1］Bazzazi M,Safaei N,Javadian N.A genetic algorithm to solve the storage space allocation problem in a container terminal［J］. Computers and Industrial Engineering,2009,56（1）：44-52.

［2］Zhang C,Liu J,Wan Y W.Storage space allocation in container terminals［J］.Transportation Research B,2003,37（10）：883-903.

［3］王斌.集裝箱碼頭堆場的一種動態(tài)隨機堆存方法［J］.系統(tǒng)工程理論與實踐,2007,27（4）：147-170.

［4］Linn R J,Liu J Y,Wan Y W.Rubber tired gantry crane deployment for container yard operation［J］.Computers amp;Industrial Engineering,2003,45（3）：429-442.

［5］Cheung R K,Li C,Lin W.Interblock crane deployment in container terminals［J］.Transportation Science,2002,36（1）：79-93.

［6］Linn R J,Zhang C.A heuristic for dynamic yard crane deployment in a container terminal［J］.IIE Transactions,2003,35（2）：161-174.

［7］Zhang C,Wan Y,Liu J.Dynamic crane deployment in container storage yards［J］.Transportation Research Part B,2002,36（6）：537-555.

［8］鄭紅星,于凱,李芳芳,等.考慮外集卡的混堆集裝箱碼頭多場橋調(diào)度［J］.計算機集成制造系統(tǒng),2014,20（12）：3 161-3 169.

［9］Bertsimas D,Brown D B,Caramanis C.Theory and Applications of Robust Optimization［J］.SIAM Review,2011,53（3）：464-501.

［10］Bertsimas D,Sim M.Robust discrete optimization and network flows［J］.Mathematical Programming Set B,2003,98（1）：49-71.

Joint Yard and Transtainer Dispatching at Container Terminals Based on Robust Response Strategy

Xu Ya1,Zhang Heng2,Quan Xiongwen2,Chen Qiushuang2
（1. School of Business, Nankai University, Tianjin 300071；2. School of Computer Control Engineering, Nankai University, Tianjin 300071, China）

In this paper, in view of the characteristics of the import yard of a container terminal and in a bid to reduce the interference ofthe uncertain operation time on the working order of the yard and improve the enforceability of the yard schedules, we proposed a robust preschedulingmodel to regulate the yard space and transtainer, solved it using the Lagrangean relaxation algorithm and next, had a responsivere- dispatching of the pre- schedule using the heuristic method. At the end, through a simulation test, we examined the validity of theproposed method under an uncertain environment, which verified its superiority over the traditional responsive method.

container terminal； yard schedule； transtainer dispatching； robust responsive strategy

U691.3；F224

A

1005-152X（2016）09-0052-06

10.3969/j.issn.1005-152X.2016.09.012

2016-08-02

國家自然科學(xué)基金資助項目（71202161,61403213，71172071）；教育部人文社會科學(xué)研究青年基金項目（11YJC630239）

徐亞（1981-），男，天津人，博士，研究方向：系統(tǒng)建模與仿真、優(yōu)化調(diào)度理論。