基于DQN的動態(tài)深度多分支搜索自動配載算法

楊 奔,王煒曄,趙婉婷,謝瑾奎

(華東師范大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,上海 200062)

0 概述

隨著經(jīng)濟(jì)全球化的不斷加深,國際航運(yùn)發(fā)展迅速,集裝箱碼頭朝著自動化、智能化的方向發(fā)展。目前,全球范圍內(nèi)已建成多個自動化碼頭,而一個合理的自動配載算法往往關(guān)系到集裝箱船營運(yùn)的經(jīng)濟(jì)性和安全性以及碼頭的整體工作效率。

洋山港四期工程作為全球規(guī)模最大的自動化碼頭,在提高自動化程度、實(shí)現(xiàn)無人化操作的同時,對船舶的裝卸效率有極高的要求,整個碼頭的裝卸工藝采用雙小車岸橋+自動引導(dǎo)小車(AGV)+自動化軌道吊(ASC)[1]。自動配載是指在船公司給出預(yù)配船圖和堆場箱區(qū)的情況下,根據(jù)橋機(jī)計(jì)劃(Crane Work Plan,CWP)給出的作業(yè)要求將堆場上需要配載的集裝箱在船舶上找一個合適位置的過程,而每個預(yù)配位對應(yīng)數(shù)十個或數(shù)百個滿足配載條件的集裝箱,從滿足配載條件的集裝箱中選擇一個合適的位置進(jìn)行配載是一個研究重點(diǎn)。

自動配載是港口的一個核心問題,是一個NP完全性問題[2-4]。自動配載算法的主流方法包括啟發(fā)式算法[5]、數(shù)學(xué)規(guī)劃模型[6]、遺傳算法[7]和蟻群算法[8]等。文獻(xiàn)[9]研究線性規(guī)劃優(yōu)化算法,通過實(shí)例測試實(shí)驗(yàn),有效提高船舶運(yùn)輸和港口運(yùn)作效率。文獻(xiàn)[10]針對配載種Bay優(yōu)選問題,以倒箱量、重心橫向偏移和初穩(wěn)性高為目標(biāo),提出一種多目標(biāo)離散粒子群算法(MODPSO),為船舶配載提供多種方案以供備選。文獻(xiàn)[11]提出一種集裝箱配載自動化解決方案,該方案的推導(dǎo)是通過組合優(yōu)化原則來完成的,主要是采用禁忌搜索的啟發(fā)式算法來產(chǎn)生一個合理解。文獻(xiàn)[12]提出一種禁忌搜索算法,該算法能夠避免局部最優(yōu)解,并且通過仿真實(shí)驗(yàn)證明了其配載的有效性。文獻(xiàn)[13]利用遺傳算法求得一個優(yōu)化的集裝箱裝船序列,優(yōu)化目標(biāo)是滿足客戶的交貨期限并最小化集裝箱船舶的在港時長。文獻(xiàn)[14]假設(shè)工作順序已知的前提下,設(shè)計(jì)了一個三段式的啟發(fā)式算法,通過該算法能夠明顯縮短橋機(jī)工作時長。文獻(xiàn)[15]建立了一個動態(tài)規(guī)劃模型確定預(yù)配箱位置以及最小化倒箱次數(shù),同時利用決策樹模型來得到實(shí)時決策信息。文獻(xiàn)[16]為簡化配載問題,在不考慮船舶穩(wěn)性以及其他一些限制的情況下以最小化倒箱量為目標(biāo)制定出一個0-1二元線性規(guī)劃模型,并用啟發(fā)式算法來尋找最佳配載方案。通常的集裝箱船舶配載量為2 000箱～3 000箱,主流方法對于這樣大規(guī)模的算例求解效率不高。傳統(tǒng)的算法往往更關(guān)注配載結(jié)果,而忽視了箱區(qū)調(diào)度效率因素,導(dǎo)致裝載時箱區(qū)設(shè)備利用低,使得整個碼頭的效率低下。

