集裝箱碼頭上多自動引導(dǎo)車的調(diào)度和路徑規(guī)劃

李 靜，朱小林,2+

(1.上海海事大學 文理學院，上海 201306；2.上海海事大學 物流科學與工程研究院，上海 201306)

1 問題的提出

隨著全球經(jīng)濟一體化的快速發(fā)展，國際貿(mào)易日益頻繁，而海運作為最基本的物流和運輸方式發(fā)揮著重要作用，其中自動化集裝箱碼頭的地位日益突顯。高效的自動引導(dǎo)車(Automatic Guided Vehicle,AGV)的調(diào)度成為保證自動化集裝箱碼頭高效運行的關(guān)鍵，直接關(guān)系到整個碼頭的運行，與之相關(guān)的AGV路徑規(guī)劃也十分重要，它會影響AGV的運輸效率，從而影響整個碼頭的運行效率。AGV根據(jù)路徑規(guī)劃的結(jié)果進行調(diào)度，而AGV的路徑規(guī)劃又受到調(diào)度的影響和約束。

整個自動化集裝箱碼頭布局如圖1所示，由岸橋、AGV運輸區(qū)域、堆場組成。AGV的運輸過程以進口集裝箱為例，進口集裝箱到達港口，通過某個岸橋?qū)⒓b箱從船上卸載后裝載到AGV上，然后AGV根據(jù)指定路線運輸?shù)郊b箱對應(yīng)堆場前卸載，出口集裝箱運輸路線相反。

目前，已經(jīng)有很多學者對AGV調(diào)度和路徑規(guī)劃進行了研究。對于在碼頭上AGV的調(diào)度研究大多是AGV與岸橋、堆場起重機的協(xié)調(diào)調(diào)度研究，還有碼頭上多載AGV的調(diào)度問題的研究。楊勇生等[1]研究了AGV與軌道式龍門起重機(Rail Mounted Gantry Grane,RMG)的協(xié)同調(diào)度問題,建立了混合整數(shù)規(guī)劃模型，小規(guī)模采用CPLEX軟件和遺傳算法分別求解，大規(guī)模采用遺傳算法求解；ZHAO等[2]建立了自動化岸橋和AGV的協(xié)同調(diào)度模型，考慮了岸橋上傳輸平臺的容量限制，并采用兩階段禁忌搜索算法進行求解；ZHONG等[3]對岸橋、AGV、堆場起重機綜合調(diào)度進行優(yōu)化，采用混合整數(shù)規(guī)劃模型，對比各種基本的元啟發(fā)式算法和改進的元啟發(fā)式算法發(fā)現(xiàn)，所提出的模糊控制自適應(yīng)自整定混合算法更有效；CHEN等[4]研究了自動化集裝箱碼頭的堆場起重機和AGV調(diào)度，提出一種多商品網(wǎng)絡(luò)流模型，采用乘數(shù)交替方向法(Alternating Direction Method of Multipliers,ADMM)來雙重化硬約束，所提方法有效地協(xié)調(diào)了自動終端中的AGV和起重機；MA等[5]提出一種基于優(yōu)先級規(guī)則的算法(帶變異過程的蛙跳算法)解決多載AGV的調(diào)度。

因為AGV應(yīng)用廣泛，所以有許多在其他場景中對AGV調(diào)度的研究。劉二輝等[6]研究作業(yè)車間中的AGV調(diào)度，提出一種基于改進花授粉算法的調(diào)度算法；FAZLOLLAHTABAR等[7]研究了制造系統(tǒng)中多個AGV的調(diào)度問題，提出一種求解空間和尋優(yōu)兩個階段的優(yōu)化方法；JIN等[8]將處理時間的組成、某些任務(wù)的優(yōu)先順序作為主要限制因素，提出動態(tài)AGV的調(diào)度方法，并采用遺傳算法進行求解；MOUSAVI等[9]研究了柔性制造系統(tǒng)中AGV的多目標調(diào)度，開發(fā)了數(shù)學模型，并將其與進化算法集成在一起；LIU等[10]考慮無人倉庫自動分揀系統(tǒng)中的多目標AGV調(diào)度，在所建模型中考慮了AGV充電任務(wù)和可變速度；ZOU等[11]研究了線性制造車間物料處理過程中的AGV調(diào)度問題，提出了整數(shù)線性規(guī)劃模型，并提出一種改進的基于最近鄰的啟發(fā)式算法以及離散人工蜂群算法。

