景貞文， 韓曉龍

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

?

自動化碼頭雙ASC優(yōu)先權規(guī)則及避讓方案仿真

景貞文， 韓曉龍

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

摘要：為了減少自動化集裝箱碼頭中，由于雙自動堆垛起重機(雙ASC)之間互相干擾造成的完工時間的延遲，提出9條優(yōu)先權分配規(guī)則和兩種避讓方案——直接避讓和動態(tài)暫存區(qū)。為了選擇最合適的分配規(guī)則和避讓方案，在回顧相關研究及反復實驗的基礎上，仿真實驗將總任務數(shù)設置為100個，根據(jù)海側任務比例(30%、40%、50%、60%、70%)將實驗劃分為5個等級。仿真結果表明，在80%的實驗中，直接避讓比動態(tài)暫存區(qū)的避讓方案的最短完工時間少至少30 s；規(guī)則LonOri(選擇在完成當前任務的前提下，距離下一任務的始發(fā)地具有最短運行時間的ASC賦予其優(yōu)先權)或者規(guī)則LonFin(選擇花費更多時間完成當前任務的ASC賦予其優(yōu)先權)可以在至少60%的試驗中取得最短完工時間。研究結果表明，規(guī)則LonOri和LonFin以及直接避讓都可以有效減少完工時間。

關鍵詞：雙自動堆垛起重機(雙ASC)； 仿真； 優(yōu)先權分配； 動態(tài)暫存區(qū)

隨著經(jīng)濟全球化的發(fā)展，集裝箱碼頭的貨運工作量持續(xù)增加，越來越多的集裝箱碼頭急切地實施新型自動化技術提高效率來維持競爭力。其中，自動堆垛起重機(automated storage cranes，ASC)作為自動化集裝箱碼頭的主要自動化設備，也越來越多地應用到碼頭中。

ASC是軌道吊的一種，一般放置在垂直于碼頭泊位的堆場箱區(qū)，并在堆場箱區(qū)頂端通過水平運輸系統(tǒng)與岸邊對接。ASC在箱區(qū)將集裝箱吊起并沿箱區(qū)軌道搬運至目的地。每個箱區(qū)上通常運行有2個ASC：一個負責海側作業(yè)，一個負責陸側作業(yè)。2個相同型號的ASC運行在同一軌道上，由于不能互相穿套，作業(yè)時可能產生干擾。本文的研究重點就是雙ASC產生干擾時的優(yōu)先權分配以及避讓規(guī)則問題。

對于堆場起重機設備的研究，國內外許多學者都集中在通過算法優(yōu)化場橋的調度，例如Ng[1]利用基于動態(tài)規(guī)劃的啟發(fā)式算法研究了堆場內只有一條是雙向車道的前提下，多臺場橋設備操作優(yōu)化的問題；Zhou等[2]在雙場橋起重機調度研究中提出了交換點的概念，用優(yōu)化算法最小化延遲時間和延遲的工作數(shù)量；文獻[3-6]通過建立混合整數(shù)規(guī)劃模型以及算法的應用解決場橋的調度問題；Chang等[7]提出新的動態(tài)滾動策略來優(yōu)化場橋調度問題。也有學者從多種設備的集成調度來研究場橋調度，如Lau等[8]考慮多種港口設備資源的同步化問題，集成調度等；文獻[9]以集卡等待時間為最小目標建立了單場橋動態(tài)調度的混合整數(shù)規(guī)劃模型；Carlo等[10]重點研究了新型自動化存取系統(tǒng)(AS/RS)中兩臺設備的作業(yè)分配問題。與本文研究方向類似的有：Park等[11]對自動化碼頭中雙RMG提出了基于啟發(fā)式和局部搜索的實時調度方法，并提出了通過分配優(yōu)先權給海側ASC以及當前工作序列排名靠前的RMG來解決RMG之間的干擾的方法；Dorndorf等[12]提出了1個由3個ASC組成的ASC系統(tǒng)，其中有1個ASC是比較大的，另外2個ASC是比較小的且是相同大小的，這樣，2個小的ASC就會從大的ASC下穿過。他們的研究的目標是最大化生產力，同時阻止延遲干擾的發(fā)生。

本文與以上研究的主要不同在于提出了9條優(yōu)先權分配規(guī)則以及直接避讓和動態(tài)暫存區(qū)(交換點)避讓2種避讓方案來實現(xiàn)雙ASC的調度。

1系統(tǒng)和問題描述

