基于滾動計劃的堆場出口箱存儲位置分配兩階段模型

劉嬋娟,胡志華

基于滾動計劃的堆場出口箱存儲位置分配兩階段模型

劉嬋娟,胡志華

(上海海事大學(xué)物流研究中心,上海201306)

考慮出口箱進場時間的隨機性,將集裝箱堆場出口箱箱位分配問題分為兩個階段進行研究:①在滾動計劃的基礎(chǔ)上,以最小化場內(nèi)集卡運輸距離為目標建立整數(shù)規(guī)劃模型,對到場出口箱進行箱區(qū)分配;②以取箱裝船過程中貝位內(nèi)翻箱數(shù)最小和平衡貝位內(nèi)各堆棧箱數(shù)為目標,建立堆場出口箱具體箱位分配的多目標優(yōu)化模型.應(yīng)用Matlab軟件中Yalmip工具箱編程求解,通過數(shù)值實驗驗證了模型的有效性.實驗結(jié)果表明,該方法能夠有效解決堆場出口箱箱位分配問題,減小堆場設(shè)備作業(yè)量,并通過減少翻箱操作提高碼頭作業(yè)效率.

堆場位置分配;出口箱;滾動計劃;多目標混合整數(shù)規(guī)劃

在集裝箱碼頭堆場中,出口箱的裝載順序?qū)Υ斑\輸效益會產(chǎn)生影響.在堆放集裝箱時,配載人員通常盡可能地在保持船舶穩(wěn)定前提下,減少起重機和堆場設(shè)備的作業(yè)量,且要滿足集裝箱的目的港以及大小等位置分配的要求.為了得到有效的裝載順序,出口箱必須被分配在適當(dāng)?shù)奈恢?因此針對集裝箱堆場出口箱的存儲空間分配問題,國內(nèi)外專家們提出了不同的解決方法和策略.

Talebibrahimi等[1-2]分析了堆場存儲空間的固定需求,提出了針對臨時箱存儲空間分配的策略,但其研究主要針對分配給每艘船舶的空間大小,而沒有考慮到場集裝箱具體存儲位置的分配;Kang等[3]和Kim等[4-5]均僅以最小化堆場作業(yè)時翻箱量為目標來進行堆場箱位分配;Preston等[6]和Bazzazi等[7]運用遺傳算法求解了堆場出口箱箱位分配問題,但是Bazzazi等[7]在應(yīng)用遺傳算法來確定出口箱存儲位置時,并沒有考慮出口集裝箱到場的隨機性;另外,還有學(xué)者采用兩階段法進行堆場出口箱箱位分配[8-11].但是,以上研究均沒有考慮堆場作業(yè)現(xiàn)實操作中晝夜不停的連續(xù)作業(yè)特性.

Park等[12]采用滾動計劃周期的方法對堆場作業(yè)的計劃周期進行模擬,以計劃周期內(nèi)各個箱區(qū)之間的作業(yè)量不均衡最小化為目標函數(shù),建立整數(shù)規(guī)劃模型,對進入堆場的集裝箱進行箱位分配.李建忠等[13]從平衡箱區(qū)貝位箱量和最小化集卡行駛距離入手,在滾動計劃的基礎(chǔ)上建立了集裝箱堆場空間動態(tài)配置模型.該模型的主要目的是提高集卡作業(yè)效率,降低裝船作業(yè)過程中堆場機械耗費成本.Kim等[14]針對集裝箱堆場存儲空間分配問題,以提高空間利用率和堆場集裝箱裝卸效率為目標,建立了基于滾動計劃的混合整數(shù)規(guī)劃模型,并設(shè)計了基于集裝箱在場時間和次梯度優(yōu)化技術(shù)的啟發(fā)式算法進行求解.但是,該模型和算法只解決了集裝箱到場后的箱區(qū)分配問題,并未給出到場集裝箱具體位置分配方法.

