楊小明，徐子奇，張夢(mèng)天，舒 帆

(1.上海海事大學(xué) 離岸工程研究院，上海 201306；2.上海海事大學(xué) 物流工程學(xué)院，上海 201306)

0 引言

隨著吞吐量的增加與船舶大型化的發(fā)展，集裝箱港口對(duì)集裝箱裝卸系統(tǒng)裝卸能力的要求越來(lái)越高。對(duì)于自動(dòng)化集裝箱碼頭，通常岸邊橋式起重機(jī)(岸橋)的數(shù)量不變，碼頭岸線的吞吐能力主要取決于支持岸橋作業(yè)的水平運(yùn)輸和箱區(qū)裝卸系統(tǒng)。水平運(yùn)輸能力可以通過(guò)增加運(yùn)輸設(shè)備來(lái)快速提高，然而承擔(dān)集裝箱裝卸、翻搗和堆存多重任務(wù)的自動(dòng)化集裝箱碼頭箱區(qū)裝卸系統(tǒng)卻難以通過(guò)簡(jiǎn)單增加設(shè)備來(lái)提升能力，必須采用先進(jìn)的管理手段提高效率。因此，優(yōu)化自動(dòng)化集裝箱碼頭箱區(qū)自動(dòng)化軌道吊(Automated Rail Mounted Gantry crane, ARMG)作業(yè)調(diào)度，對(duì)提高碼頭的整體運(yùn)作效率和提升港口的競(jìng)爭(zhēng)力具有十分重要的意義。另一方面，隨著自動(dòng)化技術(shù)的發(fā)展，近年來(lái)自動(dòng)化集裝箱碼頭得到空前發(fā)展，據(jù)統(tǒng)計(jì)2010年～2015年期間，全球新增自動(dòng)化集裝箱碼頭的數(shù)量超過(guò)30個(gè)，為2010年前建造自動(dòng)化碼頭數(shù)量的2倍以上[1]，我國(guó)廈門遠(yuǎn)海、青島前灣、上海洋山四期自動(dòng)化集裝箱碼頭也在近年先后投入運(yùn)營(yíng)，同時(shí)大量傳統(tǒng)人工碼頭的自動(dòng)化改造，尤其是堆場(chǎng)自動(dòng)化改造成為當(dāng)前主要發(fā)展方向。因此，自動(dòng)化集裝箱碼頭箱區(qū)ARMG作業(yè)調(diào)度問(wèn)題成為港口作業(yè)智能化研究領(lǐng)域中的重點(diǎn)。

為適應(yīng)港口智能化發(fā)展、提高碼頭堆場(chǎng)的作業(yè)效率，國(guó)內(nèi)外學(xué)者在集裝箱碼頭堆場(chǎng)龍門吊(場(chǎng)橋)調(diào)度問(wèn)題上進(jìn)行了大量研究。在傳統(tǒng)人工集裝箱碼頭中，場(chǎng)橋可以在不同箱區(qū)之間轉(zhuǎn)移，場(chǎng)橋調(diào)度需要解決的核心問(wèn)題是保證其在整個(gè)碼頭堆場(chǎng)轉(zhuǎn)運(yùn)作業(yè)過(guò)程中的作業(yè)時(shí)間延遲最小[2-4]、作業(yè)成本最小[5-6]、大車移動(dòng)距離最小[7-8]等目標(biāo)，這類問(wèn)題研究更多偏向粗略作業(yè)計(jì)劃，難以實(shí)現(xiàn)自動(dòng)化集裝箱碼頭箱區(qū)ARMG的精準(zhǔn)協(xié)同作業(yè)。實(shí)際上絕大部分自動(dòng)化集裝箱碼頭中，箱區(qū)配置兩臺(tái)ARMG，通過(guò)兩臺(tái)ARMG相互交接協(xié)作完成集裝箱進(jìn)出箱區(qū)作業(yè)，這種裝卸工藝使得自動(dòng)化集裝箱碼頭作業(yè)組織更加復(fù)雜，箱區(qū)裝卸效率低[9]。通常自動(dòng)化集裝箱碼頭箱區(qū)中雙ARMG系統(tǒng)分為可穿越和不可穿越兩種組合方式，可穿越式雙ARMG作業(yè)范圍覆蓋整個(gè)箱區(qū)，不可穿越式雙ARMG相互間不能交叉行走，各自負(fù)責(zé)岸側(cè)和海側(cè)裝卸作業(yè)。

在不可穿越雙ARMG調(diào)度研究方面，Ng等[10-12]研究了給定作業(yè)時(shí)間約束下雙ARMG的調(diào)度問(wèn)題，目標(biāo)是盡量減少工作等待時(shí)間的總和，并提出分支定界算法、基于動(dòng)態(tài)編程的啟發(fā)式算法求解該類問(wèn)題，然而模型僅考慮序列優(yōu)化問(wèn)題；Gharehgozli等[13-14]考慮場(chǎng)橋間可能存在的干擾、作業(yè)時(shí)的安全間隔和任務(wù)之間的作業(yè)順序等約束，優(yōu)化兩個(gè)場(chǎng)橋的作業(yè)次序和堆存策略，建立了帶優(yōu)先約束的非對(duì)稱廣義多旅行商問(wèn)題模型，但是對(duì)不可穿越雙ARMG同樣未考慮任務(wù)分配問(wèn)題；呂家智[15]、韓曉龍等[16]、魏晨等[17]都將作業(yè)總完成時(shí)間作為最小化優(yōu)化目標(biāo)，構(gòu)建了雙場(chǎng)橋調(diào)度混合整數(shù)規(guī)劃模型，不同的是問(wèn)題約束以及模型求解方法；梁承姬等[18-19]在堆場(chǎng)混堆模式下，以最小化作業(yè)完成時(shí)間和存取箱作業(yè)時(shí)間延遲量為目標(biāo)，考慮場(chǎng)橋間的安全距離和作業(yè)干擾等約束，建立了混合整數(shù)規(guī)劃模型；裴磊磊等[20]以雙ARMG總作業(yè)時(shí)間最短和行駛距離之差最小為目標(biāo)建立混合整數(shù)規(guī)劃模型，并采用遺傳算法與仿真相結(jié)合的方法進(jìn)行求解。

