黃子釗，莊子龍，滕 浩，秦 威+，秦 濤，鄒 鷹

(1.上海交通大學(xué) 機(jī)械與動(dòng)力工程學(xué)院，上海 200240；2.上海海勃物流軟件有限公司，上海 200080；3.上海國(guó)際港務(wù)(集團(tuán))股份有限公司，上海 200080)

0 引言

近年來(lái)，在集裝箱碼頭領(lǐng)域，隨著自動(dòng)化設(shè)備、人工智能算法等技術(shù)的不斷發(fā)展，自動(dòng)化集裝箱碼頭在提高碼頭整體作業(yè)效率、降低勞動(dòng)力成本等方面逐漸形成明顯優(yōu)勢(shì)，已成為未來(lái)的發(fā)展趨勢(shì)。然而，由于規(guī)模龐大、業(yè)務(wù)復(fù)雜、現(xiàn)場(chǎng)操作人員少等特點(diǎn)，自動(dòng)化集裝箱碼頭的作業(yè)效率還存在較大的提升空間，急需更高效的計(jì)劃調(diào)度方案。其中，在關(guān)系到船舶停靠時(shí)間即碼頭效率的出口箱裝船作業(yè)中，自動(dòng)化集裝箱堆場(chǎng)由于箱區(qū)垂直于岸邊、交互區(qū)位于箱區(qū)兩側(cè)、場(chǎng)橋沖突等約束的存在，以及出口箱需要從陸側(cè)入場(chǎng)、從海側(cè)出場(chǎng)導(dǎo)致的場(chǎng)橋操作距離較大的狀況，難以取得較合理的決策，是出口箱作業(yè)效率提升的瓶頸所在。在堆場(chǎng)作業(yè)中，出口箱的箱位分配是堆場(chǎng)優(yōu)化的基礎(chǔ)和關(guān)鍵，方案的優(yōu)劣直接影響到了堆場(chǎng)的吞吐能力，進(jìn)而影響出口箱裝船作業(yè)的效率。但是，由于問(wèn)題規(guī)模較大、動(dòng)態(tài)性較強(qiáng)、約束較多等特點(diǎn)，目前實(shí)際采用的箱位分配方案難以滿足任務(wù)平衡、翻箱率低等要求，制約了作業(yè)效率的提升。因此，研究自動(dòng)化集裝箱碼頭出口箱箱位分配問(wèn)題對(duì)提高出口箱整體作業(yè)效率具有重要意義，已受到學(xué)者們的持續(xù)關(guān)注。

在自動(dòng)化集裝箱碼頭出口箱箱位分配問(wèn)題中，現(xiàn)有研究按研究尺度可以分為箱區(qū)或倍位分配以及具體箱位分配兩種。在箱區(qū)或倍位分配中，LIANG等[1]考慮一個(gè)作業(yè)路上的任務(wù)，基于最小化集裝箱移動(dòng)距離，建立了混合整數(shù)規(guī)劃模型，并采用混合的遺傳算法展開求解；JIANG等[2]以最小化成本，即可預(yù)計(jì)的場(chǎng)橋移動(dòng)操作成本及翻箱成本為目標(biāo)，開發(fā)了分支定界方法展開求解，得到了每個(gè)任務(wù)的目標(biāo)倍位；梁承姬等[3]針對(duì)一個(gè)箱區(qū)，以負(fù)載均衡為目標(biāo)，設(shè)計(jì)了基于網(wǎng)絡(luò)流的禁忌搜索算法，通過(guò)與精確求解算法展開對(duì)比，證明了算法的有效性；YANG等[4]考慮到經(jīng)濟(jì)方面的約束，以最小化成本和最大化利潤(rùn)為目標(biāo)，基于遺傳算法針對(duì)每個(gè)任務(wù)指派對(duì)應(yīng)的倍位和機(jī)械資源;靳志宏等[5]考慮到外集卡提前預(yù)約入場(chǎng)的現(xiàn)狀，為了讓箱區(qū)負(fù)載均衡，建立了數(shù)學(xué)規(guī)劃模型并使用CPLEX進(jìn)行求解，結(jié)論表明預(yù)約信息對(duì)作業(yè)均衡有20～30個(gè)百分點(diǎn)的幫助;倪敏敏等[6]考慮到場(chǎng)橋同時(shí)作業(yè)的影響，采用分區(qū)域動(dòng)態(tài)平衡的方法減少場(chǎng)橋的無(wú)效作業(yè)時(shí)間，提高堆場(chǎng)效率；韓笑樂(lè)等[7]考慮泊位與堆場(chǎng)的相互影響，設(shè)計(jì)了改進(jìn)的遺傳算法得到不確定環(huán)境下的箱區(qū)和泊位分配方案，實(shí)現(xiàn)了魯棒性調(diào)度決策。

在具體箱位的分配中，CARLO等[8]綜述了早些年針對(duì)箱位分配問(wèn)題的研究，其中求解方法可以分為先執(zhí)行箱區(qū)和倍位分配后執(zhí)行具體箱位分配的兩階段方法和通過(guò)混合操作一步得到完整分配方案兩大類，通過(guò)對(duì)比發(fā)現(xiàn)后者的性能優(yōu)于前者。近五年來(lái)，BOYSEN等[9]針對(duì)一個(gè)倍位的堆存范圍，以最小化翻箱為目標(biāo)，定義了箱位分配問(wèn)題的下界，并證明了可以在n3時(shí)間復(fù)雜度內(nèi)精確求解；GOERIGK等[10]考慮到箱位分配會(huì)對(duì)場(chǎng)橋調(diào)度有直接影響，以最小化箱位沖突為目標(biāo)，建立了破壞和重建的局部搜索方法;曾建智等[11]引入后期機(jī)械資源調(diào)度的約束，開發(fā)了雙層遺傳算法同時(shí)解決箱位分配與資源調(diào)度問(wèn)題；周鵬飛等[12]也考慮了外集卡的不確定性，基于目前碼頭已有的預(yù)約信息，使用了基于圖的禁忌搜索算法，較確定性模型取得了十余個(gè)百分點(diǎn)的提高；SHEN等[13]針對(duì)一個(gè)倍位的箱位分配問(wèn)題，考慮到問(wèn)題時(shí)間要求較高，在同一種環(huán)境下應(yīng)用機(jī)器學(xué)習(xí)方法，采用堆場(chǎng)現(xiàn)狀作為狀態(tài)，目標(biāo)箱位作為動(dòng)作，方案的可行性作為回報(bào)，并采用隨機(jī)數(shù)據(jù)進(jìn)行訓(xùn)練和驗(yàn)證，得到了符合實(shí)際的分配方案;李隋凱等[14]針對(duì)出口箱箱位分配，引入接力操作，采用動(dòng)態(tài)規(guī)劃方法快速得到了較好的解;CHANG等[15]考慮箱區(qū)負(fù)載均衡以及箱位沖突最小的目標(biāo)，開發(fā)了基于模擬退火框架的兩階段調(diào)度模型，得到完整的箱位分配方案;MALDONADO等[16]基于集裝箱在港口的停留時(shí)間，開發(fā)了箱位分配模型，從而減少可預(yù)見的翻箱操作。