然而，僅對AGV路徑規(guī)劃的研究不太多，大多都是針對特殊問題或特殊情況下的研究。NISHI等[12]提出一種Petri網(wǎng)(Petri Net,PN)分解方法來優(yōu)化半導(dǎo)體制造庫中AGV的路線規(guī)劃問題；施劍烽等[13]對自動化碼頭上AGV路徑規(guī)劃的Dijkstra算法進行了研究；楊勇生等[14]研究了只卸不裝的AGV路徑規(guī)劃問題，建立了多目標混合整數(shù)規(guī)劃模型；ZHANG等[15]提出一種基于碰撞分類的AGV無碰撞路徑規(guī)劃方法，并使用網(wǎng)格方法描述AGV的環(huán)境圖，每個任務(wù)的初始路徑由改進的Dijkstra算法預(yù)先確定，然后檢測潛在沖突，給出了4種碰撞分類和3種解決方法；TAI等[16]提出一種基于時間窗的優(yōu)先AGV路徑規(guī)劃算法，解決了多個AGV延遲問題，提出的算法引入規(guī)劃原理和局部可調(diào)路徑，解決了時延問題并降低了時延；XU等[17]設(shè)計了一個AGV最多可裝載兩個集裝箱的路徑規(guī)劃模型，并采用模擬退火算法對其求解，實現(xiàn)了AGV的雙向裝載；YUAN等[18]提出了一種雙層路徑規(guī)劃算法來優(yōu)化AGV的路線，上層使用A*算法規(guī)劃全局路徑，下層提出快速探索隨機樹(Rapid-exploration Random Tree，RRT)算法獲取局部路徑，大大減少了多個AGV路徑?jīng)_突的發(fā)生。

同時，也有許多將AGV的調(diào)度和路徑規(guī)劃結(jié)合起來的研究。UMAR等[19]研究了柔性制造系統(tǒng)環(huán)境下AGV的綜合調(diào)度以及路徑規(guī)劃，提出一種混合遺傳算法，將多目標轉(zhuǎn)變?yōu)閱文繕俗鳛檫m應(yīng)值，并利用模糊專家系統(tǒng)來控制遺傳算子，即實現(xiàn)算法的自適應(yīng)調(diào)整；ZAGHDOUD等[20]將AGV對集裝箱的裝卸問題分為分配問題、安排問題和路徑問題3個子問題，并提出了用Dijkstra算法、遺傳算法、啟發(fā)式算法的混合算法來解決裝卸問題；MIYAMOTO等[21]研究了容量性AGV系統(tǒng)的調(diào)度和無沖突路徑問題(Dispatch and Conflict-free Routing Problem of Capacitated AGV，DCRPC)，提出了局部/隨機搜索方法；LYU等[22]研究了自動運輸系統(tǒng)的AGV調(diào)度和路徑規(guī)劃，并基于A*算法和復(fù)雜的調(diào)度策略解決AGV路徑規(guī)劃問題，提出一種基于單向圖路徑的規(guī)劃算法；YANG等[23]考慮岸橋、AGV、堆場起重機綜合調(diào)度下，AGV路徑的規(guī)劃，采用基于擁塞預(yù)防規(guī)則的雙層遺傳算法進行求解；FAROOQ等[24]研究了在智能紡紗生產(chǎn)系統(tǒng)中AGV分配和路徑規(guī)劃的混合流車間調(diào)度問題，通過優(yōu)化分配效率和提高自動化程度來防止沖突和死鎖；FAZLOLLAHTABAR等[25]研究了在制造系統(tǒng)中AGV的同時調(diào)度和路徑問題，將該問題公式化為網(wǎng)絡(luò)數(shù)學模型，并使用修改后的網(wǎng)絡(luò)單純形算法進行了優(yōu)化；ZHONG等[26]將路徑規(guī)劃和調(diào)度問題結(jié)合起來考慮，實現(xiàn)了多AGV無沖突路徑規(guī)劃的集成調(diào)度，提出混合遺傳-粒子群算法和模糊邏輯控制器算法對其求解；余娜娜等[27]研究在自動化分揀倉庫中多AGV調(diào)度和路徑規(guī)劃，提出一種改進差分進化算法進行求解。

綜上可知，對AGV的調(diào)度和路徑規(guī)劃的研究非常多，但對于自動化碼頭上將AGV的調(diào)度和路徑規(guī)劃結(jié)合起來的研究卻很少，大多數(shù)研究將AGV調(diào)度和路徑規(guī)劃結(jié)合考慮時，在路徑規(guī)劃上只考慮最短路徑問題，很少考慮AGV之間的沖突問題，即使考慮到?jīng)_突也是實時解決，很少有預(yù)防措施?；诖?，本文研究了自動化碼頭上AGV的調(diào)度和預(yù)防沖突的路徑規(guī)劃，并考慮了路徑上AGV是否負載，以此優(yōu)化AGV的能量消耗。

2 問題描述與模型

