自動化集裝箱碼頭雙軌道吊協(xié)調調度分析

梁承姬 陳維斗 崔佳誠

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

0 引 言

自動化已經(jīng)成為當今碼頭持續(xù)發(fā)展的一種趨勢，它的出現(xiàn)可以大幅度提高碼頭的作業(yè)效率。自動化集裝箱碼頭雖然在人工成本和安全性上具有很大優(yōu)勢，但是對碼頭設備的調度控制提出了更高的要求。在自動化集裝箱碼頭中，由于各種碼頭設備需要聯(lián)合調度，雙小車岸橋(STS)、AGV、以及軌道吊(ARMG)等設備在作業(yè)時都存在各種協(xié)調問題，其中以ARMG的協(xié)調調度問題最為突出。與傳統(tǒng)碼頭不同的是，自動化碼頭箱區(qū)垂直于岸線分布，且自動化箱區(qū)一般采用雙ARMG協(xié)同作業(yè)的方式，其布局如圖1所示。ARMG承擔了大部分的水平運輸任務，ARMG的作業(yè)效率直接影響了整個碼頭的作業(yè)效率。所以，對雙ARMG的調度優(yōu)化對于提高整個碼頭作業(yè)效率有重要意義。本文主要根據(jù)不可穿越式雙ARMG作業(yè)范圍的不同，設置接力模式和混合模式兩種模作業(yè)模式，并討論了這兩種作業(yè)模式對雙ARMG作業(yè)效率的影響。

圖1 自動化集裝箱碼頭布局圖

ARMG是碼頭作業(yè)的效率瓶頸，目前國內(nèi)外學者對自動化集裝箱碼頭ARMG調度也做了一些研究：

文獻[1]提出了基于啟發(fā)式算法和局部搜索算法的自動化碼頭雙軌道吊的實時調度，研究了不帶緩存區(qū)的自動化碼頭堆場的調度問題；文獻[2]中，為了得到一個最優(yōu)結果，作者運用啟發(fā)式算法，通過討論是否設置堆場臨時儲存區(qū)，來解決軌道吊調度問題；文獻[3]提供了基本的復雜性證明，并引入和測試了有效的啟發(fā)式解決方案；嚴偉等[5]在以提供一種新穎的場橋調度策略為目標的情況下，構建了一種基于整數(shù)規(guī)劃的場橋動態(tài)調度模型，以達到各時段中剩余的總工作量最小的目標，并采用一種啟發(fā)式算法：最佳優(yōu)先搜索算法，來作為求解該模型的算法；林艷艷等[6]考慮場橋實際作業(yè)中不可相互跨越與安全距離等特有約束，設計了兩階段啟發(fā)式算法，通過數(shù)據(jù)實驗對模型與算法的有效性進行了驗證；鄭紅星等[7]考慮了多場橋作業(yè)時須有安全距離和不可跨越，以及內(nèi)外集卡的優(yōu)先級差異和集卡等待時間有上限等現(xiàn)實約束，對此問題構建了非線性數(shù)學規(guī)劃模型。

部分國內(nèi)外學者雖對自動化集裝箱碼頭軌道吊進行了相關研究，但是均未考慮接力緩存區(qū)對軌道吊作業(yè)效率的影響，也沒有對軌道吊的作業(yè)模式進行討論研究。本文基于此背景，設置了臨時緩存區(qū)，并根據(jù)軌道吊不同的作業(yè)范圍，設置了接力模式和混合模式兩種作業(yè)模式，考慮軌道吊接力問題及軌道吊的安全距離等約束。使用遺傳算法，以最小化作業(yè)完工時間為目標，計算不同作業(yè)模式下的作業(yè)效率。最后通過算法對比進一步驗證模型和算法的有效性。

1 問題描述

自動化集裝箱碼頭中，每個箱區(qū)通常有兩臺ARMG:一個負責海側作業(yè)，一個負責陸側作業(yè)。兩個相同型號ARMG運行在同一軌道上，且不能互相穿越。由于兩臺ARMG協(xié)同作業(yè)，因此必須對ARMG的作業(yè)范圍進行限制，這就導致了箱區(qū)中大多數(shù)任務需要兩臺ARMG進行接力完成。其中箱區(qū)貝位數(shù)從海側往陸側增加。

本文根據(jù)ARMG作業(yè)范圍的不同大小，給出接力模式和混合模式兩種作業(yè)模式，具體如下：