與不可穿越雙ARMG系統(tǒng)區(qū)別最大的是，可穿越雙ARMG系統(tǒng)的雙ARMG工作范圍雖然可以覆蓋全場(chǎng)，但是ARMG作業(yè)仍然存在干涉。在可穿越雙ARMG系統(tǒng)調(diào)度問(wèn)題上，Cao等[21]基于可穿越式雙ARMG出場(chǎng)箱的操作策略建立了整數(shù)規(guī)劃模型，并設(shè)計(jì)了貪婪啟發(fā)式算法、模擬退火算法和組合啟發(fā)式算法來(lái)解決問(wèn)題；馮媛君[22]以最小化任務(wù)完工時(shí)間為目標(biāo)構(gòu)建了可穿越式雙ARMG的調(diào)度優(yōu)化模型，分析了作業(yè)過(guò)程中可能出現(xiàn)的干涉，實(shí)驗(yàn)結(jié)果表明模型能有效避免作業(yè)過(guò)程中場(chǎng)橋間的干涉并平衡兩場(chǎng)橋的任務(wù)；Vis等[23-25]以完工時(shí)間最小為目標(biāo)建立連續(xù)時(shí)間模型調(diào)度可穿越式雙ARMG，設(shè)計(jì)了基于模擬退火的啟發(fā)式算法求解該模型，并提出一種單排優(yōu)化方法計(jì)算模型的下界值；Stahlbock等[26]研究了可穿越式雙ARMG提高集裝箱碼頭效率的程度，以漢堡的CTA碼頭為實(shí)例，用不同在線算法從多個(gè)角度評(píng)估了這些算法的表現(xiàn)；Speer等[27]給出一種新的調(diào)度方法，以任務(wù)的延誤時(shí)間、雙ARMG的完工時(shí)間、任務(wù)的作業(yè)時(shí)間三者加權(quán)之和為目標(biāo)，設(shè)計(jì)了分支定界算法求解該問(wèn)題；周靜嫻等[28]考慮到可穿越式雙ARMG在同一倍位作業(yè)時(shí)會(huì)發(fā)生沖突，構(gòu)建了多目標(biāo)混合整數(shù)規(guī)劃模型來(lái)最小化完工時(shí)間和ARMG空載時(shí)間，并與單ARMG調(diào)度的效率進(jìn)行了對(duì)比；Briskorn等[29]也考慮ARMG作業(yè)時(shí)會(huì)存在干涉，以最小化完工時(shí)間為目標(biāo)對(duì)ARMG調(diào)度進(jìn)行優(yōu)化，不過(guò)假定每臺(tái)ARMG的作業(yè)次序已經(jīng)確定。

綜上所述，在港口自動(dòng)化、智能化發(fā)展趨勢(shì)下，雙ARMG系統(tǒng)調(diào)度問(wèn)題成為當(dāng)前該領(lǐng)域的研究焦點(diǎn)，由于不可穿越式雙ARMG系統(tǒng)存在諸多缺點(diǎn)[9]，可穿越式雙ARMG系統(tǒng)、軌道梭車+雙ARMG系統(tǒng)、可穿越式高架桁車系統(tǒng)等裝卸工藝引發(fā)越來(lái)越多學(xué)者的研究興趣。在自動(dòng)化集裝箱碼頭雙ARMG系統(tǒng)調(diào)度方面，雖然現(xiàn)有研究取得了重要成果，但是大部分研究將箱區(qū)任務(wù)分配與ARMG作業(yè)順序優(yōu)化兩個(gè)問(wèn)題割裂開，而實(shí)際上這兩個(gè)問(wèn)題聯(lián)系緊密，對(duì)其分開單獨(dú)研究不能保證箱區(qū)整體作業(yè)效率最優(yōu)。基于此，本文針對(duì)可穿越雙ARMG系統(tǒng)中作業(yè)分配及作業(yè)次序聯(lián)合優(yōu)化問(wèn)題建立數(shù)學(xué)規(guī)劃模型，并采用改進(jìn)的雙層遺傳算法對(duì)聯(lián)合優(yōu)化問(wèn)題進(jìn)行求解。其中外層算法求解箱區(qū)作業(yè)分配問(wèn)題，內(nèi)層算法實(shí)現(xiàn)外層分配方案下的ARMG作業(yè)順序優(yōu)化。最后通過(guò)算例實(shí)驗(yàn)論證所提改進(jìn)雙層遺傳算法在求解可穿越雙ARMG系統(tǒng)調(diào)度問(wèn)題的優(yōu)化效果和算法效率。

1 穿越式雙ARMG系統(tǒng)調(diào)度問(wèn)題描述