總之，在箱位分配問(wèn)題中，當(dāng)前的一部分研究更多關(guān)注具體箱位的選取，并采用精確求解、調(diào)度規(guī)則或智能算法加以解決。另一部分研究則關(guān)注箱區(qū)或倍位的選擇，通過(guò)和其他問(wèn)題的集成形成全局中更好的方案。然而，由于自動(dòng)化集裝箱碼頭出口箱箱位分配問(wèn)題具有較大規(guī)模和難度，當(dāng)前的解決方案還不能滿足碼頭整體高效作業(yè)的需要。同時(shí)在當(dāng)前研究中，較少考慮實(shí)際自動(dòng)化集裝箱堆場(chǎng)的接力、多箱區(qū)協(xié)同等特性，且方案效果還有較大的提升空間。基于這一現(xiàn)狀，本文提出一個(gè)考慮實(shí)際場(chǎng)景中上述兩個(gè)特性的出口箱箱位分配問(wèn)題模型，從而確定具體箱位，使后續(xù)翻箱率最低。之后，本文提出一種新穎的基于強(qiáng)化學(xué)習(xí)的超啟發(fā)式算法用于解決這一問(wèn)題，得到高質(zhì)量的箱位分配方案，提高自動(dòng)化集裝箱碼頭出口箱作業(yè)的作業(yè)效率。

1 問(wèn)題描述

如圖1所示為自動(dòng)化集裝箱堆場(chǎng)堆存的示意圖，自動(dòng)化集裝箱堆場(chǎng)可以劃分為數(shù)十個(gè)箱區(qū)，每一個(gè)箱區(qū)由若干個(gè)倍位組成，每個(gè)倍位由數(shù)列和數(shù)層構(gòu)成。在自動(dòng)化集裝箱堆場(chǎng)中，通常一個(gè)箱區(qū)包含50個(gè)倍位，一個(gè)倍位由10列和6層組成，即一個(gè)箱區(qū)包含3 000個(gè)集裝箱箱位,具有極大的規(guī)模。

如圖2所示為典型的自動(dòng)化集裝箱堆場(chǎng)的示意圖。區(qū)別于傳統(tǒng)集裝箱堆場(chǎng)，為滿足自動(dòng)化區(qū)域與人工區(qū)域的分離，自動(dòng)化集裝箱堆場(chǎng)與自動(dòng)導(dǎo)引小車(Automated Guided Vechicle,AGV)和外集卡的交互集中于箱區(qū)兩側(cè)，而不像傳統(tǒng)堆場(chǎng)那樣可以在箱區(qū)邊緣任意地方。同時(shí)，自動(dòng)化集裝箱堆場(chǎng)使用軌道吊沿著既定的軌道執(zhí)行操作，不能相互跨越和在多個(gè)箱區(qū)間移動(dòng)。因此，為了最大化工作效率，一個(gè)箱區(qū)中通常會(huì)配置兩臺(tái)場(chǎng)橋，服務(wù)于海側(cè)和陸側(cè)兩個(gè)交互區(qū)。

基于上述特點(diǎn)，自動(dòng)化集裝箱堆場(chǎng)箱區(qū)的吞吐能力的上限較低，單個(gè)箱區(qū)難以滿足短時(shí)間內(nèi)密集的出口箱運(yùn)輸任務(wù)。在此情境下，為了最小化任務(wù)延期時(shí)間和最大化工作效率，自動(dòng)化集裝箱堆場(chǎng)采用多箱區(qū)協(xié)同的方式，打破傳統(tǒng)堆場(chǎng)按類別放置集裝箱的原則，將同時(shí)段同泊位的集裝箱分散于數(shù)個(gè)箱區(qū)中，盡可能使得各個(gè)箱區(qū)的任務(wù)負(fù)荷相當(dāng)，從而發(fā)揮箱區(qū)數(shù)量大的優(yōu)勢(shì)，滿足出口箱運(yùn)輸需求。另外，基于出口箱海側(cè)任務(wù)密集的特點(diǎn)，為了使吞吐能力滿足需求，堆場(chǎng)引入了懸臂吊設(shè)備，能夠與AGV在箱區(qū)側(cè)面展開交互，減小場(chǎng)橋移動(dòng)距離，提升箱區(qū)海側(cè)交互能力。這些方式雖然具備更高的效率，但極大地提高了問(wèn)題的復(fù)雜性，對(duì)堆場(chǎng)的計(jì)劃調(diào)度提出了更大的挑戰(zhàn)。

在出口箱作業(yè)中，集裝箱由外集卡運(yùn)輸進(jìn)入堆場(chǎng)，經(jīng)過(guò)陸側(cè)入場(chǎng)作業(yè)、堆場(chǎng)存儲(chǔ)、海側(cè)出場(chǎng)作業(yè)3個(gè)階段，最終由海側(cè)經(jīng)AGV運(yùn)輸離開堆場(chǎng)，整體的作業(yè)流程如圖3所示。在這一流程中，由于自動(dòng)化集裝箱堆場(chǎng)的長(zhǎng)度較長(zhǎng)、場(chǎng)橋無(wú)法相互跨越，若由單一場(chǎng)橋執(zhí)行入場(chǎng)和出場(chǎng)作業(yè)，會(huì)使作業(yè)區(qū)間較大，極大影響到另一臺(tái)場(chǎng)橋的作業(yè)，導(dǎo)致整體效率偏低。因此，自動(dòng)化集裝箱堆場(chǎng)設(shè)計(jì)了較為復(fù)雜的接力操作，即兩臺(tái)場(chǎng)橋配合執(zhí)行一項(xiàng)出口箱的入場(chǎng)任務(wù)。首先在堆場(chǎng)中部設(shè)立了中轉(zhuǎn)區(qū)用于出口箱接力操作，其次針對(duì)出口箱制定中轉(zhuǎn)箱位，由陸側(cè)場(chǎng)橋?qū)⒊隹谙鋸耐饧ㄞD(zhuǎn)移至中轉(zhuǎn)區(qū)，之后由海側(cè)場(chǎng)橋由中轉(zhuǎn)區(qū)移動(dòng)至海側(cè)的目標(biāo)箱位。由于集裝箱堆疊的一系列原則，中轉(zhuǎn)區(qū)的箱位選擇需要盡可能均衡，從而減少阻塞情況。

由于自動(dòng)化集裝箱堆場(chǎng)是一個(gè)三維環(huán)境，在出口箱出場(chǎng)作業(yè)中，若目標(biāo)集裝箱不在最頂層，則會(huì)產(chǎn)生壓箱，需要先將上方的集裝箱翻倒再執(zhí)行出場(chǎng)作業(yè)。圖4列出了一個(gè)倍位的出場(chǎng)作業(yè)截面圖。假設(shè)當(dāng)前時(shí)刻為0，圖4中集裝箱的數(shù)字為根據(jù)船舶配積載和AGV計(jì)劃得到的出場(chǎng)時(shí)間，數(shù)字越小說(shuō)明出場(chǎng)越早。在出口箱入場(chǎng)作業(yè)時(shí)，若該集裝箱的出場(chǎng)時(shí)間晚于其下方集裝箱的出場(chǎng)時(shí)間，則產(chǎn)生壓箱，后期需要執(zhí)行一次翻箱操作。以圖4所示出口箱為例，灰色出口箱1下方?jīng)]有早于該箱的集裝箱，因此無(wú)需翻箱；而灰色出口箱8下方集裝箱的出場(chǎng)時(shí)間要早于該箱，需要翻箱，影響了作業(yè)效率。經(jīng)統(tǒng)計(jì)，在自動(dòng)化集裝箱堆場(chǎng)中，翻箱操作已成為制約堆場(chǎng)作業(yè)效率的最主要因素，需要在出口箱箱位分配時(shí)予以著重考慮。

