梁承姬 陳維斗 崔佳誠(chéng)

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

0 引 言

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

圖1 自動(dòng)化集裝箱碼頭布局圖

ARMG是碼頭作業(yè)的效率瓶頸，目前國(guó)內(nèi)外學(xué)者對(duì)自動(dòng)化集裝箱碼頭ARMG調(diào)度也做了一些研究：

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

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

1 問(wèn)題描述

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

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

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

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

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

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

圖4 ARMG沖突示意圖

2 數(shù)學(xué)模型

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

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

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

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

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

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

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

Ls：ARMG間的安全距離；

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

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

Ci：操作i進(jìn)行作業(yè)的目標(biāo)集裝箱；

Li：操作i進(jìn)行作業(yè)時(shí)所在的位置；

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

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

P1：目標(biāo)箱在初始位置提箱操作的集合，P1={n+1,n+2,…,n+n1}，當(dāng)i∈P1時(shí)，Ci=Ci-n；

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

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

di：集裝箱Ci的主任務(wù)的截止時(shí)間；

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

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

Fi：點(diǎn)i的操作完成時(shí)間點(diǎn)；

t：完成所有任務(wù)的總時(shí)間。

決策變量：

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

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

Mint

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

約束條件：

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

3 算法設(shè)計(jì)

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

3.1 編碼和解碼

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

表1 染色體編碼

3.2 交 叉

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

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

72365145274163

交叉為：

723416**276513

同理，陸側(cè)交叉：

2431515243

交叉為：

*524**431*

2) 交叉后，同一個(gè)染色體中，不重復(fù)的數(shù)字保留，重復(fù)的數(shù)字(帶*位置)采用中間段的對(duì)應(yīng)關(guān)系進(jìn)行映射。結(jié)果為：

72341654276513

及

3524154312

4 算例分析

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

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

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

4.2 兩種模式下的結(jié)果分析

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

表3 接力作業(yè)模式下ARMG調(diào)度結(jié)果

表4 混合模式下ARMG調(diào)度結(jié)果

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

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

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

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

表5 遺傳算法下不同任務(wù)量?jī)煞N作業(yè)模式作業(yè)時(shí)間對(duì)比

表6 蟻群算法下不同任務(wù)量?jī)煞N作業(yè)模式作業(yè)時(shí)間對(duì)比

表7 Cplex下不同任務(wù)量?jī)煞N作業(yè)模式作業(yè)時(shí)間對(duì)比

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

5 結(jié) 語(yǔ)

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