基于二維布局分散度的兩階段箱位指派優(yōu)化

于航，葛穎恩，樂美龍，檀財茂

（1.上海海事大學(xué)a.經(jīng)濟(jì)管理學(xué)院；b.經(jīng)濟(jì)交通運(yùn)輸學(xué)院；c.物流研究中心，上海201306；2.上海交通大學(xué)海科院海洋航運(yùn)研究所，上海200231）

基于二維布局分散度的兩階段箱位指派優(yōu)化

于航1a，葛穎恩*1b，樂美龍2，檀財茂1c

（1.上海海事大學(xué)a.經(jīng)濟(jì)管理學(xué)院；b.經(jīng)濟(jì)交通運(yùn)輸學(xué)院；c.物流研究中心，上海201306；2.上海交通大學(xué)?？圃汉Ｑ蠛竭\(yùn)研究所，上海200231）

集裝箱碼頭的資源配置優(yōu)化，是集裝箱裝卸作業(yè)組織的核心.作為集裝箱堆場空間資源配置的重要優(yōu)化指標(biāo)，提出布局分散度的規(guī)劃概念.以集裝箱碼頭堆場的箱位指派問題為應(yīng)用背景，為提高集裝箱后續(xù)作業(yè)效率，分別從堆場布局層面和箱區(qū)箱位指派層面考慮多維度布局分散度的優(yōu)化意義.建立第一階段為仿真，第二階段為混合整數(shù)二次規(guī)劃(MIQP)的兩階段優(yōu)化模型.結(jié)合實(shí)際碼頭生產(chǎn)數(shù)據(jù)進(jìn)行算例實(shí)驗(yàn)，結(jié)果緩解了堆場擁堵情況并提高了碼頭集裝箱裝卸作業(yè)效率.同時，研究也揭示了布局分散度概念在堆場資源優(yōu)化配置應(yīng)用中的重要意義.

水路運(yùn)輸;布局分散度;兩階段優(yōu)化;箱位指派;混合整數(shù)二次規(guī)劃

1 引言

堆場的作業(yè)優(yōu)化是集裝箱碼頭企業(yè)精細(xì)化管理的重點(diǎn).以往的集裝箱堆場優(yōu)化較多關(guān)注集裝箱堆存策略的優(yōu)化和堆場設(shè)備資源的優(yōu)化配置.比如Taleb-Ibrahimi等[1]針對出口集裝箱堆場的堆存策略進(jìn)行建模研究，討論了堆存策略可導(dǎo)致的翻箱情況.Zhang Liu[2]提出了進(jìn)出口集裝箱及轉(zhuǎn)運(yùn)集裝箱同箱區(qū)的混堆策略，并用整數(shù)規(guī)劃的方法分兩階段對集裝箱的資源配置進(jìn)行優(yōu)化.并由王斌[3]建立了集裝箱碼頭堆場的兩階段動態(tài)堆存策略，利用約束規(guī)劃模型對前人箱量已知條件下的堆場資源配置策略進(jìn)行改進(jìn).

近年P(guān)etering等[4]通過仿真技術(shù)針對存儲箱區(qū)的長度及龍門吊的分散配置兩個指標(biāo)進(jìn)行研究，考察了這兩個指標(biāo)對橋吊長期作業(yè)效率的影響，揭示了堆場資源分散配置對后續(xù)集裝箱作業(yè)效率的關(guān)鍵影響.Chen等[5]針對出口集裝箱箱位分配策略，分兩階段對到場船屬集裝箱進(jìn)行了精確指派策略的探索.在前人的基礎(chǔ)上進(jìn)一步進(jìn)行探索，并取得了一定的成果[6，7]，在現(xiàn)階段的成果中發(fā)現(xiàn)，堆場船屬集裝箱的分散布局對整個堆場的運(yùn)作效率有重大影響，然而當(dāng)前堆場堆存優(yōu)化研究領(lǐng)域缺乏相關(guān)的研究.因此，提出資源布局分散度的概念，并將其應(yīng)用到集裝箱堆場的布局優(yōu)化中.