由上述分析可知，在自動(dòng)化集裝箱碼頭出口箱作業(yè)中，由于問(wèn)題規(guī)模較大、堆場(chǎng)空間及場(chǎng)橋的約束較多、多箱區(qū)、懸臂吊、接力和壓箱等特點(diǎn)，出口箱箱位分配問(wèn)題具有較大的挑戰(zhàn)。因此，本文以出口箱箱位分配問(wèn)題為研究對(duì)象，以平衡箱區(qū)和中轉(zhuǎn)區(qū)的負(fù)載以及最小化后續(xù)翻箱操作為目標(biāo)，對(duì)出口箱的箱區(qū)、中轉(zhuǎn)箱位和目標(biāo)箱位的指派進(jìn)行優(yōu)化，達(dá)到堆場(chǎng)高效處理出口箱任務(wù)的目的。

2 問(wèn)題建模

由于自動(dòng)化集裝箱碼頭不斷運(yùn)行，出口箱任務(wù)的入場(chǎng)出場(chǎng)等信息需要通過(guò)預(yù)測(cè)等手段得到，存在一定的誤差，且該誤差會(huì)隨著時(shí)間的推移逐漸累積，繼而影響最終方案的性能。因此，需要引入實(shí)時(shí)修正的求解方法?；谶@一特點(diǎn)，本文采用滾動(dòng)計(jì)劃考慮一個(gè)時(shí)間窗口內(nèi)的出口箱箱位分配問(wèn)題，即每次考慮之后一段時(shí)間內(nèi)的箱位分配問(wèn)題，并在實(shí)際采用前一部分方案后，重新針對(duì)后一部分以及之后一段時(shí)間內(nèi)新的箱位分配問(wèn)題進(jìn)行分析，在獲取了新的出口箱信息的情況下，盡可能減少上述誤差。具體模型如下：

2.1 問(wèn)題假設(shè)

(1)由于箱區(qū)與泊位存在多對(duì)一的關(guān)系，考慮一個(gè)泊位對(duì)應(yīng)的數(shù)個(gè)箱區(qū)的箱位分配問(wèn)題。

(2)每個(gè)箱區(qū)中場(chǎng)橋設(shè)備是否為懸臂吊的情況已知，且不考慮設(shè)備的故障。

(3)每個(gè)出口箱的陸側(cè)入場(chǎng)時(shí)間、海側(cè)出場(chǎng)時(shí)間均已知。

(4)堆場(chǎng)初始堆存狀態(tài)以及已堆存的出口箱出場(chǎng)時(shí)間已知。

(5)本文考慮相同規(guī)格的集裝箱，以20尺集裝箱為標(biāo)準(zhǔn)，即一個(gè)箱位堆存一個(gè)集裝箱。

(6)本文不涉及冷藏箱、危險(xiǎn)箱等特種箱，僅考慮普通箱的堆存。

2.2 符號(hào)定義

2.2.1 參數(shù)

I為按入場(chǎng)順序排列的出口箱集合，I={1,2,3,…,NI}，通過(guò)i,j索引；

E為出口箱后續(xù)出場(chǎng)時(shí)間集合，E={1,2,3,…,NI}；

A為泊位對(duì)應(yīng)的箱區(qū)集合，A={1,2,3,…,NA}，通過(guò)a索引；

W為泊位對(duì)應(yīng)的箱區(qū)的權(quán)重集合，W={1,2,3,…,NA}；

BT為箱區(qū)內(nèi)中轉(zhuǎn)區(qū)的倍位集合，BT={1,2,3,…,NBT}，通過(guò)bt索引；

BG為箱區(qū)內(nèi)海側(cè)堆存區(qū)域的倍位集合，BG={1,2,3,…,NBG}，通過(guò)bg索引；

R為倍位內(nèi)列的集合，R={1,2,3,…,NR}，通過(guò)r索引；

T為倍位內(nèi)層的集合，T={1,2,3,…,NT}，通過(guò)t,ta,tb索引，其中t代表一個(gè)出口箱，ta,tb代表兩個(gè)不同的出口箱；

TC為堆場(chǎng)中中轉(zhuǎn)區(qū)已堆存的集裝箱集合，TC={1,2,3,…,NTC}，通過(guò)tc索引；

PTCtc,a,bt,r,t=

GC為堆場(chǎng)中海側(cè)堆存區(qū)域已堆存的集裝箱集合，GC={1,2,3,…,NGC}，通過(guò)gc索引；

EC為堆場(chǎng)中海側(cè)堆存區(qū)域已堆存的集裝箱出場(chǎng)時(shí)間集合，EC={1,2,3,…,NGC}；

PGCgc,a,bg,r,t=

2.2.2 過(guò)程變量

ybi,j,a,bg,r,ta,tb=

yci,gc,a,bg,r=

zbi,j,a,bg,r,ta,tb=

zci,gc,a,bg,r=

2.2.3 決策變量

xai,a,bt,r,t=

xbi,a,bg,r,t=

2.3 模型構(gòu)建

minf=f1+f2+f3,

(1)

(2)

(3)

(4)

s.t.

(5)

(6)

(7)

(8)

(9)

(10)

(11)

ybi,j,a,bg,r,ta,tb≥xbi,a,bg,r,ta+xbj,a,bg,r,tb-
1,?i,j,a,bg,r,ta>tb;

(12)

(13)

(14)

(15)

(16)

(17)

(18)

(19)

(20)

模型的目標(biāo)函數(shù)如式(1)所示，表示最小化箱區(qū)負(fù)載不均衡度、中轉(zhuǎn)區(qū)負(fù)載不均衡度和后續(xù)翻箱數(shù)量的總和。式(2)通過(guò)箱區(qū)任務(wù)數(shù)量帶權(quán)重的標(biāo)準(zhǔn)差表示箱區(qū)負(fù)載不均衡度；式(3)通過(guò)各個(gè)箱區(qū)中轉(zhuǎn)區(qū)各列任務(wù)數(shù)量的標(biāo)準(zhǔn)差表示中轉(zhuǎn)區(qū)負(fù)載不均衡度；式(4)表示需要翻箱的集裝箱數(shù)量。目標(biāo)中翻箱率的權(quán)重較高，體現(xiàn)翻箱數(shù)量的重要性。式(5)～式(20)為約束條件，其中式(5)～式(7)表示每個(gè)出口箱對(duì)應(yīng)一個(gè)箱區(qū)、一個(gè)中轉(zhuǎn)區(qū)箱位和一個(gè)目標(biāo)箱位。式(8)～式(9)表示每個(gè)箱位對(duì)應(yīng)一個(gè)集裝箱；式(10)～式(11)表示集裝箱不能懸空堆存；式(12)～式(15)判斷了出口箱之間以及出口箱與已堆存集裝箱是否在同一列；式(16)表示先入場(chǎng)的集裝箱不能擺放在后入場(chǎng)的集裝箱上方；式(17)～(20)判斷了出口箱是否擺放在更早出場(chǎng)的集裝箱上方，即該出口箱是否需要被翻箱。

基于這一問(wèn)題模型可以看出，在本文研究的自動(dòng)化集裝箱堆場(chǎng)出口箱箱位分配問(wèn)題中，在本研究的問(wèn)題假設(shè)下，實(shí)際問(wèn)題具備數(shù)百任務(wù)上千箱位的規(guī)模，且過(guò)程與決策變量包含多個(gè)維度，難以求解。其次由于堆場(chǎng)交互設(shè)備較多并且場(chǎng)橋效率有限，需要引入多元的評(píng)價(jià)方式以平衡各類設(shè)備的影響，最大化整體的作業(yè)效率。最后，基于三維碼放、場(chǎng)橋接力、懸臂吊等特性，問(wèn)題模型具備了較多種類的約束，極大地增加了有效方案的生成難度。因此，研究的問(wèn)題具備多維度評(píng)價(jià)、約束復(fù)雜、規(guī)模極大、決策變量較多等特點(diǎn)，從而導(dǎo)致了較高的求解難度。鑒于此，本文引入新穎且高效的基于強(qiáng)化學(xué)習(xí)思想的超啟發(fā)式算法，以期取得較好的箱位分配方案。

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

