約束規劃求解自動化集裝箱碼頭軌道吊調度

丁 一， 田 亮， 林國龍

(上海海事大學 物流科學與工程研究院, 上海 201306)

2018年全球集裝箱海運量達2.01億TEU[1]，海運在當前世界物流體系中承擔超過70%的國際貨物運輸量，是國際物流運輸的絕對主力。港口作為海運物流中的重要節點，其作業效率關系到海運物流的運量。港口堆場是進出口集裝箱裝卸、堆存的主要場所，堆場中集裝箱起重機(簡稱“場橋”)的作業效率直接影響碼頭執行集裝箱運輸任務的數量。合理、高效的場橋調度策略不僅能幫助碼頭在單位時間內增加集裝箱流通量，而且能減少,甚至避免因場橋調度不當而造成任務延遲的情況。

關于場橋調度的研究,早期主要針對單場橋調度。KIM等[2]以任務總完成時間最小為目標建立混合整數規劃模型(Mixed Integer Programming,MIP)，研究場橋搬運過程中的合理任務順序;NARASIMHAN等[3]證明單場橋完成集裝箱裝卸任務為N-P難題，并用分支定界的枚舉法求出小規模任務情況下的最優解;NG等[4]以最小化任務總等待時間為目標，研究單臺起重機執行1組擁有不同準備時間的集裝箱搬運問題。隨著港口操作工藝的持續發展，研究者根據輪胎式起重機可跨箱區作業的特點，對多場橋在堆場聯合調度的問題進行探究。NG等[5]研究2臺場橋協同完成1組擁有不同準備時間的集裝箱搬運任務;ZHANG等[6]對堆場中各箱區在不同時段的任務量進行預測，重點規劃起重機移動時間和移動路線;CHEUNG等[7]以每段時間內延遲工作量最少為目標，建立整數規劃模型，提出逐次分段線性逼近法，并證明該求解方法對大規模場橋調度問題的有效性。與傳統碼頭相比，發展理念更加創新、環保的自動化碼頭在近十多年得到迅猛發展，2017年年底,全球最大的自動化集裝箱碼頭——洋山港4期開通試運行,將2臺軌道式集裝箱龍門起重機(Rail-Mounted Gantry Crane,RMG)置于同一個箱區是自動化碼頭考慮較多的一種策略。LI等[8]重點考慮RMG之間的干擾關系，以所有任務等待和延時的加權時間最短為目標，引入時間離散模型，將在固定長度范圍內的任務一起考慮;LI等[9]在已有研究基礎上，將模型轉變成一個連續時間的場橋調度模型;PARK等[10]通過合理假設場橋運輸速度，將時間離散化，考慮場橋作業沖突和翻箱問題，建立以自動導引運輸車(Automated Guided Vehicle,AGV)和外集卡等待時間最短為目標的整數規劃模型;GHAREHGOZLI等[11]通過仿真證明在堆場中設置共享區有助于提高集裝箱搬運效率。

盡管關于場橋調度的研究頗多，但尚無運用約束規劃(Contraint Programming,CP)方法解決該問題的研究。本文利用CP對調度問題的適用性，從時間長度設置決策變量。在考慮任務分段和接力區容量有限等要求的同時，將碼頭堆場在實際操作中選取的調度規則加入CP技術求解過程中。

1 問題描述與條件假設

1.1 問題描述

在自動化集裝箱碼頭，堆場作為進出口集裝箱重要的交接和保管場所，通常被分為多個箱區，每個箱區由多個倍位(bay)組成。自動化軌道式龍門起重機(Automatic Rail-Mounted Gantry Crane,ARMG)在自動化集裝箱碼頭(Automated Container Terminal,ACT)堆場中,負責集裝箱的水平搬運和附帶的垂直搬運作業，主要起到串聯港口內部AGV和外部集卡運輸的作用。當前，堆場單箱區配置雙ARMG的ACT多采用垂岸式設計。[12]靠近海側的ARMG稱為海側ARMG，靠近陸側的ARMG稱為陸側ARMG,其中:海側ARMG的作業效率關系到在港船舶是否能按時離港;陸側ARMG的作業效率直接涉及外集卡的等待時間。