1) 接力模式 海側ARMG只能在海側區(qū)域(1～27貝)進行作業(yè)，陸側ARMG只能在陸側區(qū)域(24～50貝)進行作業(yè)，其中24～27貝為接力任務臨時存儲區(qū)域。若出現(xiàn)陸側ARMG的目標集裝箱在海側區(qū)域，或者海側ARMG的目標集裝箱在陸側區(qū)域，則將該任務分解為主任務和接力任務兩個任務進行操作，如圖2所示。臨時貝位上方為海側區(qū)域，下方為陸側區(qū)域。

2) 混合模式 海側ARMG和陸側ARMG可以在一定范圍內(nèi)越過臨時存儲貝位，進入對方的區(qū)域，如圖3所示。海側ARMG允許在1～38貝進行作業(yè)(即從海側到靠近陸側虛線區(qū)域)，陸側ARMG允許在13～50貝進行作業(yè)(即從陸側到靠近海側虛線區(qū)域)。若任務初始位置位于海側/陸側ARMG允許進入的箱區(qū)區(qū)域，則直接作業(yè)，如圖中的出口裝船任務；若任務初始位置位于海側/陸側ARMG不允許進入的箱區(qū)區(qū)域，則依舊使用接力策略。

圖2 接力模式 圖3 混合模式

由于兩臺ARMG協(xié)同作業(yè)，存在接力任務的分配問題及ARMG沖突問題。本文根據(jù)任務的初始、目標位置來安排ARMG接力作業(yè)：若裝船集裝箱靠近陸側時，且該位置超過海側ARMG的作業(yè)范圍，則須由陸側ARMG將該集裝箱運送至箱區(qū)中間的臨時緩存區(qū)(如圖2、圖3中間陰影部分)，再由海側ARMG從臨時存儲區(qū)取箱裝船；若ARMG調度發(fā)生沖突，圖4表示兩臺軌道吊執(zhí)行任務時發(fā)生沖突及其解決辦法，由于岸邊作業(yè)比陸側作業(yè)更重要，賦予海側ARMG優(yōu)先作業(yè)權，海側ARMG保持原有的作業(yè)線路正常作業(yè)，陸側ARMG不能進入海側ARMG的工作區(qū)域，且要保持一定的安全距離，在區(qū)域外原地等待，待海側ARMG完成作業(yè)任務后，陸側ARMG繼續(xù)其原來任務。

圖4 ARMG沖突示意圖

2 數(shù)學模型

本文考慮ARMG之間的安全距離等約束，建立整數(shù)規(guī)劃模型。為了得到最小化完工時間，本文作出如下假設：(1) 集裝箱尺寸統(tǒng)一為20英尺；(2) AMRG裝卸時起升速度一致，移動時不考慮加速減速，保持勻速；(3) 堆場兩端交互點足夠，不存在等待外集卡或AGV的情況；(4) 所有進行作業(yè)任務的集裝箱均無需翻箱。同時ARMG作業(yè)時，必須符合以下要求：(1) ARMG一次只能作業(yè)一個集裝箱；(2) ARMG移動時不能互相穿越；(3) 不同ARMG不能同時作業(yè)相同集裝箱。

2.1 參數(shù)定義與決策變量

箱區(qū)作業(yè)相關參數(shù)：

n1：主任務的數(shù)量；

n2：接力任務的數(shù)量；

n：總工作數(shù)量n=n1+n2；

M：足夠大的數(shù)；

Ls：ARMG間的安全距離；

i：表示任意一個提箱或放箱的集裝箱操作；

I：表示由放箱操作i和提箱操作n+i組成的一個完整的任務；

Ci：操作i進行作業(yè)的目標集裝箱；

Li：操作i進行作業(yè)時所在的位置；

D1：主作業(yè)放箱操作目的地的集合,D1={1，2，…，n1}；

D2：接力作業(yè)放箱操作至臨時箱位的集合,D2={n1+1，n1+2,…,n}；

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

P2：接力作業(yè)中目標箱在臨時地點提箱的集合，P2={n+n1+1,n+n1+2,…,2n}當i∈P2時，Ci=Ci-n且Li=Li-n；

Oi：操作i提箱或放箱所用的作業(yè)時間；

di：集裝箱Ci的主任務的截止時間；

K：ARMG的集合，K={1,2}，1為海側ARMG，2為陸側ARMG；