由于本文研究的問(wèn)題規(guī)模極大、約束較多，求解十分復(fù)雜，常用的啟發(fā)式規(guī)則、智能優(yōu)化算法難以獲得較滿意的箱位分配方案，需要引入更高效的優(yōu)化算法，提高求解方案的性能。本文開發(fā)了基于強(qiáng)化學(xué)習(xí)思想的超啟發(fā)式算法(Reinforcement Learning based Hyper-Heuristic,RLHH)，能夠充分利用各種不同啟發(fā)式算法的優(yōu)勢(shì)。算法可以分為低層算法和高級(jí)控制策略兩個(gè)層級(jí)。在低層算法中，本文針對(duì)問(wèn)題的特點(diǎn)和可能出現(xiàn)的不同情況引入了多種傳統(tǒng)的和新近開發(fā)的啟發(fā)式算法，盡可能地?cái)U(kuò)大算法適用的場(chǎng)景范圍。在高級(jí)控制策略中，本文采用了更為新穎的基于策略的強(qiáng)化學(xué)習(xí)算法DPPO(distributed proximal policy optimization)，根據(jù)迭代以及場(chǎng)景狀態(tài)智能選取合適的啟發(fā)式算法。在強(qiáng)化學(xué)習(xí)算法中，本文主要使用了用于加速訓(xùn)練測(cè)試過(guò)程的A3C多線程方法以及用于更快收斂策略梯度的自適應(yīng)學(xué)習(xí)率[17,18]。此外，由于深度學(xué)習(xí)能夠提供更大的狀態(tài)空間和更好的性能，本文應(yīng)用這一技術(shù)來(lái)計(jì)算策略梯度。本文采用算法的原理、流程以及重要的模塊如下所述。

3.1 算法原理

自超啟發(fā)式的概念被提出以來(lái)，它已成為了一種用于合成多種算法的高效的技術(shù)。超啟發(fā)式算法是一種特殊的搜索方法，它從一系列預(yù)定義的啟發(fā)式方法中選擇或生成新的啟發(fā)式方法，而不是直接解決問(wèn)題[19]。因此，它可以被視為一種高層的算法，自動(dòng)生成適當(dāng)?shù)膯l(fā)式算法組合，從而有效地解決問(wèn)題[20]。近年來(lái)，有許多研究集中在該領(lǐng)域，并將這一方法應(yīng)用于不同的問(wèn)題，取得了一定的成果[21-24]。

在超啟發(fā)式算法的框架中，一個(gè)關(guān)鍵點(diǎn)是如何高效地在啟發(fā)式方法空間中開展搜索，選擇最恰當(dāng)?shù)膯l(fā)式算法。為解決這一問(wèn)題，人們引入了強(qiáng)化學(xué)習(xí)方法。強(qiáng)化學(xué)習(xí)作為一種強(qiáng)大的決策工具，近些年已引起了廣泛關(guān)注，在許多領(lǐng)域取得了可喜的成就[25-27]。強(qiáng)化學(xué)習(xí)方法能夠在給定情況下智能選擇接下來(lái)應(yīng)采取的行動(dòng)，并通過(guò)與環(huán)境的交互來(lái)獲得最大的回報(bào)。在超啟發(fā)式算法框架中，這一方法能夠滿足高層控制決策的需求，形成更好的算法[28-30]。但是，當(dāng)前絕大多數(shù)應(yīng)用還僅限于基于價(jià)值的強(qiáng)化學(xué)習(xí)，而幾乎沒(méi)有基于策略的強(qiáng)化學(xué)習(xí)方法。由于基于價(jià)值的強(qiáng)化學(xué)習(xí)可能具有對(duì)問(wèn)題的描述能力有限和難以適應(yīng)隨機(jī)策略的缺點(diǎn)，并且在啟發(fā)式算法空間中對(duì)這兩個(gè)方面的要求較高，本文使用基于策略的強(qiáng)化學(xué)習(xí)方法來(lái)進(jìn)一步提高性能。

3.2 算法流程

在RLHH算法中，算法首先對(duì)當(dāng)前問(wèn)題的輸入進(jìn)行處理，得到當(dāng)前問(wèn)題矩陣化的表征。其次，算法初始化了不同的啟發(fā)式算法以及相應(yīng)的種群。然后，算法根據(jù)得到的種群以及當(dāng)前問(wèn)題的特點(diǎn)對(duì)強(qiáng)化學(xué)習(xí)的狀態(tài)參數(shù)進(jìn)行計(jì)算，并應(yīng)用DPPO算法得到當(dāng)前的策略梯度，從而確定下一步采取的啟發(fā)式算法。之后，算法應(yīng)用選定的啟發(fā)式算法開展迭代，不斷優(yōu)化問(wèn)題的解決方案，并生成優(yōu)化后的種群。最后，不斷重復(fù)上述兩步，直到滿足終止條件。整個(gè)算法的偽代碼如算法1所示。

算法 1RLHH()。

輸入:堆場(chǎng)中已有的集裝箱及其出場(chǎng)時(shí)間yard，時(shí)間窗口內(nèi)的出口箱任務(wù)task;

輸出:算法模型或箱位分配方案。

begin

1: 初始化更新前后的演員網(wǎng)絡(luò)actornew(),a_para, actorold(),a_paraold; 初始化評(píng)論家網(wǎng)絡(luò)c_para

2: 初始化不同的啟發(fā)式算法 LLH[i],i=1, 2,…, m

3: 初始化算法參數(shù)，包括最大回合數(shù)episodemax，回合中的最大步數(shù)dmmax，批尺寸batchmin

4: if當(dāng)前過(guò)程是訓(xùn)練過(guò)程then

5: 初始化中心線程tc, 初始化多個(gè)工人線程twi,i=1, 2…wn和線程同步變量mutex

6: 狀態(tài)、動(dòng)作和匯報(bào)緩存sb,ab,rb← empty

7: fornum← 1 toepisodemaxdo

8: fork← 1 towndo

9: //下面是工人線程twk流程

10: 隨機(jī)生成新的問(wèn)題status,outbound,toutandtin←yard,task

11: 群體x[i]← Rand (),i=1, 2,…,P,P為群體中個(gè)體數(shù)量

12: 個(gè)體最優(yōu)值ibest[i]←x[i],i=1, 2,…,P

13: 狀態(tài)s←x的評(píng)分和個(gè)體差異

14: fori← 1 todmmaxdo

15: 策略梯度w← actornew(s)

16:a,snew,r← ApplyAction(w,I, LLH)

17:s←snew

18:sb←sb+s

19:ab←ab+a

20:rb←rb+r

21:tmax← length ofrb

22: iftmax>batchminthen

23: //下面是中心線程tc流程

24:mutex,a_para,a_paraold,c_para← TrainNetwork(mutex,a_para,a_paraold,c_para)

25: end

26: end

27: end

28: 算法模型←a_para,c_para

29: return算法模型

30:else

31: 問(wèn)題環(huán)境status,outbound,toutandtin←yard,task

32: 群體x[i]← Rand (),i=1, 2,…,P

33: 個(gè)體最優(yōu)值ibest[i]←x[i],i=1, 2,…,P

34: 狀態(tài)s←x的評(píng)分和個(gè)體差異

35: fori← 1 todmmaxdo

36: 策略梯度w← actornew(s)

37:a,snew,r← ApplyAction(w,I, LLH)

