自動化碼頭雙場橋調度與集裝箱存儲選位建模

魏亞茹,朱 瑾

0 引言

合理分配集裝箱的堆存位置不僅能減少翻箱率而且能提高碼頭的運行效率,是研究自動化集裝箱碼頭堆場的重要內容之一;同時,軌道式龍門起重機(Rail-Mounted Gantry, RMG)的調度(也稱為場橋的調度)和集裝箱堆存位置的選擇及翻箱問題相互影響,因此,研究RMG調度問題的同時考慮集裝箱存儲選位和翻箱,使得對集裝箱碼頭堆場的研究得到更加全面的考慮。本文研究的自動化集裝箱碼頭是垂岸式的。

國內外學術界對雙RMG的調度和集裝箱的堆存策略的研究有很多,如魏晨等[1]針對堆場同一箱區的兩端作業(堆存或取出)考慮雙起重機時空同步條件,以最小化總完工時間為目標,建立雙起重機調度混合整數規劃(Mixed Integer Programming, MIP)模型,并設計了遺傳算法對大規模問題進行求解;Park等[2]提出了基于局部搜索的啟發式算法對雙自動堆垛機(Automated Stacking Crane, ASC)協調作業問題進行求解;Hu等[3]研究了在批次中雙ASC避免干擾的情況下最小化所有請求的時間間隔,建立了三個模型,設計了一種精確的算法和遺傳算法有效地解決了問題;Park等[4]提出了一種使用多目標優化算法(Multi-Objective Evolutionary Algorithm, MOEA)優化七個堆存規則,確定堆場中集裝箱的堆放位置,取得了令人滿意的結果;李建忠等[5]在滾動計劃的基礎上,建立了起重機調度和集裝箱堆場空間資源動態配置模型,優化集裝箱的堆存位置,有效地減少了集卡的運行距離;周靜嫻等[6]針對穿越式雙ASC,考慮在執行同一貝位任務時ASC間發生沖突的可能性,建立了多目標混合整數規劃模型對問題進行研究。以下研究對本文也有借鑒作用:Luo等[7]在集裝箱碼頭卸貨過程中研究自動導引運輸車(Automated Guided Vehicle， AGV)調度的同時考慮集裝箱的存儲位置,以最大限度地減少船舶停泊時間,建立MIP模型并設計遺傳算法對其進行求解;李斌等[8]在集裝箱碼頭中研究場橋的調度,同時考慮堆存空間分配問題,并提出面向哈佛體系結構的基于Agent建模和仿真實驗,提高了場橋調度的魯棒性。

在已有的研究中,對自動化集裝箱碼頭雙軌道吊的單獨研究和傳統碼頭中將起重機調度和箱位選擇的整體研究相對比較成熟,而在自動化碼頭中將軌道吊和箱位選擇作為整體研究的幾乎沒有。本文的主要工作是研究進出口集裝箱雙RMG的調度,同時考慮集裝箱的存儲選位和翻箱問題,建立以最小化完工時間為目標的雙RMG調度模型,并設計遺傳與蟻群融合算法(Genetic Algorithm-Ant Algorithm, GAAA)分別在不同作業模式和不同規模集裝箱下對模型進行求解。

1 問題描述

自動化集裝箱碼頭的俯瞰圖堆場的每個箱區中有兩個不可互相穿越的RMG,靠近海側的為海側RMG(如圖1中的RMG#1),靠近陸側的為陸側RMG(如圖1中的RMG#2),同時設置了緩存區,用于RMG與可升降式自動導引車及外集卡之間的裝卸交互作業。

本文考慮接力和混合兩種作業模式,如圖1所示,H為海側緩沖區,E為陸側緩沖區(本文不考慮陸側緩沖區的情況),A、B、C共同組成集裝箱堆存區(B為臨時交換區,在接力作業時用于臨時存放集裝箱)。在接力作業模式下,對需跨越B區的集裝箱作業分解為主作業和接力作業。混合作業模式下,可不受B區的限制,但對于距離比較遠的集裝箱任務仍需對任務進行分解。

圖1 雙RMG的作業俯視圖

圖1中,灰色部分表示該位置已存儲集裝箱,白色部分表示空槽,無集裝箱存儲。對進口集裝箱,根據目標集裝箱的信息選擇集裝箱的存儲位置即m排n堆垛q層,當RMG收到調度指令時移動到目標集裝箱的位置,同時檢索目標裝箱的上方是否有集裝箱(即阻礙箱),若無,則直接對目標集裝箱進行指派作業,將集裝箱存儲到已預先選定的位置;若有,則先對阻礙箱進行同貝位翻箱作業(不考慮二次翻箱),再進行調度作業。對出口集裝箱,由于集裝箱的位置已知,所以不需要考慮存儲選位,當RMG收到調度指令時,先根據檢索結果判斷目標集裝箱是否需要進行翻箱操作:若無,則直接進行調度作業;若有,則先進行翻箱作業,再進行調度作業。

2 模型的建立

2.1 模型假設與已知條件

通常RMG的任務總數和任務性質(進口箱/出口箱)是已知的,根據集裝箱的堆存位置可以得到RMG從集裝箱的任意初始位置到目標位置的行進時間。同時考慮AGV和外集卡到達箱區的時間及兩個RMG的移動速度是已知的,并對進行的研究作出以下假設:集裝箱尺碼統一為20寸;堆場內擁有足夠的外集卡以及AGV;兩臺RMG不能相互穿越;可采用兩種模式進行調度;每個箱區的調度策略相同,假設只考慮集裝箱都放在塊b的情況,且塊b中有足夠的插槽滿足集裝箱的堆存和翻箱使用;不考慮二次翻箱;貝內集裝箱的初始狀態已知;因為海側優先級高于陸側,只考慮堆場設有海側緩沖區的情況。

2.2 相關符號定義和決策變量

1)與本文研究問題的相關符號。

