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

劉嬋娟,胡志華

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

劉嬋娟,胡志華

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

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

堆場位置分配;出口箱;滾動計劃;多目標混合整數規劃

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

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

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

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

1 問題描述與假設

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

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

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

圖1 集裝箱堆場作業系統Fig.1 Container yard operation system

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

2 模型建立

2.1 箱區分配模型M1

2.1.1 符號說明

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

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

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

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

2.1.2 模型

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

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

2.2.1 符號說明

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

(2)參數.Ei,j表示貝位內滿足時間先后順序先到先堆存(early arrive early stack,EAES)原則的箱子,當集裝箱i和j的放置滿足時間先后順序時Ei,j取1,否則取0;Wi,j表示貝位內滿足重箱在上原則(light below heavy,LBH)約束原則的箱子數,當集裝箱i和j的放置滿足重量約束時Wi,j取1,否則取0;Ob,r,t表示貝位內已被占用的箱位;Cb表示b貝位內的集裝箱在取箱裝船過程中集卡運輸成本,該成本與貝位離岸邊的距離成正比,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 模型

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

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

在模型M2的基礎上,提出模型M3和M4對該問題進行優化.

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

3 算例

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

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

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

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

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

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

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

算例2 運用模型M2對集裝箱堆場出口箱進行具體箱位分配.本工作以實際最常見的每貝6列4層堆場為例,假定每個貝位中有3個箱位為緩沖箱位,以每個箱區有2個貝位,24個集裝箱的存儲任務為基本算例,驗證模型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 實驗分析

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

表4 實驗目的和配置Table 4 Experimental purposes and settings

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

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

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

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

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

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

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

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

圖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 結束語

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

[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]靳志宏,毛鈞,李娜.基于混合動態規劃的集裝箱堆場貝位內翻箱作業調度優化[J].交通運輸系統工程與信息,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]李建忠,丁以中,王斌.集裝箱堆場空間動態配置模型[J].交通運輸工程學報,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

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

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

E-mail:zhhu@shmtu.edu.cn