主流自動(dòng)化集裝箱碼頭箱區(qū)通常垂直于岸線布局，集裝箱堆放與岸線呈90o；海側(cè)船舶與箱區(qū)之間通過(guò)自動(dòng)導(dǎo)引小車(Automated Guided Vehicle, AGV)或跨運(yùn)車完成集裝箱水平運(yùn)輸；箱區(qū)內(nèi)通過(guò)ARMG完成集裝箱裝卸、堆存、翻搗等作業(yè)。典型的配置雙穿越式ARMG的自動(dòng)化集裝箱碼頭箱區(qū)平面布局如圖1所示(德國(guó)漢堡的Altenwerder集裝箱碼頭[26])，圖中①為海側(cè)AGV裝卸區(qū)，②為集裝箱堆存箱位，③為外層母ARMG，④為可穿越子ARMG，⑤為外集卡裝卸區(qū)。進(jìn)口集裝箱通過(guò)AGV運(yùn)送至①后由任意ARMG卸箱至箱區(qū)堆存，等待提箱外集卡到達(dá)⑤區(qū)域后，再由ARMG裝車運(yùn)走(如圖1直線⑥)。出口箱作業(yè)過(guò)程與進(jìn)口箱相反(如圖1直線⑧)，中轉(zhuǎn)箱則由AGV運(yùn)送至①區(qū)并由ARMG卸箱到箱區(qū)堆存，等待二程船舶裝船時(shí)再由ARMG裝車至①區(qū)AGV轉(zhuǎn)運(yùn)到岸邊裝船(如圖1曲線⑦)。在所有作業(yè)過(guò)程中，集裝箱在箱區(qū)內(nèi)裝卸通常不是一次裝卸到位，需要通過(guò)ARMG幾次翻搗裝卸才能完成集裝箱進(jìn)出堆場(chǎng)作業(yè)，在該作業(yè)過(guò)程中，可穿越式ARMG(如圖2)最大的特點(diǎn)是相互之間可穿越行駛，但是不能在相同區(qū)域同時(shí)作業(yè)，而且當(dāng)外層母ARMG裝卸作業(yè)時(shí)，內(nèi)層子ARMG不能穿越。

可穿越式雙ARMG任務(wù)分配與作業(yè)序列聯(lián)合優(yōu)化問(wèn)題可以描述為：在箱區(qū)一個(gè)作業(yè)批次中有N個(gè)任務(wù)待執(zhí)行，這N個(gè)任務(wù)可同時(shí)包括集港(出口箱進(jìn)場(chǎng))、裝箱(出口箱出場(chǎng))、卸船(進(jìn)口箱進(jìn)場(chǎng))、提箱(進(jìn)口箱出場(chǎng))、搗箱(箱區(qū)內(nèi)移箱)等作業(yè)類型，而且每個(gè)任務(wù)的起始位置和目標(biāo)位置均已知。現(xiàn)堆場(chǎng)中有2臺(tái)可穿越ARMG同時(shí)作業(yè)，需要將N個(gè)任務(wù)分配給這2臺(tái)ARMG并規(guī)劃每臺(tái)ARMG的作業(yè)次序。假設(shè)ARMG從初始位置出發(fā)執(zhí)行列表中的作業(yè)任務(wù)，完成最后一個(gè)任務(wù)的時(shí)刻為工作完成時(shí)間，最后一臺(tái)ARMG的工作完成時(shí)間即為整個(gè)作業(yè)批次的總完成時(shí)間。任何一個(gè)作業(yè)任務(wù)執(zhí)行時(shí)間包括ARMG行走時(shí)間、等待時(shí)間和裝卸時(shí)間，其中行走時(shí)間包括從ARMG當(dāng)前位置到目標(biāo)集裝箱初始提箱位置的行走時(shí)間，以及提取集裝箱后載箱行駛至該任務(wù)目標(biāo)卸箱位置時(shí)間；裝卸時(shí)間包括在集裝箱初始位置抓取集裝箱時(shí)間，以及在集裝箱目標(biāo)位置卸下集裝箱的操作時(shí)間。對(duì)于穿越式雙ARMG，母ARMG裝卸作業(yè)時(shí)，子ARMG不可穿越，另外在對(duì)同一倍位的集裝箱進(jìn)行裝卸作業(yè)時(shí)可能會(huì)發(fā)生沖突，此時(shí)先到達(dá)的ARMG先執(zhí)行任務(wù)操作，另一臺(tái)ARMG停止等待。該問(wèn)題優(yōu)化的目標(biāo)是在滿足約束條件的前提下使該批次任務(wù)的總完成時(shí)間最短。另外，針對(duì)該問(wèn)題還有一些常規(guī)的假設(shè)，例如集裝箱均為20英尺標(biāo)準(zhǔn)箱；ARMG在目標(biāo)位置的提箱和卸箱操作時(shí)間采用平均值，與集裝箱所處的位置無(wú)關(guān)；忽略人為和自然因素的影響等。

2 可穿越雙ARMG任務(wù)分配與作業(yè)序列聯(lián)合優(yōu)化模型構(gòu)建

2.1 符號(hào)定義

可穿越雙ARMG任務(wù)分配與作業(yè)序列聯(lián)合優(yōu)化數(shù)學(xué)模型中所涉及的所有符號(hào)定義如表1所示。

表1 符號(hào)定義

2.2 優(yōu)化模型的構(gòu)建

可穿越雙ARMG系統(tǒng)任務(wù)分配與作業(yè)序列優(yōu)化模型，以任務(wù)總完成時(shí)間最小化為目標(biāo)，考慮可穿越雙ARMG在作業(yè)過(guò)程中存在的干涉約束、任務(wù)執(zhí)行過(guò)程時(shí)序約束等，其數(shù)學(xué)優(yōu)化模型如下：