rij：0/1變量，為1表示集裝箱Ci堆放在集裝箱Cj上，否則為0；

Fi：點i的操作完成時間點；

t：完成所有任務的總時間。

決策變量：

2.2 目標函數(shù)及約束條件

目標函數(shù)：

Mint

目標函數(shù)為最小化作業(yè)完成時間。

約束條件：

(1)

(2)

(3)

(4)

(5)

Fn+i-oi>Fi?i∈P2

(6)

Fi-(Fj-oj)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

約束式(1)和式(2)分別表示每一個主作業(yè)i∈P1∪D1∪{2n+1，2n+2}必須正好進行一次操作，每個接力作業(yè)i∈P2∪D2進行一次操作或沒有進行操作。約束式(3)和式(4)確保軌道吊K的路徑從點2n+K開始，在點2n+3結束。約束式(5)保證了任務間連線的連續(xù)性。約束式(6)描述了臨時地點的提箱點應當在這個地點放箱點操作完之后再進行。約束式(7)表示了集裝箱堆放中由結構必然導致的先后約束。約束式(8)確保了箱區(qū)中總時間由操作時間和ARMG移動時間所組成。約束式(9)確保了靠海側交接點的任務只能由海側ARMG完成，而靠陸側交接點的任務只能由陸側ARMG完成。約束式(10)表示ARMG之間的安全距離約束。約束式(11)-式(15)表示ARMG的作業(yè)狀態(tài)及其與貝位之間的關系。

3 算法設計

本文設計遺傳算法進行求解，遺傳算法保留每次進化的優(yōu)勢解，逐漸迭代出最優(yōu)解，適用于作業(yè)調度類問題。在算法計算階段將兩臺軌道吊單獨考慮，即海側任務全部由海側軌道吊完成，陸側任務全部由陸側軌道吊完成，之后再考慮兩臺軌道吊協(xié)調作業(yè)。

3.1 編碼和解碼

假設有10個集裝箱任務，其中8、9號任務需要接力完成，假設8-1為陸側任務，8-2為海側任務，9-1為海側任務，9-2為陸側任務，在接力模式下，海側ARMG需要完成的任務為1、3、5、7，8-2、9-1、10，陸側ARMG需要做的任務為2、4、6、8-1、9-2。其采用整數(shù)編碼，染色體由兩部分組成，中間用0分隔。如表1所示，第一部分為海側ARMG的作業(yè)順序，第二部分為陸側ARMG的作業(yè)順序。7236514就是海側的作業(yè)任務順序,表示海側ARMG需要做的任務為10#3#5#9-1#8-2#1#7；24315為陸側作業(yè)任務順序，表示陸側ARMG需要做的任務為4#8-1#6#2#9-2。

表1 染色體編碼

3.2 交 叉

在執(zhí)行交叉操作之前，將整個染色體分解為2個部分，確定交叉操作的父代，兩兩分組，各種群采用部分映射交叉。假設需要交叉的染色體為7236514024315以及5274163015243，分別拆分為7236514和5274163，及24315和15243。

1) 海側ARMG的任務數(shù)為7個，陸側ARMG任務數(shù)為5個，則產(chǎn)生兩個[1,7]區(qū)間的隨機整數(shù)r1、r2，對r1、r2中間的數(shù)據(jù)進行交叉；同理，再產(chǎn)生兩個[1,5]區(qū)間的隨機整數(shù)r3、r4，對r3、r4中間的數(shù)據(jù)進行交叉。如果r1=4、r2=6、r3=2、r4=4，則海側染色體交叉：

72365145274163

交叉為：

723416**276513

同理，陸側交叉：

2431515243

交叉為：

*524**431*

2) 交叉后，同一個染色體中，不重復的數(shù)字保留，重復的數(shù)字(帶*位置)采用中間段的對應關系進行映射。結果為：

72341654276513

及

3524154312

4 算例分析

4.1 參數(shù)設置及輸入數(shù)據(jù)