箱區(qū)設(shè)備利用率是提高自動化碼頭效率的重要因素,為提高箱區(qū)設(shè)備利用率,本文將配載的過程建模為順序決策問題,通過無標(biāo)簽的歷史數(shù)據(jù),在線下階段通過強(qiáng)化學(xué)習(xí)[17]得到箱區(qū)狀態(tài)值函數(shù),從而對不同的箱區(qū)狀態(tài)給出一個量化的評估。在線上選箱時為了能夠得到更合理的配載結(jié)果,提出一種深度優(yōu)先且動態(tài)深度多分支搜索的配載策略。

1 研究背景及自動配載問題

自動配載是現(xiàn)代化港口的一項(xiàng)重要舉措,關(guān)系到整個碼頭的運(yùn)營效率。洋山港四期自動化碼頭將整個裝船過程分為橋機(jī)工作計(jì)劃(CWP)和自動配載模塊。其中,CWP安排了船舶上每個預(yù)配位的作業(yè)時間,該作業(yè)時間是自動配載的重要數(shù)據(jù)輸入。CWP計(jì)劃中,包含每一個橋機(jī)的工作起始時間、結(jié)束時間、橋機(jī)位置、橋機(jī)作業(yè)順等信息,橋機(jī)計(jì)劃關(guān)聯(lián)了船舶上對應(yīng)位置被作業(yè)的先后順序。因此,本文需要在遵循橋機(jī)作業(yè)的前提下進(jìn)行集裝箱的選取,才能找到符合預(yù)配條件要求的集裝箱。每個預(yù)配位對應(yīng)多個候選集裝箱,而選取集裝箱應(yīng)考慮以下因素:

1)船舶重量穩(wěn)定性和船公司的重量要求。國際集裝箱運(yùn)輸船的航海距離遠(yuǎn),航行時間長,因此對船舶的重量穩(wěn)定性要求很高,配載結(jié)果應(yīng)遵循下重上輕的原則。不同的配載結(jié)果可能導(dǎo)致船舶的重心改變,穩(wěn)定性改變,甚至吃水差發(fā)生變化。

2)箱區(qū)任務(wù)分配。岸橋的作業(yè)效率往往要高于堆場軌道吊的作業(yè)效率,因此要根據(jù)CWP的作業(yè)順序均衡堆場各個箱區(qū)的出箱量。為了最大化碼頭的整體效率,提高箱區(qū)設(shè)備利用率,減少閑置時間和阻塞時長是本文優(yōu)化目標(biāo)。

3)翻箱因素[18]。翻箱率通常會作為評判一個配載結(jié)果好壞的重要指標(biāo),往往一次翻箱會造成更多的二次翻箱,使得堆場箱區(qū)效率低下,合理的配載結(jié)果能有效減少翻箱次數(shù)。

4)雙小車拼車。為了提高裝卸效率,洋山四期軌道吊采用雙箱吊作業(yè)工藝,即岸橋可以一次抓取2個小箱同時裝載作業(yè)。為保證AGV運(yùn)輸?shù)男?雙箱工藝的2個小箱應(yīng)該嚴(yán)格地控制在同一個箱區(qū)發(fā)箱。

1.1 預(yù)處理

在配載時,一艘船一般有上千個集裝箱需要配載,但對于多目標(biāo)約束條件的優(yōu)化問題,算法的時間代價較大。在洋山港四期碼頭的預(yù)配圖信息中,船舶公司給每個預(yù)配位指定了對應(yīng)的集裝箱目的地、尺寸大小、箱型和危險品備注。因此,本文根據(jù)集裝箱的目的地、尺寸、箱型、危險品等信息將其分為不同的屬性組。這樣,對于每一個預(yù)配位,都對應(yīng)地有相應(yīng)的屬性組分類,只需要在對應(yīng)屬性組的候選集裝箱中進(jìn)行選擇,大大減少了解的搜索空間,提高了算法的效率。