minF=T。

(1)

s.t.

yki=0,1，?i∈S,?k∈{A,B}；

(2)

(3)

(4)

(5)

(6)

(7)

?i,j∈S,i≠j,?k∈{A,B}；

(8)

?i,j∈S,i≠j,?k∈{A,B}；

(9)

?i,j∈E,i≠j,?k∈{A,B}；

(10)

?i,j∈S,i≠j,?k∈{A,B}；

(11)

?i,j∈S,i≠j,?k∈{A,B}；

(12)

(13)

i≠j,?k,k′∈{A,B},k≠k′；

(14)

i≠j,?k,k′∈{A,B},k≠k′；

(15)

?k,k′∈{A,B},k≠k′；

(16)

?k,k′∈{A,B},k≠k′；

(17)

(18)

3 改進(jìn)雙層遺傳算法設(shè)計(jì)

自動(dòng)化箱區(qū)中雙ARMG任務(wù)分配與作業(yè)序列優(yōu)化有很強(qiáng)的關(guān)聯(lián)性，每一個(gè)任務(wù)分配方案對(duì)應(yīng)一種特殊的作業(yè)序列要求；同時(shí)，受時(shí)序約束和作業(yè)干涉約束的影響，由雙ARMG作業(yè)序列細(xì)微變化而導(dǎo)致的連鎖反應(yīng)會(huì)對(duì)目標(biāo)函數(shù)產(chǎn)生深遠(yuǎn)影響。實(shí)際上，每一個(gè)任務(wù)分配方案對(duì)應(yīng)該方案下的一個(gè)作業(yè)序列優(yōu)化問(wèn)題，簡(jiǎn)單通過(guò)雙層編碼方式[30-31]難以有效求解該問(wèn)題，因此本文設(shè)計(jì)雙層遺傳算法進(jìn)行求解。雖然雙層遺傳算法運(yùn)算時(shí)間較長(zhǎng)，但是相對(duì)于批次作業(yè)時(shí)間比例很小，適用于求解該問(wèn)題。

3.1 算法整體流程

雙ARMG任務(wù)分配與作業(yè)序列聯(lián)合優(yōu)化雙遺傳算法整體流程如圖3所示。外層算法用于求解雙ARMG任務(wù)分配問(wèn)題，內(nèi)層算法用于求解該分配方案下的雙ARMG作業(yè)序列優(yōu)化問(wèn)題，內(nèi)層算法整體上可以認(rèn)為是外層算法中的目標(biāo)函數(shù)求解過(guò)程。算法最主要的改進(jìn)為，在內(nèi)層算法中根據(jù)本文求解問(wèn)題的特點(diǎn)設(shè)計(jì)的基于貪婪策略和隨機(jī)策略的混合策略(用于種群初始化)，以及求解目標(biāo)函數(shù)值時(shí)使用的雙ARMG時(shí)空狀態(tài)規(guī)劃方法。

3.2 內(nèi)外層算法遺傳操作

(1)染色體編碼與解碼

1)外層算法 求解雙ARMG任務(wù)分配問(wèn)題。將雙ARMG分別命名YCA(Yard Crane A)和YCB(Yard Crane B)，其中YCA為母ARMG，YCB為子ARMG。染色體編碼通過(guò)0，1兩個(gè)數(shù)字編碼，0表示將任務(wù)分配給YCA，1表示將任務(wù)分配給YCB，基因順序號(hào)表示任務(wù)號(hào)。如圖4所示，編碼011001表示將1，4，5號(hào)任務(wù)分配給YCA，2，3，6號(hào)任務(wù)分配給YCB。

2)內(nèi)層算法 求解雙ARMG作業(yè)序列優(yōu)化問(wèn)題。染色體編碼時(shí)，基因使用任務(wù)號(hào)編碼，基因順序大小表示作業(yè)的先后順序。如圖5所示，假設(shè)365241染色體為對(duì)應(yīng)上述011001外層染色體而生成的內(nèi)層作業(yè)序列染色體，該方案下YCA被分配的任務(wù)號(hào)為145，各任務(wù)分別對(duì)應(yīng)的內(nèi)層染色體基因順序號(hào)為653，根據(jù)基因順序號(hào)從小到大排序，翻譯為YCA的實(shí)際作業(yè)序列5→4→1,5號(hào)任務(wù)順序號(hào)最小，第一個(gè)執(zhí)行，4號(hào)任務(wù)次之，1號(hào)任務(wù)順序號(hào)最大，最后執(zhí)行。同理，YCB被分配任務(wù)236，對(duì)應(yīng)的順序號(hào)為412，根據(jù)基因順序號(hào)從小到大排序，翻譯為YCB的實(shí)際作業(yè)序列3→6→2。

(2)遺傳算子操作

1)交叉算子 本文采用中間重組的交叉方法，根據(jù)事先定義的交叉概率將兩條父代染色體中間部位的基因片段交叉互換。由于內(nèi)層染色體的任務(wù)號(hào)和任務(wù)順序號(hào)之間存在一一對(duì)應(yīng)關(guān)系，交叉操作后還需要找出新生成的兩條染色體中多余和重復(fù)的基因，用缺少的基因依次替換每條染色體上多余的基因，以保證任務(wù)號(hào)和順序號(hào)之間的對(duì)應(yīng)該系。

