基于多特征與改進卷積神經網絡的AGV實時調度研究

卜人杰，朱 瑾

（上海海事大學 物流科學與工程研究院，上海 201306）

0 引言

AGV具有自主定位、自主導航、信息交互等特點，結合AGV實時數據信息的優化調度可以有效降低集裝箱的周轉時間和作業成本[1,2]。

目前針對AGV的調度研究一般在已知集裝箱作業任務信息的前提下，用啟發式算法求解[3,4]，但是這種傳統的優化方法不能滿足自動化碼頭動態變化的情況。因此近年來，基于機器學習的實時動態調度方法日益受到重視，通過真實數據或模擬仿真學習各個狀態的最優策略[5]。目前神經網絡被廣泛應用于分類、聚類、數據處理等方面[6]。解明利等[7]提出了一種基于最大熵的神經網絡權值優化算法，解決了傳統神經網絡在進行調度策略時易陷入局部最優的問題。Akyol等[8]提出了一種基于神經網絡的決策系統，通過仿真實驗獲取數據并訓練神經網絡，使得神經網絡可以根據給定的參數選擇最優的決策。Choe等[9～11]提出了一種在線學習指派策略，并以岸橋平均延遲時間和AGV空載距離最短為目標，使用BP神經網絡訓練兩個集裝箱之間的偏好強度，實現實時指派。但是BP神經網絡中權值太多，計算量太大，需要大量樣本進行訓練，影響求解速率。Xin等[12]以裝卸集裝箱的總完工時間最少為目標，提出了一種基于當前狀態的設備重調度方法。Ren等[13]采用強化學習算法，建立Q學習和離線學習模塊，針對多種調度策略，在每次調度結束后，動態的給出下一狀態的調度策略。但是使用非線性函數的強化學習往往會因為特征不同產生分歧，導致收斂性很差。因此可以利用卷積神經網絡強大的特征學習能力，學習非線性模型并通過局部擬合學習得到實時模型，為了提高卷積神經網絡的學習能力，主要是通過增加輸出通道的數量，但是這會造成參數過多和過擬合。

綜上所述，針對自動化碼頭AGV調度和卷積神經網絡中存在的參數過多、過擬合等問題，考慮AGV的行駛速度，每個集裝箱作業的緊急程度等約束，建立以岸橋（Quay Crane，QC）平均作業時間最短和AGV空載距離最小為目標的AGV實時調度模型，并設計了一種改進的一維卷積神經網絡對實時調度指派策略進行在線學習，基于InceptionNet的一維卷積通過分支的方式增大網絡的寬度和深度，去除了最后一層全連接層。確定了實驗樣本池容量，設計基于多特征在線學習指派策略與最短車程指派策略的對比實驗，比較了不同規模的AGV在作業動態程度不同的情況下的QC平均作業時間、AGV空載距離和總完成時間。

1 多特征指派模型

1.1 模型假設

首先定義一個集裝箱，當它需要QC進行裝卸貨并且還沒有分配AGV時，那么這個集裝箱就為候選作業，并作出以下假設：

1）一個岸橋對應多個堆場，AGV所服務的岸橋、場橋不固定；

2）AGV每次只運輸一個集裝箱；

3）所有集裝箱作業計劃已知；

4）當AGV無作業時回到中轉區；

1.2 模型框架和變量設定

當AGV完成當前的作業，就會觸發調度。第一步通過從每個QC的裝載或卸貨順序中收集候選作業，在線學習算法會使用當前的調度策略從候選作業中選擇一個作業，然后將該作業分配給請求新作業的AGV，當前調度策略從候選作業中選擇的作業不一定是真正的最佳作業。特別是作業開始是以隨機的初始策略開始。在第二步中，基于每個候選作業的多特征，通過短暫的超前模擬仿真個連續作業分配來評估每個候選作業，使用偏好函數檢查所有候選作業的評估值來確定最佳作業，將最佳作業與其余每個作業配對形成訓練樣本，最后使用改進的卷積神經網絡在線學習訓練樣本并更新指派策略在此仿真中，并將指派策略應用到下一次調度過程中。為了闡述模型，引用以下變量進行表示。其中流程圖如圖1所示。

圖1 AGV實時指派流程圖

J為候選作業集；

π為指派策略；

T為樣本池；

R為樣本上限；

L為仿真模擬作業個數；

I為一個集裝箱作業；

J*為最佳作業；

C為新生成的作業訓練樣本；