為了滿足船舶穩(wěn)定性和重量要求,配載結(jié)果遵循下重上輕、船舶重心不可發(fā)生偏移的原則。本文提出重量等級概念,例如將0 t～5 t、5 t～10 t、10 t～15 t……每5噸的重量差設(shè)為一個等級。根據(jù)預(yù)配船圖和堆場預(yù)配集裝箱的重量分布,將每一個預(yù)配位劃分到相應(yīng)的重量等級。重量等級劃分的思路是根據(jù)重量分布趨勢由重到輕、先下后上、從中間到兩邊的原則遍歷船舶所有的預(yù)配位,在保證屬性組匹配的前提下,為每一個預(yù)配位劃分到一個重量等級。該階段的預(yù)處理為后續(xù)的選取集裝箱提供了極大的便利。

1.2 自動配載問題

自動配載是為了找到預(yù)配位和集裝箱的最佳匹配。通過屬性組分類和重量等級劃分,一方面減少算法的搜索空間,另一方面保證了船舶重量穩(wěn)定性和船公司的要求。通過數(shù)據(jù)預(yù)處理,得到帶有重量等級信息的預(yù)配圖,根據(jù)CWP安排的預(yù)配位作業(yè)順序,可以得到配載作業(yè)列表,在列表中標(biāo)記每個預(yù)配位的作業(yè)時間和預(yù)配的信息,包括船箱位、屬性組、重量等級等。將列表中的信息依據(jù)作業(yè)時間進(jìn)行排序,然后通過屬性組和重量等級逐一地為每個預(yù)配位匹配集裝箱。預(yù)處理階段雖然減少了解的搜索空間,但是還未做到一一匹配,因此需提出一個合理的集裝箱評價函數(shù)。通過評價函數(shù)對每個候選集裝箱進(jìn)行評價,從而匹配到最合適的集裝箱。預(yù)處理階段解決了船舶重量穩(wěn)定性,其余3個因素通過圖1中的線上和線下策略解決。

圖1 自動配載算法框架Fig.1 Framework of automatic loading algorithm

2 離線學(xué)習(xí)階段

配載階段箱區(qū)設(shè)備的利用率是評價配載算法的優(yōu)劣指標(biāo)之一,同時也是最難控制的因素。當(dāng)前配載選擇哪一個箱區(qū)的集裝箱進(jìn)行配載會對后續(xù)一系列作業(yè)任務(wù)造成影響,這個決策有可能造成箱區(qū)阻塞,也有可能造成在后續(xù)任務(wù)中該箱區(qū)一直處于閑置狀態(tài)。若要最大化碼頭的效率,不僅要關(guān)注當(dāng)前的狀況,而且更需要考慮到當(dāng)前決策對未來的影響。因此,本文將配載過程構(gòu)建為馬爾可夫決策過程(MDP),將學(xué)習(xí)得到的評估函數(shù)用于評判箱區(qū)是否適合出箱,即將箱區(qū)的狀態(tài)進(jìn)行量化,從而選擇更好的箱區(qū)中的箱子進(jìn)行配載。

2.1 問題描述

MDP定義:在此階段,本文將箱區(qū)狀態(tài)構(gòu)建為一個agent,雖然會造成多個agent的問題,但由于不存在特殊箱區(qū),這些agent本質(zhì)都是一樣,因此不需要考慮多agent之間的交互問題。同時模型的構(gòu)建對于狀態(tài)轉(zhuǎn)化、行動及獎勵的定義會大大簡化。

狀態(tài):為了使箱區(qū)的效率值最大化,需要充分利用設(shè)備資源,因此最大化堆場的整體效率是本文的目的。本文在狀態(tài)定義方面不僅關(guān)注單獨(dú)的一個箱區(qū),同樣考慮堆場其他箱區(qū)的情況,此外,本文將箱區(qū)的狀態(tài)表示劃分為如下5個階段:

1)ASC從AGV交互區(qū)移動至目標(biāo)集裝箱所在貝位。

2)提取目標(biāo)集裝箱階段。

3)從目標(biāo)集裝箱所在貝位移至交互區(qū)。

4)翻箱(若存在翻箱)。

5)ASC閑置。