n1:主作業任務量。

n2:接力作業任務量。

n12:任務總量,n12=n1+n2。

i:集裝箱操作,包括提箱、放箱或翻箱操作。

Ci:目標集裝箱進行i操作。

li:操作i所在的位置。

D1:主作業放箱操作目的地的集合,D1={1,2,…,n1}。

D2:接力作業放箱操作至臨時箱位的集合,D2={n1+1,n1+2,…,n}。

P1:目標箱在初始位置提箱操作的集合,P1={n+1,n+2,…,n+n1},當i∈P1時,Ci=Ci+n。

P2:接力作業中目標箱在臨時地點提箱操作的集合,P2={n+n1+1,n+n1+2,…,2n},當i∈P2,Ci=Ci+n且li=li+n。

Oi:操作i提放箱和載箱行駛所用的時間。

tij:RMG的空載時間,即RMG從上一任務的結束位置空行駛到下一任務的初始位置。

vi:AGV或外部集卡的到達時間。

K:RMG的集合,K={1,2},K=1表示海側RMG,K=2表示陸側RMG。

N:初始集裝箱總量。

S:最大堆垛數。

n:堆垛索引,n∈S。

H:最高堆存層數。

V:箱位總量,V=S·H。

(m,n,q):堆存位置,在塊b的m排n堆垛q層,其中1≤q≤H。

(i,k):由RMGk執行的集裝箱操作，k∈K，當k=1時，表示由海側RMG執行；當k=2時，表示由陸側RMG執行。

L:海側裝載任務,L={l1,l2,…,ln}。

U:海側卸載任務,U={u1,u2,…,un}。

S1:海側RMG主任務,S1={s1,s2,…,sn},且L∪U=S1。

S2:陸側RMG主任務,S2={sn+1,sn+2,…,sn+n}。

B:緩沖區個數。

Zi:緩沖區所有作業時間,i∈S1,Zi≥0。

tr:翻箱所用時間。

Fi:任務i的完成時刻。

2n+k:RMG虛擬任務開始,k=1時,則表示海側RMG的初始位置;k=2時,則表示陸側RMG的初始位置。

2n+3:虛擬任務結束。

M:一個足夠大的正數。

t:所有任務的完成時間。

Ls:兩個RMG之間的安全距離。

2)與本文研究問題的相關決策變量。

雙RMG的調度就是試圖找到每個RMG在G=(V,A)中的路徑,使得作業的總完工時間最小,其中V={2n+k,2n}∪P∪D,P=P1∪P2,D=D1∪D2,A={(i,j)|i,j∈D,Ci=Cj,li≠lj}∪{(i,j)|i,j∈D,Ci≠Cj}∪{(2n+k,j)|k∈K,j∈P}∪{(i,2n+3)|i∈D}。

2.3 目標函數和約束條件

目標函數:

mint

(1)

約束條件:

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

?n∈N,i′∈V

(11)

(12)

(13)

Fn+i-Oi≥Fi;?i∈P2

(14)

Fi-(Fj-Oj)

(15)

(16)

(17)

(18)

(19)

(20)

S1∪S2=P1∪D1

(21)

(22)

(23)

(24)

(25)

3 算法設計

