于會(huì)群, 王意樂(lè), 黃貽海

(上海電力大學(xué) 自動(dòng)化工程學(xué)院, 上海 200090)

隨著電子商務(wù)與工業(yè)自動(dòng)化等行業(yè)的飛速發(fā)展,倉(cāng)儲(chǔ)物流行業(yè)在各個(gè)領(lǐng)域扮演的角色也越來(lái)越重要,人們迫切需要構(gòu)建一個(gè)更加高效的自動(dòng)化倉(cāng)儲(chǔ)系統(tǒng)。其中,自動(dòng)導(dǎo)引車 (Automated Guided Vehicle,AGV)是實(shí)現(xiàn)整個(gè)自動(dòng)化倉(cāng)儲(chǔ)系統(tǒng)的關(guān)鍵因素之一。訂單揀選作為倉(cāng)庫(kù)集成系統(tǒng)的關(guān)鍵環(huán)節(jié)之一,是影響物流配送中心作業(yè)效率的重要因素,AGV的出現(xiàn)實(shí)現(xiàn)了倉(cāng)儲(chǔ)系統(tǒng)從“人到貨”到“貨到人”的轉(zhuǎn)變,揀選效率提高了2～4倍[1-2]。

目前,關(guān)于AGV任務(wù)調(diào)度與路徑規(guī)劃問(wèn)題的研究都聚焦于單一問(wèn)題[3],然而兩者存在相同的優(yōu)化目標(biāo),綜合優(yōu)化能更好地提高AGV分揀效率。

對(duì)于AGV任務(wù)調(diào)度問(wèn)題,文獻(xiàn)[4]建立了一個(gè)混合整數(shù)規(guī)劃模型,采用文化算法和改進(jìn)遺傳算法的混合算法進(jìn)行優(yōu)化調(diào)度;文獻(xiàn)[5]將AGV無(wú)沖突路徑的任務(wù)調(diào)度問(wèn)題描述為整數(shù)規(guī)劃問(wèn)題進(jìn)行求解;文獻(xiàn)[6]通過(guò)改進(jìn)的Memetic算法來(lái)對(duì)多AGV調(diào)度問(wèn)題進(jìn)行求解,但并未考慮AGV之間的碰撞沖突以及死鎖。

AGV路徑規(guī)劃的好壞直接影響系統(tǒng)的效率[7]。路徑規(guī)劃問(wèn)題的常用算法包括傳統(tǒng)的Dijkstra算法[8]與A*算法[9],近年來(lái)Q-learning算法[10]、遺傳算法[11],以及PSO算法[12]也陸續(xù)出現(xiàn)在求解路徑規(guī)劃問(wèn)題上,但是大多僅能求解單AGV的路徑問(wèn)題。對(duì)于多AGV系統(tǒng),如何避免AGV的路徑?jīng)_突尤為重要。文獻(xiàn)[13]提出了一種在線學(xué)習(xí)的Q-learning算法,通過(guò)構(gòu)建獎(jiǎng)懲矩陣的形式,實(shí)現(xiàn)了多AGV的無(wú)沖突路徑規(guī)劃;文獻(xiàn)[14]通過(guò)預(yù)約表、改進(jìn)A*算法與動(dòng)態(tài)加權(quán)地圖,實(shí)現(xiàn)了多AGV的路徑協(xié)同優(yōu)化。

上述文獻(xiàn)在研究AGV任務(wù)調(diào)度問(wèn)題時(shí),大多將AGV運(yùn)行路徑進(jìn)行固定且很少考慮AGV間的碰撞沖突,同時(shí),研究AGV路徑優(yōu)化問(wèn)題時(shí),大多默認(rèn)分配給AGV的任務(wù)調(diào)度是固定的。另外,當(dāng)前研究大都忽略了AGV電量的影響。因此,本文針對(duì)自動(dòng)化揀選倉(cāng)儲(chǔ)的多AGV環(huán)境,在考慮AGV電量的情況下,綜合研究任務(wù)調(diào)度和路徑優(yōu)化問(wèn)題。首先,針對(duì)路徑規(guī)劃問(wèn)題,設(shè)計(jì)了多AGV的路徑規(guī)劃算法,同時(shí)考慮AGV電量的影響,綜合優(yōu)化多AGV任務(wù)調(diào)度和路徑規(guī)劃,最終通過(guò)本文設(shè)定的AGV沖突優(yōu)先級(jí),生成多AGV的無(wú)沖突路徑。

