基于混合算法的自動導引車調度問題研究

屈新懷, 嚴 飛, 丁必榮, 孟冠軍

(合肥工業大學 機械工程學院,安徽 合肥 230009)

0 引 言

隨著電子商務與工業自動化等行業的飛速發展,自動化倉庫在各領域扮演的角色愈加重要。自動導引車(automated guided vehicle,AGV)作為現代倉庫的重要一環,對提高倉儲效率有著重要意義[1]。目前,針對解決AGV作業效率問題,主要從優化AGV任務調度[2]、AGV作業路徑以及避免交通擁堵[3]3個方面入手。

AGV任務調度問題屬于NP-hard問題,精確算法只能用于求解該類問題小型實例,因此求解策略集中于使用啟發式算法。文獻[4]用改進的三交換交叉算子遺傳算法求解AGV調度問題,同時對所有AGV總行駛距離和單AGV最長行駛距離進行優化;文獻[5]針對制造車間AGV運輸問題設計了一種粒子交叉、變異新機制的改進粒子群算法,并用實驗驗證該算法求解AGV最短運輸時間問題的有效性;文獻[6]用改進的遺傳算法求解多AGV作業車間調度問題,并分析了運輸時間、AGV數量與電量之間的相互影響關系;文獻[7]在倉儲AGV任務調度問題中提出了基于LRU緩存的高效K-opt優化算法,改進了原始計算方式,加快了算法收斂速度。以上研究雖然對AGV行駛距離有較好的優化結果,但研究目標較為單一,沒有考慮AGV總能耗等目標,忽略了AGV載重約束,對實際問題刻畫過于理想。

近年來,求解AGV任務調度問題的啟發式算法有遺傳算法、粒子群優化算法、差分進化算法、蟻群算法、模擬退火算法等[8]。其中蟻群算法因操作簡便性和易于改進性得到廣泛研究。蟻群算法的優化速度可以通過設計算法參數自適應規則、設置多蟻群協同優化、改進信息素更新規則3個方面加以改進[9]。文獻[10]針對帶碳排放約束的車輛路徑問題,提出一種在信息素更新規則中引入混動擾動機制的改進蟻群算法,有效提高了求解車輛行駛里程最短和碳排放量最小的多目標非線性規劃模型的概率;文獻[11]提出一種偽動態搜索蟻群優化算法,改進了信息素更新規則,避免了局部優化,提高了算法的收斂速度。

根據上述研究,本文基于AGV任務調度問題的基本模型,構建以AGV行駛總距離和總能耗最小為目標的非線性規劃模型;利用結合離散差分進化算法與蟻群算法的混合算法對該模型進行求解,并通過算例來驗證本文所提出算法的有效性。

1 問題描述和數學模型

1.1 問題描述

多自動導引車多任務點調度問題描述為:在自動化倉庫分揀中心(編號為0),一共有M輛單一型號AGV可執行任務,每輛AGV的空車質量為w,每輛AGV的額定載重為Q,一段時間內隨機生成的分揀任務數量為N,每個任務i(i=1,2,…,n)對應的需求質量為qi(qi

單個AGV多任務的行駛流程為:AGV從分揀中心點出發,根據接收的任務點信息,規劃合理行駛方案,前往各個任務點取對應貨物,再返回分揀中心點。

在AGV多任務調度過程中引入能耗約束,需對小車行駛過程中能源消耗進行刻畫。小車行駛中的能耗受到小車類型、載重負荷、行駛速度、行駛距離等多個變量的影響。參考文獻[12],考慮倉庫中AGV行駛速度較慢,忽略空氣阻力對能耗的影響,在本文中,采用下式計算AGV能耗eij:

eij=μ(w+lijk)gdij/θ+(dij/V)P

(1)

其中:μ為滾動阻力系數;w為空車質量;lijk為車輛的負載;g為重力加速度,取9.81 m/s2;dij為車輛行駛距離;θ為驅動功率因數;V為車輛行駛速度;P為車載系統功率。

1.2 數學模型

根據以上關于多自動導引車多任務點調度問題的描述,本文構建的考慮能源消耗的AGV調度問題的數學模型如下。

目標函數為:

(2)

(dij/V)P]xijk

(3)

約束條件為:

(4)

(5)

(6)

(7)

(8)

xijk=0, ?i=j,k∈M,i,j∈N

(9)

xijk,yik∈{0,1},i,j∈N,k∈M

(10)