2 問題描述

2.1 布局分散度的定義及應(yīng)用價值

將堆場一維布局分散度定義為船只靠泊后，其對應(yīng)的堆場發(fā)箱點(diǎn)與作業(yè)點(diǎn)中心的直線距離測度.如圖1所示.圖中斜線部分的橋吊表示船只?？康淖鳂I(yè)線位置，分散度標(biāo)尺表示了該船只的布局分散度選擇范圍.在常見的碼頭作業(yè)工藝下，船舶靠泊后，船屬集裝箱在堆場的堆存位置直接關(guān)系著船舶開始作業(yè)后集裝箱上橋作業(yè)的合理性，過度的聚集會導(dǎo)致堆場作業(yè)擁堵和工作量不均，過度的分散會導(dǎo)致集卡運(yùn)輸距離增加和橋吊作業(yè)等待.

圖1 堆場布局分散度示意圖Fig.1 The distribution dispersion in the yard template

在一維布局分散度的定義下，將二維箱區(qū)布局分散度定義為一維布局分散度對應(yīng)垂直范圍內(nèi)的船屬集裝箱指派量.該變量影響了作業(yè)線對應(yīng)的集裝箱發(fā)箱點(diǎn)數(shù)量和堆場同種集裝箱的聚集密度.進(jìn)而決定了堆場箱區(qū)作業(yè)的擁擠程度，影響到橋吊的裝船效率.一維及二維分散度的定義決定了船屬集裝箱后續(xù)作業(yè)時各設(shè)備間生產(chǎn)節(jié)拍配合的協(xié)調(diào)性，與碼頭后續(xù)的裝船作業(yè)效率密切相關(guān).

2.2 兩階段優(yōu)化框架

通過仿真模擬與優(yōu)化建模相結(jié)合的方法分兩階段對出口箱箱位指派策略進(jìn)行優(yōu)化.其中，第一階段利用仿真方法對集裝箱碼頭的裝卸作業(yè)情況進(jìn)行模擬，得到一維布局分散度策略下的船屬集裝箱裝卸作業(yè)時間估計.進(jìn)而將仿真結(jié)果作為集裝箱箱位指派模型的約束參數(shù)估計，輸入到第二階段考慮箱區(qū)堆存布局分散度的箱位指派模型中，綜合求出考慮布局分散度和堆場作業(yè)約束的集裝箱箱位指派策略.兩階段箱位指派優(yōu)化框架如圖2所示.研究建立在以下的假設(shè)之上：

（1）船屬的集裝箱裝卸數(shù)量是已知且不變的.班輪的集裝箱裝卸作業(yè)船圖一般會在集裝箱開始作業(yè)前拿到，雖然在實(shí)際的作業(yè)中有部分集裝箱因?yàn)楦鞣N因素?zé)o法按計劃信息作業(yè)，但這部分集裝箱所占比重較小且對整體布局影響不大.

（2）不考慮堆場設(shè)備緊缺的限制.集裝箱箱位指派策略將影響堆場設(shè)備的調(diào)度，進(jìn)而決定裝卸作業(yè)的效率.研究的重點(diǎn)是堆場箱位指派策略的優(yōu)化，先于設(shè)備的調(diào)度，因此不考慮堆場設(shè)備資源限制對生產(chǎn)的影響.

圖2 兩階段箱位指派優(yōu)化框架Fig.2 The structure of the two-stage optimization for container assignment

3 第一階段仿真模擬

3.1 仿真系統(tǒng)事件

針對碼頭裝卸作業(yè)的特點(diǎn)，仿真主要劃分為5類事件：

（1）Loading事件.

用來描述橋吊從集卡上卸載出口箱的動作，同時也包括了龍門吊向集卡上裝載出口箱的動作.

（2）Unloading事件.

用來描述橋吊向集卡上卸載進(jìn)口箱的動作，同時也包括了龍門吊從集卡上提取進(jìn)口箱的動作.

（3）Dual-Loading事件.