1 任務(wù)調(diào)度與路徑規(guī)劃問(wèn)題描述

通過(guò)柵格化建模方式建立的自動(dòng)化倉(cāng)儲(chǔ)模型如圖1所示。

圖1 自動(dòng)化倉(cāng)儲(chǔ)模型

圖1中,倉(cāng)儲(chǔ)的貨架排列是整齊對(duì)稱的,多AGV在倉(cāng)儲(chǔ)環(huán)境中工作。其中,①為揀選區(qū),人工揀選區(qū)域;②為空載AGV,前往目標(biāo)點(diǎn)搬運(yùn)貨架;③為載貨AGV,搬運(yùn)貨架中;④為貨架,AGV的搬運(yùn)目標(biāo);⑤為充電區(qū),AGV電量不足時(shí)會(huì)駛?cè)氤潆姟?/p>

為了便于求解,本文對(duì)多AGV的運(yùn)行場(chǎng)景簡(jiǎn)化如下

(1) AGV的每條通行道是單向的,且相鄰?fù)ㄐ械赖耐ㄐ蟹较蛳喾?

(2) 每個(gè)貨架僅搬運(yùn)1次;

(3) 忽略貨架重量的影響,AGV裝貨與卸貨時(shí)間固定為2 s;

(4) AGV運(yùn)行速度是固定的,AGV運(yùn)動(dòng)一個(gè)柵格的時(shí)間為1 s;

(5) AGV執(zhí)行一次啟停操作時(shí)間為2 s,AGV執(zhí)行一次轉(zhuǎn)彎操作時(shí)間為3 s;

(6) AGV在載貨狀態(tài)的電量是空載狀態(tài)的2倍,空載AGV運(yùn)行1 s消耗電量1;

(7) AGV不可沿對(duì)角線跨越柵格。

AGV在執(zhí)行任務(wù)過(guò)程中,根據(jù)其運(yùn)行狀態(tài)的不同,將其分為載貨和空載2個(gè)工作狀態(tài)。載貨狀態(tài)指AGV將目標(biāo)貨架搬運(yùn)到揀選區(qū)再返回時(shí)的狀態(tài),此時(shí)AGV只能在規(guī)定巷道內(nèi)行駛,AGV的運(yùn)動(dòng)障礙點(diǎn)為固定貨架與其他AGV;空載狀態(tài),即AGV前往目標(biāo)貨架點(diǎn)時(shí)的狀態(tài),AGV可從規(guī)定巷道內(nèi)行駛,亦可從貨架下方行駛,此時(shí)AGV在倉(cāng)儲(chǔ)環(huán)境中運(yùn)動(dòng)時(shí),障礙僅為其他AGV。

為方便描述,本文定義以下符號(hào):i表示AGV編號(hào);j表示任務(wù)編號(hào);n表示機(jī)器人數(shù)量;m表示任務(wù)數(shù)量;AGVi表示編號(hào)為i的AGV;Yi表示AGVi的任務(wù)搬運(yùn)序列;Yi(r) 表示Yi的第r個(gè)任務(wù);D表示AGV設(shè)定的最低電量;Ei表示AGVi的電量;hij表示AGVi執(zhí)行第j個(gè)任務(wù)載貨運(yùn)行時(shí)間;kij表示AGVi執(zhí)行第j個(gè)任務(wù)空載運(yùn)行時(shí)間;Ti表示AGVi的搬運(yùn)任務(wù)完成時(shí)間;Tes表示為電量充足的AGV搬運(yùn)任務(wù)完成時(shí)間最大值與最小值的差值;S1i表示AGVi空載狀態(tài)下的停車等待次數(shù);S2i表示AGVi載貨狀態(tài)下的停車等待次數(shù);Ts表示AGV單次停車避讓時(shí)間。

Ti的計(jì)算公式為

(1)

AGV完成任務(wù)的空載時(shí)間與AGV空置率的優(yōu)化目標(biāo)函數(shù)為

(2)

考慮AGV電量的影響,設(shè)置AGV完成任務(wù)后的電量不能低于設(shè)定值D,即

Ts(S1i+2×S2i)]≥D

(3)

在調(diào)度過(guò)程中,若AGV電量低于設(shè)定值時(shí),應(yīng)對(duì)AGV所承擔(dān)任務(wù)進(jìn)行舍棄,使之電量不能低于設(shè)定值,且將此AGV設(shè)定為低電量狀態(tài)。

