基于混合算法的自動(dòng)導(dǎo)引車調(diào)度問(wèn)題研究

屈新懷, 嚴(yán) 飛, 丁必榮, 孟冠軍

(合肥工業(yè)大學(xué) 機(jī)械工程學(xué)院,安徽 合肥 230009)

0 引 言

隨著電子商務(wù)與工業(yè)自動(dòng)化等行業(yè)的飛速發(fā)展,自動(dòng)化倉(cāng)庫(kù)在各領(lǐng)域扮演的角色愈加重要。自動(dòng)導(dǎo)引車(automated guided vehicle,AGV)作為現(xiàn)代倉(cāng)庫(kù)的重要一環(huán),對(duì)提高倉(cāng)儲(chǔ)效率有著重要意義[1]。目前,針對(duì)解決AGV作業(yè)效率問(wèn)題,主要從優(yōu)化AGV任務(wù)調(diào)度[2]、AGV作業(yè)路徑以及避免交通擁堵[3]3個(gè)方面入手。

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

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

根據(jù)上述研究,本文基于AGV任務(wù)調(diào)度問(wèn)題的基本模型,構(gòu)建以AGV行駛總距離和總能耗最小為目標(biāo)的非線性規(guī)劃模型;利用結(jié)合離散差分進(jìn)化算法與蟻群算法的混合算法對(duì)該模型進(jìn)行求解,并通過(guò)算例來(lái)驗(yàn)證本文所提出算法的有效性。

1 問(wèn)題描述和數(shù)學(xué)模型

1.1 問(wèn)題描述

多自動(dòng)導(dǎo)引車多任務(wù)點(diǎn)調(diào)度問(wèn)題描述為:在自動(dòng)化倉(cāng)庫(kù)分揀中心(編號(hào)為0),一共有M輛單一型號(hào)AGV可執(zhí)行任務(wù),每輛AGV的空車質(zhì)量為w,每輛AGV的額定載重為Q,一段時(shí)間內(nèi)隨機(jī)生成的分揀任務(wù)數(shù)量為N,每個(gè)任務(wù)i(i=1,2,…,n)對(duì)應(yīng)的需求質(zhì)量為qi(qi

單個(gè)AGV多任務(wù)的行駛流程為:AGV從分揀中心點(diǎn)出發(fā),根據(jù)接收的任務(wù)點(diǎn)信息,規(guī)劃合理行駛方案,前往各個(gè)任務(wù)點(diǎn)取對(duì)應(yīng)貨物,再返回分揀中心點(diǎn)。

在AGV多任務(wù)調(diào)度過(guò)程中引入能耗約束,需對(duì)小車行駛過(guò)程中能源消耗進(jìn)行刻畫。小車行駛中的能耗受到小車類型、載重負(fù)荷、行駛速度、行駛距離等多個(gè)變量的影響。參考文獻(xiàn)[12],考慮倉(cāng)庫(kù)中AGV行駛速度較慢,忽略空氣阻力對(duì)能耗的影響,在本文中,采用下式計(jì)算AGV能耗eij:

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

(1)

其中:μ為滾動(dòng)阻力系數(shù);w為空車質(zhì)量;lijk為車輛的負(fù)載;g為重力加速度,取9.81 m/s2;dij為車輛行駛距離;θ為驅(qū)動(dòng)功率因數(shù);V為車輛行駛速度;P為車載系統(tǒng)功率。

1.2 數(shù)學(xué)模型

根據(jù)以上關(guān)于多自動(dòng)導(dǎo)引車多任務(wù)點(diǎn)調(diào)度問(wèn)題的描述,本文構(gòu)建的考慮能源消耗的AGV調(diào)度問(wèn)題的數(shù)學(xué)模型如下。

目標(biāo)函數(shù)為:

(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行駛路徑的長(zhǎng)度之和;(3)式表示所有AGV行駛過(guò)程中能耗之和;(4)式表示AGV載重負(fù)荷約束;(5)式表示每個(gè)任務(wù)有且只能被一輛AGV完成;(6)式表示所有AGV從分揀中心點(diǎn)出發(fā)并返回分揀中心點(diǎn);(7)式表示AGV接受某個(gè)任務(wù),必定從某個(gè)地方行駛到該任務(wù)點(diǎn),且任務(wù)完成后必定從該任務(wù)點(diǎn)離開(kāi);(8)式表示每輛AGV行駛路線中沒(méi)有子回路,S為若干任務(wù)的集合;(9)式、(10)式定義決策變量是0-1變量。

2 模型求解

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

圖1 混合算法求解流程圖

2.1 狀態(tài)轉(zhuǎn)移概率的設(shè)置

狀態(tài)轉(zhuǎn)移概率是指螞蟻在搜索路徑時(shí)從一個(gè)點(diǎn)到另一個(gè)點(diǎn)的轉(zhuǎn)移概率。經(jīng)典蟻群算法中考慮從當(dāng)前任務(wù)點(diǎn)i到所選任務(wù)點(diǎn)j的路徑長(zhǎng)度和路徑 (i,j)上的信息素濃度2個(gè)方面的因素,其狀態(tài)轉(zhuǎn)移公式如下:

(11)

本文研究的是考慮能耗的多自動(dòng)導(dǎo)引車調(diào)度問(wèn)題,在設(shè)置狀態(tài)轉(zhuǎn)移概率時(shí)既要考慮AGV行駛距離,又要考慮能耗量。為此,將能耗量作為啟發(fā)信息引入到狀態(tài)轉(zhuǎn)移概率計(jì)算模型中,即

(12)

2.2 信息素更新策略

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

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

(13)

(14)

(15)

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

2.3 離散差分進(jìn)化算法

利用上述改進(jìn)的蟻群算法求解多自動(dòng)導(dǎo)引車調(diào)度問(wèn)題時(shí),連續(xù)5次迭代搜索到的最優(yōu)解不發(fā)生變化,可以認(rèn)為算法陷入停滯,引入離散差分進(jìn)化算法的變異、交叉、選擇操作,幫助算法擴(kuò)大搜索空間,跳出局部最優(yōu)解。

2.3.1 變異

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

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

p1≠p2≠p3≠i

(16)

j=1,2,…,n

(17)

(18)

(19)

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

2.3.2 交叉

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

(20)

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

每只螞蟻解的交叉向量Di可以根據(jù)隨機(jī)變量的值,從解向量Xi和變異向量Vi對(duì)應(yīng)位置處求得。同時(shí),交叉操作前應(yīng)先去除變異向量中可能重復(fù)的任務(wù)點(diǎn),以保證任務(wù)不會(huì)重復(fù)完成。

2.3.3 選擇

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

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

圖2 離散差分進(jìn)化算法變異、交叉操作實(shí)例

2.4 2-opt局部?jī)?yōu)化改進(jìn)