38:s←snew

39: end

40: 最佳個(gè)體編號(hào)best← 評(píng)分最高的x的編號(hào)

41: 箱位分配方案 ←x[best]

42: return箱位分配方案

end

3.3 超啟發(fā)式算法設(shè)計(jì)

為了進(jìn)一步提高算法的求解性能，本文設(shè)計(jì)了一種新穎的超啟發(fā)式算法。算法中主要包含了問(wèn)題映射、低層啟發(fā)式算法以及高層強(qiáng)化學(xué)習(xí)控制策略3個(gè)關(guān)鍵部分。問(wèn)題映射主要解決低層啟發(fā)式算法與高層強(qiáng)化學(xué)習(xí)算法之間的環(huán)境定義與計(jì)算以及本文解決的箱位分配問(wèn)題與啟發(fā)式算法之間的編碼與解碼流程；低層啟發(fā)式算法主要包含用于求解箱位分配問(wèn)題的多種局部搜索算子、全局搜索算子以及智能算法，形成備選的啟發(fā)式算法庫(kù)；高層控制策略主要包含針對(duì)問(wèn)題特點(diǎn)設(shè)計(jì)的強(qiáng)化學(xué)習(xí)方法，算法具體內(nèi)容將在3.4節(jié)中詳細(xì)闡述。

3.3.1 問(wèn)題映射

在RLHH算法中，主要包含3個(gè)層面的內(nèi)容：高層強(qiáng)化學(xué)習(xí)決策算法、低層啟發(fā)式算法以及出口箱箱位分配問(wèn)題。其中，前兩個(gè)內(nèi)容主要依靠強(qiáng)化學(xué)習(xí)的環(huán)境作為橋梁。由于高級(jí)策略只能從環(huán)境中學(xué)習(xí)問(wèn)題及其變化歷史，這一環(huán)境應(yīng)當(dāng)包含低層算法的所有特征。由于強(qiáng)化學(xué)習(xí)算法將從選擇的啟發(fā)式算法的迭代過(guò)程中學(xué)習(xí)，特征是啟發(fā)式算法的種群及其得分。另外，為了更方便地調(diào)用特定的低級(jí)啟發(fā)式方法，環(huán)境中還包括了種群中每個(gè)個(gè)體的最佳歷史記錄及其分?jǐn)?shù)。

另一方面，后兩個(gè)內(nèi)容之間需要依靠特定的編碼和解碼方式來(lái)連接。在RLHH中，采用了箱位坐標(biāo)的方式進(jìn)行直接編碼，即每一個(gè)出口箱任務(wù)具有箱區(qū)、中轉(zhuǎn)箱位和目標(biāo)箱位3個(gè)數(shù)值。其中具體箱位采用層次編碼形式，即按倍位、排的順序依次給每個(gè)箱位一個(gè)數(shù)值，并將出口箱將放在這一排的最上方，如圖5所示。例如(2,62,125)為一個(gè)出口箱的箱位分配結(jié)果，包含3個(gè)數(shù)字，其中第一個(gè)出口箱的箱位分配結(jié)果，這一出口箱分配給第2箱區(qū)，中轉(zhuǎn)箱位為第7倍位、第2排，目標(biāo)箱位為第13倍位、第5排。

3.3.2 低層啟發(fā)式算法

針對(duì)上述編碼方式，算法將在解碼流程中通過(guò)模擬的方式計(jì)算出每個(gè)出口箱的具體位置，之后計(jì)算目標(biāo)函數(shù)。由于編碼沒(méi)有限制目標(biāo)箱位的可行性，在啟發(fā)式算法中需要引入個(gè)體修復(fù)策略滿足問(wèn)題需求。同時(shí)，為了提高算法運(yùn)行性能，個(gè)體修復(fù)策略將會(huì)在個(gè)體解碼的流程中開展應(yīng)用。在模擬過(guò)程中，當(dāng)某一出口箱的目標(biāo)箱位所在排已經(jīng)堆存了6個(gè)集裝箱，即沒(méi)有多余空間堆存當(dāng)前出口箱時(shí)，算法將自動(dòng)就近選取空閑的箱位并將其分配給該出口箱，同時(shí)對(duì)這一個(gè)體進(jìn)行修改，防止后續(xù)迭代過(guò)程中再次計(jì)算，減小計(jì)算量并提高種群中個(gè)體的質(zhì)量。

為了提高RLHH算法的性能，算法中采用了局部和全局搜索算子以及智能算法組成低層啟發(fā)式算法庫(kù)。其中，任務(wù)不平衡性僅取決于出口箱的碼放區(qū)域，但翻箱率指標(biāo)取決于堆存現(xiàn)狀以及出口箱具體的碼放方案。為此，在算法中引入了不同的局部搜索算子，修改一個(gè)或數(shù)個(gè)出口箱的碼放位置，在不大幅改變?nèi)蝿?wù)不平衡性的基礎(chǔ)上盡可能獲得更小的翻箱率。基于全局優(yōu)化的考慮，引入不同的全局搜索算子修改一部分出口箱的碼放位置，從而跳出局部最優(yōu)方案。最后，引入研究中常用的且性能已獲得實(shí)際驗(yàn)證的智能算法，進(jìn)一步提高算法性能。算法中使用的啟發(fā)式算法及其簡(jiǎn)要描述如表1所示。

表1 低層啟發(fā)式算法

3.4 強(qiáng)化學(xué)習(xí)算法設(shè)計(jì)

由于常規(guī)方法難以根據(jù)不同問(wèn)題合理地選擇不同低層啟發(fā)式算法，取得良好的性能，本文引入基于策略的DPPO強(qiáng)化學(xué)習(xí)方法作為高層決策算法，以期得到滿意的算法性能?？紤]到應(yīng)用強(qiáng)化學(xué)習(xí)的一項(xiàng)重要條件是問(wèn)題的決策過(guò)程具備無(wú)后效性，即某階段的狀態(tài)一旦確定，則此后過(guò)程的演變不再受此前各狀態(tài)及決策的影響，本文首先針對(duì)問(wèn)題特點(diǎn)進(jìn)行了分析。針對(duì)高層決策算法這一模塊，考慮的是如何合理應(yīng)用不同的低層啟發(fā)式算法來(lái)改進(jìn)當(dāng)前箱位分配問(wèn)題的解。一方面，在低層啟發(fā)式算法改進(jìn)的過(guò)程中，基于搜索算子和智能算法的定義，算法僅考慮當(dāng)前求解方案的編碼以及對(duì)應(yīng)的評(píng)價(jià)指標(biāo)，采用不同策略修改編碼并提升指標(biāo)，而與求解方案的歷史變化無(wú)關(guān)。另一方面，在選擇合適的低層啟發(fā)式算法時(shí)，考慮到上述改進(jìn)措施的特點(diǎn)，相關(guān)歷史信息不會(huì)對(duì)算法的迭代造成影響，因此算法也僅需考慮當(dāng)前種群中各個(gè)求解方案的編碼以及指標(biāo)，從而滿足決策過(guò)程的無(wú)后效性。在滿足應(yīng)用強(qiáng)化學(xué)習(xí)條件的基礎(chǔ)上，本文針對(duì)問(wèn)題以及低層啟發(fā)式算法的特點(diǎn)有針對(duì)性開發(fā)了狀態(tài)、動(dòng)作、回報(bào)、神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)和訓(xùn)練策略等模塊。

3.4.1 狀態(tài)

