魏亞茹,朱 瑾

0 引言

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

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

在已有的研究中,對(duì)自動(dòng)化集裝箱碼頭雙軌道吊的單獨(dú)研究和傳統(tǒng)碼頭中將起重機(jī)調(diào)度和箱位選擇的整體研究相對(duì)比較成熟,而在自動(dòng)化碼頭中將軌道吊和箱位選擇作為整體研究的幾乎沒(méi)有。本文的主要工作是研究進(jìn)出口集裝箱雙RMG的調(diào)度,同時(shí)考慮集裝箱的存儲(chǔ)選位和翻箱問(wèn)題,建立以最小化完工時(shí)間為目標(biāo)的雙RMG調(diào)度模型,并設(shè)計(jì)遺傳與蟻群融合算法(Genetic Algorithm-Ant Algorithm, GAAA)分別在不同作業(yè)模式和不同規(guī)模集裝箱下對(duì)模型進(jìn)行求解。

1 問(wèn)題描述

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

本文考慮接力和混合兩種作業(yè)模式,如圖1所示,H為海側(cè)緩沖區(qū),E為陸側(cè)緩沖區(qū)(本文不考慮陸側(cè)緩沖區(qū)的情況),A、B、C共同組成集裝箱堆存區(qū)(B為臨時(shí)交換區(qū),在接力作業(yè)時(shí)用于臨時(shí)存放集裝箱)。在接力作業(yè)模式下,對(duì)需跨越B區(qū)的集裝箱作業(yè)分解為主作業(yè)和接力作業(yè)?；旌献鳂I(yè)模式下,可不受B區(qū)的限制,但對(duì)于距離比較遠(yuǎn)的集裝箱任務(wù)仍需對(duì)任務(wù)進(jìn)行分解。

圖1 雙RMG的作業(yè)俯視圖

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

2 模型的建立

2.1 模型假設(shè)與已知條件

通常RMG的任務(wù)總數(shù)和任務(wù)性質(zhì)(進(jìn)口箱/出口箱)是已知的,根據(jù)集裝箱的堆存位置可以得到RMG從集裝箱的任意初始位置到目標(biāo)位置的行進(jìn)時(shí)間。同時(shí)考慮AGV和外集卡到達(dá)箱區(qū)的時(shí)間及兩個(gè)RMG的移動(dòng)速度是已知的,并對(duì)進(jìn)行的研究作出以下假設(shè):集裝箱尺碼統(tǒng)一為20寸;堆場(chǎng)內(nèi)擁有足夠的外集卡以及AGV;兩臺(tái)RMG不能相互穿越;可采用兩種模式進(jìn)行調(diào)度;每個(gè)箱區(qū)的調(diào)度策略相同,假設(shè)只考慮集裝箱都放在塊b的情況,且塊b中有足夠的插槽滿足集裝箱的堆存和翻箱使用;不考慮二次翻箱;貝內(nèi)集裝箱的初始狀態(tài)已知;因?yàn)楹?cè)優(yōu)先級(jí)高于陸側(cè),只考慮堆場(chǎng)設(shè)有海側(cè)緩沖區(qū)的情況。

2.2 相關(guān)符號(hào)定義和決策變量

1)與本文研究問(wèn)題的相關(guān)符號(hào)。

n1:主作業(yè)任務(wù)量。

n2:接力作業(yè)任務(wù)量。

n12:任務(wù)總量,n12=n1+n2。

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

Ci:目標(biāo)集裝箱進(jìn)行i操作。

li:操作i所在的位置。

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,Ci=Ci+n且li=li+n。

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

tij:RMG的空載時(shí)間,即RMG從上一任務(wù)的結(jié)束位置空行駛到下一任務(wù)的初始位置。

vi:AGV或外部集卡的到達(dá)時(shí)間。

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

N:初始集裝箱總量。

S:最大堆垛數(shù)。

n:堆垛索引,n∈S。

H:最高堆存層數(shù)。

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

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

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

L:海側(cè)裝載任務(wù),L={l1,l2,…,ln}。

U:海側(cè)卸載任務(wù),U={u1,u2,…,un}。

S1:海側(cè)RMG主任務(wù),S1={s1,s2,…,sn},且L∪U=S1。

S2:陸側(cè)RMG主任務(wù),S2={sn+1,sn+2,…,sn+n}。

B:緩沖區(qū)個(gè)數(shù)。

Zi:緩沖區(qū)所有作業(yè)時(shí)間,i∈S1,Zi≥0。

tr:翻箱所用時(shí)間。

Fi:任務(wù)i的完成時(shí)刻。

2n+k:RMG虛擬任務(wù)開(kāi)始,k=1時(shí),則表示海側(cè)RMG的初始位置;k=2時(shí),則表示陸側(cè)RMG的初始位置。

2n+3:虛擬任務(wù)結(jié)束。