為對(duì)離散差分進(jìn)化算法與蟻群算法相結(jié)合的混合算法搜索到的路線進(jìn)行進(jìn)一步優(yōu)化,本文采用2-opt法對(duì)路線內(nèi)子路徑(即調(diào)度方案內(nèi)某車輛的行駛路徑)進(jìn)行改進(jìn)。

改進(jìn)方法如下:設(shè)路線內(nèi)子路徑任務(wù)點(diǎn)為:(i,i+1),…,(j-1,j)。反轉(zhuǎn)i+1與j-1之間的路線,若反轉(zhuǎn)后整個(gè)路線行駛距離減少,則更新該車輛行駛路線。依次對(duì)所有車輛路徑進(jìn)行2-opt優(yōu)化,減少整個(gè)調(diào)度方案車輛行駛距離。

3 數(shù)值仿真及算例分析

為驗(yàn)證所設(shè)計(jì)的混合算法的有效性及對(duì)實(shí)際問(wèn)題的求解能力,本文設(shè)計(jì)了2個(gè)實(shí)驗(yàn):

(1) 實(shí)驗(yàn)1。利用本文算法對(duì)CVRPLIB SET P標(biāo)準(zhǔn)數(shù)據(jù)集求解,并與改進(jìn)蟻群算法、遺傳算法等求解結(jié)果進(jìn)行對(duì)比,以驗(yàn)證本文算法的有效性。

(2) 實(shí)驗(yàn)2。為驗(yàn)證算法能有效提高自動(dòng)化分揀倉(cāng)庫(kù)作業(yè)效率及降低AGV能耗,分別運(yùn)用本文混合算法與改進(jìn)蟻群算法對(duì)案例模型進(jìn)行求解。

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

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

3.1 混合算法有效性驗(yàn)證

為驗(yàn)證本文混合算法的有效性,實(shí)驗(yàn)1利用本文算法對(duì)CVRPLIB SET P標(biāo)準(zhǔn)數(shù)據(jù)集求解,并與文獻(xiàn)[15]改進(jìn)的蟻群算法、遺傳算法、模擬退火算法、粒子群算法求解的最優(yōu)解對(duì)比。實(shí)驗(yàn)對(duì)比結(jié)果見(jiàn)表1所列。