在算法迭代過(guò)程中，啟發(fā)式算法對(duì)種群進(jìn)行更新后，強(qiáng)化學(xué)習(xí)策略都會(huì)計(jì)算環(huán)境狀態(tài)，指導(dǎo)下一步的迭代。由于在不同的種群狀態(tài)即質(zhì)量與分散程度下不同的啟發(fā)式算法存在性能差異，算法采用了個(gè)體得分和個(gè)體差異性作為狀態(tài)內(nèi)容，即s= {f，d}。其中：f是歸一化的種群中每個(gè)個(gè)體的得分，即當(dāng)前箱位分配方案的目標(biāo)函數(shù)值，其大小為1×n，且n為個(gè)體數(shù)量；d表示所有個(gè)體之間的差異，為一個(gè)n×n的矩陣，且每個(gè)數(shù)字dij由式(21)得到，表示種群中indi和indj之間的差異性。

(21)

3.4.2 動(dòng)作

在強(qiáng)化學(xué)習(xí)的學(xué)習(xí)和運(yùn)行過(guò)程中，需要在每個(gè)決策時(shí)刻選擇下一步迭代的啟發(fā)式算法。因此，本文中強(qiáng)化學(xué)習(xí)算法的動(dòng)作為特定的啟發(fā)式算法，以a= {0，1，2，…，m}表示，其中m為啟發(fā)式方法的數(shù)量。此外，本文采用ε-貪婪的方法來(lái)平衡動(dòng)作選取的探索和利用，在不同情況下選擇正確的行動(dòng)。在每個(gè)決策時(shí)刻，算法會(huì)根據(jù)之前計(jì)算得到的不同動(dòng)作的策略梯度進(jìn)行動(dòng)作選擇。算法會(huì)生成一個(gè)隨機(jī)數(shù)，若該數(shù)字大于固定概率ε(0≤ε≤1)，則將貪婪地選擇動(dòng)作，即選擇策略梯度最大的那個(gè)動(dòng)作;否則，算法將隨機(jī)選擇動(dòng)作。其中該參數(shù)采用研究中常用的0.8，平衡貪婪與隨機(jī)選擇之間的比例。選擇了下一步的動(dòng)作后，選定的啟發(fā)式算法將更新種群，并連續(xù)運(yùn)行幾代，以消除隨機(jī)誤差。另外，為了更高效地運(yùn)行啟發(fā)式方法，算法保留了每個(gè)個(gè)體各次迭代中的最優(yōu)值，記為ibest。最后，算法將計(jì)算新的狀態(tài)和獎(jiǎng)勵(lì)用于后續(xù)迭代與網(wǎng)絡(luò)訓(xùn)練。動(dòng)作選擇和應(yīng)用的偽代碼如算法2所示。

算法 2ApplyAction()。

輸入:策略梯度w，當(dāng)前決策時(shí)刻序號(hào)i以及低層啟發(fā)式算法LLH;

輸出:動(dòng)作a、新的狀態(tài)snew和回報(bào)r。

begin

1:temp← Rand (range =[0,1])

2: iftemp> 0.8 then

3: a←Randint (range =[0, m -1], weight =w)

4: else

5:a← Randint (range =[0, m -1])

6: 選擇的啟發(fā)式算法MH← LLH[a]，并初始化運(yùn)行代數(shù)genmax

7: 新的種群xnew←x

8: 新的個(gè)體最優(yōu)值ibestnew←ibest

9: forj← 0 togenmaxdo

10:xnew,ibestnew←MH(xnew,ibestnew)

11:end

12:x←xnew

13:ibest←ibestnew

14:snew←xnew的評(píng)分和個(gè)體差異性

15:ifi

16:r← 0

17:else

18:r← 整個(gè)過(guò)程中的評(píng)分提升

19:returna,snewandr

end

3.4.3 回報(bào)

回報(bào)定義了強(qiáng)化學(xué)習(xí)策略的目標(biāo)，并根據(jù)狀態(tài)變化提供了選取動(dòng)作的即時(shí)和后續(xù)效果。在此過(guò)程中，強(qiáng)化學(xué)習(xí)算法選擇動(dòng)作以最大化總回報(bào)，并嘗試在回報(bào)的指導(dǎo)下達(dá)到最終目標(biāo)。在本文研究的問(wèn)題中，總體目標(biāo)是找出最優(yōu)的箱位分配方案，最小化任務(wù)的不平衡性以及后續(xù)的翻箱率。因此，這一評(píng)價(jià)指標(biāo)將隨著算法迭代而持續(xù)下降，直到最終獲得較好的分配方案。在算法中，為了更好地表征策略的好壞，回報(bào)被定義為最終狀態(tài)與初始狀態(tài)之間的評(píng)價(jià)方案的差值，并在最后給予算法。

3.4.4 訓(xùn)練方式

RLHH算法引入基于策略的演員—評(píng)論家框架，以提取狀態(tài)中的隱藏模式,因此算法是一種在線學(xué)習(xí)(on-policy)方法。由于傳統(tǒng)的演員—評(píng)論家框架需要較長(zhǎng)時(shí)間進(jìn)行訓(xùn)練，近年來(lái)人們引入了A3C方法[31]。A3C方法是一種新穎的強(qiáng)化學(xué)習(xí)訓(xùn)練方式，可以充分利用多線程來(lái)加速訓(xùn)練過(guò)程，以滿足實(shí)際問(wèn)題的需要。在提出的算法中，系統(tǒng)包括一個(gè)中心線程和多個(gè)工人線程。中心線程負(fù)責(zé)更新和訓(xùn)練網(wǎng)絡(luò)，并為工人線程提供網(wǎng)絡(luò)參數(shù)；工人線程使用來(lái)自中心線程的網(wǎng)絡(luò)參數(shù)并且并行運(yùn)行算法，以收集不同情況下的狀態(tài)、動(dòng)作和獎(jiǎng)勵(lì)。這一并行訓(xùn)練過(guò)程可以大大加快訓(xùn)練過(guò)程，并顯著減少運(yùn)行時(shí)間。

在工人線程收集了足夠的訓(xùn)練數(shù)據(jù)之后，算法將對(duì)神經(jīng)網(wǎng)絡(luò)進(jìn)行訓(xùn)練，并從所有工人線程的經(jīng)驗(yàn)即每個(gè)決策時(shí)刻的狀態(tài)，行動(dòng)和獎(jiǎng)勵(lì)中學(xué)習(xí)。訓(xùn)練過(guò)程在中心線程運(yùn)行，第一步是使用稱為事件的線程同步方法掛起所有工人線程。然后，中心線程使用所有收集的數(shù)據(jù)來(lái)訓(xùn)練演員和評(píng)論家網(wǎng)絡(luò)。對(duì)于演員網(wǎng)絡(luò)，算法采用式(22)所示的目標(biāo)進(jìn)行更新[18]。

(22)

式中：rt(θ)為新策略與舊策略的比值，可以使用新的策略梯度網(wǎng)絡(luò)和舊的策略梯度網(wǎng)絡(luò)進(jìn)行計(jì)算；At為預(yù)測(cè)的差異，從收集的數(shù)據(jù)中獲得的回報(bào)與評(píng)論家網(wǎng)絡(luò)計(jì)算出的相應(yīng)狀態(tài)的價(jià)值之間的差異得到。對(duì)于評(píng)論家網(wǎng)絡(luò)，訓(xùn)練過(guò)程相對(duì)容易。這一網(wǎng)絡(luò)的損失是上述預(yù)測(cè)的差異，可以表現(xiàn)狀態(tài)值的預(yù)測(cè)性能。最后，在演員和評(píng)論家網(wǎng)絡(luò)都完成訓(xùn)練之后，中心線程使用事件告訴所有工人線程可以使用新的網(wǎng)絡(luò)參數(shù)來(lái)繼續(xù)收集數(shù)據(jù)。訓(xùn)練過(guò)程的偽代碼如算法3所示。