其中:(2)式表示所有AGV行駛路徑的長度之和;(3)式表示所有AGV行駛過程中能耗之和;(4)式表示AGV載重負荷約束;(5)式表示每個任務有且只能被一輛AGV完成;(6)式表示所有AGV從分揀中心點出發并返回分揀中心點;(7)式表示AGV接受某個任務,必定從某個地方行駛到該任務點,且任務完成后必定從該任務點離開;(8)式表示每輛AGV行駛路線中沒有子回路,S為若干任務的集合;(9)式、(10)式定義決策變量是0-1變量。

2 模型求解

本文研究的考慮能耗的多自動導引車調度問題是以行駛總距離和總能耗最小為目標的路徑問題,屬于典型的NP難題,擬用結合離散差分進化算法與蟻群算法的混合算法對該模型進行求解。蟻群算法是一種模仿蟻群覓食行為的群體智能算法[13],具有系統性、自組織性、正反饋性與較強的魯棒性,可以在短時間內找到問題較為滿意的解,但當求解問題規模較大時,蟻群算法容易出現早熟、停滯現象[14]。離散差分進化算法區別于經典差分進化算法,可以應用于離散空間,幫助解決離散域中的組合優化問題。當蟻群算法陷入停滯時,引入離散差分進化算法的變異、交叉、選擇操作,擴大算法搜索解的空間,幫助蟻群算法跳出停滯。因此,利用2種算法結合的混合算法對本文的多自動導引車調度問題進行求解,算法流程如圖1所示。

圖1 混合算法求解流程圖

2.1 狀態轉移概率的設置

狀態轉移概率是指螞蟻在搜索路徑時從一個點到另一個點的轉移概率。經典蟻群算法中考慮從當前任務點i到所選任務點j的路徑長度和路徑 (i,j)上的信息素濃度2個方面的因素,其狀態轉移公式如下:

(11)

本文研究的是考慮能耗的多自動導引車調度問題,在設置狀態轉移概率時既要考慮AGV行駛距離,又要考慮能耗量。為此,將能耗量作為啟發信息引入到狀態轉移概率計算模型中,即

(12)

2.2 信息素更新策略

蟻群算法在一次尋優結束后,需要對各任務點間的信息素濃度進行更新,信息素更新的快慢將直接影響算法優化結果。更新過快,算法將陷入局部最優解甚至停滯;更新過慢,算法收斂速度緩慢。本文提出一種引入排名因子的信息素更新策略,提高較優解的信息素濃度,加快算法收斂速度。具體更新策略如下:

τij(t+1)=(1-ρ)τij(t)+Δτij(t)

(13)

(14)

(15)

同時,在迭代中早期,允許更多螞蟻表達信息素,即參與排名;在迭代晚期,只允許排名前列的螞蟻表達信息素,加快收斂速度又防止陷入局部最優解。

2.3 離散差分進化算法

利用上述改進的蟻群算法求解多自動導引車調度問題時,連續5次迭代搜索到的最優解不發生變化,可以認為算法陷入停滯,引入離散差分進化算法的變異、交叉、選擇操作,幫助算法擴大搜索空間,跳出局部最優解。

2.3.1 變異

將每只螞蟻尋找的完整路徑中的分揀中心點(編號)去除,并按順序存放于解矩陣X;隨機選取矩陣中不等于Xi的3行向量,并按以下操作生成該行對應的變異向量Vi,即

Vi=Xp1+F?(Xp2-Xp3),

p1≠p2≠p3≠i

(16)

j=1,2,…,n

(17)

(18)

(19)

其中:(16)式表示離散差分進化算法的變異操作;(17)～(19)式表示離散域中變異向量各位置的取值規則。差分進化算法中,F為變異尺度參數,本算法中F定義為常量,取0.5;r1∈[0,1],為隨機變量。

2.3.2 交叉

按以上操作取得每只螞蟻對應解X的變異矩陣V后,可以求得對應向量Xi的交叉向量Di。求解公式如下:

(20)

其中:r2∈[0,1],為隨機變量;pcr為常量,取0.5。

每只螞蟻解的交叉向量Di可以根據隨機變量的值,從解向量Xi和變異向量Vi對應位置處求得。同時,交叉操作前應先去除變異向量中可能重復的任務點,以保證任務不會重復完成。

2.3.3 選擇

每只螞蟻對應解向量Xi和交叉向量Di均已生成,根據車輛(螞蟻)額定載重限制,生成對應完整路徑(包含分揀中心點),比較車輛總行駛距離,選擇更優解進入迭代。同時為保證擴大搜索空間,設置一定交叉向量Di的被選擇概率。

離散差分進化算法的變異、交叉操作如圖2所示。

圖2 離散差分進化算法變異、交叉操作實例

2.4 2-opt局部優化改進

為對離散差分進化算法與蟻群算法相結合的混合算法搜索到的路線進行進一步優化,本文采用2-opt法對路線內子路徑(即調度方案內某車輛的行駛路徑)進行改進。