本文主要研究AGV的調(diào)度與路徑規(guī)劃問題。AGV具體運輸路徑如圖2所示，其中：節(jié)點2，4，6表示岸橋所在點，節(jié)點11，13，15表示堆場所在點，外循環(huán)是AGV主道路行駛方向，為順時針方向，中間的雙向道路為輔助道路?，F(xiàn)考慮在已知若干進口、出口集裝箱裝卸點的情況下，如何給若干AGV進行分配任務(wù)、安排任務(wù)的處理順序，以及如何規(guī)劃若干AGV運輸路徑，使得AGV能量消耗最小，并且使AGV之間的沖突降到最低。在運輸路徑圖2下，交叉口容易出現(xiàn)沖突死鎖的情況，而對輔助道路進行容量限制則可以降低AGV之間發(fā)生沖突的可能性[26]，因此本文考慮輔助道路容量限制來預(yù)防沖突的發(fā)生。

2.1 設(shè)置和假設(shè)

(1)AGV都以同樣的速度勻速運輸，AGV彼此保持安全距離行駛，即在非輔助道路節(jié)點上不存在沖突情況,在輔助道路節(jié)點上遵守先到先得(First Come First Serve,FCFS)的規(guī)則，即先到的AGV先行駛，因為安全距離小，所以等待時間忽略。

(2)考慮將AGV整個路徑分段，包括AGV分別負載每個所分配集裝箱時的路徑和AGV空載時，從上一個集裝箱任務(wù)的卸載點到下一個任務(wù)的裝載點時的路徑。

(3)每條輔助道路上每個方向的道路限制容量不超過兩輛AGV，以盡量減少擁堵和沖突的情況發(fā)生。若在輔助道路中某方向道路上同一時間出現(xiàn)了3輛及以上的AGV，則需要重新規(guī)劃路徑。

(4)AGV處理完成該集裝箱任務(wù)是指到其裝載點裝載該集裝箱，并到其卸載點卸載該集裝箱。

(5)假設(shè)所有AGV同時從各自第一個集裝箱任務(wù)裝載點出發(fā)。

(6)所有集裝箱的優(yōu)先級相同。

2.2 符號說明

As為調(diào)用的AGV集合，As={1,2,…,k,…}；

Cs為進出口集裝箱的集合，Cs={1,2,…,p,…}；

NODE為節(jié)點集合，NODE={nod1,nod2,nod3,…}；

Dirpathau為輔助道路節(jié)點間有向道路的集合；

lop為集裝箱p的裝載點，p∈Cs；

uop為集裝箱p的卸載點，p∈Cs；

αpk表示AGVk是否處理集裝箱p，處理αpk=1，否則αpk=0，k∈As，p∈Cs；

opk表示AGVk處理集裝箱p的順序，此時αpk=1；

xi*表示從節(jié)點nodi到任意節(jié)點的有向路徑；

x*j表示從任意節(jié)點到節(jié)點nodj的有向路徑；

tin(xk)表示AGVk進入xk路徑的時間；

tout(xk)表示AGVk離開xk路徑的時間；

AdjMatrix,AdjMatrix=(disij)表示節(jié)點間的鄰接矩陣，其中nodi和nodj為鄰接節(jié)點時，disij為從節(jié)點nodi到節(jié)點nodj之間的距離，否則disij=0；

cfk表示AGVk滿載時單位時間內(nèi)所消耗的能量；

cek表示AGVk空載時單位時間內(nèi)所消耗的能量；

2.3 數(shù)學模型

目標函數(shù)：

(1)

s.t.

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

tin(x)≥0，tout(x)>0，α,β∈0,1。

(14)

(15)

其中：式(1)中f是目標函數(shù)，目標是使得所有AGV的耗能之和最小，其中耗能的計算包括空載和滿載兩種情況下的計算；約束(2)確保每個集裝箱的裝卸有且僅由一個AGV處理；約束(3)保證每個集裝箱的裝卸任務(wù)都被完成；約束(4)～約束(7)為AGV在有負載和空載的情況下進入、離開所走道路時間之間的關(guān)系，約束(4)將AGV負載時進入道路時間之間的關(guān)系分為3種情況：①道路起始點為負載集裝箱的裝載點且該集裝箱是該AGV第一個處理的，進入該道路的時間為0；②道路起始點并不是所負載集裝箱的裝載點，則進入該道路的時間為離開上一段道路的時間;③道路的起始點為負載集裝箱的裝載點，但該集裝箱并不是該AGV第一個處理的，進入該道路的時間為到達裝載點的時間加上裝載集裝箱的時間；約束(5)將空載時進入道路時間分為兩種情況：①該道路的起始點不是AGV上一個處理的集裝箱的卸載點，則進入該道路的時間為離開上一個道路的時間;②該道路的起始點是上一個集裝箱的卸載點，則進入該道路的時間為離開上一個道路的時間加上卸載上一個集裝箱的時間；約束(8)和約束(9)保證集裝箱裝卸處理先后順序及集裝箱處理順序；約束(10)保證除了每個AGV的首發(fā)點和最終點，每個節(jié)點的出入度是一樣的；約束(11)保證每個AGV所走路徑都是可行的；約束(12)保證輔助道路密度要小于等于2；約束(13)表示進入輔助道路的時間要么是某個AGV在裝卸某個集裝箱的過程中進入該輔助道路的時間，要么是某個AGV在從上一個集裝箱的卸載點到下一個集裝箱的裝載點過程中進入該輔助道路的時間；約束(14)和約束(15)為變量的約束。