其中,第1階段和第3階段操作的預(yù)估平均時間長度都是1 min30 s,目標(biāo)集裝箱的貝位距離交互區(qū)越遠(yuǎn),則這2個階段的時間越久。第2階段預(yù)估執(zhí)行時間長度也是1 min,翻箱階段中同貝位執(zhí)行翻箱操作的時間長度是1 min。由此,任何一個箱區(qū)的狀態(tài)都可以通過一個5維向量來表示該箱區(qū)的狀態(tài)。那么對于一個箱區(qū)集合G={g},任意一個箱區(qū)的狀態(tài)表示如下:

sgi=(gi1,gi2,gi3,gi4,gi5)

(1)

(2)

(3)

其中,i∈[1,2,…,b]代表b個箱區(qū),用來區(qū)分代表不同的箱區(qū),sgi雖然能夠表示gi箱區(qū)的狀態(tài),但是要使整個堆場的效率最大化,同時還需要兼顧除了目標(biāo)箱區(qū)的其他箱區(qū)狀態(tài),故給出統(tǒng)籌其他箱區(qū)的綜合表示:

(4)

其中,k表示目標(biāo)箱區(qū),則可以將目標(biāo)箱區(qū)的狀態(tài)表示為:

(5)

動作:本文中的模型有2種動作類型,第1種是agent選擇出箱,進(jìn)而更改箱區(qū)狀態(tài)的矩陣表示,第2種是agent不選擇出箱,有2種情況下會出現(xiàn)這種情況,一種是因?yàn)檫@個箱區(qū)不合適出箱,另一種是因?yàn)檫@次預(yù)配位需求的箱子在這個箱區(qū)不存在候選箱。

獎勵:獎勵的定義決定了模型優(yōu)化的目標(biāo)。自動配載算法的目的是為了提高碼頭的工作效率,那么如何在最短的時間內(nèi)完成裝船任務(wù)將作為算法優(yōu)化的目標(biāo)。作為箱區(qū)狀態(tài)評估模型,本文希望agent能夠給出一個評判箱區(qū)狀態(tài)優(yōu)劣的優(yōu)勢值,優(yōu)勢值越好,表示這個箱區(qū)在接下來的作業(yè)中越適合出箱。目標(biāo)箱區(qū)進(jìn)行出箱操作和箱區(qū)的狀態(tài)息息相關(guān),若目標(biāo)箱區(qū)還處于上次配載作業(yè)的某一階段,那么本次配載的預(yù)配箱需等待上次作業(yè)結(jié)束,ASC才可以進(jìn)行提箱任務(wù)。若目標(biāo)箱區(qū)處于閑置狀態(tài),上述情況將不存在,可以直接進(jìn)行提箱任務(wù)。本文將延緩時間和配載時間作為獎罰值,延緩時間是指目標(biāo)箱區(qū)在當(dāng)前時間窗口完成上次配載作業(yè)的預(yù)估時間長度,若目標(biāo)箱區(qū)處于閑置狀態(tài),則延緩時間為0。配載時間指目標(biāo)箱區(qū)完成本次配載的時間長度,即階段1～階段3的時間總和,若存在翻箱,則將翻箱時間損耗加入配載時間。對于某次配載,若總共預(yù)估需要T個階段,延緩時間需要T′個階段,其中T′

(6)

其中,σ表示ASC和QC效率的比值,不同的碼頭設(shè)備,效率會有所差別,效率比值越高,獎勵值相對更大,如洋山港四期的比值為2。

2.2 策略評估