用來描述橋吊裝卸同步操作的動作，裝卸同步工藝近幾年在大型碼頭中的應(yīng)用比例逐漸上升，該工藝要求橋吊在完成一個集卡的裝載任務(wù)之后立刻為該集卡安排一個卸載箱的運(yùn)輸任務(wù).

（4）Traveling事件.

用來描述集卡運(yùn)輸集裝箱在堆場與其他設(shè)備間來往的動作.

（5）Waiting事件.

用來描述集卡等待橋吊和龍門吊前一動作完畢的動作.

3.2 仿真系統(tǒng)流程

第一階段的集裝箱裝卸作業(yè)模擬系統(tǒng)流程如圖3所示，主要對以下兩點(diǎn)進(jìn)行說明：

（1）在船舶裝卸操作開始后，橋吊及龍門吊空閑時間所占比例較小.因此仿真不考慮集卡已經(jīng)派出后，橋吊及龍門吊等待集卡的時間.等待時間以設(shè)備阻塞導(dǎo)致的集卡等待時間為主，其他設(shè)備等待時間僅考慮橋吊開始作業(yè)時作業(yè)線對應(yīng)集卡池的配置時間.

（2）在第一階段的仿真模擬中，研究將根據(jù)堆場箱區(qū)情況、作業(yè)泊位的分配及靠泊船只的裝卸箱信息進(jìn)行布局分散度所對應(yīng)作業(yè)效率的仿真模擬.

4 第二階段指派模型

（1）集合說明.

S={i|i=1,2,…,n}——作業(yè)船舶的集合；

D={j|j=1,2,…,n}——堆場對應(yīng)的布局分散度值的集合，代表了堆場堆存范圍的選擇；

B={k|k=1,2,…,n}——堆場箱區(qū)的集合.

（2）參數(shù)說明.

Ck——k箱區(qū)的最大存量，k∈B;

Vk——k箱區(qū)的實(shí)際集裝箱存量，k∈B;

Wi——i船的集裝箱作業(yè)量，i∈S;

βi,j,k——i船在布局分散度為j時對應(yīng)在箱區(qū)k的單位箱平均作業(yè)時間估計，i∈S,j∈D,k∈B;

αi,j——i船在布局分散度為j條件下的裝卸作業(yè)完成時間估計，i∈S,j∈D;——α水平下i船在布局分散度為ji,j時對應(yīng)的箱區(qū)k的箱位分配量估計值，i∈S,j∈D,k∈B;

Δt——箱區(qū)k的存量超過（小于）X'i,j,k時單位操作時間的懲罰（獎勵）因子；

μ——箱區(qū)容積率，表示了集裝箱存儲所占箱區(qū)存量的比例；

M——極大正值常數(shù).

（3）決策變量.

Xi,j,k——連續(xù)整形變量，表示i船以布局分散度j在箱區(qū)k的集裝箱存量，i∈S,j∈D,k∈B; Yi,j∈{}

0,1——1代表i船以布局分散度j進(jìn)行箱位指派，否則取0，i∈S,j∈D.

圖3 第一階段集裝箱作業(yè)仿真系統(tǒng)流程Fig.3 The simulation process of the container handling in the first stage

（4）目標(biāo)函數(shù).

目標(biāo)函數(shù)由兩部分構(gòu)成，第一部分基礎(chǔ)函數(shù)可表示為

該部分函數(shù)表示集裝箱在仿真估計作業(yè)時間下的系統(tǒng)整體作業(yè)時間.

第二部分函數(shù)表示為

αi,jYi,j代表了各船舶選擇不同一維布局分散度策略的作業(yè)時間估計.因此對不同堆場一維布局分散度策略下的碼頭整體作業(yè)時間水平進(jìn)行了描述.

綜合可得到基本目標(biāo)