3 算法設(shè)計

3.1 總體算法的設(shè)計

算法整體設(shè)計如圖3所示。其中第一階段算法中優(yōu)化任務(wù)調(diào)度，所有AGV不論是否滿足輔助道路密度約束，全部按照最短路徑運輸，第二階段算法根據(jù)第一階段算法輸出的調(diào)度及路徑重新規(guī)劃路徑，使路徑在滿足輔助道路密度的情況下使目標最小化。

為了避免在最優(yōu)任務(wù)分配下，輔助道路沖突多，而主道路所耗時間長，重新規(guī)劃的路徑所花費時間過長，在第一階段算法中保留3個較優(yōu)任務(wù)調(diào)度，比較3個任務(wù)調(diào)度下路徑重新規(guī)劃后的目標時間，取時間最短的為最優(yōu)調(diào)度，其對應(yīng)的路徑為該調(diào)度下最優(yōu)路徑。其中兩個階段算法在3.2節(jié)和3.3節(jié)中詳細介紹。

3.2 考慮任務(wù)組合分解的灰狼優(yōu)化算法

對于第一階段算法中的任務(wù)調(diào)度，考慮當一個集裝箱的卸載點和另一個集裝箱的裝載點相同時，將兩個集裝箱組合調(diào)度，即分配給同一個AGV并連續(xù)處理這兩個集裝箱，這樣可以有效減少初始解的空間[17]。本文采用灰狼優(yōu)化(Grey Wolf Optimizer,GWO)算法在最短路徑下對任務(wù)調(diào)度進行求解，其中GWO算法的適應(yīng)值為目標函數(shù)的負數(shù)。

3.2.1 GWO算法原理

因為本研究中的優(yōu)化問題比較復(fù)雜，且在規(guī)模較大的情況下，傳統(tǒng)優(yōu)化算法缺乏可行性，所以考慮采用元啟發(fā)式算法解決?；依莾?yōu)化(GWO)算法[28]是2014年提出的新的元啟發(fā)式算法，在與一些著名元啟發(fā)式算法進行實驗對比下，GWO算法表現(xiàn)出了較高的性能[28]。GWO算法只需要調(diào)整兩個參數(shù)，因此，對于大規(guī)模計算來說其速度非常有優(yōu)勢，且該算法采用了隨機和固定兩個操作來避免局部最優(yōu)解，提高了算法的后期開發(fā)能力，有效避免了算法在局部最優(yōu)停滯的情況，本研究中存在大量集裝箱任務(wù)以及多極值情況，因此考慮求解速度以及解的質(zhì)量GWO算法是十分合適的。

GWO算法靈感來自灰狼，該算法模擬灰狼群在自然界中的等級機制和狩獵機制。GWO算法認為α是最好的解，β、δ是第二、第三最佳解，其余解為ω，優(yōu)化過程由α、β、δ引導(dǎo)，ω根據(jù)這3個解進行優(yōu)化。優(yōu)化過程如下：

A=2×a×r1-a。

(16)

C=2×r2。

(17)

Dα=|C1×Xα-X|,Dβ=|C2×Xβ-X|,Dδ=|C3×Xδ-X|。

(18)

X1=Xα-A1×(Dα),X2=Xβ-A2×(Dβ),X3=Xδ-A3×(Dδ)。

(19)

(20)

其中:t為當前迭代次數(shù);A、C為系數(shù)向量，計算如式(16)和式(17)所示。其中a向量在迭代中每一維從2線性下降到0，r1、r2每一維是[0,1]中的隨機向量，灰狼們位置根據(jù)Xα、Xβ、Xδ位置進行更新。算法的具體流程如下：

(1)初始化灰狼群的位置和各a、A、C向量。

(2)根據(jù)位置計算每個狼的適應(yīng)值。

(3)根據(jù)適應(yīng)值找到α、β、δ。

(4)根據(jù)式(18)～式(20)更新每個狼的位置并計算適應(yīng)值。

(5)更新α、β、δ。

(6)更新各a、A、C向量。

(7)判斷迭代終止條件是否達到，若未達到則轉(zhuǎn)步驟(4),否則轉(zhuǎn)步驟(8)。