基于2.1節(jié)模型的構(gòu)建,該階段模型求解通過歷史預(yù)配數(shù)據(jù)訓(xùn)練得到,這里使用的歷史預(yù)配數(shù)據(jù)是指沒有配載結(jié)果的初始數(shù)據(jù),本文通過文獻(xiàn)[19-20]中的算法框架來求解強(qiáng)化學(xué)習(xí)模型。DQN通過建立2個相同結(jié)構(gòu)的神經(jīng)網(wǎng)絡(luò)來求解,包括當(dāng)前網(wǎng)絡(luò)Q和目標(biāo)網(wǎng)絡(luò)Q′,當(dāng)前網(wǎng)絡(luò)用來評判箱區(qū)狀態(tài)優(yōu)劣,實(shí)時更新模型參數(shù),目標(biāo)網(wǎng)絡(luò)Q′的參數(shù)不需要迭代更新,而是每隔一定輪數(shù)從Q網(wǎng)絡(luò)中復(fù)制過來,即延時更新,這樣減少了目標(biāo)Q′和當(dāng)前Q的相關(guān)性,同時可以得到損失函數(shù)。算法中通過建立經(jīng)驗(yàn)池機(jī)制,將 (S,S′,R)三元組存入經(jīng)驗(yàn)池。由于模型是針對于箱區(qū)狀態(tài)進(jìn)行評估,如圖2所示,將箱區(qū)狀態(tài)序列作為輸入,評估值作為神經(jīng)網(wǎng)絡(luò)的輸出。因此,經(jīng)驗(yàn)池中沒有動作因素,agent在進(jìn)行箱區(qū)選擇時,都要根據(jù)之前的任務(wù)來更新每個箱區(qū)的狀態(tài)矩陣,得到當(dāng)前時間窗口的狀態(tài)矩陣。

圖2 模型結(jié)構(gòu)Fig.2 Model structure

目標(biāo)神經(jīng)網(wǎng)絡(luò)Q′的狀態(tài)價值函數(shù)如下:

V′=R+γmaxQ′(S′)

(7)

損失函數(shù)定義如下:

(8)

算法1基于DQN的箱區(qū)狀態(tài)值評估算法

輸出箱區(qū)狀態(tài)值函數(shù)v(s)

1.初始化神經(jīng)網(wǎng)路Q并隨機(jī)化參數(shù)θ,初始化神經(jīng)網(wǎng)路Q′和隨機(jī)化參數(shù)θ′=θ;建立經(jīng)驗(yàn)池D。

2.For episode = 1,M do

4.For t = 1,T do

5.根據(jù)ε-貪婪策略,從箱區(qū)狀態(tài)集合中通過Q(S)選擇合適的箱區(qū)發(fā)箱;

10.使用均方誤差(V′-Q(S))2做梯度下降更新網(wǎng)絡(luò)參數(shù)θ;

11.每隔α步更新θ′=θ;

12.End for

13.End for

3 線上規(guī)劃階段

線下通過大規(guī)模的原始數(shù)據(jù)訓(xùn)練得到了箱區(qū)狀態(tài)評估函數(shù),那么在線上配載時,通過箱區(qū)評估函數(shù)給出的評估值再結(jié)合候選集裝箱的實(shí)際位置情況進(jìn)行一個統(tǒng)一的評價,從而得到一個合理的配載方案。

3.1 翻箱與雙小車拼車

洋山港四期的堆場由多個并排的箱區(qū)組成,在箱區(qū)中,豎直堆放的一列成為排,排列在一起的多個排組成一個貝,從底部到頂部又分為若干個層。每一個集裝箱都會放在其中具體的一個位置上,而其對應(yīng)的箱區(qū)號、貝位號、排號、層號標(biāo)記了該集裝箱在堆場中唯一的位置,這也是配載過程中判斷集裝箱具體位置的重要依據(jù)。在配載中,倒箱是影響配載效率的重要因素之一。倒箱是指在集裝箱提取過程中,當(dāng)目標(biāo)集裝箱所在位置上方有其他阻礙箱壓在上面時,只能將阻礙箱移動到其他位置后才能取到目標(biāo)集裝箱,移開阻礙箱的過程叫倒箱。

目前雙箱吊具已普遍應(yīng)用于現(xiàn)代化港口,如圖3所示,針對20英尺的小箱,岸橋可以通過一次性抓取兩個同時進(jìn)行裝載。所以,針對雙箱作業(yè)工藝,每次AGV從堆場提取集裝箱時,應(yīng)嚴(yán)格控制從一個箱區(qū)發(fā)箱,若將雙箱工藝的作業(yè)安排到兩個箱區(qū)進(jìn)行發(fā)箱,AGV需要前往不同的箱區(qū)提取集裝箱,這樣嚴(yán)重降低了裝卸效率。

圖3 20英尺小箱和40英尺大箱Fig.3 Twenty foot small box and forty foot large box