2 多AGV路徑規(guī)劃算法

若搬運(yùn)路徑確認(rèn)的情況下,多AGV搬運(yùn)問(wèn)題可以理解為多旅行商問(wèn)題,針對(duì)多AGV調(diào)度問(wèn)題本文設(shè)計(jì)了一種改進(jìn)的遺傳算法。

在執(zhí)行任務(wù)序列Yi時(shí),采用一種基于Q-learning的路徑規(guī)劃算法。Q-learning算法通過(guò)建立獎(jiǎng)勵(lì)函數(shù)R和Q值表,分別用來(lái)存儲(chǔ)瞬時(shí)獎(jiǎng)勵(lì)和Q值函數(shù)值。通過(guò)AGV的當(dāng)前位置s和相應(yīng)的路徑動(dòng)作a,計(jì)算并更新對(duì)應(yīng)的Q值函數(shù)值,記為Q(s,a)。最終通過(guò)選擇最大的累計(jì)回報(bào)值,選擇AGV的下一位置s′,從而生成AGV的運(yùn)動(dòng)路徑。

將獎(jiǎng)勵(lì)函數(shù)R分為主獎(jiǎng)勵(lì)函數(shù)R1與輔助獎(jiǎng)勵(lì)函數(shù)R2,即

R=R1+R2

(4)

首先,建立主獎(jiǎng)勵(lì)函數(shù)R1為

(5)

對(duì)于傳統(tǒng)的Q-learning算法,存在收斂速度慢等問(wèn)題,因此本文引入了導(dǎo)向機(jī)制,用以建立輔助獎(jiǎng)勵(lì)函數(shù)R2。

R2=C(s,goal)-C(s′,goal)

(6)

式中:C(s,goal)——AGV當(dāng)前位置點(diǎn)到目標(biāo)點(diǎn)的歐式距離;

C(s′,goal)——AGV下一位置點(diǎn)到目標(biāo)點(diǎn)的歐式距離。

當(dāng)R2為正值時(shí),表示AGV正在向目標(biāo)點(diǎn)靠近,應(yīng)給予獎(jiǎng)勵(lì);反之,應(yīng)給予懲罰。引入導(dǎo)向機(jī)制,可以加快Q-learning算法的迭代速度,使得AGV更快地向目標(biāo)點(diǎn)靠近。

本文對(duì)Q值函數(shù)值進(jìn)行初始化操作,同時(shí)在Q值函數(shù)值中加入導(dǎo)向機(jī)制,減少算法前期大量的無(wú)用迭代,以提高算法效率。具體公式為

Q(s,a)=C(s,goal)-C(s′,goal)

(7)

Q′(s,a)=(1-α)Q(s,a)+α(R(s,a)+

βmaxQ(s′,a′))

(8)

式中:Q′(s,a)——更新后的Q值函數(shù)值;

α——學(xué)習(xí)率,α∈[0,1],定義了Q值更新占原Q值的比例;

R(s,a)——當(dāng)前狀態(tài)下,系統(tǒng)采取的路徑動(dòng)作獲得的獎(jiǎng)勵(lì);

β——折扣因子,β∈[0,1],定義未來(lái)獎(jiǎng)勵(lì)的重要程度;

a′——下一狀態(tài)所采取的路徑動(dòng)作;

Q(s′,a′)——下一狀態(tài)下所能得到的最大Q值函數(shù)值。

AGV在運(yùn)行過(guò)程中,如果同一時(shí)間內(nèi)有2臺(tái)或以上AGV占據(jù)了同一柵格,即發(fā)生了AGV沖突。為了解決AGV的沖突問(wèn)題,本文設(shè)置AGV沖突避讓規(guī)則如下。

規(guī)則1 低電量機(jī)器人獲得最高優(yōu)先級(jí),即:AGV設(shè)置2個(gè)電量等級(jí),機(jī)器人電量不可低于20%的電量,否則,將前往充電區(qū);對(duì)低電量機(jī)器人賦予高優(yōu)先級(jí)。

規(guī)則2 若不滿足規(guī)則1,即AGV的電量充足,則先判斷AGV是否為載貨狀態(tài),載貨狀態(tài)的AGV賦予高優(yōu)先級(jí)。