(8)輸出當前α即為最優(yōu)解。

3.2.2 編碼及解碼設(shè)計

考慮第一階段要解決任務(wù)調(diào)度問題,即要解決任務(wù)分配、處理順序,編碼采用實數(shù)編碼,對每個待處理集裝箱對應(yīng)一個實數(shù),按照集裝箱編碼的從大到小,將集裝箱均勻地分配給序號從小到大的AGV,多出來的集裝箱分配給序號最大的AGV,具體用下面的例子來說明。

現(xiàn)有10個待處理集裝箱,3個AGV,假設(shè)編碼如圖4所示,按照規(guī)則,每個AGV先分配3個集裝箱,多出來的1個集裝箱分配給AGV3,本文將集裝箱按照編碼從大到小的排序,并按3∶3∶4分配給AGV1、AGV2、AGV3,且AGV處理集裝箱的順序也是按照從大到小的順序,最終結(jié)果如圖4所示。

由于編碼長度與集裝箱個數(shù)相同，當集裝箱個數(shù)過多時會導(dǎo)致編碼過長，若采取任務(wù)組合，可以使編碼變短，同時初始解的空間也會減少。假設(shè)上述例子中10個集裝箱的裝卸點如圖5上半部分所示，將一些集裝箱根據(jù)規(guī)則組合起來，組合規(guī)則是：若集裝箱a的卸載點與集裝箱b的裝載點相同，則組合起來的任務(wù)點就是集裝箱a的裝載點、集裝箱a的卸載點(集裝箱b的裝載點)、集裝箱b的卸載點，任務(wù)點是有順序的，集裝箱也有順序，形成新的任務(wù)，新的任務(wù)序列中的每個任務(wù)由集裝箱和任務(wù)點組成。

新的任務(wù)序列形成過程如下：

(1)初始時待組合序列中為所有集裝箱，任務(wù)序列為空。

(2)在待組合序列中按順序?qū)⒚總€集裝箱的卸載點、裝載點分別與排在它之后的集裝箱的裝載點、卸載點進行對比，若找到，則與找到的第一個匹配的集裝箱組合放入任務(wù)序列中，并將兩個集裝箱從待組合序列中去除。

(3)若待組合序列中的集裝箱沒有可以組合的，則將剩下的所有集裝箱插到任務(wù)序列的最前面，得到的即為最終新的任務(wù)序列。

按照以上步驟對10個集裝箱進行組合，得到的新任務(wù)如圖5下半部分所示，此時由原來的10個集裝箱任務(wù)變成了6個任務(wù)，編碼長度也從原來的10維變成了6維。當集裝箱數(shù)量龐大時，因為裝卸點個數(shù)有限，所以組合概率也會變大，編碼長度有效減少，在第4章實驗中也驗證了此觀點。

編碼方式不變，但因為集裝箱的組合，所以解碼時還要將組合進行分解，得到AGV所分配的集裝箱以及處理順序，以上述組合為例，示例如圖6所示?？梢钥吹?，根據(jù)上面的解碼方法可以得到任務(wù)的分配及處理順序，需要根據(jù)任務(wù)所對應(yīng)的集裝箱找到集裝箱的分配及處理順序。以AGV1為例，根據(jù)初步解碼，需要處理的任務(wù)及順序為5→2，由圖6下半部分可以得到，任務(wù)5對應(yīng)集裝箱6、5，任務(wù)2對應(yīng)集裝箱7，按照任務(wù)及集裝箱在任務(wù)中的順序可以得到AGV1所分配到的集裝箱及處理順序為6→5→7。剩余AGV按照同樣的方法解碼，最終結(jié)果如圖6所示。

3.2.3 算法步驟

根據(jù)前面兩節(jié)的介紹，考慮任務(wù)組合分解的GWO算法的具體步驟如下：

步驟1將所有集裝箱根據(jù)裝卸任務(wù)點進行組合(如圖4)，得到新的任務(wù)。

步驟2根據(jù)新的任務(wù)個數(shù)確定GWO算法中的編碼長度即解的長度。

步驟3通過GWO算法進行求解任務(wù)調(diào)度，其中在計算某個解的適應(yīng)值時，需要對其進行解碼(如圖5)，得到AGV相應(yīng)的路徑從而計算適應(yīng)值。

步驟4通過步驟3所得到的最終解，通過解碼得到AGV所走路徑、所分配到的任務(wù)及其執(zhí)行順序，此時還需要將AGV所分配到的任務(wù)進行分解，對應(yīng)于步驟1中的逆操作，得到AGV所分配到的集裝箱以及其執(zhí)行順序。

需要說明的是，任務(wù)點之間的路徑在這里按照最短路徑規(guī)劃。

3.3 基于Floyd的時間沖突預(yù)測算法