3.2 集裝箱評價函數(shù)

在線上配載具體某一個預(yù)配位時,對于所有的候選集裝箱,需要指定一個合理評價策略,整個決策過程根據(jù)評價策略的指標(biāo)來進(jìn)行,每一個預(yù)配位的決策過程都希望選到最優(yōu)解或者次優(yōu)解,進(jìn)而獲得整體的優(yōu)解。因此,評價函數(shù)的制定對預(yù)配位選擇的結(jié)果起到?jīng)Q定性的作用。

雖然線下通過大規(guī)模原始數(shù)據(jù)訓(xùn)練得到了箱區(qū)狀態(tài)評價函數(shù),在線上配載時,V(S)最有優(yōu)勢值的箱區(qū)并不一定可以選到最優(yōu)的箱子,如在眾多箱區(qū)中,此次配載1號箱區(qū)的優(yōu)勢值最高,但是該箱區(qū)的預(yù)配集裝箱都需要翻箱才能夠得到,因此這并不是一個較好的策略,同時還需要控制雙箱工藝作業(yè)同一個箱區(qū)發(fā)箱。

綜合考慮翻箱和雙箱工藝的線上集裝箱配載評價函數(shù)如式(10)所示:

f(c)=θΔhc(V(Sc)+δ),0<θ<1

(9)

算法2動態(tài)深度多分支搜索算法

輸出每個船舶預(yù)配位對應(yīng)的堆場集裝箱信息

2.Fort = 1,T do

3.Find C′ from C//根據(jù)重量等級和屬性組約束

4.For c∈C′ do

5.f(c)=θΔhc(V(Sc)+δ),0<θ<1

6.End for

7.根據(jù)評價函數(shù)選擇最好的前W個集裝箱作為候選箱;

8.根據(jù)船舶預(yù)配位來搜索當(dāng)前預(yù)配位后面的(D-1)個預(yù)配位;

9.假設(shè)將當(dāng)前評價最好的前W個集裝箱中的每個集裝箱作為目標(biāo)集裝箱,分別求這(D-1)個預(yù)配位最合適的一個集裝箱;

10.根據(jù)加權(quán)每條分支的結(jié)果來為當(dāng)前預(yù)配位選擇最佳的一個集裝箱;

12.End for

動態(tài)深度多分支搜索算法示意圖如圖4所示,算法中的搜索寬度W和深度D作為可調(diào)節(jié)的輸入?yún)?shù),通過設(shè)置不同的參數(shù)可以使算法適用于不同規(guī)模的配載問題,也能夠使算法的計(jì)算時間在可控的范圍內(nèi)結(jié)束。此外,算法深度D在同一次配載過程中是會出現(xiàn)動態(tài)調(diào)整的,因?yàn)槊恳粋€預(yù)配位的后續(xù)不一定有(D-1)個未配載預(yù)配位(如配載結(jié)束的預(yù)配位),或者后續(xù)預(yù)配位中可能會遇到?jīng)]有符合條件候選箱的情況,這時需要將當(dāng)前預(yù)配位的搜索深度調(diào)整為可計(jì)算的深度。

圖4 動態(tài)深度多分支搜索算法示意圖Fig.4 Schematic diagram of dynamic deep multi-branch search algorithm

4 實(shí)驗(yàn)結(jié)果與分析

本文通過洋山港四期真實(shí)船舶數(shù)據(jù)來驗(yàn)證算法的有效性。在離線訓(xùn)練階段,本文通過2019年1月至3月的洋山港四期的歷史船舶配載數(shù)據(jù)來訓(xùn)練,其中包括100箱～400箱的沿海駁船和1 000箱～3 000箱的集裝箱船。通過這些大規(guī)模的數(shù)據(jù)訓(xùn)練,得到最終的V(S)函數(shù)。堆場集裝箱的進(jìn)箱結(jié)果對配載結(jié)果也會有部分影響,本文堆場集裝箱的進(jìn)箱是通過DMDP算法[21]生成,集裝箱均勻分布在不同箱區(qū)。

4.1 自動配載指標(biāo)分析