由于2臺ARMG共用同一軌道，相互之間不可跨越，因此須重視ARMG在搬運集裝箱過程中的干擾問題。在箱區中間設置接力區是本文考慮用來解決干擾問題的方法,見圖1。將1個堆存在路側箱區的集裝箱搬運至海測緩存區，既可由海側ARMG直接完成作業,也可由陸側ARMG先將集裝箱搬運至箱區中間的接力區，再由海側ARMG將該集裝箱搬運至海側緩存區。

圖1 任務接力示意

1.2 條件假設

本文緊密聯系ACT堆場場橋實際作業情況，如：集裝箱初始和目標位置已知、集裝箱作業要求已知等，提出的假設條件為

1) 堆場2端交接點容量足夠大，ARMG在ACT兩端作業時無需等待。

2) ARMG作勻速移動。

3) ARMG水平方向移動時間取決于其移動bay數，垂直方向移動時間取決于吊具抓箱和放箱的對準時間，忽略堆高度的影響。

4) 所有作業中不考慮翻箱作業。

5) 集裝箱尺寸統一定為20英尺箱，不考慮偶數倍位放40英尺箱的情況。

6) 固定接力區位置，接力區容量可知。

為將ARMG在ACT兩端交接區作業時間考慮在模型中，本文將兩端的交接區各視為1個Bay，即在原箱區bay數量上增加2個Bay數量。

2 CP模型

本文建立的模型借助CPLEX12.4中的OPL語言實現。OPL語言中提出區間變量[13-14]的概念，區間變量即決策變量，是約束規劃在調度問題研究方面的重要擴展。區間變量區別于一般的決策變量，具有起點、終點和長度(起點為任務開始時間，終點為任務結束時間，長度為任務持續的時長)。同時，每個區間變量都有出現狀態[13]，該狀態用來表示區間變量是否會出現在最終的解中。

本文基于區間變量設計CP模型，采用OPL中特定的函數和約束表達方式，如alwaysEqual、NoOverlap和endBeforeStart等[15]，在下文出現時解釋其含義。

2.1 集合與參數

1)R1={1,2,…,m}為不需要通過接力完成的集裝箱作業。

2)R2={m+1,m+2,…,n}為需要通過接力完成的集裝箱作業。

3)K={1,2}，其中：1為海側ARMG；2為陸側ARMG。

4)RS為海側ARMG作業集合；RL為陸側ARMG作業集合；R為作業總集合，R=R1∪R2=RS∪RL。

5)t0為ARMG移動1個Bay長度的時間。

6)t1為ARMG在垂直方向上單次抓取或放下集裝箱的時間。

7)c為堆場接力區容量。

8)bi,0為集裝箱作業i初始Bay；bi,1為接力區Bay；bi,2為集裝箱作業目標Bay。

9)B={1,2,…,bn}為堆場Bay集合，其中:1為海側交接區;bn為陸側交接區。

10)di為作業i的目標完成時間。

2.2 決策變量與約束條件

2.2.1變量值域約束

CP模型定義xi,k、zki,1和zki,2等3個區間決策變量。

(1)xi,k為ARMGk進行作業i，ARMG的作業順序是通過求解xi,k開始和結束時刻所得的。對xi,k的值域進行約束,有

start(xi,k)≥0,i∈R

(1)

end(xi,k)≤M

(2)

(3)

presence(xi,k)=1

(4)

式(1)為ARMGk進行作業i的開始時刻必須大于0；式(2)為ARMGk進行作業i的結束時刻，給出一個簡單的上界，M為一個自修正的參數；式(3)為ARMGk進行作業i的時長；式(4)為所有屬于ARMGk的作業都會被ARMGk執行。

(2)zki,1為需通過接力完成搬運任務的集裝箱i的第1段作業，對于i∈R2，k∈K，有

start(zki,1)≥0

(5)

end(zki,1)≤M

(6)

(7)

presence(zki,1)=1

(8)

式(5)為集裝箱i第1段作業開始時刻必須大于0；式(6)為集裝箱i第1段作業結束時刻；式(7)為集裝箱i第1段作業時長；式(8)為所有集裝箱i第1段作業都會被執行。

(3)zki,2為需通過接力完成搬運任務的集裝箱的第2段作業，有