對于路徑規(guī)劃中，如果在任務(wù)調(diào)度確定的情況下，當前的最短路徑不滿足輔助道路密度限制，第二階段算法則根據(jù)時間沖突預(yù)測規(guī)則修改參數(shù)，利用Floyd算法重新規(guī)劃路徑，使重新規(guī)劃出的路徑滿足道路密度限制。

3.3.1 算法原理

Floyd算法是利用動態(tài)規(guī)劃思想尋找給定的加權(quán)圖中多源點之間最短路徑的算法，是一種在具有正或負邊緣權(quán)重的加權(quán)圖中找到最短路徑的算法。該算法的優(yōu)點在于它可以算出任意兩個節(jié)點之間的最短距離，但時間復(fù)雜度高，不利于計算大量數(shù)據(jù)。對于本研究來說，規(guī)劃路徑時起始點和終點對于不同集裝箱是不同的，即需要知道任意兩個節(jié)點之間的最短距離，并且路徑節(jié)點數(shù)有限且規(guī)模小，因此該方法是適用于本研究的。

Floyd算法的基本步驟為：

(1)用G表示圖的帶權(quán)鄰接矩陣，初始時所有兩點之間的距離是邊的權(quán)，如果兩點之間沒有邊相連，則權(quán)為無窮大。

(2)定義矩陣D記錄兩點最短路徑中必經(jīng)節(jié)點，對于頂點u和v，判斷是否有頂點w使得u到w再到v比已知的路徑更短，若有則更新鄰接矩陣G和矩陣D中有關(guān)信息。

(3)最終得到的鄰接矩陣G記錄了兩點之間的最短路徑距離，而根據(jù)矩陣D可以找到兩點間的最短路徑。

3.3.2 算法設(shè)計

具體設(shè)計如算法1所示:

算法1路徑重新規(guī)劃算法偽代碼。

輸入:原始鄰接矩陣map，所有agv的路徑agv.route，所有agv所分配的集裝箱agv.con，所有集裝箱的裝卸點con.lp、con.up；

輸出:agv.route重新規(guī)劃后的路徑。

1:[D, R] ← floyd(map); //原始鄰接矩陣下最短路徑信息

2:predict_set ← [agv1, agv2]；

3: k ← 3；

4:while 1 do

5: p ← 判斷所有 agv 在當前路徑下是否使輔助道路密度大于 2；

6: if p == 1 && predict_set 中不包含所有 agv then

7: conflict ← predict_set 中使得輔助道路密度大于等于 2 的時間段集合；

8: predict_set = [predict_set, agvk]；

9: agvk.route = []； //將 agvk 中的路徑清空，重新規(guī)劃

10: a = agvk.con；

11: i = 1； //從處理第一個集裝箱開始

12: s = a(i).lp； //以裝載點為起點

13: e = a(i).up； //以卸載點為終點

14: tag = 0

15: while 1 do

16: map1 = map；

17: for 遍歷每個輔助道路 L do

18: tp_L ← 以s為起點、t為起始時間，基于R預(yù)測通過輔助道路L的時間段

19: for 遍歷 conflict(L) 中的每個時間段 t_c do

20: if tp_L 的時間段與 t_c 有重合 then

21: map1(L(1), L(2)) = map1(L(1), L(2)) + M； //增加該道路權(quán)重

22: end if

23: end for

24: end for

25: [D1, R1] ← floyd(map1)；

26: route ← 根據(jù) R1、s、e 重新求解該段路徑

27: agvk.route = [agvk.route, route]；

28: if tag==0 then

29: if i == length(a) then //所有集裝箱任務(wù)都規(guī)劃完畢

30: break；

31: else

32: s = a(i).up；

33: e = a(i + 1).lp；

34: tag = 1；

35: end if

36: else

37: i = i + 1；

38: s = a(i).lp；

39: e = a(i).up；

40: tag = 0；

41: end if

42: end while

43: k ← k + 1；

44: else

45: return agv.route；

46: end if

47:end while

算法基本步驟如下：

步驟1已知所有AGV的任務(wù)調(diào)度及初始運輸路徑，圖的原始鄰接矩陣，初始預(yù)測集中只有前兩個AGV。

步驟2根據(jù)所有AGV當前的運輸路徑，判斷是否使得輔助道路的道路密度大于2，是則轉(zhuǎn)步驟3,否則轉(zhuǎn)步驟8。

步驟3計算預(yù)測集中的AGV在其規(guī)定的路徑下處理所有集裝箱時，各個輔助道路上的道路密度，記錄道路密度大于等于2時的時間段，形成該輔助道路的沖突集合。

步驟4加入新的AGV到預(yù)測集中，其路徑重新規(guī)劃所以置為空，記起點為第一個要處理集裝箱的裝載點，終點為其卸載點，當前時間記為0。