M:一個(gè)足夠大的正數(shù)。

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

Ls:兩個(gè)RMG之間的安全距離。

2)與本文研究問(wèn)題的相關(guān)決策變量。

雙RMG的調(diào)度就是試圖找到每個(gè)RMG在G=(V,A)中的路徑,使得作業(yè)的總完工時(shí)間最小,其中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 目標(biāo)函數(shù)和約束條件

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

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 算法設(shè)計(jì)

雙RMG的調(diào)度問(wèn)題可以看作非對(duì)稱多旅行商問(wèn)題(Asymmetric Multiple Traveling Salesman Problem, AMTSP),本文m=2,將每個(gè)作業(yè)任務(wù)視為一個(gè)城市,如從任務(wù)1的初始位置到其目標(biāo)位置的這一過(guò)程視為一個(gè)城市,任務(wù)1的目標(biāo)位置到任務(wù)2的初始位置的行駛時(shí)間看作城市1到城市2的距離,因?yàn)橐?—2作業(yè)順序完成任務(wù)的時(shí)間和以2—1作業(yè)順序完成任務(wù)的時(shí)間不同,所以將其轉(zhuǎn)化為AMTSP。設(shè)計(jì)GAAA進(jìn)行求解。

3.1 算法流程和主要步驟

算法的流程如圖2所示。

圖2 GAAA流程

算法的主要步驟為:

步驟1 定義目標(biāo)函數(shù)和適應(yīng)值函數(shù),隨機(jī)生成一組染色體編碼;

步驟2 對(duì)染色體編碼進(jìn)行選擇、交叉、變異操作;

步驟3 重復(fù)步驟2,生成若干優(yōu)化解;

步驟4 初始化蟻群算法中的參數(shù),根據(jù)優(yōu)化解生成信息素強(qiáng)度初始分布,并選擇蟻群路徑的起點(diǎn)位置;

步驟5 計(jì)算每只螞蟻移動(dòng)到下一任務(wù)的概率,并更新信息素;

步驟6 重復(fù)步驟5,當(dāng)算法運(yùn)行次數(shù)達(dá)到設(shè)定值時(shí),停止計(jì)算,輸出最優(yōu)解和最優(yōu)目標(biāo)值。

3.2 GAAA中遺傳算法的編碼設(shè)計(jì)

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

3.3 GAAA中蟻群算法的設(shè)計(jì)

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

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

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

集裝箱任務(wù)間的轉(zhuǎn)移概率為:

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

(26)

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

螞蟻在當(dāng)前任務(wù)i時(shí)訪問(wèn)下一個(gè)任務(wù)j的概率為:

(27)

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

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

4)更新箱位信息,根據(jù)箱位選擇評(píng)分規(guī)則得到新的集裝箱任務(wù)的存儲(chǔ)位置,同時(shí)根據(jù)路徑選擇評(píng)分因素得到新的集裝箱評(píng)分值。

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

6)通過(guò)根據(jù)約束式(11)～(18)計(jì)算任務(wù)的完工時(shí)間,并可以通過(guò)最小化總完工時(shí)間獲得目標(biāo)函數(shù)。

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

4 算例分析

4.1 參數(shù)設(shè)置

在文獻(xiàn)[9]的基礎(chǔ)上進(jìn)行參數(shù)設(shè)置。翻箱時(shí)間為15 s,放箱和提箱時(shí)間均為10 s；兩個(gè)RMG之間的安全距離為1個(gè)貝位；海側(cè)緩沖區(qū)個(gè)數(shù)設(shè)置為2；g1、g3、g4均設(shè)置為0.2,g2設(shè)置為0.4。蟻群算法中的參數(shù)設(shè)置為:α=1,β=2,信息素?fù)]發(fā)因子設(shè)置為0.05,螞蟻數(shù)量設(shè)置為50,最大迭代次數(shù)設(shè)置為200。

4.2 兩種RMG作業(yè)模式的調(diào)度結(jié)果分析

在一臺(tái)處理器為Intel Core i5-7200U CPU 2.5 GHz、內(nèi)存為8 GB的個(gè)人電腦上,利用本文的GAAA對(duì)雙RMG調(diào)度模型求解。以10個(gè)集裝箱為例,對(duì)兩種作業(yè)模式下的雙RMG調(diào)度結(jié)果進(jìn)行分析。

1)接力模式下的雙RMG調(diào)度結(jié)果。

運(yùn)行30次GAAA得到接力模式下的雙RMG調(diào)度結(jié)果,如表1所示。

表1 接力模式下集裝箱的調(diào)度結(jié)果 s

圖3為接力模式下調(diào)度結(jié)果的甘特圖。任務(wù)的總完工時(shí)間為607 s,共有13個(gè)任務(wù),其中任務(wù)8、9、10需接力完成,分別為8—1、8—2、9—1、9—2、10—1、10—2;調(diào)度結(jié)果中1表示由海側(cè)RMG調(diào)度,2表示由陸側(cè)RMG調(diào)度。