基于Kim等[14]的研究,本工作考慮出口箱進場時間的隨機性,將堆場出口箱箱位分配問題分兩個階段進行研究:①在滾動計劃的基礎(chǔ)上,以最小化場內(nèi)集卡運輸距離為目標建立整數(shù)規(guī)劃模型,對到場出口箱進行箱區(qū)貝位分配;②以取箱裝船過程中貝位內(nèi)翻箱數(shù)最小和平衡貝位內(nèi)各堆棧箱數(shù)為目標,建立堆場出口箱箱位分配的多目標優(yōu)化模型來進行具體的箱位分配.最后,本工作通過數(shù)值實驗驗證了模型的有效性.與已有研究相比,本工作的貢獻主要在于考慮了現(xiàn)實操作中堆場作業(yè)晝夜不停的連續(xù)作業(yè)特性,在使翻箱操作量最小和集卡運輸距離最短的同時,使貝位內(nèi)各堆棧中的箱數(shù)達到均衡,這既可以減少起重機工作量,又能防止堆棧過高而發(fā)生傾倒,從而提高堆場作業(yè)的安全性.

1 問題描述與假設(shè)

現(xiàn)代集裝箱碼頭作業(yè)系統(tǒng)主要包括堆場作業(yè)、集卡作業(yè)和前方泊位作業(yè)系統(tǒng),其中堆場作業(yè)系統(tǒng)的任務(wù)有進口及轉(zhuǎn)運集裝箱卸載后的箱位安排問題、出口集裝箱到場的箱位安排、空箱到場的堆垛策略以及堆場各設(shè)備的協(xié)同作業(yè)配置計劃等(見圖1).本工作主要研究堆場作業(yè)系統(tǒng)中出口箱到場后的箱位安排問題.

由于堆場作業(yè)是晝夜不停的連續(xù)作業(yè),因此采用滾動計劃的方法對堆場作業(yè)的計劃周期進行模擬.考慮到在實際生產(chǎn)作業(yè)中,出口箱到場的提前期通常為1～3 d,故選取3 d為一個計劃周期,每天分2個計劃階段,故一個計劃期共有6個階段,其中每個計劃階段12 h.在實際生產(chǎn)時,僅根據(jù)計劃期首日制定的計劃完成當(dāng)天的生產(chǎn),計劃期次日的生產(chǎn)根據(jù)下一計劃期首日信息與本計劃期現(xiàn)有信息綜合決定.依此類推,滾動進行每天生產(chǎn)計劃的制定.滾動計劃周期示意圖如圖2所示.

堆場空間資源配置優(yōu)化的目的是:①減少船舶在港停留時間以提高港口生產(chǎn)效率;②使港口設(shè)備利用率最大化以降低港口運營成本.本工作采用兩階段分析方法,將堆場出口箱存儲空間配置問題分為兩個階段:①為了提高堆場設(shè)備利用率和降低場內(nèi)集卡運輸成本,在平衡各箱區(qū)貝位作業(yè)量的約束下將集裝箱分配到各個箱區(qū)貝位中;②以取箱裝船過程中貝位內(nèi)翻箱數(shù)最小和各堆棧箱數(shù)均衡為目標建立多目標規(guī)劃模型進行具體箱位分配(見圖3).

圖1 集裝箱堆場作業(yè)系統(tǒng)Fig.1 Container yard operation system

圖2 滾動計劃周期示意圖Fig.2 Illustration of the rolling plan schedule

2 模型建立

2.1 箱區(qū)分配模型M1

2.1.1 符號說明

(1)集合.I為計劃初期需要被分配存儲空間的船舶集合,I={1,2,···,NI},NI為待裝船舶總數(shù),通過i∈I索引;J為滾動計劃周期階段數(shù),J={1,2,···,NJ},NJ為計劃周期內(nèi)計劃階段總數(shù),通過j∈J索引;M 為堆場箱區(qū)集合,M={1,2,···,NM},NM為堆場箱區(qū)總數(shù),通過m∈M索引.