步驟5鄰接矩陣設(shè)為原始鄰接矩陣，通過當前時間及起點，預(yù)測AGV通過輔助道路的時間段，若與其對應(yīng)的沖突集中的時間段重合，則增加鄰接矩陣中該輔助道路的權(quán)重。所有輔助道路判斷完成后，將得到的新的鄰接矩陣重新通過Floyd算法計算最短距離，并根據(jù)起點和終點產(chǎn)生路徑插到該AGV路徑的最后面，現(xiàn)在的時間更新為到達終點的時間。

步驟6若該AGV所有集裝箱都處理完畢，即已經(jīng)規(guī)劃出新的路徑，則轉(zhuǎn)步驟2，否則轉(zhuǎn)步驟7。

步驟7若剛剛的起點和終點是處理完畢最后一個集裝箱的裝卸點，則現(xiàn)將起點設(shè)為該集裝箱的卸載點，終點設(shè)為下一個待處理集裝箱的裝載點；否則將起點和終點設(shè)為下一個待處理集裝箱的裝卸點，轉(zhuǎn)步驟5。

步驟8所得路徑則為滿足道路密度約束的路徑。

其中輔助道路密度大于等于2的時間段集合包括每一種使得該輔助道路密度大于等于2的情況下的時間段，這個時間段是指：第2個AGV進入該輔助道路的時間到第1個AGV離開該輔助道路的時間，其中這里的第1、第2是按照AGV進入該輔助道路的時間，按照由先到后進行排序所得。因為無論之后有哪個AGV從進入到離開該輔助道路的時間與該時間段重合都會使得該輔助道路密度大于2，所以以這個時間段集合來進行預(yù)測。又因為主道路上不存在道路密度的問題，所以該算法一定可以規(guī)劃出滿足輔助道路密度限制的路徑。

4 實驗結(jié)果

本章研究了任務(wù)組合操作對算法的影響及第二階段算法中路徑規(guī)劃的正確性，比較了在不同元啟發(fā)式算法和各種問題規(guī)模下總體算法的最終結(jié)果與運行時間，對比了不同算法的收斂情況以及解的質(zhì)量。本文算法是在MATLAB R2018b中實現(xiàn)的，所有實驗都是在Windows 10操作系統(tǒng)下使用AMD Ryzen 7 4800U with Radeon Graphics 1.80 GHz和16 GB RAM的計算機進行的。

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

本研究的AGV運輸速度、運輸?shù)缆烽L度參考廈門遠海自動化碼頭，AGV的運輸速度為5 m/s，AGV空載時消耗0.7 kWh，負載時消耗2 kWh，運輸?shù)缆烽L度為240 m，寬度為100 m，其中輔助道路之間的距離為30 m，AGV在碼頭起重機(Quay Crane,QC)處裝卸集裝箱時，時間為10 s,AGV在堆場處裝卸集裝箱時，時間為5 s?？紤]裝卸集裝箱數(shù)量從5～5000個不等，AGV數(shù)量從2～30個不等，QC數(shù)量8個，堆場數(shù)量8個，集裝箱的裝卸點隨機產(chǎn)生。為了使算法進行公平比較，所有算法的編碼解碼方式相同，群規(guī)模及最大迭代次數(shù)相同。算法中的具體參數(shù)設(shè)置如下：粒子群優(yōu)化(Particle Swarm Optimization,PSO)算法中:c1=c2=1,w=1;社會學習型粒子群(Social Learning PSO,SL_PSO)算法中:a=0.5,b=0.01。

4.2 任務(wù)組合的影響及路徑規(guī)劃正確性

在相同任務(wù)下，將集裝箱任務(wù)經(jīng)過組合分解所產(chǎn)生的最終解與直接參與調(diào)度產(chǎn)生的最終解進行比較，結(jié)果如表1所示。可以看到，隨著集裝箱數(shù)量的增大，編碼長度的差距也在增大，最大差距達到了50%左右，目標值在小的問題規(guī)模下差距不大，但隨著規(guī)模的增大，目標值的差距就達到了11%左右。從結(jié)果可以得出，將任務(wù)先組合后再求解可以有效減少編碼長度，優(yōu)化求解結(jié)果。

表1 任務(wù)組合與否比較結(jié)果