圖3 接力模式下調(diào)度結(jié)果的甘特圖

2)混合模式下的雙RMG調(diào)度結(jié)果。

同樣地,運(yùn)行30次GAAA得到混合模式下的雙RMG調(diào)度結(jié)果,如表2所示。

表2 混合模式下集裝箱的調(diào)度結(jié)果 s

圖4為混合模式下調(diào)度結(jié)果的甘特圖。任務(wù)的總完工時(shí)間為655 s,混合模式下共有11個(gè)任務(wù),其中任務(wù)9需接力完成,分為9—1、9—2;調(diào)度結(jié)果中1表示由海側(cè)RMG調(diào)度,2表示由陸側(cè)RMG調(diào)度。

圖4 混合模式下調(diào)度結(jié)果的甘特圖

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

表3 接力模式和混合模式下的最小完工時(shí)間對(duì)比

關(guān)于評(píng)估GAAA中參數(shù)影響的實(shí)驗(yàn),采用幾個(gè)不同值的組合,找到GAAA中具有最佳收斂性能曲線的參數(shù)設(shè)置。對(duì)于50個(gè)集裝箱,蟻群參數(shù)設(shè)置取值如下:

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

啟發(fā)函數(shù)重要程序因子為β={1,2,3,5};

信息素?fù)]發(fā)因子為ρ={0.02,0.05,0.2,0.5}。

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

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

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

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

4.3 小規(guī)模集裝箱的雙RMG調(diào)度結(jié)果分析

集裝箱個(gè)數(shù)從5到20變化，研究5個(gè)小規(guī)模實(shí)驗(yàn)。在這里,根據(jù)4.2節(jié)得出的結(jié)論,采用接力模式進(jìn)行本節(jié)實(shí)驗(yàn)。這5個(gè)小規(guī)模實(shí)驗(yàn)采用與4.1節(jié)相同的參數(shù)設(shè)置,結(jié)果如表4所示。

表4 小規(guī)模算例的對(duì)比實(shí)驗(yàn)

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

4.4 中、大規(guī)模集裝箱的雙RMG調(diào)度結(jié)果分析

實(shí)驗(yàn)參數(shù)設(shè)置同4.3節(jié),擴(kuò)大集裝箱的規(guī)模,將本文GAAA得到的結(jié)果與CPLEX對(duì)比,如表5所示。

表5 中、大規(guī)模算例的對(duì)比實(shí)驗(yàn)

由表5可得,當(dāng)集裝箱個(gè)數(shù)在25～150時(shí),GAAA求得的最小完工時(shí)間比CPLEX平均減少18.50%,運(yùn)行時(shí)間比CPLEX平均減少99.19%;當(dāng)集裝箱數(shù)量達(dá)到150時(shí),CPLEX的運(yùn)行時(shí)間達(dá)到3.4 h,不符合實(shí)際的自動(dòng)化集裝箱碼頭運(yùn)作的要求。

5 結(jié)語(yǔ)

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

在堆場(chǎng)的實(shí)際作業(yè)過(guò)程中,還有其他因素影響接力模式和混合模式的效率,下一步的研究中可以考慮增加兩側(cè)RMG任務(wù)量均勻程度、集裝箱翻箱率等評(píng)判因素,分析不同規(guī)模下兩種作業(yè)模式的調(diào)度結(jié)果,并與其他優(yōu)化算法對(duì)比分析。

參考文獻(xiàn)(References)

[1] 魏晨, 胡志華, 高超鋒, 等.自動(dòng)化集裝箱碼頭堆場(chǎng)內(nèi)雙起重機(jī)調(diào)度模型與算法[J]. 大連海事大學(xué)學(xué)報(bào), 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] 李建忠, 丁以中, 王斌.集裝箱堆場(chǎng)空間動(dòng)態(tài)配置問(wèn)題研究[J]. 交通運(yùn)輸工程學(xué)報(bào), 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] 周靜嫻, 胡志華.自動(dòng)化集裝箱碼頭穿越式雙自動(dòng)堆碼起重機(jī)調(diào)度優(yōu)化[J]. 計(jì)算機(jī)應(yīng)用, 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] 李斌, 李文鋒.面向哈佛體系結(jié)構(gòu)的集裝箱碼頭場(chǎng)橋作業(yè)調(diào)度[J]. 計(jì)算機(jī)工程與應(yīng)用, 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] 崔佳誠(chéng).自動(dòng)化集裝箱碼頭堆場(chǎng)軌道吊分析與算法研究[D]. 上海: 上海海事大學(xué), 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] 鄭紅星, 吳岳, 涂闖, 等.單船岸橋分配與調(diào)度集成優(yōu)化模型[J]. 計(jì)算機(jī)應(yīng)用, 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).