(2)參數(shù).Cm為箱區(qū)m的最大堆存容量;mi為能分配給船舶i的最大箱區(qū)數(shù);B為一個很大正整數(shù);dij為j階段到達堆場的i船集裝箱數(shù);xm0i為開始時刻,m箱區(qū)中已有的i船集裝箱數(shù);c1為場內(nèi)集卡運輸一個集裝箱的單位距離運輸成本;tmi為從泊位i到箱區(qū)m的運輸距離.

(3)變量.xmji為j階段到達堆場的i船集裝箱被分配到m箱區(qū)中的數(shù)量;在m箱區(qū)中有i船集裝箱時,設(shè)變量δmi等于1,否則等于0.

圖3 堆場出口箱存儲空間配置方案Fig.3 Storage space allocation scheme for export containers in the yard

2.1.2 模型

第一階段模型M1的目標是使場內(nèi)集卡的總運輸成本最低,其目標函數(shù)如式(1)所示.式(2)～(6)是約束條件,其中式(2)表示任一箱區(qū)中堆存的集裝箱數(shù)不能超過箱區(qū)最大容量;式(3)表示任一階段所有箱區(qū)中放入的集裝箱數(shù)之和等于該階段到達堆場的集裝箱總數(shù);式(4)表示任一階段放入m箱區(qū)的i船集裝箱數(shù)大于等于0;式(5)表示在一個計劃周期結(jié)束后,如m箱區(qū)中有i船集裝箱,則δmi等于1,否則等于0;式(6)表示i船集裝箱所占的箱區(qū)數(shù)不能超過規(guī)定的最大值.

2.2 貝位及具體箱位選擇模型M2

2.2.1 符號說明

(1)集合.I={1,2,···,NI}為所有出口集裝箱的集合,NI為到場集裝箱總數(shù),通過i,j∈I索引;B={1,2,···,NB}為箱區(qū)內(nèi)貝位集合,NB為箱區(qū)內(nèi)貝位總數(shù),通過b∈B索引;R={1,2,···,NR}為貝位內(nèi)列數(shù)的集合,NR為貝位內(nèi)總列數(shù),通過r∈R索引;T={1,2,···,NT}為貝位內(nèi)層數(shù)的集合,NT為貝位內(nèi)總層數(shù),通過t∈T索引.

(2)參數(shù).Ei,j表示貝位內(nèi)滿足時間先后順序先到先堆存(early arrive early stack,EAES)原則的箱子,當(dāng)集裝箱i和j的放置滿足時間先后順序時Ei,j取1,否則取0;Wi,j表示貝位內(nèi)滿足重箱在上原則(light below heavy,LBH)約束原則的箱子數(shù),當(dāng)集裝箱i和j的放置滿足重量約束時Wi,j取1,否則取0;Ob,r,t表示貝位內(nèi)已被占用的箱位;Cb表示b貝位內(nèi)的集裝箱在取箱裝船過程中集卡運輸成本,該成本與貝位離岸邊的距離成正比,Cb∈{1,2,···,B},通過b∈B索引.

(3)決策變量.xi,b,r,t∈{0,1},如集裝箱i被放置在b貝r列t層的位置時,xi,b,r,t的值為1,否則為0;yi,j,b,r,t1,t2∈{0,1},如集裝箱i和j被分配到(b,r,t1)和(b,r,t2)兩個箱位時足時間先后順序EAES約束原則時zwi,j,b,r,t1,t2的值為1,否則為0.

2.2.2 模型

在第二階段進行貝位和具體箱位選擇時,本工作建立了多目標混合整數(shù)優(yōu)化模型M2.