雙RMG的調度問題可以看作非對稱多旅行商問題(Asymmetric Multiple Traveling Salesman Problem, AMTSP),本文m=2,將每個作業任務視為一個城市,如從任務1的初始位置到其目標位置的這一過程視為一個城市,任務1的目標位置到任務2的初始位置的行駛時間看作城市1到城市2的距離,因為以1—2作業順序完成任務的時間和以2—1作業順序完成任務的時間不同,所以將其轉化為AMTSP。設計GAAA進行求解。

3.1 算法流程和主要步驟

算法的流程如圖2所示。

圖2 GAAA流程

算法的主要步驟為:

步驟1 定義目標函數和適應值函數,隨機生成一組染色體編碼;

步驟2 對染色體編碼進行選擇、交叉、變異操作;

步驟3 重復步驟2,生成若干優化解;

步驟4 初始化蟻群算法中的參數,根據優化解生成信息素強度初始分布,并選擇蟻群路徑的起點位置;

步驟5 計算每只螞蟻移動到下一任務的概率,并更新信息素;

步驟6 重復步驟5,當算法運行次數達到設定值時,停止計算,輸出最優解和最優目標值。

3.2 GAAA中遺傳算法的編碼設計

對遺傳算法進行編碼時,通過加入一個虛擬點將AMTSP轉換成非對稱旅行商問題(Asymmetric Traveling Salesman Problem, ATSP),在旅行商訪問路徑中出現的虛擬點表示旅行商完成任務。編碼設計如下:兩個RMG可以看作兩個旅行商,存在兩條路線,以10個集裝箱任務為例,加入一個虛擬點11,隨機生成新的編碼,用來表示旅行商問題的染色體,如:10、5、2、4、7、11、3,6、1、8、9,則兩條路徑分別為:10—5—2—4—7和3—6—1—8—9,前者表示海側RMG的調度結果,后者表示陸側RMG的調度結果。為了避免出現0—0的路徑,設置各節點到虛擬點的距離為無窮大。

3.3 GAAA中蟻群算法的設計

1)蟻群路徑的起點:計算集裝箱從工作點到所有可用堆場的運行時間,選擇具有最短行進時間的兩個RMG初始位置最近的集裝箱任務作為起點,并用于進口集裝箱的初始堆存位置。因此,選擇的堆場位置的數量等于進口集裝箱的數量,滿足約束式(6)～(8)。

2)選擇海側或陸側的RMG(約束式(4)和(5)),即分配哪一個RMG完成集裝箱在主作業、接力作業或海側緩沖區的裝卸載任務,滿足約束式(2)和(3)及約束式(20)～(25)。

3)蟻群路徑的生成:首先由集裝箱的基本信息根據箱位選擇的評分規則確定集裝箱的位置(箱位選擇的具體評分細則參考文獻[9]),然后根據路徑選擇的評分因素采用式(26)、(27)確定后面的集裝箱任務。

集裝箱任務間的轉移概率為:

P(k)=(τ(i,k))α·(s(i,k))β;i∈tabu,k∈allow

(26)

其中:P(k)為螞蟻在集裝箱k處的概率值;s(i,k)為集裝箱任務k的評分值;τ(i,k)為信息矩陣中第i行第k列的值;tabu為禁忌表記錄已訪問的任務;allow為未訪問任務的集合;α為信息重要度因子;β為啟發式函數重要度因子。

螞蟻在當前任務i時訪問下一個任務j的概率為:

(27)

路徑選擇的評分因素為:RMG的重進重出r1,即當前任務若為裝載任務,則下一個任務希望是卸載任務,其權重為g1;RMG與集裝箱任務的初始位置的距離r2,其權重為g2;任務的性質(主任務的優先級高于接力任務)r3,其權重為g3;翻箱r4,其權重為g4;根據公式SI=r1·g1+(1/r2)·g2-r3·g3-r4·g4得到任務I的評分,其中:r1、r3、r4為0-1變量。

通過步驟1)～3)可以獲得存儲集裝箱的初始順序,滿足約束式(9)和(10)。

4)更新箱位信息,根據箱位選擇評分規則得到新的集裝箱任務的存儲位置,同時根據路徑選擇評分因素得到新的集裝箱評分值。

5)信息素更新:參考文獻[10],文獻[10]中的TAU(i,j)相當于這里的τ(i,k)。

6)通過根據約束式(11)～(18)計算任務的完工時間,并可以通過最小化總完工時間獲得目標函數。

7)解空間切割策略:由于要求兩個RMG之間要有一定的安全距離,所以螞蟻行走的路徑會有不滿足約束的解,需剔除。根據約束式(19)對解空間進行切割,具體的切割策略參考文獻[10]。

