約束規(guī)劃求解自動化集裝箱碼頭軌道吊調(diào)度

丁 一， 田 亮， 林國龍

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

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

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

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

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

1.1 問題描述

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

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

圖1 任務(wù)接力示意

1.2 條件假設(shè)

本文緊密聯(lián)系A(chǔ)CT堆場場橋?qū)嶋H作業(yè)情況，如：集裝箱初始和目標(biāo)位置已知、集裝箱作業(yè)要求已知等，提出的假設(shè)條件為

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

2) ARMG作勻速移動。

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

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

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

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

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

2 CP模型

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

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

2.1 集合與參數(shù)

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

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

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

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

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

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

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

8)bi,0為集裝箱作業(yè)i初始Bay；bi,1為接力區(qū)Bay；bi,2為集裝箱作業(yè)目標(biāo)Bay。

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

10)di為作業(yè)i的目標(biāo)完成時間。

2.2 決策變量與約束條件

2.2.1變量值域約束

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

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

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

(1)

end(xi,k)≤M

(2)

(3)

presence(xi,k)=1

(4)

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

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

start(zki,1)≥0

(5)

end(zki,1)≤M

(6)

(7)

presence(zki,1)=1

(8)

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

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

(9)

end(zki,2)≤M

(10)

(11)

presence(zki,1)=1

(12)

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

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

alwaysEqual(zki,1,xi,k)

(13)

alwaysEqual(zki,2,xi,k)

(14)

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

2.2.2任務(wù)不重疊約束

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

k∈K，transitionTimesARMGk:

(15)

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

(16)

(17)

noOverlap(qk,transitionTimesARMGk)

(18)

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

2.2.3接力箱的作業(yè)順序約束

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

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

(19)

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

2.2.4接力區(qū)集裝箱容量約束

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

(20)

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

2.2.5ARMG之間距離約束

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

(21)

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

(22)

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

2.3 目標(biāo)函數(shù)

目標(biāo)是將海、陸兩側(cè)ARMG作業(yè)總延誤時間最小化。

(23)

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

3 結(jié)合調(diào)度規(guī)則的求解過程

3.1 調(diào)度規(guī)則

在ACT堆場上，不同調(diào)度規(guī)則實(shí)質(zhì)上是ARMG在作業(yè)過程中產(chǎn)生沖突時所選擇優(yōu)化的側(cè)重點(diǎn)不同。本文結(jié)合ACT堆場作業(yè)實(shí)際和CP模型考慮的接力區(qū)容量，提出3種調(diào)度規(guī)則。

3.1.1ARMG作業(yè)準(zhǔn)備時間最短的任務(wù)優(yōu)先

ARMG作業(yè)準(zhǔn)備時間最短的任務(wù)優(yōu)先(簡稱“Y1”)可有效縮短ARMG空載行駛距離，借助第2.2.2節(jié)提出的ARMG作業(yè)準(zhǔn)備時間的計算函數(shù)transtionTimesARMGk，可幫助ARMG在作業(yè)過程中進(jìn)行任務(wù)選擇。

3.1.2海側(cè)ARMG任務(wù)優(yōu)先

海側(cè)ARMG作業(yè)情況直接關(guān)系到港區(qū)內(nèi)部AGV的運(yùn)行效率，給予海側(cè)ARMG任務(wù)優(yōu)先權(quán)(簡稱“Y2”)可有效縮短海側(cè)ARMG的作業(yè)等待時間，提高AGV作業(yè)效率。

3.1.3接力箱任務(wù)優(yōu)先

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

3.2 求解流程

1) 讀入時間T內(nèi)所有集裝箱任務(wù)始末位置和目標(biāo)完成時間；設(shè)定任務(wù)開始時間T0和其他參數(shù)。

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

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

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

(24)

4 算例分析

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

表1 多規(guī)模算例集求解結(jié)果

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

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

圖2 海、陸側(cè)在不同調(diào)度規(guī)則下的作業(yè)延誤情況

5 結(jié)束語

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