2)變異算子 變異算子根據(jù)事先設(shè)定的變異概率判斷是否對(duì)該個(gè)體進(jìn)行變異，是則對(duì)該個(gè)體隨機(jī)選擇變異位進(jìn)行變異。本文采用交換變異的方法選取待變異染色體任意兩個(gè)位置上的基因，對(duì)調(diào)這兩個(gè)基因的順序完成變異，該操作適用于內(nèi)外層染色體。

3.3 基于混合策略種群初始化

由于雙層遺傳算法同時(shí)求解雙ARMG任務(wù)分配與作業(yè)序列優(yōu)化，需要使用內(nèi)層算法求解外層的每一個(gè)可行解(任務(wù)分配方案)，以得到外層可行解的目標(biāo)函數(shù)，因此算法計(jì)算量大。為使內(nèi)層算法加速收斂，提高其求解速度，在種群初始化時(shí)使用貪婪策略與隨機(jī)策略組合的混合策略，貪婪策略能使算法在較高起點(diǎn)開始進(jìn)化，隨機(jī)策略可以保證算法的隨機(jī)性，避免早熟。

內(nèi)層算法初始化使用貪婪策略時(shí)，雙ARMG根據(jù)最近原則依次確定任務(wù)的作業(yè)順序。以3.2節(jié)YCA被分配任務(wù)號(hào)145、YCB被分配任務(wù)號(hào)236為例，假設(shè)各項(xiàng)任務(wù)作業(yè)的起始位置和目標(biāo)位置如表2所示，YCA的初始位置在12倍，YCB的初始位置在36倍。使用貪婪策略生成內(nèi)層算法初始解時(shí)，YCA優(yōu)先選擇作業(yè)起始位置最近的1號(hào)任務(wù)，完成1號(hào)任務(wù)后將其坐標(biāo)位置變?yōu)?0倍，因此1號(hào)任務(wù)結(jié)束后選擇起始位置離30倍更近的5號(hào)任務(wù)，最后執(zhí)行4號(hào)任務(wù)。同理，使用貪婪策略的YCB任務(wù)序列為2→3→6。在使用混合策略生成內(nèi)層算法初始種群時(shí)，可以設(shè)定一定比例數(shù)量的種群使用貪婪策略，另外一部分種群使用隨機(jī)策略。

表2 小型算例

3.4 雙ARMG時(shí)空狀態(tài)規(guī)劃

當(dāng)內(nèi)層算法生成雙ARMG作業(yè)序列時(shí)，可以通過(guò)雙ARMG時(shí)空狀態(tài)規(guī)劃計(jì)算可行解目標(biāo)函數(shù)。雙ARMG雖然可以相互穿越，但是仍然存在兩種干涉約束：①同一時(shí)段二者不能在同一倍位進(jìn)行裝卸作業(yè)；②當(dāng)母ARMG裝卸作業(yè)時(shí)，子ARMG不能穿越。由于直接規(guī)劃雙ARMG時(shí)空狀態(tài)比較困難，本文提出兩階段雙ARMG時(shí)空狀態(tài)規(guī)劃方法。第一階段，不考慮雙ARMG作業(yè)沖突，直接根據(jù)雙ARMG作業(yè)序列和其他已知條件計(jì)算雙ARMG時(shí)空狀態(tài)的推進(jìn)過(guò)程，得到松弛條件下(不考慮干涉)雙ARMG時(shí)空狀態(tài)表；第二階段，在松弛條件下時(shí)空狀態(tài)表的基礎(chǔ)上檢測(cè)干涉情況，并調(diào)整時(shí)空狀態(tài)表，直到消除所有干涉情況后得到滿足所有約束條件的雙ARMG時(shí)空狀態(tài)表。

表3 松弛條件下的ARMG時(shí)空狀態(tài)

第二階段，在松弛條件下的時(shí)空狀態(tài)表中，針對(duì)兩類潛在干涉情形進(jìn)行檢測(cè)和調(diào)整。第一類潛在干涉和調(diào)整是針對(duì)母ARMG和子ARMG不能同時(shí)在相同位置進(jìn)行裝卸操作的約束，調(diào)整情形如圖6所示。如果未調(diào)整，則場(chǎng)橋1和場(chǎng)橋2會(huì)在位置18處發(fā)生同時(shí)裝卸作業(yè)事件，因此后到場(chǎng)橋1需要等待先到場(chǎng)橋2完成該項(xiàng)操作后再進(jìn)入倍位18進(jìn)行裝卸作業(yè)。第二類潛在干涉和調(diào)整是針對(duì)母ARMG進(jìn)行作業(yè)時(shí)子ARMG不能穿越的約束，調(diào)整情形如圖7所示，若未經(jīng)調(diào)整，則場(chǎng)橋1(母ARMG)在裝卸作業(yè)時(shí)場(chǎng)橋2(子ARMG)將會(huì)穿越場(chǎng)橋1，調(diào)整后場(chǎng)橋2將等待場(chǎng)橋1完成裝卸作業(yè)后再穿越。

第二階段干涉檢查和調(diào)整算法偽代碼如下所示。其中：LastBay表示上次倍位，ThisBay表示本次倍位，STime表示任務(wù)開始時(shí)刻，RTime表示到達(dá)時(shí)刻，PTime表示操作時(shí)刻，ETime表示操作完成時(shí)刻,SafeTime表示走過(guò)安全距離所需的時(shí)間。

表3按PTime列升序排序

For i=2;i≤最大行;i++:

//第一類干涉檢測(cè)與調(diào)整

If(時(shí)段[PTime(i),ETime(i)]與時(shí)段[PTime(i-1)-SafeTime,ETime(i-1)+SafeTime]重疊且ThisBay(i)=ThisBay(i-1)):