V為候選作業集合的評價數組；

ω為權重。

1.3 基于多特征的集裝箱作業表示

在為AGV指派作業時，通過對候選作業的各種標準評估來選擇最佳作業，其中一些標準是經過設計盡量減少AGV的空載距離和最小化QC的平均作業時間。本文使用7個狀態來表示一個裝卸船候選作業，如表1所示。每個標準將在下文進行詳細描述。

表1 候選作業特征指標

令X為候選作業的集裝箱，然后基于d個不同的標準，根據X的評估結果來構建關于候選作業的d維向量，即：

其中，Ci（x）是基于第i個標準的當前情況下的X的評估值。

C1（x）表示集裝箱的緊急程度，即：

其中td（x）是AGV到達集裝箱X的時間，tc為當前時間，C1（x）越小，表示該集裝箱作業越緊急。

C2（x）表示當前小車到達集裝箱X的時間與另一個最快完成作業的AGV到達時間之差，即：

其中ta（v，x）為當前請求作業的AGV到達集裝箱X的時間，x為請求作業的AGV到達集裝箱X的空載距離，v'表示除了v以外另一個最快到達該集裝箱X的AGV，此標準使得在做出調度決策時不僅考慮已經完成作業的當前AGV，還考慮了在不久的將來即將完成作業的其他AGV。

C3（x）表示當前請求作業的AGV到達集裝箱X的空載距離。

C4（x）表示當前請求作業的AGV運輸作業X的負載行駛距離的相反數。取相反數的目的是使分數變小，以獲得更好的偏好。

如果是對集裝箱作業X進行裝船，則C5（x）=0，如果是對X進行卸船，則C5（x）=1，這表明該策略對于裝船的偏好高于卸船，因為對于自動化集裝箱碼頭，裝載的效率是最重要的。

C6（x）表示QC平均延遲的相反數，即：

Dx（Xi）表示QC作業第i個集裝箱所需要的時間，k表示到目前為止QC作業的集裝箱數量。

C7（x）表示作業X的相對剩余工作負載，即：

其中Wx為存儲當前作業X的堆場的集裝箱數量，Wavg表示所有堆場中的平均剩余集裝箱數量，C7（x）給予裝載集裝箱更高的優先級，當工作負載平均分配時，該值為-1/2，對于集裝箱卸船作業時，該值固定為-1/2，C7（x）有助于均衡各個堆場間的集裝箱數量。

使用以下歸一化函數對上述7個指標特征進行歸一化處理，處理為[0，1]中的值。

2 在線學習算法

2.1 偏好函數與目標函數

對于一對候選作業Xi和Xj，它們之間的偏好函數用式(7)表示，結果為[0，1]之間的實數，即：

返回值接近于1表示第一個候選作業對第二個的偏好更高，當給出k個不同的候選作業時，可以將成對的偏好函數應用于每個可能組合的候選作業對來確定最佳作業。利用式(8)求出候選作業Xi在狀態θ下的候選作業集合中的偏好之差總和。v（Xi|Jθ）值最大的作業Xi是當前候選作業集Jθ中的最佳作業J^*，因此對于一個給定的狀態θ下的候選作業集Jθ中的指派策略π為式(9)所示。

在實驗中要實現的兩大目標即：最大程度減少QC的平均作業時間和AGV的空載距離，我們應在此方面衡量調度決策的優劣，選擇Tn和Dn最小作為評價指標建立目標函數f（n），假設已使用該調度策略處理了n個集裝箱作業，使用目標函數(10)來衡量該調度決策的性能。

其中Tn表示QC處理n個集裝箱的平均作業時間，Dn表示AGV運輸n個集裝箱的平均空載距離，ωT，ωD分別為各自的權重。這里Tn和Dn的計算方式如下：

其中Q為QC的集合，tn為當第n個作業完成時，QC的作業時間，s是所有作業的開始時間，Fq，n是到時間tn為止時QC完成的作業集合，eJ是作業J的AGV的空載距離。ωT，ωD可以根據兩個目標的相對重要性而發生變化。

2.2 樣本的訓練與評價函數