本文研究的系統(tǒng)和問題都是在以下假設下進行的。

1)雙ASC速度相同，且不因承重改變。

2)干擾產生之后系統(tǒng)才能識別干擾，而不能實現(xiàn)預見干擾。

3)堆場存貯能力足夠。

4)ASC作業(yè)時間不變。

圖1給出了本文研究的堆場雙ASC布局模型。模型中有2輛ASC，C1和C2，位于堆場箱區(qū)的兩側，分別負責海側和陸側的作業(yè)。在箱區(qū)兩端各有一個暫存區(qū)，負責暫存來自海陸兩側的任務集裝箱。

圖1　雙ASC布局模型

圖1中，雙ASC在到達各自的任務地點前，可能會產生干擾。導致任務不能按時完成，造成整個系統(tǒng)完工時間的延遲。為了使系統(tǒng)快速地完成任務，要選擇最佳的優(yōu)先權分配以及非優(yōu)先權ASC避讓方案，減少干擾引起的延遲。因此，本文的研究重點是：1)在已知任務序列的情況下，確定兩輛ASC的優(yōu)先權分配規(guī)則；2)非優(yōu)先權的ASC避讓方案。

關于ASC之間優(yōu)先權分配規(guī)則，會在本文第3部分進行詳細的介紹。關于非優(yōu)先權的ASC的避讓方式，本文提出了2個方案:一是直接回避，非優(yōu)先權ASC退讓到不影響優(yōu)先權ASC作業(yè)而又能夠最小化等待時間的地點等待；方案二是動態(tài)暫存區(qū)，即選擇一個距離優(yōu)先權ASC作業(yè)點最近的可行區(qū)作為動態(tài)暫存區(qū)，將非優(yōu)先權ASC的任務暫時存放在動態(tài)暫存區(qū)，等待優(yōu)先權ASC作業(yè)完畢后，運行到動態(tài)暫存區(qū)繼續(xù)完成非優(yōu)先權的ASC的作業(yè)任務。

本文借助圖表識別ASC避讓方案的運動軌跡:Fij和Gij分別代表C1和C2的運動軌跡，其中i=1,2,…,n代表ASC要執(zhí)行的第i個作業(yè)任務，j=1，2，3，4，2+,4+代表ASC執(zhí)行一個作業(yè)任務要完成的步驟，具體步驟如表1所示。例如F23代表C1正在執(zhí)行第2個作業(yè)任務的第3步，即C1正在把第2個作業(yè)任務的目標集裝箱運輸?shù)侥繕素愇弧?/p>

表1　步驟描述

表2　雙ASC作業(yè)任務順序

基于表2給出的雙ASC作業(yè)任務順序，圖2給出了2個大小不一的ASC在可穿套情況下的作業(yè)軌跡圖。

圖2　可穿套雙ASC作業(yè)軌跡

通過分段函數(shù)圖表可以簡單地判斷，在不可互相穿套的雙ASC作業(yè)下，如果按照給定的作業(yè)順序操作，C1和C2會在第5個貝位附近發(fā)生干擾。為了避免這種干擾，如果采用動態(tài)暫存區(qū)的避讓方案，并賦予C1優(yōu)先權，雙ASC的作業(yè)軌跡圖如圖3所示。其中，在t=4附近時，C2由第6個貝位返回至第7個貝位，G14+代表C2將第1個作業(yè)任務暫時存放在第7個貝位(動態(tài)暫存區(qū))，相應地，在t=6時，C1完成第1個作業(yè)任務，F(xiàn)G11代表C1正在向C2的第1個作業(yè)任務的暫存區(qū)(第7個貝位)運行，F(xiàn)G12+代表C1正在動態(tài)暫存區(qū)拾取C2的第1個作業(yè)任務，F(xiàn)G13代表C1正在將C2的第1個作業(yè)任務運輸?shù)狡淠繕素愇?第4個貝位)，F(xiàn)G14+代表C1將C2的第1個作業(yè)任務集裝箱釋放到目標貝位的過程，則在t=11時，C2的第1個作業(yè)任務完成。通過圖3可以得到在動態(tài)暫存區(qū)避讓方案中各作業(yè)任務的實際完工時間。

圖3　動態(tài)暫存區(qū)的雙ASC作業(yè)軌跡

2規(guī)則

參照Carlo等[13]的觀點，本文提出了9條雙ASC優(yōu)先權分配規(guī)則。