自動配載算法的有效性除了碼頭工人的判斷外,一般通過以下幾個指標(biāo)來判斷配載方案的優(yōu)劣,即線上算法的計(jì)算時間、翻箱率、箱區(qū)設(shè)備利用率、雙小箱拼車率。

本文通過一艘積載量為1 572箱量的集裝箱船來測試分析動態(tài)深度多分支策略的寬度和深度參數(shù),如表1所示,通過設(shè)置不同的搜索寬度W和深度D,分析算法的計(jì)算時間、翻箱率和拼車率。隨著寬度和深度的增加,算法的執(zhí)行時間明顯增加,但是對應(yīng)的翻箱率和拼車率都有相應(yīng)的下降,尤其是在寬度為5、深度為10時可以得到一個較好的結(jié)果。雖然之后隨著深度和寬度的增加,翻箱和拼車的指標(biāo)略有下降,但是算法的執(zhí)行時間卻相對增加。為方便分析,本文后面的測試對比分析均采用寬度為5、深度為10的參數(shù)設(shè)置。

為測試分析不同規(guī)模船舶的效果,本文通過4組不同規(guī)模的數(shù)據(jù)進(jìn)行測試,如表2所示,這4個航次對應(yīng)的積載箱量分別是389個、1 239個、1 980個、2 750個。其中,航次1為沿海駁船,積載量相對較少,算法翻箱率指標(biāo)可以控制在12%以下。堆場上箱子的堆放會影響翻箱數(shù)目,在做堆場計(jì)劃時,往往并不知道配載船舶的信息和后期的積載需求,堆場進(jìn)口的箱子只能根據(jù)其重量、大小等因素的不同分配指定到合理的箱區(qū)中,所以部分翻箱仍然難免。在拼車率的指標(biāo)上,可以直觀地看到本文算法可以控制在20%左右。造成拼車的原因主要有2個方面:1)由于翻箱約束導(dǎo)致,候選的集裝箱為了避免翻箱不得不去其他箱區(qū)拼車;2)堆場計(jì)劃影響導(dǎo)致,部分箱區(qū)中候選的20英尺小箱數(shù)目是奇數(shù),往往導(dǎo)致最后一個小箱不得不與其他箱區(qū)的小箱拼車,所以,部分拼車情況是不可避免的。

表3展示了航次2的箱區(qū)作業(yè)統(tǒng)計(jì)結(jié)果。箱區(qū)的工作方式與數(shù)據(jù)結(jié)構(gòu)中的隊(duì)列相似,每次需要把舊的任務(wù)處理后才能開始下一次的任務(wù)。如果把每個箱區(qū)看作是一個隊(duì)列,當(dāng)目標(biāo)箱區(qū)每添加一個新的任務(wù)時,查看當(dāng)前箱區(qū)隊(duì)列是否為空,若為空則代表本次作業(yè)的阻塞時長是0,若隊(duì)列不為空則統(tǒng)計(jì)隊(duì)列中待做任務(wù)的工作時長。最后將每次作業(yè)的阻塞時長累加得到阻塞總時長。航次2總共的裝箱量是1 239個,這些箱子分布在堆場的10個箱區(qū)。表3中的總作業(yè)時長代表這個箱區(qū)整個作業(yè)過程的模擬預(yù)估時長,此外統(tǒng)計(jì)了每個箱區(qū)的空閑總時長和阻塞總時長。通過表3可以看出,經(jīng)過強(qiáng)化學(xué)習(xí)得到的模型能將空閑時長和阻塞時長多數(shù)控制在15 min左右。其中,45箱區(qū)和51箱區(qū)的阻塞時長甚至可以控制到0 min,47箱區(qū)的箱子數(shù)目遠(yuǎn)遠(yuǎn)多于其他箱區(qū),因此造成了阻塞時長高達(dá)31 min,這種情況是可接受的。實(shí)驗(yàn)結(jié)果表明,本文算法能夠合理地分配箱區(qū)任務(wù)以及充分利用設(shè)備資源。

表3 箱區(qū)作業(yè)情況分析Table 3 Analysis of box area task

4.2 對比算法