每次使用基于上述偏好函數的調度策略將集裝箱作業分配給AGV之后，都會更新偏好函數以用于下一輪集裝箱作業分配。即每完成一次調度決策，都會進行一次短暫的超前模擬評估每個候選作業，假設僅在k個候選作業中進行作業分配，把k中的每一個作業都作為一次最佳作業，然后進行模擬仿真，在這個過程中指派規則ω不變，在超前模擬仿真k個候選作業后，使用以下目標函數進行候選作業的評估，并得到一個評價矩陣，找出評價矩陣中評價函數最小的初始作業。在第一次AGV指派時，由于沒有樣本進行學習，我們是采用隨機策略來進行訓練樣本的獲取。

超前模擬仿真過程中的評價函數如下：

其中Tn+k和Dn+k的計算方式如下：

在洋蔥的種植基地內，要嚴格進行管理，禁止對于高毒、劇毒或者高殘留農藥的使用，同時還需要禁止除草劑的使用。在種植過程中，應當選擇抗病蟲害能力較強的品種，減少使用化學藥劑處理種子的操作。并針對種子的生長發育進行科學的田間管理。

Dn+k的計算方式與Dn相同，但是Tn+k是通過計算處理集裝箱作業數量最少的那個QC的平均作業時間來獲得的，因為如果在短期的超前模擬仿真中使用式(11)來計算，則會使得QC首先去處理那些作業時間較短的集裝箱，以得到較小的QC平均作業時間，但是這種對具有較短時間作業的偏向會使得具有較長處理時間的集裝箱作業直到最后才會被選擇，最終會導致分配這些作業的QC的延遲。所以采用式(14)來評估會促使所有QC的作業進度相對平均。

找出評價矩陣中評價函數最小的初始作業J*，然后將最佳作業J*與k中的其他候選作業兩兩配對，生成（k-1）個訓練樣本，由于生成的（k-1）個訓練樣本總數通常不足以使模型能夠可靠的學習整個新功能，因此在線偏好學習算法維護著一組最近的樣本池T，這些新的訓練樣本已經累積到樣本池T中，然后，該樣本池T中的所有樣本都將學習新的偏好進而更新偏好函數用于下一次作業分配。

2.3 基于改進卷積神經網絡的在線學習

候選作業之間的偏好選擇可以歸于多分類問題，通過改進的卷積神經網絡使用增量學習策略對偏好函數進行學習。改進卷積神經網絡模型如圖2所示，將InceptionNet和傳統卷積神經網絡相結合，從網絡結構和參數優化方面構造了新的分類模型。首先將每個作業兩兩比較轉化成一個15×7的矩陣輸入得到第一層，通過三個不同的分支1×3的卷積、1×5的卷積、1×7的卷積進行特征變換得到三個15×16的卷積，隨后通過聚合操作將三個分支的結果進行合并得到了最終的過濾器作為下一個卷積層的輸入。按照與上一層相同的邏輯，再分別經過三個1×3的卷積、1×5的卷積、1×7的卷積的特征變換，并通過全局平均池化層得到三個8×32的卷積，最后通過維度的聚合在輸出通道上將三個分支的結果進行合并輸出一個長度為6的向量，因為同時有6個作業進行分類，激活函數采用的是Softmax函數。與傳統的卷積神經網絡相比，基于InceptionNet的改進卷積神經網絡雖然在每層卷積前面增加了三個1×3的卷積、1×5的卷積、1×7的卷積，增加了網絡層數，但是去除了最后的全連接層，使用全局平均池化層代替全連接層，進而減少了參數的數量，提高了運算速度并減輕過擬合，同時網絡中卷積核的大小也不一樣，增加了神經網絡對不同尺度的適應性。

圖2 改進卷積神經網絡的網絡結構

3 實驗場景與結果分析

3.1 實驗場景

本實驗采用Python語言實現，進行實驗的計算機參數為Inter（R）Core（TM）i7-7700HQ CPU @ 2.80GHz 2.80GHz，內存16G，Windows10。實驗中的自動化集裝箱碼頭布局如圖3所示。

圖3 自動化集裝箱碼頭布局

假設有6個QC，集裝箱堆場數量為14，總共有900個集裝箱作業，實驗模擬的AGV數量為12，18，24，速度v=4m/s，ωT:ωD=1:1，QC所處理的集裝箱作業目的堆場編號服從正態分布N（μi，σ2i）。如μ4=9時，表示由QC4所處理的集裝箱存放在堆場B9附近，隨著σ4的增大或減小，集裝箱存放在B9的更大或更小范圍內，因此可以通過改變μi和σi的值，來模擬不同的實驗場景。