算法 3TrainNetwork()。

輸入:事件mutex，網(wǎng)絡(luò)參數(shù)a_para,a_paraold,c_para;

輸出:事件mutex，更新的網(wǎng)絡(luò)參數(shù)a_para,a_paraold,c_para。

begin

1:mutex← 等待狀態(tài)

2:a_paraold←a_para

3:tmax←rb的長(zhǎng)度

4: 狀態(tài)的價(jià)值vs← critic (sb)

4: forj←1 totmaxdo

5:s←sb[j],a←ab[j],r←rb[j],v←vs[j]

6: 預(yù)測(cè)差異adv←r-v

7: 新的策略梯度newp← actornew(a)

8: 舊的策略梯度oldp← actorold(a)

9:ratio←newp/oldp

10: 演員網(wǎng)絡(luò)的損失aloss由式(22)計(jì)算得到

11: 訓(xùn)練演員網(wǎng)絡(luò)并更新a_para

12: 評(píng)論家網(wǎng)絡(luò)的損失closs←adv

13: 訓(xùn)練評(píng)論家網(wǎng)絡(luò)并更新c_para

14:end

15:sb,ab,rb← empty

16:mutex← 就緒狀態(tài)

17:returnmutex,a_para,a_paraold,c_para

end

3.4.5 神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)

在演員—評(píng)論家框架中，演員網(wǎng)絡(luò)在每個(gè)決策時(shí)刻計(jì)算策略梯度，而評(píng)論家網(wǎng)絡(luò)預(yù)測(cè)狀態(tài)的價(jià)值以教導(dǎo)演員網(wǎng)絡(luò)從而得到更好的策略梯度。兩個(gè)網(wǎng)絡(luò)共享相同的狀態(tài)輸入，即種群的質(zhì)量與分散程度。但兩個(gè)網(wǎng)絡(luò)具備不同的輸出，其中演員網(wǎng)絡(luò)輸出計(jì)算動(dòng)作需要的策略梯度，而評(píng)論家網(wǎng)絡(luò)輸出狀態(tài)的價(jià)值，用于指導(dǎo)演員網(wǎng)絡(luò)的迭代。因此，本文采用相似的神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)來(lái)搭建演員和評(píng)論家網(wǎng)絡(luò)。輸入的狀態(tài)首先會(huì)分為個(gè)體分?jǐn)?shù)和個(gè)體差異兩部分。然后，這兩部分分別經(jīng)過(guò)兩次卷積層和池化層以提取其中的隱藏信息，定義當(dāng)前種群的特點(diǎn)。之后，網(wǎng)絡(luò)將結(jié)果合并為完整的數(shù)據(jù)并通過(guò)全連接層將所有信息匯總在一起，形成狀態(tài)的分類。最后，網(wǎng)絡(luò)使用歸一化技術(shù)并輸出。

4 實(shí)例驗(yàn)證

為了驗(yàn)證所提RLHH算法的有效性及其性能，本文基于洋山四期自動(dòng)化集裝箱堆場(chǎng)的實(shí)際場(chǎng)景設(shè)計(jì)了一系列不同規(guī)模的問(wèn)題。所有實(shí)驗(yàn)均在TensorFlow 1.4，Python 3.5、16 GB RAM和i7-8 700 CPU的環(huán)境下實(shí)現(xiàn)。同時(shí)，為了讓算法的性能達(dá)到最優(yōu)，本文通過(guò)實(shí)驗(yàn)得到RLHH的超參數(shù)，如表2所示。最后，為了更直觀地獲得所提算法的性能，本文引入不同問(wèn)題中常用的性能較高的一系列智能算法如遺傳算法、模擬退火算法[7,15]等進(jìn)行算法比較。

表2 超參數(shù)選擇

4.1 算例生成

本文算例的數(shù)據(jù)主要根據(jù)以下規(guī)則產(chǎn)生：

(1)問(wèn)題規(guī)模 根據(jù)洋山四期自動(dòng)化集裝箱堆場(chǎng)的布局方案，生成對(duì)應(yīng)一個(gè)泊位的數(shù)個(gè)箱區(qū)的場(chǎng)景。為了兼顧有限的運(yùn)算資源，設(shè)計(jì)了較小規(guī)模的實(shí)驗(yàn)以更好驗(yàn)證算法性能以及根據(jù)堆場(chǎng)軌道吊工作效率以及出口箱任務(wù)數(shù)量生成大規(guī)模的實(shí)際箱位分配問(wèn)題。

(2)箱區(qū)現(xiàn)狀 根據(jù)堆場(chǎng)箱位實(shí)際的利用率，初始時(shí)刻每個(gè)箱區(qū)內(nèi)已存放50%的集裝箱，已堆存集裝箱的箱位隨機(jī)產(chǎn)生。

(3)出口箱入場(chǎng)順序 由于外集卡的到達(dá)時(shí)間隨外圍交通、外集卡自身時(shí)間安排決定，不存在必須遵守的約束，因此每個(gè)出口箱的入場(chǎng)順序隨機(jī)產(chǎn)生。

(4)作業(yè)順序 根據(jù)船公司提供的船舶預(yù)配載圖以及預(yù)先決定的橋吊作業(yè)順序和船舶積載方案，預(yù)先制定海側(cè)軌道吊的作業(yè)順序，即各集裝箱的海側(cè)出場(chǎng)作業(yè)順序。

4.2 算法結(jié)果分析

由于本文提出的RLHH算法中采用強(qiáng)化學(xué)習(xí)方法作為高層策略，需要前期的訓(xùn)練過(guò)程以最大化算法性能。在此過(guò)程中，本文引入了多線程并行方式以加速訓(xùn)練過(guò)程。在訓(xùn)練過(guò)程中，本文采用上述方法生成的問(wèn)題來(lái)提供訓(xùn)練算例，并基于問(wèn)題的復(fù)雜程度設(shè)置了對(duì)應(yīng)的訓(xùn)練數(shù)據(jù)集。訓(xùn)練數(shù)據(jù)集包含了隨機(jī)生成的900個(gè)不同規(guī)模的算例，包括300個(gè)3個(gè)箱區(qū)較小倍位數(shù)的小規(guī)模算例、300個(gè)3個(gè)箱區(qū)較大倍位數(shù)的中等規(guī)模算例以及300個(gè)7個(gè)箱區(qū)的大規(guī)模算例。由于每個(gè)算例中均需要強(qiáng)化學(xué)習(xí)算法進(jìn)行數(shù)十次的算法決策，上述訓(xùn)練數(shù)據(jù)集能夠滿足算法的訓(xùn)練要求。在訓(xùn)練過(guò)程結(jié)束后，使用生成的強(qiáng)化學(xué)習(xí)模型開展測(cè)試以驗(yàn)證其性能。為了直觀地體現(xiàn)算法迭代過(guò)程，以3個(gè)箱區(qū)15個(gè)倍位的堆場(chǎng)和60個(gè)出口箱任務(wù)為例，使用所提算法開展研究，算法迭代過(guò)程如圖6所示。

由此可以得到在迭代過(guò)程中，目標(biāo)函數(shù)值不斷下降，并且算法能夠選擇不同的啟發(fā)式算法來(lái)盡可能增加這一下降率。具體來(lái)說(shuō)，在早期，由于種群隨機(jī)產(chǎn)生，算法傾向于選擇局部搜索算子、遺傳算法、人工蜂群算法來(lái)尋找局部最優(yōu)值。之后，在找到局部最優(yōu)值并且最優(yōu)值不變時(shí)，算法改變策略，選擇全局搜索算子或具有強(qiáng)大探索能力的布谷鳥算法。由于找到了新的搜索領(lǐng)域，算法重新選擇局部搜索能力較強(qiáng)的算法來(lái)尋找新的局部最優(yōu)。算法不斷重復(fù)該過(guò)程，直到輸出最終解決方案為止。因此，所提RLHH算法可以在有限的迭代過(guò)程內(nèi)獲得較好的結(jié)果，也證明了其有效性。