以ARMG作業(yè)完成20個集裝箱存取任務為基本數(shù)據(jù)。假設一個箱區(qū)共有10排、50個貝位、6層，1號貝位為最靠近海側的貝位，50號貝位為最靠近陸側的貝位，中間24、25、26、27四個貝位為臨時交換區(qū)域，第1層為底層箱位，第6層為最高箱位，箱區(qū)最左側排為第1排，箱區(qū)最右側排為第10排。假設ARMG大車(即ARMG門架，垂直于岸方向移動)小車(即吊具)移動速度均為0.5貝位/秒，一個箱位的長度為1貝位，寬度為0.5貝位，層高為0.5貝位，ARMG提取和放下一個集裝箱的時間為70 s。假設海側ARMG初始位置位于(5,0,1)，陸側ARMG初始位置位于(5,51,1)，且堆場內(nèi)集裝箱均為20英尺標準箱。遺傳算法的設置參考文獻[9]：最大迭代數(shù)為10 000代，種群數(shù)量為60，變異率為0.10，交叉率為0.9,500代內(nèi)結果無改善則輸出最優(yōu)解。輸入數(shù)據(jù)如表2所示。

表2 作業(yè)任務相關數(shù)據(jù)

4.2 兩種模式下的結果分析

本文將采用接力作業(yè)和混合作業(yè)兩種模式分別對ARMG進行作業(yè)調度。為不失一般性，堆場臨時存儲位置隨機產(chǎn)生，貝位、排位、層高分別滿足U(24,27)、U(1,10)、U(1,6)，分別表示貝位滿足在(24,27)、排位滿足在(1,10)、層高滿足在(1,6)上的均勻分布。通過遺傳算法計算，得到兩種模式下的調度結果如表3、表4所示。

表3 接力作業(yè)模式下ARMG調度結果

表4 混合模式下ARMG調度結果

根據(jù)表3、表4的調度結果可知，對相同任務數(shù)據(jù)，在接力作業(yè)模式下ARMG最大耗時為3 615 s，混合作業(yè)模式下最大耗時為3 358 s，延誤時間為ARMG作業(yè)沖突時產(chǎn)生的等待時間，混合作業(yè)模式下的延誤時間也明顯小于接力作業(yè)模式。由此可以得出本算例運用混合作業(yè)模式效率更高。圖5、圖6分別為兩種作業(yè)模式下的ARMG作業(yè)圖，橫坐標表示時間，縱坐標表示貝位，可以發(fā)現(xiàn)兩臺ARMG之間也不存在作業(yè)沖突問題。

圖5 接力模式下ARMG作業(yè)調度圖

圖6 混合模式下ARMG作業(yè)調度圖

為了進一步分析混合模式的有效性，通過增加集裝箱任務數(shù)量，運用遺傳算法、蟻群算法、Cplex對不同任務數(shù)量、不同作業(yè)模式下的ARMG進行計算。其具體結果如表5-表7所示。

表5 遺傳算法下不同任務量兩種作業(yè)模式作業(yè)時間對比

表6 蟻群算法下不同任務量兩種作業(yè)模式作業(yè)時間對比

表7 Cplex下不同任務量兩種作業(yè)模式作業(yè)時間對比

表5-表7分別為遺傳算法、蟻群算法和Cplex的計算結果對比。由表可知，遺傳算法在不同任務量下均可得到與Cplex相近的計算結果，而蟻群算法所得到的結果要明顯大于Cplex，且遺傳算法與蟻群算法在計算時間上相差不大。當任務量大于等于50時，Cplex運行時間較長，因此在本算例中，設置14 400 s作為Cplex的最大運算時間。隨著任務量的增加，Cplex在任務量為200時，無法在可接受范圍內(nèi)求解出最優(yōu)解，且遺傳算法得到的解也越來越優(yōu)于蟻群算法。因此通過遺傳算法、蟻群算法、Cplex的對比結果，可以將遺傳算法得到的結果接受作為最優(yōu)解。

5 結 語

本文以自動化集裝箱碼頭ARMG協(xié)調調度為主要研究內(nèi)容，針對臨時緩存區(qū)大小對ARMG作業(yè)效率的影響，考慮ARMG沖突及安全距離等問題，以最小化任務完工時間為目標，根據(jù)緩存區(qū)大小設置了兩種不同的作業(yè)模式，并運用遺傳算法進行求解，得到混合模式比接力模式效率更高。再分別通過遺傳算法、蟻群算法、Cplex計算不同任務量下的完工時間，并通過實驗結果的對比，驗證了遺傳算法計算出的結果的有效性。雖然本文得到了較為理想的結果，但是也存在不足，未考慮實際集裝箱任務的隨機性，以及ARMG與陸側集卡、海側AGV的協(xié)調問題等，這些都將增加ARMG的調度難度，但是也更符合碼頭實際作業(yè)，因此會在以后的研究中逐一解決。