R1:(PricC1)C1一直有優(yōu)先權。

R2:(PricC2)C2一直有優(yōu)先權。

R3:(AdvFun)選擇距離當前任務最近的ASC，賦予其優(yōu)先權。

R4:(ShoOri)在完成當前任務的前提下，選擇距離下一任務的始發(fā)地有最短運行時間的ASC，賦予其優(yōu)先權。

R5:(LonOri)在完成當前任務的前提下，選擇距離下一任務的始發(fā)地有最長運行時間的ASC，賦予其優(yōu)先權。

R6:(ShoFin)選擇花費較短時間完成當前任務的ASC，賦予其優(yōu)先權。

R7:(LonFin)選擇花費較長時間完成當前任務的ASC，賦予其優(yōu)先權。

R8:(RemReq)選擇剩余任務最多的ASC，并賦予其優(yōu)先權。

R9:(Rand)隨機賦予ASC優(yōu)先權。例如，每個ASC有50%的可能擁有優(yōu)先權。

以上9條規(guī)則以及第2部分中提到的直接避讓和動態(tài)暫存區(qū)的避讓方案都會通過仿真軟件實現(xiàn)。要注意的是，本文提出這些優(yōu)先權分配規(guī)則的目的是實現(xiàn)堆場雙ASC作業(yè)的最短完工時間，但是每個規(guī)則適用的方案不同，并不是每條規(guī)則都能實現(xiàn)較短的完工時間。

3建模仿真

3.1仿真建模

eM-Plant是目前比較成熟的功能強大的作業(yè)系統(tǒng)仿真軟件，它是面向對象的、圖形化的、集成的建模、仿真工具[14]。集裝箱碼頭作業(yè)系統(tǒng)是一個復雜的離散系統(tǒng)，在eM-Plant中，通過修改SingleProc、Entity、Transporter、Bay等對象的屬性，可以將這些對象抽象成為岸橋、AGV、ASC、堆場、集裝箱等港口設備，來實現(xiàn)集裝箱碼頭作業(yè)的仿真。最重要的是，eM-Plant可以運用SimTalk語言為不同的對象編寫Method。Method可以用來修改對象的屬性，控制對象的運動，本文也是通過大量的Method在仿真中實現(xiàn)雙ASC之間9條規(guī)則和2種避讓方案的。

3.2仿真參數(shù)設置

本文研究的仿真模型主要包括港口作業(yè)的幾個過程：岸橋移動過程、裝載過程、卸載過程;AGV裝載過程、搬運過程、卸載過程;ASC裝載過程、搬運過程、卸載過程[15]。不管在實際操作還是仿真實驗中，由于資源調配不均或者突發(fā)狀況等，在每個過程中都可能存在等待時間。為了便于仿真模型的運行以及數(shù)據(jù)分析工作，本文將仿真模型中各裝卸設備的作業(yè)時間進行了簡化，具體如表3所示。

表3　仿真實驗參數(shù)設置

在不考慮其他因素的情況下，任務量是對完工時間影響最大的因素，是仿真實驗中重要的輸入?yún)?shù)?？紤]到仿真模型中堆場的存儲能力以及仿真結果的準確性，本文將仿真實驗的任務量設為100個。此次仿真實驗中，堆場任務包括海側進口任務和陸側進口任務，為了說明9條優(yōu)先規(guī)則和2種避讓方案的適用情況，仿真實驗根據(jù)海側任務比例劃分為5個等級，具體如表4所示。同時，完工時間作為主要的衡量數(shù)據(jù)，也是該仿真系統(tǒng)的主要輸出參數(shù)。

表4　仿真實驗等級設置

3.3仿真結果分析

從直接避讓的仿真結果(表5)可以看出，在5個等級實驗下，每個等級最優(yōu)的2個優(yōu)先權分配規(guī)則分別是：LonOri，LonFin；LonFin，RemReq；PriC1，LonFin；PriC1，LonOri；LonOri，RemReq。而且規(guī)則LonOri和LonFin都在3個等級的試驗下取得較短完工時間，所以，在直接避讓的方案中，最佳的優(yōu)先權分配規(guī)則應該是LonOri(在完成當前任務的前提下，選擇距離下一任務的始發(fā)地有最長運行時間的ASC，賦予其優(yōu)先權)和LonFin(選擇花費較長時間完成當前任務的ASC，賦予其優(yōu)先權)。