規(guī)則3 若不滿足規(guī)則1和規(guī)則2,即AGV電量充足且在相同工作狀態(tài)下發(fā)生沖突,則計(jì)算各個(gè)AGV完成分配的任務(wù)序列總時(shí)間長(zhǎng)短,賦予搬運(yùn)時(shí)間長(zhǎng)的機(jī)器人高優(yōu)先級(jí)。

規(guī)則4 若AGV均不滿足以上3條規(guī)則,則隨機(jī)確定AGV的沖突優(yōu)先級(jí)。

規(guī)則1的制定是為了保證AGV的電量充足,避免AGV因?yàn)殡娏坎蛔?從而導(dǎo)致碰撞或死鎖;規(guī)則2的制定,是為了減少AGV的電量消耗;規(guī)則3的制定,使得AGV的最大搬運(yùn)時(shí)間不會(huì)再增加,降低AGV空置率。根據(jù)以上規(guī)則,在AGV發(fā)生沖突時(shí),使得高優(yōu)先級(jí)AGV直接通過(guò),低優(yōu)先級(jí)AGV停車避讓。

3 改進(jìn)遺傳算法求解調(diào)度問(wèn)題

本文針對(duì)AGV搬運(yùn)任務(wù)序列提出了一種改進(jìn)的遺傳算法,設(shè)計(jì)了雙重染色體編碼方案,使得每個(gè)個(gè)體中都包含各AGV的搬運(yùn)任務(wù)序列;然后通過(guò)本文設(shè)置的自適應(yīng)交叉和變異因子對(duì)個(gè)體進(jìn)行進(jìn)化。AGV的搬運(yùn)任務(wù)序列表示為Y={r1,r2,r3,…,rm}。為了提高AGV的運(yùn)行效率,需要通過(guò)調(diào)度來(lái)生成一條有序地任務(wù)序列,使AGV按照序列有序地執(zhí)行訂單任務(wù),以保障:低電量機(jī)器人不會(huì)承擔(dān)超過(guò)設(shè)定值電量的任務(wù);AGV執(zhí)行任務(wù)的路徑最短;降低AGV最大任務(wù)完成時(shí)間,從而降低AGV空置率。

3.1 種群初始化

本文為解決多AGV的任務(wù)調(diào)度問(wèn)題,設(shè)計(jì)了一種雙重染色體編碼方案。染色體分為2層:第1層決定任務(wù)序列;第2層決定AGV編碼。例如,任務(wù)數(shù)m為4,AGV數(shù)量n為2。染色體Ca為

(9)

此時(shí)AGV的搬運(yùn)序列為:Y1為4-1;Y2為2-3。

3.2 選 擇

遺傳算法通過(guò)選擇最優(yōu)的個(gè)體作為父代,然后通過(guò)進(jìn)化操作產(chǎn)生新的子代,但如果將所有的個(gè)體都放入進(jìn)化過(guò)程,個(gè)體中的優(yōu)質(zhì)基因很容易被破壞,因此本文通過(guò)輪盤賭和精英保留的方式進(jìn)行個(gè)體選擇。將種群中適應(yīng)度值前10%的個(gè)體進(jìn)行保留,確保種群的群優(yōu)良,然后再通過(guò)輪盤賭的方式選擇個(gè)體成為父代。

3.3 交叉變異

遺傳算法的交叉過(guò)程為隨機(jī)產(chǎn)生兩個(gè)數(shù)(大小不能超過(guò)染色體的長(zhǎng)度),通過(guò)兩個(gè)隨機(jī)數(shù)可選中父代染色體的兩段基因片段,然后將兩個(gè)基因片段進(jìn)行互換,即可生成兩個(gè)子代染色體,染色體進(jìn)行基因片段互換后,可能會(huì)使得個(gè)體中出現(xiàn)重復(fù)任務(wù),需要對(duì)染色體進(jìn)行調(diào)整,最終生成交叉后的子代染色體。具體交叉操作如圖2所示。

圖2 染色體交叉過(guò)程示意

染色體交叉過(guò)程中,AGV編碼可與任務(wù)序列編碼一起變動(dòng)。在算法進(jìn)化過(guò)程中,如果給予所有個(gè)體相同的交叉概率Cr,在進(jìn)化過(guò)程中會(huì)造成種群優(yōu)良基因的流失,因此本文提出一種自適應(yīng)交叉因子。對(duì)每1對(duì)交叉的個(gè)體賦予1個(gè)交叉概率,當(dāng)該個(gè)體的質(zhì)量較好時(shí),賦予較低的交叉概率,希望將個(gè)體保留下來(lái);反之,則提高交叉概率,希望生成更好的個(gè)體。