4.3 算法比較分析

為了進(jìn)一步研究RLHH算法用于出口箱箱位分配問(wèn)題的有效性和性能，本文建立了一系列箱位分配問(wèn)題算例，并引入其他常見的智能算法如人工蜂群算法( Artificial Bee Colony algorithm，ABC)、布谷鳥算法(Cuckoo Search algorithm，CS)、遺傳算法(Genetic Algorithm,GA)、粒子群優(yōu)化算法(Particle Swarm Optimization，PSO)和模擬退火算法(Simulated Anneal algorithm，SA)以及近期研究中采用的改進(jìn)的遺傳算法(Improved GA,IGA)[11]、改進(jìn)的模擬退火算法(Improved SA,ISA)[15]開展對(duì)比試驗(yàn)，從而比較算法性能并驗(yàn)證本文算法使用的必要性和優(yōu)越性。由于求解問(wèn)題存在差異性，相關(guān)對(duì)比算法在近期研究的參數(shù)選擇基礎(chǔ)上均采用了正交實(shí)驗(yàn)來(lái)獲取最佳的參數(shù)組合，相關(guān)參數(shù)如表3所示。為了更完整地得到算法性能對(duì)比結(jié)果，本文采用控制變量的方法來(lái)設(shè)計(jì)算例。因?yàn)閱?wèn)題規(guī)模由箱區(qū)數(shù)量、倍位數(shù)量以及出口箱任務(wù)數(shù)量決定，所以全部算例也相應(yīng)分為3個(gè)部分。整個(gè)實(shí)驗(yàn)的結(jié)果如表4所示。其中對(duì)于每個(gè)算例，本文控制了每個(gè)算法的計(jì)算時(shí)間，以確保所有算法使用相同的計(jì)算能力，并能用于實(shí)際問(wèn)題，參數(shù)計(jì)算時(shí)間表示了實(shí)驗(yàn)中算法的最大計(jì)算時(shí)間。此外，參數(shù)中名為“X-Y-Z”的算例表示X個(gè)箱區(qū)Y個(gè)倍位的堆場(chǎng)以及Z個(gè)出口箱任務(wù)。

表3 對(duì)比算法配置

表4 算法對(duì)比結(jié)果

續(xù)表4

根據(jù)表4的實(shí)驗(yàn)結(jié)果，可以得出以下結(jié)論。在自動(dòng)化集裝箱碼頭出口箱箱位分配問(wèn)題中，本文提出的RLHH算法能夠在有限的時(shí)間內(nèi)得到較好的可接受的箱位分配方案。算法能夠在全部28個(gè)算例中的27個(gè)獲得最佳的箱位分配方案。而在“3-15-60”算例中，模擬退火算法得到了最佳的箱位分配方案。此外，在全部算例的箱位分配方案的平均結(jié)果中，RLHH算法獲得了最好的算法評(píng)價(jià)，較其他常見的智能算法有18.8%以上的提升，較近期研究中改進(jìn)的智能算法有15.2%的提升。因此可以看出，提出的RLHH算法具備比單一智能算法更好的性能，能夠更好地求解研究的出口箱箱位分配問(wèn)題。

另外，為了更直觀比較提出的RLHH算法與智能算法的算法性能，本文通過(guò)式(23)計(jì)算算法之間的性能差距，

(23)

其中X表示當(dāng)前算法，T(X)表示X算法得到的目標(biāo)函數(shù)的平均值。由于表6中人工蜂群算法在常見智能算法中的表現(xiàn)最好，采用這一算法為性能基準(zhǔn)，即以當(dāng)前算法與人工蜂群算法的性能對(duì)比表現(xiàn)算法之間的性能差距。此外，由于目標(biāo)函數(shù)值越小意味著箱位分配方案越合理，INC值越低意味著算法性能越好。根據(jù)3組算例得到的算法對(duì)比圖如圖7所示。

從圖7的3個(gè)部分算法對(duì)比中可以看出，所提出的算法的INC值在0%～-27%之間，且在大多數(shù)情況下具有最低的INC值。此外，隨著問(wèn)題規(guī)模的增加，RLHH算法的INC值存在下降趨勢(shì)。因此可以得出結(jié)論，RLHH算法具有最佳的性能，并且能在較大規(guī)模的實(shí)際問(wèn)題中取得更好的效果，具備應(yīng)用價(jià)值。

總之，從上述實(shí)驗(yàn)可以得出以下結(jié)論。本文提出的RLHH算法能夠根據(jù)當(dāng)前迭代情況智能選取合適的啟發(fā)式算法進(jìn)行接下來(lái)的迭代，從而得到更好的箱位分配方案。同時(shí)，針對(duì)研究的箱位分配問(wèn)題，提出的算法能夠獲得比常見的智能算法更好的箱位分配方案，在不同情況下的性能提高了15%。并且在較大規(guī)模的實(shí)際問(wèn)題中，所提算法具備更好的效果，提供具備使用價(jià)值的高性能計(jì)劃方案。

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

在自動(dòng)化集裝箱碼頭的出口箱箱位分配問(wèn)題中，由于具有問(wèn)題規(guī)模極大、動(dòng)態(tài)性強(qiáng)、場(chǎng)橋接力、多箱區(qū)協(xié)同等特性，現(xiàn)有研究存在較大的提升空間。為了更好地解決這一問(wèn)題，本文基于滾動(dòng)計(jì)劃的方法，構(gòu)建了一個(gè)以最小化任務(wù)不均衡性和翻箱率為目標(biāo)的出口箱箱位分配問(wèn)題模型。在堆場(chǎng)初始堆存狀態(tài)、出口箱入場(chǎng)和出場(chǎng)順序已知的情況下，提出了一種基于強(qiáng)化學(xué)習(xí)的超啟發(fā)式算法得到箱位分配方案。該方案將強(qiáng)化學(xué)習(xí)和深度學(xué)習(xí)用作高級(jí)選擇策略，將啟發(fā)式算子、智能算法用作低級(jí)啟發(fā)式方法。經(jīng)過(guò)不同規(guī)模的實(shí)驗(yàn)，并與常規(guī)及近期研究采用的智能算法進(jìn)行對(duì)比，證明了本文所提算法能夠有效解決這一箱位分配問(wèn)題，并且在算法表現(xiàn)上優(yōu)于不同的智能算法，從而表明所提算法能夠提供高水平的箱位分配問(wèn)題解決方案。

盡管本文研究解決了這一具有挑戰(zhàn)性的出口箱箱位分配問(wèn)題，但將來(lái)可以嘗試更多的工作來(lái)進(jìn)一步改善算法，以實(shí)現(xiàn)更高的效率和性能。第一個(gè)改進(jìn)方向是在強(qiáng)化學(xué)習(xí)策略中開發(fā)更有效的網(wǎng)絡(luò)結(jié)構(gòu)和框架；另一個(gè)方向是引入更多更有效的低級(jí)啟發(fā)式算法，包括但不限于智能算法、啟發(fā)式算子和混合算法；最后，可以考慮更復(fù)雜的堆場(chǎng)場(chǎng)景和問(wèn)題，從而使所提算法能夠啟時(shí)更多的挑戰(zhàn)。