仿真實驗也給出了直接避讓方案下的延遲時間，結果如表6所示。從結果可以看出，AdvFun有最小的延遲時間，這與表5得到的最小完工時間是沖突的，經(jīng)過分析，原因可能有以下幾點：1)在不同等級的實驗下，產生的干擾次數(shù)是不一樣的；2)延遲時間與產生干擾時雙ASC所處的位置有關。

表5　直接避讓方案的完工時間仿真結果

表6　直接避讓延遲時間

動態(tài)暫存區(qū)避讓方案的仿真結果如表7所示。由于動態(tài)暫存區(qū)的避讓方案比直接避讓更加復雜，也面臨著更多的可能性。所以，各優(yōu)先權分配規(guī)則的優(yōu)勢并不明顯，不同等級試驗下的完工時間差別比較大。經(jīng)過對比可以發(fā)現(xiàn)，在動態(tài)暫存區(qū)避讓方案下，有4個等級的最短完工時間比直接避讓的最短完工時間長，所以綜合穩(wěn)定性以及最短完工時間可以看出，直接避讓的避讓方案比動態(tài)暫存區(qū)更有優(yōu)勢。此外，即使動態(tài)暫存區(qū)在避讓方案中并不是最優(yōu)選擇，但規(guī)則LonOri和LonFin仍是這個方案中相對具有優(yōu)勢的分配規(guī)則。

表7動態(tài)暫存區(qū)避讓方案的完工時間仿真結果

Tab.7Makespan simulation results of the dynamic exchange area

從圖4來看，等級Ⅲ的仿真結果較為平緩而且明顯優(yōu)于其他等級的試驗結果。相比之下，海陸兩側的任務數(shù)差別越大，其完工時間越長，而且波動越大。因此，在堆場雙ASC的實際操作中，當海陸兩側任務數(shù)差別不大時，可以選擇LonFin；當海側任務明顯大于陸側任務數(shù)時，選擇RemReq；當海側任務明顯小于陸側任務時，選擇LonOri。此外，在避讓方案的選擇上，直接避讓比動態(tài)暫存區(qū)更加優(yōu)化可行。

圖4　仿真結果折線圖

綜上所述，由于并不存在對于每個等級實驗都是最優(yōu)的分配規(guī)則，所以就整體而言，LonOri和LonFin是最具優(yōu)勢的優(yōu)先權分配規(guī)則。直接避讓的避讓方案比動態(tài)暫存區(qū)的避讓方案有明顯的優(yōu)勢，所以本文推薦直接避讓的避讓方案。

4結論

本文重點研究了雙ASC作業(yè)工藝下，雙ASC之間優(yōu)先權分配規(guī)則的問題，提出了9條優(yōu)先權分配規(guī)則以及直接避讓和動態(tài)暫存區(qū)兩種非優(yōu)先ASC避讓方案。以最小化完工時間為目標，并以其為衡量標準，通過5個等級的仿真實驗，對9條規(guī)則和2種避讓方案進行了評估。結果證明，在80%的實驗中，直接避讓比動態(tài)暫存區(qū)的避讓方案的最短完工時間少至少30 s，規(guī)則LonOri 和 LonFin可以在至少60%的實驗中取得最短完工時間。因此，本文得到整體而言最具優(yōu)勢的優(yōu)先規(guī)則LonOri 和 LonFin，而動態(tài)暫存區(qū)的避讓方案從仿真結果以及現(xiàn)實的堆場管理來講都不是一個較好的選擇。雖然本文的研究得到了較為理想的結果，但是也存在許多不足，比如，由于技術不足，不能在仿真過程中放入集裝箱出口過程；缺乏對固定暫存區(qū)的思考；仿真實驗中的等級設置考慮不足可能會影響到仿真結果，等等。這些問題都會在以后的研究中一一解決。

參考文獻：

[1]NG W C. Crane scheduling in container yards with inter-crane interference[J]. European Journal of Operational Research, 2005, 164(1):64-78.

[2]ZHOU W, WU X. An efficient optimal solution of a two-crane scheduling problem[J]. General Information, 2009, 26(1):31-58.

[3]KIM K H, PARK Y M. A crane scheduling method for port container terminals[J]. European Journal of Operational Research, 2004, 156(3):752-768.

[4]樂美龍, 林艷艷, 范志強. 基于兩階段啟發(fā)式算法的多場橋作業(yè)調度研究[J]. 武漢理工大學學報, 2012, 34(1):60-65.