(10)

式中:Crmax,Crmin——最大和最小交叉概率;

f′——當(dāng)前2個(gè)個(gè)體中最高的適應(yīng)度值;

favg,fmax——種群中個(gè)體平均和最高適應(yīng)度值。

在算法迭代前期,種群個(gè)體的適應(yīng)差值較大,需要較大的交叉概率來(lái)生成新的個(gè)體,而隨著迭代逐漸靠近中后期,此時(shí)的種群個(gè)體的適應(yīng)差值逐漸減小,需要減小交叉概率,因此設(shè)計(jì)了隨算法迭代次數(shù)而變化的最大交叉概率為

(11)

式中:gen,Gen——當(dāng)前和最大迭代次數(shù)。

變異操作時(shí),采用單點(diǎn)變異的方式,即產(chǎn)生兩個(gè)隨機(jī)數(shù),確定父代個(gè)體中2個(gè)基因點(diǎn),將選中的2個(gè)基因點(diǎn)位置進(jìn)行互換,即可得到變異后子代個(gè)體。AGV染色體編碼與任務(wù)序列編碼一起變動(dòng)用來(lái)避免算法早熟且可以改善算法的局部搜索能力。本文設(shè)計(jì)的自適應(yīng)變異算子Mr計(jì)算公式如下

(12)

(13)

式中:Mrmax,Mrmin——最大和最小變異概率。

4 仿真驗(yàn)證

構(gòu)建仿真場(chǎng)景模型,設(shè)置基本參數(shù)如下:AGV數(shù)量為5,任務(wù)數(shù)量為100,2#AGV初始電量為低電量4 000,其他編號(hào)的AGV初始電量為滿電量10 000,AGV最低運(yùn)行電量D為2 000。算法參數(shù)設(shè)置如下:α為0.6,β為0.2;初始種群數(shù)量為100,最大迭代次數(shù)為2 000,最小交叉概率為0.3,最小變異概率為0.1。 為了更加直觀地觀察算法的性能,將本文所提算法與其他算法進(jìn)行對(duì)比,結(jié)果如圖3所示。

圖3 不同算法收斂曲線對(duì)比

由圖3可知:本文所提算法在650代取得了最小值821,而遺傳算法、蟻群算法和模擬退火算法分別在555,596,343取得最小值825,828,836;本文所提算法在396代收斂到823,就已經(jīng)超越其他算法的最優(yōu)收斂值。因此,本文所提算法在收斂速度上要優(yōu)于其他算法。

在最終求解的路徑結(jié)果上,表1和表2分別給出了4種算法的AGV運(yùn)行時(shí)間以及AGV空置時(shí)間。

表1 AGV運(yùn)行時(shí)間對(duì)比 單位:s

表2 AGV空置時(shí)間對(duì)比 單位:s

由表1和表2可以看出:對(duì)低電量2#AGV的調(diào)度和路徑優(yōu)化,所有算法都得出了相同的規(guī)劃結(jié)果;而對(duì)于其他編號(hào)的AGV,本文所提算法的AGV運(yùn)行時(shí)間和AGV空置時(shí)間更短,系統(tǒng)的運(yùn)行效率更高。由此可以得出本文所提算法在求解質(zhì)量上優(yōu)于其他算法。

5 結(jié) 語(yǔ)

本文針對(duì)多AGV的路徑及調(diào)度優(yōu)化問(wèn)題,綜合AGV完成任務(wù)的空載時(shí)間與AGV的空置時(shí)間為目標(biāo)展開研究。針對(duì)路徑優(yōu)化過(guò)程,通過(guò)加入導(dǎo)向機(jī)制用來(lái)改善Q-learning算法的效率低下問(wèn)題。針對(duì)多AGV路徑和調(diào)度的綜合優(yōu)化,本文通過(guò)設(shè)計(jì)自適應(yīng)的交叉和變異因子來(lái)改善遺傳算法的效率以及局部最優(yōu)問(wèn)題。最后通過(guò)仿真驗(yàn)證,本文算法在收斂速度和求解質(zhì)量方面要優(yōu)于其他算法,在一定程度上體現(xiàn)了該算法的高效性。