M2的目標函數(shù)如式(7)所示,式(7)表示最小化貝位內(nèi)翻箱操作數(shù)、最小化場內(nèi)集卡運輸距離和使貝位內(nèi)各堆棧中箱數(shù)均衡.式(8)中frehandle為翻箱操作數(shù),式(9)中fw為不滿足重量約束原則的箱數(shù),式(10)中fe為不滿足時間先后順序原則的箱數(shù),式(11)中fb為存儲在貝位中集裝箱在取箱裝船過程中的運輸成本,式(12)中fh為堆棧堆存高度.式(13)～(21)是約束條件,其中式(13)表示一個集裝箱只能占用一個箱位,式(14)表示一個箱位只能放一個箱子,式(15)表示某一貝位內(nèi)堆存集裝箱總數(shù)不能超過貝內(nèi)箱位數(shù),這里假定每貝由6列4層構(gòu)成,且有3個緩沖箱位,則貝內(nèi)可堆存集裝箱數(shù)最多為21個.式(16)表示決策變量yi1,i2,b,r,t1,t2和xi,b,r,t之間的關(guān)系,只有當(dāng)i1和i2集裝箱分別分配給箱位(b,r,t1)和(b,r,t2)時,決策變量yi1,i2,b,r,t1,t2的值為1,否則為0,式(17)表示箱子不能懸空放置.式(18)和(19)表

在模型M2的基礎(chǔ)上,提出模型M3和M4對該問題進行優(yōu)化.

M3是對目標函數(shù)fh的最小值進行求解,使貝位內(nèi)各堆棧箱數(shù)盡量均衡,避免堆存過高;M4是將目標函數(shù)fh和fb作為一個整體進行優(yōu)化.該過程分為兩個階段:①根據(jù)M3求出目標函數(shù)fh的最小值,令其等于fh?;②是對目標函數(shù)fb優(yōu)化,其中α是目標函數(shù)fh的松弛系數(shù).

3 算例

為了驗證本工作提出的基于滾動計劃的堆場出口箱箱位分配兩階段模型的正確性和有效性,運用Matlab中的Yalmip工具箱包含的線性規(guī)劃求解算法,輸入統(tǒng)一的建模語言,得到M1的最優(yōu)箱區(qū)分配方案和M2的最優(yōu)具體箱位分配方案.

算例1 運用模型M1對集裝箱堆場出口箱進行箱區(qū)優(yōu)化配置.假定一個計劃周期為3 d,每天分為2個階段,則一個計劃周期共6個階段;待裝船舶數(shù)NI為3,箱區(qū)數(shù)為5,每個箱區(qū)的最大容量為42.為了使同一船舶的集裝箱能夠盡可能地集中堆存,故分配給每艘船舶的最大箱區(qū)數(shù)均為2.場內(nèi)集卡運輸單個集裝箱的單位運輸成本為1,其余輸入?yún)?shù)如表1和2所示.所得場內(nèi)集卡運輸成本為440,箱區(qū)分配結(jié)果如圖(4)～(6)所示.

表1 j階段到達堆場的i船集裝箱數(shù)djiTable 1 Container number djiof ship i arriving at the yard at stage j

表2 m箱區(qū)到i船的距離tmiTable 2 Distance tmifrom block m to ship i

圖4 船舶1的集裝箱箱區(qū)分配Fig.4 Block distributions of containers on ship 1

圖5 船舶2的集裝箱箱區(qū)分配Fig.5 Block distributions of containers on ship 2

圖6 船舶3的集裝箱箱區(qū)分配Fig.6 Block distributions of containers on ship 3

算例2 運用模型M2對集裝箱堆場出口箱進行具體箱位分配.本工作以實際最常見的每貝6列4層堆場為例,假定每個貝位中有3個箱位為緩沖箱位,以每個箱區(qū)有2個貝位,24個集裝箱的存儲任務(wù)為基本算例,驗證模型M2的實用性.24個出口箱隨機到場順序及重量分布如表3所示,所得具體箱位分配方案如圖7所示.

表3 24個出口箱的時間順序和重量分布Table 3 Time sequence and weight distributions of 24 containers

圖7 24個集裝箱具體箱位分配Fig.7 Specif i c space allocations of 24 containers

4 實驗分析

為了進一步分析參數(shù)變化對實驗結(jié)果的影響,本工作設(shè)計了4組實驗場景,場景描述和不同場景中模型需作的調(diào)整如表4所示.

表4 實驗?zāi)康暮团渲肨able 4 Experimental purposes and settings

基于以上4個實驗,對所得結(jié)果結(jié)合圖(8)～(12)進行分析,得出如下結(jié)論.