4 算例分析

4.1 參數設置

在文獻[9]的基礎上進行參數設置。翻箱時間為15 s,放箱和提箱時間均為10 s；兩個RMG之間的安全距離為1個貝位；海側緩沖區個數設置為2；g1、g3、g4均設置為0.2,g2設置為0.4。蟻群算法中的參數設置為:α=1,β=2,信息素揮發因子設置為0.05,螞蟻數量設置為50,最大迭代次數設置為200。

4.2 兩種RMG作業模式的調度結果分析

在一臺處理器為Intel Core i5-7200U CPU 2.5 GHz、內存為8 GB的個人電腦上,利用本文的GAAA對雙RMG調度模型求解。以10個集裝箱為例,對兩種作業模式下的雙RMG調度結果進行分析。

1)接力模式下的雙RMG調度結果。

運行30次GAAA得到接力模式下的雙RMG調度結果,如表1所示。

表1 接力模式下集裝箱的調度結果 s

圖3為接力模式下調度結果的甘特圖。任務的總完工時間為607 s,共有13個任務,其中任務8、9、10需接力完成,分別為8—1、8—2、9—1、9—2、10—1、10—2;調度結果中1表示由海側RMG調度,2表示由陸側RMG調度。

圖3 接力模式下調度結果的甘特圖

2)混合模式下的雙RMG調度結果。

同樣地,運行30次GAAA得到混合模式下的雙RMG調度結果,如表2所示。

表2 混合模式下集裝箱的調度結果 s

圖4為混合模式下調度結果的甘特圖。任務的總完工時間為655 s,混合模式下共有11個任務,其中任務9需接力完成,分為9—1、9—2;調度結果中1表示由海側RMG調度,2表示由陸側RMG調度。

圖4 混合模式下調度結果的甘特圖

由表1～2可得,在10個集裝箱任務量中,接力模式下的作業總耗時比混合模式下的作業總耗時少,且兩RMG作業任務量也比混合模式下的RMG任務量較均勻。增加集裝箱的個數至150,如表3所示,在不考慮其他因素的情況下,以最短完工時間為評判標準,當集裝箱個數為5時兩種作業模式的效率相同;集裝箱數量在8～150范圍內,接力模式比混合模式的效率要高。

表3 接力模式和混合模式下的最小完工時間對比

關于評估GAAA中參數影響的實驗,采用幾個不同值的組合,找到GAAA中具有最佳收斂性能曲線的參數設置。對于50個集裝箱,蟻群參數設置取值如下:

信息素重要程度因子為α={1,2,3,5};

啟發函數重要程序因子為β={1,2,3,5};

信息素揮發因子為ρ={0.02,0.05,0.2,0.5}。

圖5 不同α值的GAAA收斂性對比(β=2, ρ=0.05)

圖5～7為不同參數設置的性能比較。根據圖5～7的收斂曲線,觀察到信息素重要程度因子α=1,啟發函數重要程序因子β=2,信息素揮發因子ρ=0.05時收斂性最小。具體地說, 在圖5中,α=1的曲線收斂值最小; 在圖6中,β=2的曲線也收斂于較小的值；在圖7中,ρ=0.05曲線收斂值最小。這些數據還表明,對于這些實驗,最優值在200代后沒有改善,所以200代的最大迭代次數足以獲得近似最優解。本文算法中的其他參數設置也采用相同的實驗得到。

圖6 不同β值的GAAA收斂性對比(α=1, ρ=0.05)

圖7 不同ρ值的GAAA收斂性對比(α=1, β=2)

4.3 小規模集裝箱的雙RMG調度結果分析

集裝箱個數從5到20變化，研究5個小規模實驗。在這里,根據4.2節得出的結論,采用接力模式進行本節實驗。這5個小規模實驗采用與4.1節相同的參數設置,結果如表4所示。

表4 小規模算例的對比實驗

表4表明:1)當集裝箱個數為5時,本文算法GAAA得到的最小完工時間與CPLEX的相同;隨著集裝箱數量的增加,GAAA求得的最小完工時間比CPLEX的小,即GAAA的結果比CPLEX的越來越好,算法的運行時間也明顯小于CPLEX的。2)當集裝箱數量為5時,由于GAAA的波動性,GAAA求得的平均最小完工時間比CPLEX的大,相差0.33%,但在能接受的范圍內;隨著集裝箱數量的增加,GAAA與CPLEX的最小總完工時間平均相差2.65%,當集裝箱數量增加到20時,兩算法求得的最小完工時間相差最大,為7.9%;算法的運行時間也相差越來越大,平均降低了88.6%。