設計了兩個實驗場景，每個實驗場景包含900個集裝箱作業。場景1設置為各個QC所處理的集裝箱大都分布在最近的堆場周圍，AGV的負載距離都相對均勻和較短，此時集裝箱的分布參數設置為（μ1，μ2，μ3，μ4，μ5，μ6）=（2，4，6，9，11，13），σi=1，場景2設置為集裝箱被廣泛的分布在各個堆場，AGV的負載距離各不均勻，此時集裝箱的分布參數設置為（μ1，μ2，μ3，μ4，μ5，μ6）=（4，5，6，7，8，9），σi=5。

3.2 實驗結果分析

3.2.1 實驗1結果分析

在場景1的情況下，確定合適的樣本池容量上限大小，為后續實驗做好基礎。

表3顯示了通過從樣本池中的樣本學習來更新偏好功能所花費的CPU時間。學習時間包括生成訓練示例和計算所花費的時間。

表3 場景1樣本容量實驗結果

由表3可知，盡管學習時間隨樣本池上限的增加而增加，但仍為1秒左右，對于在AGV調度中進行實時處理來說足夠了。當樣本池中數據過多時，隨著樣本池上限的增加，Tn和Dn都會有所增加，CPU學習時間隨著樣本池上限的增加而增加，指派算法的性能下降，就會導致模型無法準確獲取不斷變化的指派規則。當樣本池上限R=225時，CPU學習時間為0.684s，小于1s，可以接受，由此后續實驗，將樣本池上限R設置為225。

3.2.2 實驗2結果分析

比較12～24臺不同規模的AGV在場景1和場景2下的調度結果。

實驗結果如表4所示，當AGV的數量從12逐漸增加到24時，Tn和Dn減少的速率逐步放緩，因為隨著AGV的數量的增加，同樣也可能會伴隨AGV之間的沖突。

表4 不同場景下AGV的調度情況

1）場景2下的和都高于場景1，這是因為場景2的集裝箱散落在各個堆場之間，動態程度更高，AGV的負載距離是不均勻的。

2）當集裝箱作業數量相同時，場景1下18臺AGV運行下的與場景2下24臺AGV運行下的接近。因此可以根據QC和AGV的信息收集和集裝箱作業的偏好，對指派策略進行調整，從而減少AGV數量的投入。

3.2.3 實驗3結果分析

通過改變集裝箱作業的數量，比較采用基于多特征的在線學習指派策略與采用最短車程指派策略的調度結果。

由圖4可知，采用多特征在線學習指派策略下比采用最短車程指派策略的Dn大約多了13%，但是隨著QC所處理的集裝箱數量增加，多特征在線學習指派策略與最短車程指派策略間的Dn差值大約不變。兩種指派策略情況下總完成時間隨著集裝箱數量增加不斷增加，采用多特征在線學習指派策略的總完成時間比采用最短車程指派策略的總完成時間約平均縮短12%，當每個QC平均處理約225個TEU時，采用多特征在線學習指派策略能節省約21%總完成時間。

圖4 不同指派規則下的調度結果

由表5可知，兩種指派策略下的QC的Tn差值為3.9s，26.2s，33.8s，56.4s等，并且隨著集裝箱數量的增加，在線學習指派策略和最短車程指派策略之間Tn差值不斷增加，說明基于多特征的在線學習指派策略能夠有效減少QC的平均作業時間和最小化完成時間。

表5 不同指派規則下的QC平均完成時間

4 結語

本文設計了一種基于InceptionNet的卷積神經網絡模型，使用全局平均池化層代替了全連接層，減少了參數數量，同時InceptionNet通過分支的方式增大網絡的深度和寬度能夠很好的提高網絡的性能，避免過擬合。然后使用改進的卷積神經網絡用于在線學習基于多特征指派策略的AGV動態調度模型，并通過更新偏好函數來進行指派策略的調整。設計了三組實驗，首先確定樣本池容量實驗，R=225，然后進一步對12～24臺不同規模的AGV在作業動態程度不同的情況下的調度結果進行分析，表明在場景1的情況下18臺AGV的Tn與場景2下24臺AGV的Tn十分接近，因此可以根據集裝箱作業的分布，減少AGV運行數量。最后對比了基于多特征的在線學習指派策略與最短車程指派策略，實驗結果表明，隨著集裝箱作業量的增加，采用基于多特征的在線學習指派策略比采用最短車程指派策略的Tn約平均縮短17%，總完成時間均大約縮短12%。驗證了提出的基于多特征指派策略能夠有效的提高AGV作業效率。