Δt=ETime(i-1)+SafeTime-PTime(i)；

For j=I;j≤最大行;j++:

If(場(chǎng)橋(j)=場(chǎng)橋(i)):STime(j),RTime(j),PTime(j),ETime(j)都增加Δt。

//第二類干涉檢測(cè)與調(diào)整(場(chǎng)橋A為母ARMG)

If(場(chǎng)橋(i)='A'):

//檢測(cè)i-1行狀態(tài)并調(diào)整

If(場(chǎng)橋(i-1)='B'且時(shí)段[STime(i-1),RTime(i-1)]與時(shí)段[PTime(i)-SafeTime,ETime(i)+SafeTime]重疊且i-1行倍位與i行倍位存在穿越關(guān)系)：

Δt=ETime(i)+SafeTime-PTime(i-1)；

For j=i-1,j≤最大行，j++:

If(場(chǎng)橋(j)=場(chǎng)橋(i-1))：STime(j),RTime(j),PTime(j),ETime(j)都增加Δt。

//檢測(cè)i+1行狀態(tài)并調(diào)整

與i-1行檢測(cè)與調(diào)整方法相同

4 實(shí)驗(yàn)設(shè)計(jì)與結(jié)果分析

本文實(shí)驗(yàn)以自動(dòng)化集裝箱碼頭常規(guī)配置方案進(jìn)行參數(shù)設(shè)置，實(shí)驗(yàn)中的各項(xiàng)參數(shù)如下：倍位間距ds=6.5 m，ARMG抓取集裝箱時(shí)間po=25 s，ARMG放落集裝箱時(shí)間pd=30 s，ARMG大車移動(dòng)速度V=4 m/s。本文所有算例基于Intel Xeon(R)E5520 CPU@2.25 GHz，4 GB內(nèi)存的Window10系統(tǒng)運(yùn)行。

4.1 典型算例分析

首先通過(guò)一個(gè)任務(wù)規(guī)模為20、箱區(qū)長(zhǎng)度為48倍的典型算例，分析改進(jìn)雙層遺傳算法的收斂過(guò)程和計(jì)算結(jié)果。算例所有任務(wù)的起始提箱倍位、目標(biāo)落箱倍位如表4所示。

表4 典型算例輸入任務(wù)列表

續(xù)表4

該算例中，設(shè)置內(nèi)外層算法選擇概率均為0.6，變異概率為0.05，內(nèi)層算法初始種群生成策略隨機(jī)生成概率為0.9，貪婪策略生成概率為0.1；外層算法的最大迭代次數(shù)為500代，內(nèi)層算法連續(xù)10代最佳目標(biāo)函數(shù)不變?yōu)槭諗颗袆e條件。經(jīng)過(guò)500代運(yùn)算后得到的最佳目標(biāo)函數(shù)收斂過(guò)程如圖8所示。

由圖8可見，20項(xiàng)作業(yè)任務(wù)完成時(shí)間從初代934.875 s快速下降，在第14代下降為891.25 s，最終在第108代收斂到888 s，可見算法具有較好的收斂性。最終得到的雙ARMG任務(wù)分配、作業(yè)序列和最終時(shí)空狀態(tài)推進(jìn)過(guò)程如表5所示。

表5 最優(yōu)解中的ARMG時(shí)空狀態(tài)

續(xù)表5

表中外層母ARMG(YCA)被分配10項(xiàng)任務(wù)，任務(wù)序列為4，3，5，10，15，2，16，8，12，9，完成時(shí)間888 s；子ARMG(YCB)被分配10項(xiàng)任務(wù)，任務(wù)序列為13，11，17，14，1，19，7，6，20，18，完成時(shí)間為883.13 s。將表5雙ARMG時(shí)空狀態(tài)推進(jìn)過(guò)程轉(zhuǎn)化為圖9雙ARMG時(shí)空狀態(tài)圖。從圖9可見，雙ARMG作業(yè)過(guò)程不存在相同位置同時(shí)作業(yè)的情況，也不存在子ARMG(YCB)在母ARMG(YCA)裝卸作業(yè)時(shí)穿越的情況，但允許外層YCA在YCB裝卸作業(yè)時(shí)穿越?？梢?，該算例的最優(yōu)解滿足雙ARMG作業(yè)過(guò)程干涉約束，同時(shí)雙ARMG作業(yè)過(guò)程也滿足時(shí)序約束。

4.2 靈敏度分析

改進(jìn)雙層遺傳算法對(duì)算法性能影響的參數(shù)主要有內(nèi)外層算法選擇與變異概率、內(nèi)外層算法收斂條件、內(nèi)層算法初始化種群生成中貪婪策略與隨機(jī)策略的生成比例。由于參數(shù)眾多，通過(guò)逐步確定方式進(jìn)行參數(shù)選擇來(lái)分析這些參數(shù)對(duì)算法性能的影響。

(1)實(shí)驗(yàn)一——內(nèi)層算法收斂條件

經(jīng)過(guò)預(yù)先算例實(shí)驗(yàn)分析發(fā)現(xiàn)，內(nèi)層算法收斂條件對(duì)算法運(yùn)算時(shí)間和優(yōu)化效果影響較大，因此優(yōu)先確定內(nèi)層算法收斂條件。先假設(shè)內(nèi)外層算法的選擇、變異概率分別為0.6和0.05，外層算法收斂條件為連續(xù)30代不變；內(nèi)層算法種群初始化時(shí)的隨機(jī)策略概率為0.9，收斂條件分別設(shè)置為連續(xù)10，20，30，40代不變，結(jié)合表4算例對(duì)內(nèi)層算法收斂條件進(jìn)行實(shí)驗(yàn)，每組運(yùn)算10次求得的最終目標(biāo)函數(shù)和CPU消耗時(shí)間均值如圖10所示。