(9)

end(zki,2)≤M

(10)

(11)

presence(zki,1)=1

(12)

式(9)為集裝箱i第2段作業開始時刻須大于等于第1段的結束時刻；式(10)為集裝箱i第2段作業結束時刻；式(11)為集裝箱i第2段作業時長；式(12)為所有需接力完成搬運的集裝箱i第2段作業都會被執行。

CP中針對決策變量之間的關系有特定的表達方式。在此引入alwaysEqual函數，用來表示與控制變量之間關系。對于i∈R2，k∈K，有

alwaysEqual(zki,1,xi,k)

(13)

alwaysEqual(zki,2,xi,k)

(14)

式(13)和式(14)中:由zki,1和zki,2表示的接力箱第1段和第2段作業的開始、結束時刻與由xi,k表示的接力箱作業開始、結束時刻一致，即通過式(13)和式(14)將整個由xi,k所表示的作業順序補充完整。

2.2.2任務不重疊約束

屬于海側或陸側ARMG執行的作業在時間上不能重疊，即在ARMGk執行前后2個作業之間有段準備時間,等于ARMGk完成1次搬運作業之后，從當前Bay前往下一個作業位置的時間和2次垂直作業時間之和。為實現這個約束，現定義1個計算準備時間的函數

k∈K，transitionTimesARMGk:

(15)

式(15)中:i,j∈Rk,且i≠j。該函數用來定義海側或陸側ARMG在執行前后2個作業之間的準備時間。隨后定義序列變量qk，k∈K。1個序列變量是1組決策區間的集合。

(16)

(17)

noOverlap(qk,transitionTimesARMGk)

(18)

式(16)為序列變量qk為所有ARMGk作業集合；式(17)為ARMGk作業設置序號；式(18)保證該序列qk中任務之間不重疊，且2個相繼任務之間存在一段準備時間,其計算由系統從序列變量中取得2個作業序號，將這2個作業序號代入計算準備時間的函數中。

2.2.3接力箱的作業順序約束

需通過接力完成搬運的集裝箱作業，第1段作業必須先于第2段作業完成。在此，引入函數表示2個具有順序關系的作業在發生時間上的先后關系。

endBeforeStart(zki,1,z(3-k)i,2),i∈R2;k∈K

(19)

式(19)為接力箱的第1段作業由ARMGk完成，第2段作業由ARMG(3-k)后完成。

2.2.4接力區集裝箱容量約束

接力區由堆場中間固定的Bay組成，其容量有限。在此引入資源約束，表示任意時刻所有作業的資源消耗量不得超過最大值。pulse函數是OPL中的基本累積函數，一般可表示為pulse(a,b)，其括號中參數a為消耗資源的區間變量，參數b為區間變量在執行過程中消耗的資源數?；纠鄯e函數通過累加成為總累積函數，對總累積函數施加約束即為資源約束。

(20)

式(20)中:括號中參數為完成接力任務第1段之后會消耗1個接力區Bay。式(20)為堆存在接力區中的集裝箱總數不得大于接力區容量。

2.2.5ARMG之間距離約束

設置輔助決策變量fkb,t：t時刻ARMGk在Bayb上為1，否則為0。

(21)

b×f2b,t-b′×f1b′,t≥α

(22)

式(22)為在任意時刻，海、陸兩側ARMG之間的距離大于規定的安全距離α。

2.3 目標函數

目標是將海、陸兩側ARMG作業總延誤時間最小化。

(23)

式(23)中:括號中第1部分為海側ARMG在完成任務過程中的總延遲時間;第2部分為陸側ARMG在完成任務過程中的總延遲時間。

3 結合調度規則的求解過程

3.1 調度規則

在ACT堆場上，不同調度規則實質上是ARMG在作業過程中產生沖突時所選擇優化的側重點不同。本文結合ACT堆場作業實際和CP模型考慮的接力區容量，提出3種調度規則。

3.1.1ARMG作業準備時間最短的任務優先

ARMG作業準備時間最短的任務優先(簡稱“Y1”)可有效縮短ARMG空載行駛距離，借助第2.2.2節提出的ARMG作業準備時間的計算函數transtionTimesARMGk，可幫助ARMG在作業過程中進行任務選擇。