(1)由實驗1的結(jié)果可知,當(dāng)箱區(qū)容量和每階段到達堆場的集裝箱數(shù)以及場內(nèi)集卡單位運輸成本保持不變時,分配給船舶i的箱區(qū)數(shù)越多,則目標函數(shù)值越小,場內(nèi)集卡運輸成本越小(見圖8).

圖8 模型M1中參數(shù)mi對實驗結(jié)果的影響Fig.8 Inf l uence of parameters mion the results in model M1

(2)由實驗2的結(jié)果可知,參數(shù)Ob,i,t變化對目標函數(shù)fw,fe的值并無影響.在算例2中,當(dāng)有2個貝位時,目標函數(shù)fb和fh的值會隨著已被占用箱位數(shù)的變化而變化.總體上,已被占用的箱位數(shù)越多,則目標函數(shù)fh的值越大,即堆棧越高.集裝箱堆存太高可能引發(fā)倒塌,存在安全隱患.此外,貝內(nèi)堆棧高度分布不均衡將會增加取箱裝船過程中場橋移動距離,提高機械作業(yè)成本(見圖9).

圖9 模型M2中參數(shù)Ob,i,t對實驗結(jié)果的影響Fig.9 Inf l uence of parameters Ob,i,ton the results in Model M2

(3)由實驗3的結(jié)果可知,假如不考慮各堆棧中箱子數(shù)均衡原則,即在模型M2中去掉第4個目標函數(shù),則箱位分配方案會發(fā)生改變(見圖10).兩種分配方式所得目標函數(shù)fb,fh的值如圖11所示.由實驗結(jié)果可知,在考慮各堆棧箱數(shù)均衡原則的情況下,集裝箱存儲成本較高,為34;而不考慮各堆棧箱數(shù)均衡原則的情況下,堆存成本只有31.相反,在考慮各堆棧箱數(shù)均衡原則的情況下,目標函數(shù)fh的值僅為118,在不考慮各堆棧箱數(shù)均衡原則的情況下fh的值為168.在考慮各堆棧箱數(shù)均衡原則的情況下,集裝箱明顯堆存于較低層.這樣不但提高了堆棧的安全性,而且有利于在取箱裝船過程中減少場橋上下移動距離,降低機械作業(yè)成本.

圖10 不考慮堆棧中箱數(shù)均衡原則時24個集裝箱箱位分配Fig.10 Specif i c space allocation of 24 containers not considering the number equilibrium in each stack

(4)以算例2中24個集裝箱數(shù)據(jù)為例,根據(jù)模型M3和M4對目標函數(shù)fh和fb進行均衡分析.結(jié)合圖12可知,當(dāng)fh的松弛系數(shù)α值在0.8到2.4之間時,存儲成本fb的值幾乎呈線性減小;而當(dāng)fh的值大于2.4時,存儲成本fb的值保持為20,不再改變.當(dāng)fb在34～20之間時,兩個目標可以同時優(yōu)化.

圖11 兩種不同分配方式所得fb和fh的值Fig.11 Values of fband fhin two dif f erent distribution ways

圖12 fh和fb之間的均衡分析Fig.12 Tradeof fanalysis between fhand fb

5 結(jié)束語

在滾動計劃的基礎(chǔ)上,以最小化場內(nèi)集卡運輸成本和最小化翻箱操作數(shù)為目標,建立了集裝箱堆場出口箱箱位分配的兩階段整數(shù)規(guī)劃模型,并通過不同算例分析,驗證了模型的有效性,結(jié)果顯示本模型能夠在優(yōu)化場內(nèi)集卡水平運輸距離的同時,平衡各箱區(qū)作業(yè)量且盡可能減少翻箱操作量.對集裝箱碼頭堆場出口箱區(qū)的存儲位置分配問題有一定的借鑒意義.但是,在實際生產(chǎn)過程中由于各個堆場作業(yè)計劃周期不同,堆場作業(yè)設(shè)備數(shù)量不同,以及出口箱到場的隨機性等因素,都將不同程度增大出口箱箱位分配的難度.因此,在以后的工作中可融入出口箱到場的隨機性因素,以進一步增強集裝箱碼頭堆場出口箱存儲位置分配的準確性,提高堆場作業(yè)的效率.