由圖10可見，內(nèi)層算法收斂條件逐步提高，CPU消耗時(shí)間顯著增加，但目標(biāo)函數(shù)下降緩慢。因此，從算法效率優(yōu)先角度考慮內(nèi)層算法收斂條件選擇連續(xù)10代不變，此時(shí)平均CPU時(shí)間為117.97 s，相對(duì)于批次任務(wù)完成時(shí)間在可接受范圍內(nèi)。

(2)實(shí)驗(yàn)二——內(nèi)層算法初始化隨機(jī)策略比例

在實(shí)驗(yàn)一基礎(chǔ)上固定內(nèi)層算法收斂條件為連續(xù)10代不變，內(nèi)層算法種群初始化時(shí)的隨機(jī)策略概率為0.1～0.9，分別設(shè)置9組實(shí)驗(yàn)，每組實(shí)驗(yàn)運(yùn)行10次，得到最終目標(biāo)函數(shù)和CPU消耗時(shí)間均值如圖11所示。

由圖11可見，內(nèi)層算法初始化時(shí)隨機(jī)策略概率從0.1～0.9，最佳目標(biāo)函數(shù)先逐漸下降，在0.6時(shí)達(dá)到最小然后逐漸上升，CPU運(yùn)算時(shí)間無(wú)明顯變化，因此內(nèi)層算法初始化時(shí)選擇隨機(jī)策略概率為0.6，對(duì)應(yīng)的貪婪策略生成概率為0.4。

(3)實(shí)驗(yàn)三——外層算法收斂條件

在實(shí)驗(yàn)二基礎(chǔ)上，進(jìn)一步固定內(nèi)層初始化隨機(jī)策略概率為0.6，外層算法收斂條件分別設(shè)置為連續(xù)10，20，30，40，50代不變，每組實(shí)驗(yàn)運(yùn)行10次，得到目標(biāo)函數(shù)和CPU消耗時(shí)間均值如圖12所示。

由圖12可見，外層算法收斂條件逐步提高時(shí)，CPU消耗時(shí)間顯著增加，但目標(biāo)函數(shù)下降緩慢。當(dāng)外層算法收斂條件為連續(xù)30代不變時(shí)，CPU消耗時(shí)間增速加快，最佳目標(biāo)函數(shù)減速降低，此時(shí)CPU時(shí)間均值為137 s，相對(duì)于批次任務(wù)完成時(shí)間在可接受范圍內(nèi)，因此選擇外層算法收斂條件為連續(xù)30代不變。

(4)實(shí)驗(yàn)四——交叉、變異概率

在實(shí)驗(yàn)三基礎(chǔ)上，固定外層算法收斂條件為連續(xù)30代不變，內(nèi)層算法交叉概率設(shè)為[0.4,0.5,0.6]，變異概率設(shè)為[0.04,0.05,0.06],每組實(shí)驗(yàn)運(yùn)行10次，得到目標(biāo)函數(shù)和CPU消耗時(shí)間均值如表6所示。

表6 內(nèi)層算法交叉率與變異率分析

續(xù)表6

由表6可見，內(nèi)層算法交叉概率不變時(shí)，變異概率變化對(duì)CPU耗時(shí)基本沒(méi)有影響，但是3組實(shí)驗(yàn)中變異概率為0.05時(shí)，目標(biāo)函數(shù)值在同組實(shí)驗(yàn)中均較小，因此變異概率選擇0.05。對(duì)相同交叉概率實(shí)驗(yàn)結(jié)果求均值，發(fā)現(xiàn)隨著內(nèi)層算法交叉概率的提高，CPU耗時(shí)提升得比較明顯，當(dāng)交叉概率從0.4提升到0.5和0.6時(shí)，目標(biāo)函數(shù)值下降明顯且較為穩(wěn)定，因此內(nèi)層算法選擇交叉概率為0.5，變異概率為0.05。

固定內(nèi)層算法的交叉概率和變異概率，外層算法的交叉概率分別設(shè)置為[0.4,0.5,0.6]，變異概率分別設(shè)置為[0.04,0.05,0.06],每組實(shí)驗(yàn)運(yùn)行10次，得到目標(biāo)函數(shù)和CPU消耗時(shí)間均值如表7所示。

表7 外層算法交叉率與變異率分析

由表7可見，外層算法變異概率對(duì)目標(biāo)函數(shù)和CPU耗時(shí)均無(wú)明顯影響，當(dāng)變異概率為0.04時(shí),總體上目標(biāo)函數(shù)值較小，因此選擇外層變異概率為0.04.對(duì)相同交叉概率實(shí)驗(yàn)結(jié)果求均值，發(fā)現(xiàn)隨著外層算法交叉概率的提高，CPU耗時(shí)提升得比較明顯，目標(biāo)函數(shù)值略微上升，因此選擇交叉概率為0.4。

4.3 算法性能分析