目前對于自動配載算法的研究大多使用整數(shù)規(guī)劃、遺傳算法,算例規(guī)模較大時算法的求解時間也較長。因此本文使用以下3個算法進(jìn)行對比實(shí)驗(yàn)。

算法1通過文獻(xiàn)[22]的算法思想和洋山四期的數(shù)據(jù)性質(zhì)進(jìn)行擴(kuò)充修改的自動配載算法。在實(shí)驗(yàn)過程中,訓(xùn)練期間采用了原文算法中的9個隱含層網(wǎng)絡(luò),通過迭代訓(xùn)練不同的配載數(shù)據(jù)得到算法模型。為了方便比較雙小車拼車率的指標(biāo),本文在網(wǎng)絡(luò)結(jié)構(gòu)的輸入節(jié)點(diǎn)的第9維上進(jìn)行了修改,將判斷從同一個貝位修改為同一個箱區(qū),同時加上雙箱作業(yè)的約束條件。

算法2基于時間差值的貪心配載策略。根據(jù)CWP安排時間點(diǎn)和配載過程中預(yù)估的時間點(diǎn)做差值,其中翻箱通過時間罰值體現(xiàn),實(shí)驗(yàn)中每翻一個箱子,時間罰值是150 s。雙小車拼車情況通過目標(biāo)箱區(qū)20英尺小箱占比率轉(zhuǎn)化為時間罰值來計(jì)算,實(shí)驗(yàn)過程中每個20英尺小箱轉(zhuǎn)化罰值為1 min的罰分時長,最終通過貪心策略得到配載結(jié)果。

算法3本文算法。

3個對比算法分別根據(jù)4.1節(jié)中的4個航次數(shù)據(jù)進(jìn)行比較,通過分析翻箱率和雙小車拼車率來驗(yàn)證本文算法。通過對比實(shí)驗(yàn)結(jié)果可以看出,在航次1的沿海駁船上,3個算法在翻箱率和拼車率上的指標(biāo)基本一致,但是在大型集裝箱船舶的數(shù)據(jù)上,本文算法相對于算法1和算法2,在這2個指標(biāo)上得到了很大程度的優(yōu)化,尤其是在航次4,本文算法相比于算法1在翻箱率上下降了3%,與算法2相比下降了4%。在雙小車拼車率方面,航次3的數(shù)據(jù)表現(xiàn)更佳,相比算法1和算法2分別下降了6%和11%,效果比較明顯。

通過以上實(shí)驗(yàn)的分析和對比可以看出,本文算法在不同規(guī)模的船舶上的指標(biāo)均優(yōu)于現(xiàn)有的傳統(tǒng)算法。在求解時間上,即使采用寬度為5、深度為10的參數(shù)設(shè)置,2 000積載量的船舶也可以在5 min之內(nèi)得到配載方案。本文算法在減少翻箱率和雙小車拼車率的同時,提高了箱區(qū)設(shè)備的利用率,提升了整個碼頭的工作效率。翻箱率與雙小箱拼車率對比如圖5、圖6所示。

圖5 翻箱率對比Fig.5 Comparison of turn-over rate

5 結(jié)束語

本文主要研究自動化碼頭集裝箱出口流程中的自動配載問題。通過將配載過程建模為順序決策問題,運(yùn)用強(qiáng)化學(xué)習(xí)通過大規(guī)模數(shù)據(jù)訓(xùn)練得到箱區(qū)狀態(tài)值函數(shù),以均衡箱區(qū)工作能力,并使堆場箱區(qū)設(shè)備的利用率穩(wěn)定在90%～96%。為得到合理的配載結(jié)果,提出一種深度優(yōu)先且動態(tài)深度多分支搜索的線上策略。實(shí)驗(yàn)結(jié)果表明,相比于傳統(tǒng)貪心算法,該算法翻箱率和雙小車拼車率下降了2%～5%。下一步將考慮實(shí)船配載作業(yè)的容錯度,以加強(qiáng)對實(shí)時問題的處理能力。

感謝洋山港四期項(xiàng)目團(tuán)隊(duì)的數(shù)據(jù)支持！