[1]TALEbIbRAHIMI D C M.Modeling and analysis of container storage in ports[J].Journal of Clinical Microbiology,1989,47(12):4144-4145.

[2]TALEbIbRAHIMI D C M,CASTILHO B D,DAGANZO C F.Storage space vs.handling work in container terminals[J].Transportation Research Part B Methodological,1993,27(1):13-32.

[3]KANG J K R,KIM R K H.Deriving stacking strategies for export containers with uncertain weight information[J].Intelligent Manufacturing,2006,17:399-410.

[4]KIM K H.Evaluation of the number of rehandlings in the container yards[J].Computers and Industrial Engineering,1997,32(4):701-711.

[5]KIM K H,PARk Y M,RYU K R.Deriving decision rules to locate export containers in container yards[J].European Journal of Operational Research,2000,124(1):80-101.

[6]PRESTON P,KOZAN E.An approach to determine storage locations of containers at seaport terminal[J].Computers and Operations Research,2001,28(10):983-995.

[7]BAZZAZI M,SAFAEI 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.

[8]CHEN L,LU Z.The storage location assignment problem for outbound containers in a maritime terminal[J].International Production Economics,2012,135:73-80.

[9]HU W,WANG H,MIN Z.A storage allocation algorithm for outbound containers based on the outer-inner cellular automation[J].Information Sciences,2014,281:147-171.

[10]ZHANG C,LIU J,WAN Y W,et al.Storage space allocation in container terminals[J].Transportation Research Part B,2003,37:883-903.

[11]靳志宏,毛鈞,李娜.基于混合動態(tài)規(guī)劃的集裝箱堆場貝位內(nèi)翻箱作業(yè)調(diào)度優(yōu)化[J].交通運輸系統(tǒng)工程與信息,2011,16(3):131-136.

[12]PARk T,CHOE R,KIM Y H.Dynamic adjustment of container stacking policy in an automated container terminal[J].International Journal of Production Economics,2011,133(25):385-392.

[13]李建忠,丁以中,王斌.集裝箱堆場空間動態(tài)配置模型[J].交通運輸工程學(xué)報,2007,3(7):50-55.

[14]KIM K H,PARk K T.A note on a dynamic space-allocation method for outbound containers[J].European Journal of Operational Research,2003,148:92-101.

Two-stage model for outbound containers’space allocation assignment using rolling horizon method

LIU Chanjuan,HU Zhihua
(Logistics Research Center,Shanghai Maritime University,Shanghai 201306,China)

This paper addresses storage location assignment for outbound containers.Considering randomness of the containers’approach time,this study divides the problem into two phases.The f i rst is distribution of blocks and bays for containers based on a rolling plane.The second is to propose a multi-objective optimization model to minimize reshuffling and balance the number of each stack.The Yalmip toolbox of Matlab is used to solve the problem.Experimental results show that proposed method can ef f ectively solve the space allocation problem for outbound containers,and reduce the amount of yard equipment operations.Efficiency of the terminal operation is signif i cantly improved by reducing reshuffling.

yard space allocation;outbound container;rolling horizon method;multiobjective mixed integer programming

U 691.3

A

1007-2861(2017)05-0789-12

10.12066/j.issn.1007-2861.1741

2016-02-19

國家自然科學(xué)基金面上資助項目(71471109);國家自然科學(xué)基金青年資助項目(71101088);教育部博士點基金資助項目(20113121120002);交通部應(yīng)用基礎(chǔ)研究資助項目(2015329810260);上海市教委科研創(chuàng)新資助項目(14YZ100);上海市曙光計劃資助項目(13SG48)

胡志華(1977—),男,教授,博士,研究方向為港航與物流運作優(yōu)化、社會科學(xué)計算實驗和計算智能.

E-mail:zhhu@shmtu.edu.cn