4.4 中、大規模集裝箱的雙RMG調度結果分析

實驗參數設置同4.3節,擴大集裝箱的規模,將本文GAAA得到的結果與CPLEX對比,如表5所示。

表5 中、大規模算例的對比實驗

由表5可得,當集裝箱個數在25～150時,GAAA求得的最小完工時間比CPLEX平均減少18.50%,運行時間比CPLEX平均減少99.19%;當集裝箱數量達到150時,CPLEX的運行時間達到3.4 h,不符合實際的自動化集裝箱碼頭運作的要求。

5 結語

本文針對雙RMG調度和集裝箱存儲選位問題:1)考慮了雙RMG間的安全距離、緩沖區容量和翻箱約束,建立了以最小化完工時間為目標的雙RMG調度和集裝箱存儲選位耦合模型;2)利用GA的前期快速搜索能力和AA的后期快速搜索能力,改進了GAAA對模型進行求解;3)對比分析了小中大規模下接力模式和混合模式的效率問題,實驗結果表明集裝箱數量在8～150時,接力模式更高效;并對比分析了改進的GAAA與CPLEX在小中大規模下的最小完工時間和運行時間,驗證了GAAA能夠在更短的時間內得到近似最優解。

在堆場的實際作業過程中,還有其他因素影響接力模式和混合模式的效率,下一步的研究中可以考慮增加兩側RMG任務量均勻程度、集裝箱翻箱率等評判因素,分析不同規模下兩種作業模式的調度結果,并與其他優化算法對比分析。

參考文獻(References)

[1] 魏晨, 胡志華, 高超鋒, 等.自動化集裝箱碼頭堆場內雙起重機調度模型與算法[J]. 大連海事大學學報, 2015, 41(4): 75-80.(WEI C, HU Z H, GAO C F, et al. Scheduling model and algorithm of twin synchronized stacking cranes in stack yard of automated container terminal [J]. Journal of Dalian Maritime University, 2015, 41(4): 75-80.)

[2] 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.

[3] HU Z H, SHEU J B, LUO J X. Sequencing twin automated stacking cranes in a block at automated container terminal [J]. Transportation Research Part C: Emerging Technologies, 2016, 69: 208-227.

[4] PARK T, SOHN M, RYU K R. Optimizing stacking policies using an MOEA for an automated container terminal [C]// Proceedings of the 2010 40th International Conference on Computers and Industrial Engineering. Piscataway, NJ: IEEE, 2010: 1-6.

[5] 李建忠, 丁以中, 王斌.集裝箱堆場空間動態配置問題研究[J]. 交通運輸工程學報, 2007, 7(3): 50-55.(LI J Z, DING Y Z, WANG B. Dynamic space deployment model of container storage yard [J]. Journal of Traffic and Transportation Engineering, 2007, 7(3): 50-55.)

[6] 周靜嫻, 胡志華.自動化集裝箱碼頭穿越式雙自動堆碼起重機調度優化[J]. 計算機應用, 2015, 35(9): 2673-2677.(ZHOU J X, HU Z H. Scheduling optimization for cross-over twin automated stacking cranes in automated container terminal [J]. Journal of Computer Applications, 2015, 35(9): 2673-2677.)

[7] LUO J, WU Y, MENDES A B. Modeling of integrated vehicle scheduling and container storage problems in unloading process at an automated container terminal [J]. Computers and Industrial Engineering, 2016, 94(C): 32-44.

[8] 李斌, 李文鋒.面向哈佛體系結構的集裝箱碼頭場橋作業調度[J]. 計算機工程與應用, 2011, 47(22): 17-20.(LI B, LI W F. Yard crane dispatching at container terminals based on Harvard architecture [J]. Computer Engineering and Applications, 2011, 47(22): 17-20.)

[9] 崔佳誠.自動化集裝箱碼頭堆場軌道吊分析與算法研究[D]. 上海: 上海海事大學, 2015: 26-56.(CUI J C. Analysis and research on algorithm of RMG in automated container terminal yard [D]. Shanghai: Shanghai Maritime University, 2015: 26-56.)

[10] 鄭紅星, 吳岳, 涂闖, 等.單船岸橋分配與調度集成優化模型[J]. 計算機應用, 2015, 35(1): 247-251.(ZHENG H X, WU Y, TU C, et al. Quay crane allocation and scheduling joint optimization model for single ship [J]. Journal of Computer Applications, 2015, 35(1): 247-251.)

This work is partially supported by the Sponsored by the Shanghai Pujiang Program (16PJC043), the Research Innovation Project of Shanghai Municipal Education Commission Project (15ZZ078).