下面需要驗證所求結(jié)果是否滿足輔助道路密度約束，即第二階段算法中道路規(guī)劃的正確性，以集裝箱100個，AGV 9個規(guī)模為例，第一階段算法所得AGV隨時間所走輔助道路如圖7所示，圖中縱坐標為輔助道路中的有向道路，橫坐標為時間?？梢钥吹?，不是所有輔助道路密度都滿足小于等于2這個條件，例如：①在450 s左右的時間段上，在15→20這條道路上AGV1、AGV4、AGV7、AGV9在時間上是有重疊的，即道路密度為4大于2；②在570 s、580 s左右的時間段上，在32→3這條道路上AGV3、AGV8、AGV9之間，AGV3、AGV7、AGV9之間在時間上有重疊，道路密度為3大于2。將所有AGV路徑經(jīng)過第二階段算法重新規(guī)劃，得到的結(jié)果如圖8所示，可以看到每條道路上至多有兩個AGV在時間段上有重合，其中在上文中所列舉不滿足密度條件的例子，在進行重新規(guī)劃路徑后情況如下：①目前只有AGV1、AGV4有時間重疊；②目前是分別只在兩個AGV之間有時間重疊，分別是AGV8和AGV3，AGV7和AGV3，AGV7和AGV1?？梢钥吹剑匦乱?guī)劃后所有輔助道路密度都滿足了小于等于2的條件，即路徑重新規(guī)劃成功，第二階段算法有效。

4.3 總體算法實驗

為了驗證總體算法在不同規(guī)模下的有效性，進行了以下實驗：在不同問題規(guī)模，總體算法框架不變的情況下將GWO算法分別替換成PSO算法、SL_PSO算法、蛙跳算法(Shuffled Frog Leaping Algorithm,SFLA)，在相同種群數(shù)量及最大迭代次數(shù)下運行30次，其中每種問題規(guī)模下的30次運行都是對同一隨機產(chǎn)生的集裝箱任務(wù)進行的，比較其運行結(jié)果如表2和表3所示，表2為CPU運行30次的平均運行時間，表3為30次運行結(jié)果的平均值。這4種算法都為群智能算法，其中PSO算法、SFLA是較早提出并應(yīng)用廣泛的，SL_PSO算法是對PSO算法的改進，和GWO算法一樣是較新提出的算法。

由表2可知，GWO算法CPU運行時間小于其他3個算法，特別是在大規(guī)模問題中，GWO算法的優(yōu)勢更加明顯，例如集裝箱個數(shù)為2 000時，GWO算法的CPU運行時間相比于其余算法減少了8.10%～56.22%。由表3可知，GWO算法的結(jié)果基本上均為4個算法中的最優(yōu)，即使不是最優(yōu)也是次優(yōu)，并且與最優(yōu)的結(jié)果相差不大。

表2 CPU平均運行時間的對比 s

表3 平均目標值的對比 kWh

如圖9所示，比較了各算法的收斂情況,其中圖9a～圖9d分別表示在集裝箱—AGV個數(shù)為30-4、100-9、800-16、1000-20，最大迭代次數(shù)為300、400、500、600的情況下的收斂圖?？梢杂^察到，GWO算法的收斂時間是隨著規(guī)模的增大而增大的，收斂的值相比其余算法更優(yōu)。可以看到，在迭代初始階段，GWO算法的收斂速度較快，即在探索階段，GWO算法的全局搜索能力在4個算法中較優(yōu)，特別是在圖9a和圖9b中，可以看到GWO算法在迭代前期目標值下降速度非常快。而在迭代后期，可以看到GWO算法的開發(fā)能力也是較優(yōu)的，在圖9中有些算法過早收斂，陷入局部最優(yōu)，可以看到GWO算法因全局搜索能力較優(yōu)，所以在別的算法已經(jīng)收斂的情況下，GWO算法雖然還未收斂，但其值也較優(yōu)，并且在較優(yōu)的值情況下，GWO算法的局部搜索能力即開發(fā)能力使其在迭代最后可以找到比其他算法都要優(yōu)的值，如圖9c和圖9d所示。綜上所述，本文所設(shè)計總體算法在解決該問題上無論是小規(guī)模還是大規(guī)模問題都是較好的。

5 結(jié)束語

本文考慮了自動化集裝箱碼頭上AGV的調(diào)度和路徑規(guī)劃，使得在降低沖突發(fā)生的情況下AGV能量消耗最少。通過實驗可以看出，所設(shè)計算法的有效性，先將集裝箱任務(wù)組合，可以有效優(yōu)化算法所求得的結(jié)果，所提出的GWO算法與PSO算法、SL_PSO算法、SFLA算法相比，運行時間短，并且在各種規(guī)模下都有良好的結(jié)果，是更有效、更可靠的算法。

在本文中考慮裝卸情況時，沒有考慮AGV多載的情況，未來的研究可以考慮AGV裝載兩個及以上集裝箱的情況。在AGV路徑規(guī)劃中，本文只考慮了輔助道路密度問題，今后可以考慮更多可能產(chǎn)生沖突的情況，以更大地降低沖突發(fā)生的可能性；運算時間在大規(guī)模集裝箱下不夠快，未來也可以考慮并行運算，從而減少運行時間。