對式（3）進(jìn)行改進(jìn)，考慮碼頭在具體箱區(qū)箱量指派中的第二維布局分散度策略，考慮仿真作業(yè)時間水平αi,j下i船在布局分散度為j時對應(yīng)的箱區(qū)k的箱位分配量估計值對指派產(chǎn)生的影響.改進(jìn)模型討論了Xi,j,k與的關(guān)系.當(dāng)≥0時，可令t表示由于裝卸阻塞導(dǎo)致的單位作業(yè)時間增加.相反≤0時，可令[Δt表示由于作業(yè)流順暢促進(jìn)的箱區(qū)集裝箱單位作業(yè)時間縮短幅度.進(jìn)而可知代表了在仿真估計存儲量基礎(chǔ)上建立的箱區(qū)集裝箱單位作業(yè)時間估計.綜上可知代表了在堆場整體及箱區(qū)箱位指派兩個維度考慮布局分散度策略的集裝箱作業(yè)總時間估計.

改進(jìn)的目標(biāo)可表示為

式（5）代表了對變量Vk的約束，該變量代表了箱區(qū)實(shí)際的箱位指派情況.式（6）表示了Vk的值應(yīng)小于箱區(qū)合理存儲量μCk.式（7）保證了為船舶在各箱區(qū)指派的箱位與船舶的集裝箱作業(yè)量相同.式（8）保證了船舶只能同時在一種堆場布局分散度策略下進(jìn)行集裝箱堆存.式（9）保證了船只分散度布局策略和箱位安排關(guān)系的平衡.式（10）和式（11）是對決策變量Xi,j,k和Yi,j∈{0,1}取值范圍的約束.綜合目標(biāo)函數(shù)和約束條件可以看出，第二階段的基本指派模型為典型的線性規(guī)劃模型，改進(jìn)的箱位指派模型為混合整數(shù)二次規(guī)劃模型(MIQP).并通過ilog-cplex求解器嘗試對模型進(jìn)行求解.

5 算例實(shí)驗(yàn)

（1）第一階段仿真模擬.

參考洋山深水港的實(shí)際作業(yè)數(shù)據(jù)進(jìn)行算例實(shí)驗(yàn)，選取一期岸線中的4個深水泊位，2 000 m的岸線及6個前方堆存大區(qū)進(jìn)行模擬.同時，從船期表中選取連續(xù)靠港的4艘船只進(jìn)行裝卸作業(yè)的仿真，已知數(shù)據(jù)信息和第一層仿真的參數(shù)設(shè)置如表1所示.

表1 已知數(shù)據(jù)及仿真參數(shù)設(shè)置Table 1The parameters used in the simulation and the model

研究利用Flexterm仿真平臺對第一階段碼頭裝卸情況進(jìn)行仿真，仿真模型如圖4所示.

通過仿真模擬可以從第一階段得到各船只在不同堆場分散度策略水平下的箱區(qū)平均作業(yè)時間和箱量指派估計值.組成每艘船作業(yè)時間估計和指派量估計的參數(shù)組合(βi,j,k,.本算例中i=1,2,3,4分別代表了展明，以星，聰河和三井四艘船.所得的參數(shù)矩陣(βi,j,通過仿真實(shí)驗(yàn)輸出，如表2和表3所示.

圖4 碼頭裝卸作業(yè)仿真模型Fig.4 The simulation model of the upper level built in Flexterm

表2 1號和2號船的仿真輸出參數(shù)矩陣Table 2The output parameters from the simulation of No.1 and No.2 ship（min，TEU）

表3 3號和4號船的仿真輸出參數(shù)矩陣Table 3The output parameters from the simulation of No.3 and No.4 ship（min，TEU）

除此以外，不同布局分散度水平下船舶整體作業(yè)時間水平αi,j輸出匯總?cè)绫?所示.

表4 四艘船舶的整體作業(yè)完成時間估計Table 4The estimation of total handling time of all four ships

（2）第二階段箱位指派求解.

把上述由第一階段仿真得到的參數(shù)估計值輸入第二階段模型，在Intel(R)Core(TM)i7-3537U CPU@2.00GHz處理器的支持下，利用ilog-cplex對第二階段的線性規(guī)劃及混合整數(shù)二次規(guī)劃模型進(jìn)行求解，其中基礎(chǔ)目標(biāo)值求得為12 721.混合整數(shù)二次規(guī)劃模型通過8 772 s的求解，在MIP相對容差0.01%的條件下求得了最優(yōu)目標(biāo)值11085.

6 結(jié)果分析

通過對基本目標(biāo)和改進(jìn)目標(biāo)的求解可以得到兩種分配方案.結(jié)果如表5所示.其中第二種方案考慮了在堆存范圍和箱區(qū)兩個維度上考慮了布局分散度的優(yōu)化意義，結(jié)果如表6所示.

表5 基本求解結(jié)果Table 5The solution of the basic problem

表6 改進(jìn)求解結(jié)果Table 6The solution of the improved problem

表5和表6中分散度值代表了堆場布局層面的布局分散度最優(yōu)值，該值反映了箱位指派時的船屬箱區(qū)指派范圍，是第一維的布局分散度指標(biāo). Xi,j,k值反映了集裝箱在第一階段堆場布局分散度范圍約束下的具體箱區(qū)布局分散度策略，是第二維的布局分散度指標(biāo).通過上述結(jié)果，可以看出在堆場和箱區(qū)兩個層面均考慮布局分散度策略的箱位指派優(yōu)化方案，優(yōu)于僅考慮堆場布局分散度的箱位指派方案.在整體作業(yè)時間上，由于改進(jìn)方案緩解了箱區(qū)因過度堆存相同作業(yè)線集裝箱導(dǎo)致的作業(yè)壓力，整體作業(yè)時間縮短明顯.通過改進(jìn)的指派方案，箱區(qū)內(nèi)的集裝箱布局分散度得到優(yōu)化，基本指派方案和改進(jìn)指派方案在各箱區(qū)的堆存情況匯總?cè)鐖D5和圖6所示.

圖5 基本的指派方案Fig.5 The basic assignment method

圖6 改進(jìn)的指派方案Fig.6 The improved assignment method

通過圖5和圖6可以看出，基本指派方案使船屬同一作業(yè)線下的集裝箱分配較集中，造成箱區(qū)作業(yè)壓力增大，阻塞增強(qiáng)，進(jìn)而導(dǎo)致作業(yè)時間增長.改進(jìn)后的指派策略有效地分散了同一作業(yè)線下集裝箱的堆場分布情況，緩解了船屬同一作業(yè)線下集裝箱的作業(yè)壓力，從而減少阻塞，促進(jìn)總體作業(yè)時間的縮短.結(jié)合表6可以看出，下劃線標(biāo)記的箱區(qū)箱量指派較其他箱區(qū)分配量明顯增大，箱量分配的增大均發(fā)生在距船舶泊位較遠(yuǎn)的1號和6號箱區(qū).結(jié)合第一階段的仿真模型可以看出，這種現(xiàn)象是因集裝箱會先在距離船舶較近的位置進(jìn)行堆存導(dǎo)致的，即首先在2，3，4，5號箱區(qū)進(jìn)行堆存.當(dāng)這些箱區(qū)存滿后，再在邊緣箱區(qū)進(jìn)行存儲.在制定二維布局分散度策略的時候，研究考慮了邊緣箱區(qū)堆存對整體策略選擇的影響，給出以布局分散度為主要規(guī)劃指標(biāo)的堆場最優(yōu)布局方案如表7所示.

根據(jù)所給策略，船舶應(yīng)在一維布局分散度約束的箱區(qū)范圍內(nèi)，按照二維布局分散度的箱量進(jìn)行各箱區(qū)的箱位指派.在兩個維度均考慮布局分散度策略的箱位分配策略，使得箱區(qū)內(nèi)不同作業(yè)線的集裝箱實(shí)現(xiàn)了錯峰作業(yè)，減少了同一作業(yè)線集裝箱作業(yè)時阻塞情況的出現(xiàn).也為堆場箱區(qū)箱位調(diào)度和移箱管理提供了更大的調(diào)整空間.

表7 布局分散度參考Table 7The distribution dispersion result in different dimension

7 研究結(jié)論

本文的創(chuàng)新和關(guān)注重點(diǎn)是從布局分散度的角度對傳統(tǒng)的船屬集裝箱分配問題進(jìn)行優(yōu)化.建立了仿真和建模相結(jié)合的兩階段箱位優(yōu)化配置方法.以集裝箱碼頭箱位分配問題為應(yīng)用背景，揭示了布局分散度對生產(chǎn)作業(yè)整體優(yōu)化的重要意義.未來研究應(yīng)著力將基于布局分散度的資源優(yōu)化方法理論化，進(jìn)一步的挖掘布局分散度在不同生產(chǎn)制造領(lǐng)域的應(yīng)用意義.

[1]Taleb-Ibrahimi M,B de Castilho,C F Daganzo.Storage space vs handling work in container terminals[J]. Transportation Research Part B:Methodological,1993. 27(1):13-32.

[2]Zhang C,J Liu,Y-w Wan,et al.Storage space allocation in container terminals[J].Transportation Research Part B:Methodological,2003.37(10):883-903.

[3]王斌.集裝箱碼頭堆場的一種動態(tài)隨機(jī)堆存方法[J].系統(tǒng)工程理論與實(shí)踐,2007,27(4):147-153.[WANG B.Dynamic and stochastic storage model in a container yard[J].Journal of Systems Science and Information, 2007.27(4):147-153.]

[4]Petering M E,K G Murty.Effect of block length and yard crane deployment systems on overall performance at a seaport container transshipment terminal[J].Computers &Operations Research,2009,36(5):1711-1725.

[5]Chen L,Z Lu.The storage location assignment problem for outbound containers in a maritime terminal[J]. International Journal of Production Economics,2012, 135(1):73-80.

[6]Le M,H Yu.The RHSA strategy for the allocation of outboundcontainersbasedonthehybridgenetic algorithm[J].Journal of Marine Science and Application, 2013,12(3):344-350.

[7]樂美龍，于航.考慮箱區(qū)利用率的出口箱資源配置啟發(fā)式算法[J].計算機(jī)工程與應(yīng)用,2013,49(8):231-235.[LE M L,YU H.A heuristic algorithm for outbound container allocation considering the different utilization betweenblocks[J].ComputerEngineeringand Applications,2013,49(8):231-235.]

Two-stage Optimization of Container Assignment Based on Distribution Dispersion

YU Hang1a,GE Yin-gen1b,LE Mei-long2,TAN Cai-mao1c
(1a.School of Economics&Management;1b.College of Transport and Communication;1c.Logistics Research Center, Shanghai Maritime University,Shanghai 201306,China;2.Ocean&Shipping Institute,Shanghai Jiaotong University,Shanghai 200231,China)

The optimization of resource scheduling for the container terminal is the key point of container handling.A new index called the distribution dispersion as the indicator of the optimization for the space scheduling of the production resources is touched,which is related to the container assignment model in the container terminal to improve the efficiency of the following works.The distribution dispersion is discussed both in the yard template scheduling and the block assignment in different dimensions.A two-stage optimization model which the first is a simulation model of the operations and the second stage is a mixed integer quadratic programming(MIQP)model is built to find the best assignment solution.A series of real production data are used to carry out the two-stage optimization.An improvement of the handling and ease of the congestion are shown from the result.The profound meanings of the distribution dispersion are obvious in the scheduling of the resource from our research.

waterwaytransportation;distributiondispersion;two-stageoptimization;container assignment;mixed integer quadratic programming

1009-6744（2015）05-0223-08

U691.3

A

2015-04-24

2015-06-25錄用日期：2015-07-06

國家自然科學(xué)基金項(xiàng)目（51409157，61304203）；上海市自然科學(xué)基金(12ZR1444800)；上海海事大學(xué)優(yōu)秀博士學(xué)位論文培育項(xiàng)目（2015BXLP003）；上海市自然科學(xué)基金創(chuàng)新行動計劃項(xiàng)目(10190502500).

于航(1989-)，男，江蘇徐州人，博士生. ＊

yege@shmtu.edu.cn