LE Meilong, LIN Yanyan, FAN Zhiqiang. Research on multi-yard-crane scheduling problem based on two-phase heuristic algorithm[J]. Journal of Wuhan University of Technology, 2012, 34(1):60-65.

[5]趙磊, 胡志華, 李淑琴. 基于作業(yè)均衡的集裝箱堆場箱區(qū)場橋作業(yè)調度[J]. 武漢理工大學學報, 2013, 35(1):69-74.

ZHAO Lei, HU Zhihua, LI Shuqin. Container yard crane scheduling for operations balance between yard cranes[J]. Journal of Wuhan University of Technology,2013, 35(1):69-74.

[6]何軍良, 宓為建, 嚴偉. 基于爬山算法的集裝箱堆場場橋調度[J]. 上海海事大學學報, 2007, 28(4):11-15.

HE Junliang, MI Weijian, YAN Wei. Container yard crane scheduling based on hill-climbing algorithm[J].Journal of Shanghai Maritime University, 2007, 28(4):11-15.

[7]CHANG D, JIANG Z, YAN W, et al. Developing a dynamic rolling-horizon decision strategy for yard crane scheduling[J]. Advanced Engineering Informatics, 2011, 25(3):485-494.

[8]LAU H Y K, ZHAO Y. Integrated scheduling of handling equipment at automated container terminals[J]. Annals of Operations Research, 2008, 159(1):665-682.

[9]GUO X, HUANG S Y, WEN J H, et al. Dynamic yard crane dispatching in container terminals with predicted vehicle arrival information[J]. Advanced Engineering Informatics, 2011, 25(3):472-484.

[10]CARLO H J, VIS I F A. Sequencing dynamic storage systems with multiple lifts and shuttles[J]. International Journal of Production Economics, 2012, 140(2):844-853.

[11]PARK T, CHOE R, OK S M, et al. Real-time scheduling for twin RMGs in an automated container yard[J]. Or Spectrum, 2010, 32(3):593-615.

[12]DORNDORF U, SCHNEIDER F. Scheduling automated triple cross-over stacking cranes in a container yard[J]. Or Spectrum, 2010, 32(3):617-632.

[13]CARLO H J. Priority rules for twin automated stacking cranes that collaborate [J]. Computers & Industrial Engineering, 2015, 6(1):5-20.

[14]施於人,鄧易元. EM- Plant 仿真技術教程[M]. 北京:科學出版社,2009.

[15]張少凱, 韓曉龍, 胡少龍. 新舊工藝下集裝箱港口裝卸設備配置仿真研究[J]. 廣西大學學報(自然科學版), 2013, 38(2):368-373.

ZHANG Shaokai，HAN Xiaolong，HU Shaolong. Simulation of equipment allocation under two different handling technologies[J]. Journal of Guangxi University(Nature Science Ed, 2013, 38(2):368-373.

Twin ASCs Priority Rules and Avoidance Plans Simulation in Automated Container Terminal

JING Zhenwen， HAN Xiaolong

(Logistic Research Center, Shanghai Maritime University, Shanghai 201306, China)

Abstract：In order to reduce the delay of makespan caused by the interference between the twin ASCs in automated container terminal, nine priority rules and two avoidance plans are proposed: direct avoidance and dynamic exchange area. To choose the best priority rules and avoidance plans, on the basis of relevant research review and repeated experiments, the total number of tasks is set to 100, and the experiments will be divided into five levels according to the proportion of seaside tasks (30%, 40%, 50%, 60%, and 70%). The simulation results show that the shortest makespan in direct avoidance will be at least 30 seconds shorter than that for dynamic exchange area in 80% of the experiments; rules LonOri (giving priority to the ASC with the longest travel time to the origin of the next request, upon completion of the current request) and LonFin (giving priority to the ASC with the longest time to finish the current request) can get the shortest makespan in at least 60% of the experiments. The results show that the rules LonOri and LonFin and direct avoidance can effectively reduce the makespan.

Key words：twin automated storage cranes(twin ASCs); simulation; priority assignment; dynamic exchange area

收稿日期：2015- 07- 15

基金項目：上海市科委能力提升資助項目(14DZ2280200)

作者簡介：景貞文(1991-)，女，河南省人，碩士研究生，主要研究方向為自動化碼頭仿真.

doi:10.3969/j.issn.1007- 7375.2016.02.019

中圖分類號：TP391.9

文獻標志碼：A

文章編號：1007-7375(2016)02- 0128- 06