3.1.2海側ARMG任務優先

海側ARMG作業情況直接關系到港區內部AGV的運行效率，給予海側ARMG任務優先權(簡稱“Y2”)可有效縮短海側ARMG的作業等待時間，提高AGV作業效率。

3.1.3接力箱任務優先

本文考慮的中間接力區是固定Bay。為確保ARMG在接力區作業的便利性，接力區的堆存箱量不能按滿載情況考慮。接力箱完成第1段搬運之后，堆存在接力區會造成接力區Bay資源被占據。因此，接力區容量在第2.2.4節作為重要資源進行考慮。優先考慮接力箱任務(簡稱“Y3”)，可弱化接力區容量帶來的限制。

3.2 求解流程

1) 讀入時間T內所有集裝箱任務始末位置和目標完成時間；設定任務開始時間T0和其他參數。

2) 借助CP技術對時間T內所有的作業任務進行約束傳播，如：對接力作業的前后2段作業進行控制，將第2段作業先于第1段作業完成的情況剔除，形成ARMG初始可選任務集合。

3) 將調度規則Y1、Y2和Y3分別置于CP求解階段，在調度過程中，結合CP具備的搜索能力，求解ARMGk在t時刻從可選任務集合中所選取執行的任務i。

(bi,2-α-∑b·f2b,t)×t0

(24)

4 算例分析

以任務組為單位生成目標完成時間,以2臺ARMG在各自固定的初始位置向任務開始運行的時刻作為開始時間，ARMG移動速度為v=6 m/s，即t0=1；安全距離α=2；ARMG垂直方向上抓取或放下1個集裝箱的時間t1=30 s；本文箱區總bay包括陸側交接點和海側緩存區，共52個bay。將以上CP模型用CPLEX12.4編程求解，運行硬件環境為Intel(R) Core(TM) i5—320 M，2.60 GHz CPU，4 GB內存。多規模算例集求解結果見表1。

表1 多規模算例集求解結果

由表1可知:在小規模(50及以下)任務情況下，結合Y1的求解方式,可在10 s內求解出結果，總延誤值皆為最小;在中規模(70～150)任務情況下，3種調度規則求解的總延誤值的差距在5 min以內，其中任務規模越大，Y3在求解速度方面的優越性明顯;在大規模(180及以上)任務情況下，結合Y3的求解方式有明顯優勢，求解質量提升約30.87%，且規模越大，提升越多。在求解速度方面，結合Y3的求解方式比其他2種提高1倍。

進一步從海、陸兩側的延誤時間和任務延誤總次數分析各調度規則對海、陸兩側ARMG作業的影響,見圖2。Y2給予海側ARMG作業優先權，海側任務總延遲時間在各算例下都明顯小于同規則下陸側任務總延遲時間。在大規模算例下，Y2海側任務總延遲時間明顯優于Y1和Y3。Y1和Y3規則以符合調度規則的任務為優先，沒有明確海側或陸側ARMG作業優先。在延誤總累計次數方面，Y1與Y3有著相反的表現。在小、中規模算例下，Y1延誤次數有7次最優;在大規模算例下，Y1延誤次數最多,且伴隨任務規模增加，延誤次數擴增顯著;Y3在大規模算例下可減少延誤次數。

圖2 海、陸側在不同調度規則下的作業延誤情況

5 結束語

在ACT堆場中， ARMG作業是集裝箱內、外運輸的串聯環節，綜合考慮其對在港船舶和外集卡的作業效率十分必要。本文建立單箱區雙ARMG調度問題CP模型，采用任務接力的方式解決ARMG在作業時存在的干擾問題，設置3種任務調度規則。在CP求解過程中，通過多規模任務量算例分析，CP技術能在港口作業實時性的要求下求解出滿足作業要求的調度次序。在小規模任務情況下，結合 ARMG作業準備時間最短、任務優先的搜索方法求解效果最好；在大規模任務情況下，接力箱任務優先的規則有明顯優勢，求解質量能提升約30.87%，求解時間可縮短1/2。因此，自動化碼頭的各堆場可根據不同時間段內任務數量規模的實際情況，選取不同的任務調度方式實現效率提升，提高對外服務的質量。