根據(jù)4.2節(jié)參數(shù)靈敏度分析結(jié)果，外層算法的交叉概率為0.4，變異概率為0.04，收斂條件連續(xù)30代不變；內(nèi)層算法的交叉概率為0.5，變異概率為0.05，初始化隨機(jī)策略概率為0.6，貪婪策略概率為0.4，收斂條件連續(xù)10代不變，根據(jù)不同箱區(qū)規(guī)模和任務(wù)規(guī)模設(shè)計(jì)15組實(shí)驗(yàn)，每組實(shí)驗(yàn)運(yùn)行10次求均值，得到不同規(guī)模下的單任務(wù)平均完成時(shí)間，如圖13所示。

由圖13可見，不同規(guī)模下任務(wù)的平均完成時(shí)間基本在40 s～50 s之間。任務(wù)數(shù)量增加，任務(wù)的平均完成時(shí)間沒(méi)有增加，可見算法優(yōu)化效果不受任務(wù)數(shù)量的影響。箱區(qū)規(guī)模變化時(shí)，不同實(shí)驗(yàn)表現(xiàn)出不同的變化趨勢(shì)，主要因?yàn)橄鋮^(qū)倍位數(shù)增加會(huì)使任務(wù)運(yùn)輸距離增加，但不同算例下任務(wù)的起始取箱點(diǎn)和目標(biāo)卸箱點(diǎn)之間的距離隨機(jī)性較大，因此不同算例會(huì)有不同的表現(xiàn)。

圖14所示為不同規(guī)模下的CPU平均耗時(shí)，可見隨著任務(wù)規(guī)模的增加，CPU平均耗時(shí)呈現(xiàn)線性增長(zhǎng)，算法CPU運(yùn)算時(shí)間可控，相對(duì)于批次任務(wù)總體完成時(shí)間較小，適用于求解實(shí)際問(wèn)題。

為分析雙層遺傳算法的優(yōu)化效果，設(shè)計(jì)單層遺傳算法，將任務(wù)分配與作業(yè)序列分層編碼[30-31]。上層染色體使用“01”編碼，0表示對(duì)應(yīng)位置的任務(wù)分配給YCA，1表示對(duì)應(yīng)位置的任務(wù)分配給YCB；下層染色體使用任務(wù)號(hào)編碼，基因位置表示任務(wù)先后順序，例如01011#53214，表示YCA任務(wù)序列為52，YCB任務(wù)序列為314。在遺傳操作時(shí)，上下層染色體分別獨(dú)立操作。遺傳操作中采用輪盤賭選擇策略，交叉變異操作同雙層遺傳算法中的內(nèi)外層染色體操作，并通過(guò)預(yù)先實(shí)驗(yàn)分析設(shè)置單層遺傳算法的交叉率為0.8，變異率為0.05。單層遺傳算法和雙層遺傳算法在不同規(guī)模實(shí)驗(yàn)中的性能表現(xiàn)如表8所示。由表8可見，單層遺傳算法運(yùn)算時(shí)間在0.6 s以內(nèi)，相對(duì)于雙層遺傳算法存在較大優(yōu)勢(shì)，但是優(yōu)化效果明顯差于雙層遺傳算法，平均單任務(wù)完成時(shí)間比雙層遺傳算法增加30%左右?？梢?，雙層遺傳算法對(duì)作業(yè)時(shí)間敏感的雙ARMG任務(wù)分配與作業(yè)序列聯(lián)合優(yōu)化問(wèn)題具有良好的優(yōu)化效果。

表8 單、雙層遺傳算法在不同規(guī)模實(shí)驗(yàn)中的性能(每組實(shí)驗(yàn)運(yùn)行10次取均值)

5 結(jié)束語(yǔ)

本文針對(duì)自動(dòng)化集裝箱碼頭的可穿越式雙ARMG任務(wù)分配與作業(yè)序列聯(lián)合優(yōu)化問(wèn)題建立數(shù)學(xué)優(yōu)化模型，以雙ARMG完成任務(wù)時(shí)間最小為目標(biāo)，考慮了雙ARMG作業(yè)過(guò)程時(shí)序約束和相互干涉約束等，設(shè)計(jì)了改進(jìn)的雙層遺傳算法求解該問(wèn)題，其中外層算法求解任務(wù)分配問(wèn)題，內(nèi)層算法求解作業(yè)序列優(yōu)化問(wèn)題。另外，本文在內(nèi)層算法初始種群生成過(guò)程中引入包含隨機(jī)策略和貪婪策略的混合生成策略，貪婪策略可生成較為合理的初始解集，隨機(jī)策略用于擴(kuò)大算搜索空間，以避免算法早熟。

實(shí)驗(yàn)分析表明，本文提出的改進(jìn)雙層遺傳算法可以有效求解可穿越式雙ARMG任務(wù)分配分配和序列優(yōu)化問(wèn)題，與傳統(tǒng)的將兩個(gè)問(wèn)題分開求解方法相比有一定的優(yōu)勢(shì)。然而雙層遺傳算法也存在運(yùn)算量較大的不足，外層算法中計(jì)算每個(gè)個(gè)體目標(biāo)函數(shù)都需要完整運(yùn)行一次內(nèi)層遺傳算法，當(dāng)任務(wù)規(guī)模增加時(shí)計(jì)算量呈線性增長(zhǎng)，影響了算法的效率，未來(lái)的研究可考慮在提高算法優(yōu)化效果同時(shí)，一步提高算法效率。另一方面，自動(dòng)化集裝箱碼頭雙ARMG箱區(qū)系統(tǒng)作業(yè)與水平運(yùn)輸系統(tǒng)協(xié)同作業(yè)對(duì)于提升自動(dòng)化集裝箱碼頭整體裝卸效率具有重要意義，這也將是下一步研究工作的重點(diǎn)。