改進方法如下:設路線內子路徑任務點為:(i,i+1),…,(j-1,j)。反轉i+1與j-1之間的路線,若反轉后整個路線行駛距離減少,則更新該車輛行駛路線。依次對所有車輛路徑進行2-opt優化,減少整個調度方案車輛行駛距離。

3 數值仿真及算例分析

為驗證所設計的混合算法的有效性及對實際問題的求解能力,本文設計了2個實驗:

(1) 實驗1。利用本文算法對CVRPLIB SET P標準數據集求解,并與改進蟻群算法、遺傳算法等求解結果進行對比,以驗證本文算法的有效性。

(2) 實驗2。為驗證算法能有效提高自動化分揀倉庫作業效率及降低AGV能耗,分別運用本文混合算法與改進蟻群算法對案例模型進行求解。

使用MATLAB R2016a編寫算法代碼,在Intel Core i7-7500U 2.7 GHz (8.00 GiB RAM)、Windows 10操作系統的環境下運行算法。

本文算法相關參數設置為:螞蟻數量AntNum=50;最大迭代次數Max-Iter=200;信息素重要程度因子α=1;啟發式因子β=2,γ=1;信息素揮發系數ρ=0.5;變異尺度參數F=0.5;常量pcr=0.5。

3.1 混合算法有效性驗證

為驗證本文混合算法的有效性,實驗1利用本文算法對CVRPLIB SET P標準數據集求解,并與文獻[15]改進的蟻群算法、遺傳算法、模擬退火算法、粒子群算法求解的最優解對比。實驗對比結果見表1所列。

表1 本文算法與其他算法求解算例結果對比

表1中加粗數據表示該算例最優解。由表1可知,本文算法在小型、中型算例中均能取得較好的解,僅在P-n23-k8、P-n51-k10、P-n55-k10、P-n65-k10、P-n76-k4、P-n76-k5這6個算例中相較于其他算法未取得最優解,且結果與最優解差距不大,說明本文提出的混合算法在求解路徑問題上表現較好,可以對AGV任務調度模型求解。

3.2 自動化分揀倉庫AGV調度

實驗1驗證了本文算法的有效性,但未對具體案例場景進行實驗分析。本文借鑒文獻[16]中的倉庫模型,提出一典型的自動化分揀倉庫模型,其柵格地圖如圖3所示。

圖3 自動化分揀倉庫模型

多輛AGV根據圖中3個訂單任務點信息,在載重約束下,從分揀中心出發前往各訂單任務點,并返回分揀中心點。柵格長寬均為5 m;AGV空車質量w=60,額定載重Q=200,行駛速度V=1,滾動阻力系數μ=0.03,驅動功率因數θ=0.6,車載系統功率P=25。

采用改進蟻群算法和本文提出的混合算法對自動化分揀倉庫AGV調度問題進行求解,算法分別運行10次,平均解中AGV行駛總距離及總能耗見表2所列,算法運行迭代圖如圖4所示。

表2 本文算法與改進蟻群算法求解結果對比

圖4 算法運行迭代圖

由表2可知,應用本文算法對提出的自動化分揀倉庫AGV調度問題求解,AGV行駛總距離及總能耗均小于改進蟻群算法求解結果。同時由圖4算法運行迭代圖可知,本文算法收斂結果、收斂速度均優于改進蟻群算法。這表明本文提出的混合算法可以有效提高自動化分揀倉庫作業效率及降低AGV能耗。

4 結 論

本文對自動化倉庫中AGV多任務調度問題進行了研究,在考慮車輛載重等前提下,構建了以車輛行駛總距離和總能耗最小為目標的非線性規劃模型,并提出了一種離散差分進化算法與蟻群算法相結合的混合算法求解模型。主要貢獻可歸結如下:

(1) 根據所提出能源消耗模型,改進了螞蟻狀態轉移公式。

(2) 提出一種引入排名因子的信息素更新策略,提高較優解的信息素濃度,加快算法收斂速度。

(3) 在蟻群算法中引入離散差分進化算法的變異、交叉、選擇操作,擴大了算法搜索范圍,降低了算法陷入局部最優概率。

最后設計了2種實驗,驗證了本文算法的有效性。結果表明,本文提出的混合算法可以根據實際算例規劃合理路線,有效提高自動化倉庫倉儲效率。

考慮電子商務和工業自動化等行業的飛速發展,未來自動化倉庫環境必將更加復雜,對倉儲效率的要求也愈加提高。未來的研究可以更貼合AGV運輸的實際情況和任務的動態需求。在求解方法上,可以設計多啟發式算法結合的混合算法以及人工智能算法對大型問題進行更高效求解。