表1 本文算法與其他算法求解算例結(jié)果對(duì)比

表1中加粗?jǐn)?shù)據(jù)表示該算例最優(yōu)解。由表1可知,本文算法在小型、中型算例中均能取得較好的解,僅在P-n23-k8、P-n51-k10、P-n55-k10、P-n65-k10、P-n76-k4、P-n76-k5這6個(gè)算例中相較于其他算法未取得最優(yōu)解,且結(jié)果與最優(yōu)解差距不大,說(shuō)明本文提出的混合算法在求解路徑問(wèn)題上表現(xiàn)較好,可以對(duì)AGV任務(wù)調(diào)度模型求解。

3.2 自動(dòng)化分揀倉(cāng)庫(kù)AGV調(diào)度

實(shí)驗(yàn)1驗(yàn)證了本文算法的有效性,但未對(duì)具體案例場(chǎng)景進(jìn)行實(shí)驗(yàn)分析。本文借鑒文獻(xiàn)[16]中的倉(cāng)庫(kù)模型,提出一典型的自動(dòng)化分揀倉(cāng)庫(kù)模型,其柵格地圖如圖3所示。

圖3 自動(dòng)化分揀倉(cāng)庫(kù)模型

多輛AGV根據(jù)圖中3個(gè)訂單任務(wù)點(diǎn)信息,在載重約束下,從分揀中心出發(fā)前往各訂單任務(wù)點(diǎn),并返回分揀中心點(diǎn)。柵格長(zhǎng)寬均為5 m;AGV空車質(zhì)量w=60,額定載重Q=200,行駛速度V=1,滾動(dòng)阻力系數(shù)μ=0.03,驅(qū)動(dòng)功率因數(shù)θ=0.6,車載系統(tǒng)功率P=25。

采用改進(jìn)蟻群算法和本文提出的混合算法對(duì)自動(dòng)化分揀倉(cāng)庫(kù)AGV調(diào)度問(wèn)題進(jìn)行求解,算法分別運(yùn)行10次,平均解中AGV行駛總距離及總能耗見(jiàn)表2所列,算法運(yùn)行迭代圖如圖4所示。

表2 本文算法與改進(jìn)蟻群算法求解結(jié)果對(duì)比

圖4 算法運(yùn)行迭代圖

由表2可知,應(yīng)用本文算法對(duì)提出的自動(dòng)化分揀倉(cāng)庫(kù)AGV調(diào)度問(wèn)題求解,AGV行駛總距離及總能耗均小于改進(jìn)蟻群算法求解結(jié)果。同時(shí)由圖4算法運(yùn)行迭代圖可知,本文算法收斂結(jié)果、收斂速度均優(yōu)于改進(jìn)蟻群算法。這表明本文提出的混合算法可以有效提高自動(dòng)化分揀倉(cāng)庫(kù)作業(yè)效率及降低AGV能耗。

4 結(jié) 論

本文對(duì)自動(dòng)化倉(cāng)庫(kù)中AGV多任務(wù)調(diào)度問(wèn)題進(jìn)行了研究,在考慮車輛載重等前提下,構(gòu)建了以車輛行駛總距離和總能耗最小為目標(biāo)的非線性規(guī)劃模型,并提出了一種離散差分進(jìn)化算法與蟻群算法相結(jié)合的混合算法求解模型。主要貢獻(xiàn)可歸結(jié)如下:

(1) 根據(jù)所提出能源消耗模型,改進(jìn)了螞蟻狀態(tài)轉(zhuǎn)移公式。

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

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

最后設(shè)計(jì)了2種實(shí)驗(yàn),驗(yàn)證了本文算法的有效性。結(jié)果表明,本文提出的混合算法可以根據(jù)實(shí)際算例規(guī)劃合理路線,有效提高自動(dòng)化倉(cāng)庫(kù)倉(cāng)儲(chǔ)效率。

考慮電子商務(wù)和工業(yè)自動(dòng)化等行業(yè)的飛速發(fā)展,未來(lái)自動(dòng)化倉(cāng)庫(kù)環(huán)境必將更加復(fù)雜,對(duì)倉(cāng)儲(chǔ)效率的要求也愈加提高。未來(lái)的研究可以更貼合AGV運(yùn)輸?shù)膶?shí)際情況和任務(wù)的動(dòng)態(tài)需求。在求解方法上,可以設(shè)計(jì)多啟發(fā)式算法結(jié)合的混合算法以及人工智能算法對(duì)大型問(wèn)題進(jìn)行更高效求解。