王云峰,曹小華,郭 興

(武漢理工大學(xué) 物流工程學(xué)院,湖北 武漢 430063)

0 引言

隨著科技的不斷進(jìn)步,AGV(automated guided vehicle)越來越廣泛地應(yīng)用到生產(chǎn)、搬運(yùn)等工作中,尤其在物流倉儲中,AGV扮演著重要的角色。有關(guān)AGV路徑規(guī)劃方面的研究一直以來都是重點(diǎn)。常用到的有關(guān)路徑規(guī)劃方面的算法有A*算法[1-3]、Dijkstra算法[4-5]、蟻群算法[6]等。荊學(xué)東等[7]針對A*算法在復(fù)雜地圖軌跡規(guī)劃耗時(shí)長、拐點(diǎn)多的問題,提出了一種基于圖論及幾何方法的改進(jìn)A*算法,在傳統(tǒng)A*算法上結(jié)合圖論進(jìn)行路徑規(guī)劃;張新艷等[8]提出一種引入時(shí)間因子的改進(jìn)A*算法,結(jié)合時(shí)間窗以及優(yōu)先級策略實(shí)現(xiàn)多AGV的動態(tài)無碰撞路徑規(guī)劃;吳飛龍等[9]在傳統(tǒng)A*算法的評價(jià)函數(shù)中添加了環(huán)境信息和位置信息,并設(shè)置了代價(jià)函數(shù)和啟發(fā)函數(shù)的權(quán)重系數(shù)來改進(jìn)A*算法,提高搜索效率。但他們都沒有衡量和比較AGV由于頻繁轉(zhuǎn)彎帶來的時(shí)間損耗與AGV總行駛時(shí)間之間的最優(yōu)解關(guān)系。在多AGV路徑規(guī)劃方面,DAI等[10]建立了最小化能耗和完工時(shí)間的多目標(biāo)路徑規(guī)劃優(yōu)化模型,并提出一種改進(jìn)遺傳算法來求解該調(diào)度問題。RAHMAN等[11]研究開發(fā)了一種適用于碼頭物料搬運(yùn)場景的多AGV路徑規(guī)劃方法,通過建立一個(gè)混合整數(shù)規(guī)劃模型,采用了遺傳算法等元啟發(fā)式算法,以實(shí)現(xiàn)在合理的時(shí)間內(nèi)完成調(diào)度;曹小華等[12]提出了基于沖突預(yù)測的避碰策略,但沒有考慮減少沖突次數(shù)來提高系統(tǒng)的運(yùn)行效率;劉二輝等[13]提出了基于改進(jìn)花授粉算法的共融AGV作業(yè)車間調(diào)度,解決了傳統(tǒng)智能算法求解AGV與機(jī)器集成的車間調(diào)度問題效率低且易早熟的缺點(diǎn)。

AGV路徑規(guī)劃的優(yōu)化目標(biāo)通常是最短路徑[14-15]或最短耗時(shí)[16]。但由于AGV因障礙物的存在需要繞路和頻繁轉(zhuǎn)彎,降低系統(tǒng)的運(yùn)行效率;并且存在不同的路段資源使用不均衡的現(xiàn)象,增加了AGV之間的沖突幾率,增多路徑中的沖突節(jié)點(diǎn)。首先在單AGV路徑規(guī)劃中,針對傳統(tǒng)A*算法的不足,提出一種改進(jìn)的A*算法,對單AGV進(jìn)行全局路徑規(guī)劃,在其啟發(fā)函數(shù)中添加“方向函數(shù)”,引入障礙矩陣,在節(jié)點(diǎn)搜索的過程中判斷目標(biāo)點(diǎn)和障礙物的位置來不斷修正啟發(fā)函數(shù),減少單AGV不必要的轉(zhuǎn)彎次數(shù);其次在多AGV路徑規(guī)劃中,以單AGV路徑規(guī)劃為基礎(chǔ),提出基于系統(tǒng)短期狀態(tài)預(yù)測的多AGV路徑規(guī)劃方法,優(yōu)化短期內(nèi)各路段AGV數(shù)量,使道路資源分配更加合理化,減少路徑中沖突節(jié)點(diǎn)數(shù)量。最后在VS2019上搭建的仿真實(shí)驗(yàn)平臺上進(jìn)行了驗(yàn)證,改進(jìn)A*算法可以大幅降低單AGV的轉(zhuǎn)彎次數(shù),避免繞路現(xiàn)象,降低AGV總行駛時(shí)間;基于系統(tǒng)短期狀態(tài)預(yù)測的多AGV路徑規(guī)劃方法,減少了多AGV在道路中的沖突節(jié)點(diǎn),降低了任務(wù)總完成時(shí)間。

1 問題描述與建模

1.1 應(yīng)用場景

傳統(tǒng)電商物流倉儲的環(huán)節(jié)是入庫、上架、揀貨、包裝、分揀到最后配送到用戶手中。過去通過人工對貨物進(jìn)行入庫、上架、驗(yàn)貨、取貨、分揀等存在很大的弊端,耗時(shí)長、效率低、人力消耗多?，F(xiàn)代物流倉儲中引入AGV、機(jī)械手等自動化設(shè)備后,利用相關(guān)算法,降低了成本,工作效率以及工作秩序都得到了極大的提升。目前電商物流領(lǐng)頭公司順豐、京東、菜鳥等都在智慧物流領(lǐng)域加大投入。

本文研究的問題基于智慧物流中的倉儲AGV搬運(yùn)任務(wù)。倉儲模型如圖1所示,有AGV初始區(qū)域、分揀臺區(qū)域和貨架區(qū)以及各種路段。在搬運(yùn)任務(wù)中,AGV需要避開其他貨架到達(dá)目標(biāo)點(diǎn)。

在多AGV系統(tǒng)中,每條路段上行駛的AGV數(shù)量不同、AGV小車之間的任務(wù)執(zhí)行情況不同、路線不同、速度不同等,某一刻可能會在不同的路徑節(jié)點(diǎn)處發(fā)生沖突,如圖2所示。

1號AGV和2號AGV將在節(jié)點(diǎn)A處發(fā)生沖突,此時(shí)應(yīng)采取必要的避碰策略,如任務(wù)優(yōu)先級避碰策略、貪心算法避碰策略等。在搭建的實(shí)驗(yàn)仿真平臺中顯示各個(gè)AGV的實(shí)時(shí)動態(tài)軌跡,若兩臺及以上AGV同時(shí)到達(dá)某個(gè)節(jié)點(diǎn),將該節(jié)點(diǎn)記為路徑中的沖突節(jié)點(diǎn)。

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

1.2.1 單AGV路徑規(guī)劃模型

由于AGV在執(zhí)行任務(wù)過程中,需要頻繁轉(zhuǎn)彎以及在沖突節(jié)點(diǎn)進(jìn)行避碰處理,會使倉儲多AGV系統(tǒng)中AGV的的總行駛時(shí)間增加。

設(shè)在一次搬運(yùn)任務(wù)中,某臺AGV的轉(zhuǎn)彎次數(shù)為K,每次由于轉(zhuǎn)彎帶來的時(shí)間損耗為ta,規(guī)劃的路徑長度為SD,平均運(yùn)行速度為V,則在本次任務(wù)中,由于AGV轉(zhuǎn)彎帶來的系統(tǒng)時(shí)間損耗

TW=K×ta,

(1)

對于單AGV,其路徑規(guī)劃時(shí)的目標(biāo)函數(shù)即為:

min{TW+SD/V}。

(2)

即在單AGV路徑規(guī)劃中,考慮到減少轉(zhuǎn)彎次數(shù),以最小化單次任務(wù)中AGV總行駛時(shí)間為目標(biāo)對單AGV進(jìn)行路徑規(guī)劃,本文采用改進(jìn)A*算法進(jìn)行求解。

1.2.2 多AGV路徑規(guī)劃模型

多AGV路徑規(guī)劃是在上述單AGV路徑規(guī)劃基礎(chǔ)上進(jìn)行的,即在多AGV路徑規(guī)劃中,每輛AGV都是上述單AGV路徑規(guī)劃,因此轉(zhuǎn)彎次數(shù)多的問題已經(jīng)解決,但要考慮到路徑中的沖突節(jié)點(diǎn)數(shù)量問題,合理分配任務(wù)給各個(gè)AGV。設(shè)在一段時(shí)間T內(nèi),共有Nagv輛AGV執(zhí)行任務(wù),沖突節(jié)點(diǎn)的數(shù)量為Nc,每個(gè)沖突節(jié)點(diǎn)帶來的時(shí)間損耗為tb,第i輛AGV的完成任務(wù)時(shí)間為Ti,在{T1,T2,T3,...Tk}中的最大值為Tmax。因此,對于多AGV,其路徑規(guī)劃時(shí)的目標(biāo)函數(shù)為:

min{Tmax+Nc×tb}。

(3)

即多AGV路徑規(guī)劃時(shí),考慮到路徑中沖突節(jié)點(diǎn)數(shù)量,以最小化多AGV中最大完成時(shí)間為目標(biāo)對多AGV進(jìn)行路徑規(guī)劃,由于是同時(shí)對所有AGV進(jìn)行路徑規(guī)劃,最大完成時(shí)間即為任務(wù)總完成時(shí)間。本文采用基于系統(tǒng)短期狀態(tài)預(yù)測的多AGV路徑規(guī)劃方法進(jìn)行求解。

2 A*算法的改進(jìn)

2.1 傳統(tǒng)A*算法

A*算法是一種靜態(tài)網(wǎng)路中求解最短路徑最有效的啟發(fā)式搜索算法。算法的核心為評價(jià)函數(shù):

F(n)=G(n)+H(n)。

(4)

式中:n為節(jié)點(diǎn),G(n)表示從初始節(jié)點(diǎn)(起點(diǎn))到任意節(jié)點(diǎn)n的實(shí)際代價(jià),H(n)表示從節(jié)點(diǎn)n到目標(biāo)點(diǎn)(終點(diǎn))啟發(fā)式評估代價(jià)。H(n)的計(jì)算方法有很多,如曼哈頓距離、歐幾里得距離、對角線距離等。這里選擇標(biāo)準(zhǔn)啟發(fā)函數(shù)—曼哈頓距離,即

H(n)=|nx-Dx|+|ny-Dy|。

(5)

式中:nx、ny分別為當(dāng)前節(jié)點(diǎn)n的x坐標(biāo)、y坐標(biāo),Dx、Dy分別為終點(diǎn)的x坐標(biāo)、y坐標(biāo)。

算法原理大致為:如圖3,圖中藍(lán)色方格為障礙物,從紅色方格起點(diǎn)S尋找至黃色方格終點(diǎn)D的最短路徑,考慮到上述智慧倉儲模型,只允許AGV上下左右4個(gè)方向運(yùn)動,并且它們的移動代價(jià)都設(shè)為1。

步驟1將起點(diǎn)S加入一個(gè)待檢查節(jié)點(diǎn)的列表open list,接著尋找S周圍所有可達(dá)到的節(jié)點(diǎn),圖3中為S的上下左右4個(gè)節(jié)點(diǎn),計(jì)算它們的G值,將其加入open list,并且將S設(shè)為父節(jié)點(diǎn);

步驟2將S從open list中移除,將其加入另一個(gè)已檢查列表close list;計(jì)算每個(gè)在open list中的節(jié)點(diǎn)的H值,即每個(gè)節(jié)點(diǎn)到終點(diǎn)D的曼哈頓距離。然后將每個(gè)節(jié)點(diǎn)的G值和H值相加,記為F;

步驟3選擇F值最小的節(jié)點(diǎn),對它進(jìn)行步驟1的檢查,如圖4中綠色方格,這也是傳統(tǒng)A*算法的不足之處,只考慮移動代價(jià)而沒有考慮轉(zhuǎn)彎代價(jià)。但需要注意:若可達(dá)到的節(jié)點(diǎn)已經(jīng)在close list中,則忽略;若不在,則計(jì)算其G、H、F,設(shè)置父節(jié)點(diǎn),并將其加入open list;若可達(dá)到的節(jié)點(diǎn)已經(jīng)在open list中,即它們已經(jīng)有了父節(jié)點(diǎn),計(jì)算從當(dāng)前節(jié)點(diǎn)移動到該節(jié)點(diǎn)是否具有更小的G值,若有,則將該節(jié)點(diǎn)的父節(jié)點(diǎn)重設(shè)為當(dāng)前節(jié)點(diǎn),重新計(jì)算G值和F值;

步驟4不斷重復(fù)以上步驟,直到終點(diǎn)D加入open list中,其H=0,即結(jié)束算法,通過父節(jié)點(diǎn)回溯得到最短路徑,如圖5所示。

2.2 改進(jìn)A*算法

傳統(tǒng)A*算法在尋找最短路徑時(shí)非常有效,很多時(shí)候可以尋找到最短路徑,但是在上述智慧物流倉儲中,路徑最短并不一定效率最高,這是因?yàn)锳GV由于轉(zhuǎn)彎會帶來時(shí)間損耗。而傳統(tǒng)A*算法帶來的多余的轉(zhuǎn)彎主要是由于障礙物的存在使其必須變向擴(kuò)展節(jié)點(diǎn)。

一方面,改進(jìn)A*算法實(shí)行“獎懲機(jī)制”,尋路擴(kuò)展節(jié)點(diǎn)時(shí),讓它更偏向于沿直線擴(kuò)展節(jié)點(diǎn),若擴(kuò)展的節(jié)點(diǎn)出現(xiàn)拐點(diǎn),則在其評價(jià)函數(shù)中予以“懲罰”,即增加其代價(jià)值,懲罰函數(shù)如下:

(6)

其中:λ為懲罰因子;C為單位移動代價(jià),即上述地圖中相鄰柵格之間的移動代價(jià);xp為擴(kuò)展節(jié)點(diǎn)的父節(jié)點(diǎn)x坐標(biāo);yp為擴(kuò)展節(jié)點(diǎn)的父節(jié)點(diǎn)y坐標(biāo);xo為擴(kuò)展節(jié)點(diǎn)的子節(jié)點(diǎn)x坐標(biāo);yo為擴(kuò)展節(jié)點(diǎn)的子節(jié)點(diǎn)y坐標(biāo)。

另一方面,引入“AGV的方向感”概念,在其啟發(fā)函數(shù)H(n)中加入“方向函數(shù)”H*(n)?！癆GV的方向感”是指通過障礙矩陣M,判斷和比較任務(wù)終點(diǎn)位置以及AGV周圍障礙物的位置,使算法在擴(kuò)展節(jié)點(diǎn)時(shí)有方向性,給予符合條件的節(jié)點(diǎn)一定的獎勵,即減少其代價(jià)值來不斷修正啟發(fā)函數(shù)。

矩陣M大小與模型地圖保持一致,由0和1組成,0表示可通行,1表示障礙物。

AGV在進(jìn)行路徑規(guī)劃時(shí),將自身所在位置坐標(biāo)和任務(wù)終點(diǎn)坐標(biāo)與矩陣M中相應(yīng)位置坐標(biāo)匹配,比較AGV位置與障礙物位置的相對關(guān)系,確定障礙物相對于AGV的方向。對矩陣M中AGV位置以及任務(wù)終點(diǎn)的周圍進(jìn)行檢查,若周圍為0,則表示沒有障礙物,若為1,則表示有障礙物。在有障礙物的情況下,改進(jìn)A*算法在擴(kuò)展節(jié)點(diǎn)時(shí),若該節(jié)點(diǎn)方向與障礙物所在方向一致,則通過方向函數(shù)對其H值予以修正。方向函數(shù)H*(n)

H*(n)=H(n)+δ×C。

(7)

式中δ為方向系數(shù),根據(jù)具體模型取值。

經(jīng)過懲罰函數(shù)P以及方向函數(shù)H*(n)修正后的評價(jià)函數(shù)F(n)為:

F(n)=G(n)+H(n)+(P+δ)×C。

(8)

如圖6,綠色路徑為傳統(tǒng)A*算法所規(guī)劃,橙色路徑為改進(jìn)A*算法所規(guī)劃,可以看出,改進(jìn)A*算法沒有走到障礙前才進(jìn)行避障,相比于傳統(tǒng)A*算法,在路徑長度不變的情況下減少了轉(zhuǎn)彎次數(shù),可以降低AGV的總行駛時(shí)間。

改進(jìn)A*算法的流程圖如圖7所示:

由式(2)可得,單AGV路徑規(guī)劃綜合評價(jià)函數(shù)LS為:

LS=Kp×Sp/V+N×ta。

(9)

式中:Kp為改進(jìn)A*算法得到得路徑節(jié)點(diǎn)數(shù)量;Sp為路徑節(jié)點(diǎn)長度;V為AGV平均運(yùn)行速度;N為路徑節(jié)點(diǎn)中拐點(diǎn)數(shù)量;ta為AGV每轉(zhuǎn)彎耗時(shí)。

綜合評價(jià)函數(shù)LS反映了改進(jìn)A*算法在減少AGV總行駛時(shí)間方面的優(yōu)化效果,函數(shù)LS的值越小,說明優(yōu)化效果越好。

2.3 算法實(shí)現(xiàn)過程

圖8中,橙色柵格表示貨架,S表示AGV初始位置,D表示AGV終點(diǎn),即目標(biāo)貨架所在位置,現(xiàn)需將S處的貨架送回原處D。

步驟1將起點(diǎn)S點(diǎn)、終點(diǎn)D點(diǎn)位置與障礙矩陣M中相對應(yīng)的位置匹配,對S點(diǎn)和D點(diǎn)之間進(jìn)行障礙檢測,如圖8,D點(diǎn)位于S點(diǎn)的右上方,并確定兩點(diǎn)之間有障礙物。將S點(diǎn)上下左右4個(gè)方向的擴(kuò)展節(jié)點(diǎn)加入open list中,對他們進(jìn)行代價(jià)值計(jì)算時(shí),增加其上方節(jié)點(diǎn)的代價(jià)值;

步驟2檢測終點(diǎn)D周圍障礙物情況,如圖9所示,D的下方一格沒有障礙物,上方一格有障礙物,右側(cè)障礙物數(shù)量低于左側(cè),對open list中的節(jié)點(diǎn)計(jì)算代價(jià)值時(shí),減少其右方節(jié)點(diǎn)的代價(jià)值;

步驟3綜合步驟1 和步驟2計(jì)算open list中的節(jié)點(diǎn)代價(jià)值,由于S點(diǎn)右方節(jié)點(diǎn)代價(jià)值小,將其加入close list中;重復(fù)步驟1和步驟2;

步驟4如圖10,將紅色方格加入open list中,檢測到上方節(jié)點(diǎn)與終點(diǎn)D之間沒有障礙物,對它們進(jìn)行代價(jià)值計(jì)算時(shí),減少上方紅色節(jié)點(diǎn)的代價(jià)值。

步驟5繼續(xù)完成整個(gè)尋路過程,如圖11,其中藍(lán)色路徑代表改進(jìn)的A*算法尋找的路徑,比傳統(tǒng)A*算法尋找的紫色路徑減少了不必要的轉(zhuǎn)彎。

綜上所述,改進(jìn)A*算法可以在擴(kuò)展節(jié)點(diǎn)時(shí)根據(jù)自身、障礙以及目標(biāo)所在位置,通過上述方向函數(shù)不斷修正代價(jià)值以減少不必要的轉(zhuǎn)彎,降低AGV的總行駛時(shí)間。

3 基于短期狀態(tài)預(yù)測的多AGV路徑規(guī)劃方法

3.1 揀選作業(yè)系統(tǒng)的短期運(yùn)行狀態(tài)分析

在本文研究的智慧物流倉儲AGV路徑規(guī)劃中,上文針對單AGV提出了改進(jìn)A*算法,使得單AGV在執(zhí)行多任務(wù)時(shí)能夠減少轉(zhuǎn)彎次數(shù)、避免不必要的路徑節(jié)點(diǎn)?，F(xiàn)提出基于短期狀態(tài)預(yù)測的多AGV路徑規(guī)劃方法,在單AGV路徑規(guī)劃基礎(chǔ)上對多AGV進(jìn)行路徑規(guī)劃。在多AGV路徑規(guī)劃問題中,系統(tǒng)短期運(yùn)行狀態(tài)與貨架數(shù)量、揀選臺數(shù)量、AGV數(shù)量等系統(tǒng)配置相比,不能在系統(tǒng)運(yùn)行過程中提前獲取,而是會隨著搬運(yùn)任務(wù)的處理情況和調(diào)度方案實(shí)時(shí)變化。整個(gè)系統(tǒng)的多AGV路徑規(guī)劃除了考慮對AGV資源的分配,還應(yīng)考慮到對作業(yè)區(qū)域道路資源的分配。尤其是在實(shí)際作業(yè)中,道路資源不是無限制使用的,其分配對系統(tǒng)運(yùn)行效率有著極大的影響。因此,在本文的研究中,將重點(diǎn)考慮短期路段AGV通行量對路徑規(guī)劃的影響。

圖12為某一時(shí)段(100 s)內(nèi)倉儲模型中某6條路段AGV通行量分布圖,可以看出多AGV系統(tǒng)的道路資源的占用情況在系統(tǒng)運(yùn)行過程中并不是均勻的,在1s～20s這段時(shí)間內(nèi),道路2經(jīng)過的AGV比較多,而道路6經(jīng)過的AGV數(shù)量相對較少。而6號路段再20s～60s這段時(shí)間的AGV通行量大幅增加,這就意味著在這一段時(shí)間內(nèi)6號路段更容易發(fā)生擁堵以及沖突等情況,而1、4、5路段則更容易順暢通過。同樣也可以看出在90 s～100 s的時(shí)段內(nèi),路段3的通行量逐漸增加,這同樣表明了AGV在路段3的擁塞沖突的可能性逐漸增加。因此,對于多AGV系統(tǒng)來說,路段的短期AGV通行量對AGV的通行狀態(tài)有著不可忽視的影響,路段資源的合理分配能降低擁堵和沖突幾率。

3.2 基于短期狀態(tài)預(yù)測的路徑規(guī)劃方法

倉儲多AGV系統(tǒng)的路徑規(guī)劃是一個(gè)復(fù)雜且高實(shí)時(shí)性的問題,對于多AGV系統(tǒng)的路徑規(guī)劃方法來說,掌握系統(tǒng)狀態(tài)信息越多越及時(shí),做出合理規(guī)劃的可能性就越大。而單一的規(guī)劃方法如任務(wù)完成時(shí)間最少、AGV總路徑最短等沒有考慮到道路資源的占用情況以及AGV的擁塞、沖突等情況。因此,在單一規(guī)劃方法的基礎(chǔ)上,提出一種基于系統(tǒng)短期狀態(tài)預(yù)測的路徑規(guī)劃方法,通過時(shí)間軸來模擬預(yù)測短期時(shí)段內(nèi)道路的AGV通行量以及可能發(fā)生的沖突碰撞等情況,降低沖突次數(shù),降低任務(wù)總完成時(shí)間。

圖13為短期狀態(tài)預(yù)測下的多AGV路徑規(guī)劃方法流程圖。預(yù)測方法采用按時(shí)間軸進(jìn)行模擬預(yù)測,即對于若干輛AGV,利用改進(jìn)A*算法對其進(jìn)行路徑規(guī)劃,將它們的路徑節(jié)點(diǎn)存放在數(shù)組中。從某一時(shí)刻起,在已知AGV的平均速度以及每轉(zhuǎn)彎耗時(shí)后,上述若干AGV的路徑節(jié)點(diǎn)與時(shí)間軸具有一一對應(yīng)關(guān)系。通過判斷時(shí)間軸上同一位置的節(jié)點(diǎn)是否一致來預(yù)測該節(jié)點(diǎn)是否為沖突節(jié)點(diǎn)。同時(shí),由于每個(gè)路徑節(jié)點(diǎn)與各條路段一一對應(yīng),可以對短期內(nèi)各路段的AGV通行量進(jìn)行預(yù)測,然后在此基礎(chǔ)上建立新的路徑規(guī)劃評價(jià)函數(shù),為AGV和正在請求的任務(wù)進(jìn)行路徑規(guī)劃,以優(yōu)化道路資源使用不平衡現(xiàn)象、減少AGV之間沖突節(jié)點(diǎn)數(shù)量為目標(biāo),得到新的路徑方案。AGV將按照新的路徑方案展開作業(yè),直到系統(tǒng)作業(yè)結(jié)束。

下面給出基于短期狀態(tài)預(yù)測的多AGV路徑規(guī)劃方法詳細(xì)過程:

已知在決策時(shí)刻T0時(shí),系統(tǒng)共有Nagv臺AGV,作業(yè)系統(tǒng)已產(chǎn)生Np個(gè)任務(wù),其中,Nf個(gè)任務(wù)已處理完畢,尚有Nw個(gè)任務(wù)正在執(zhí)行過程中。在未完成的Nw個(gè)任務(wù)中,有Nm個(gè)任務(wù)處于執(zhí)行狀態(tài),有Na個(gè)任務(wù)處于接受狀態(tài),處于這兩種狀態(tài)下的任務(wù)無法重新分配。除此之外,還有Nr個(gè)任務(wù)處于請求狀態(tài),這種狀態(tài)下的訂單可以重新分配。以最短路徑規(guī)劃方法分配Nm和Na個(gè)任務(wù)給數(shù)量為Nv的AGV,每臺AGV執(zhí)行一個(gè)或多個(gè)任務(wù),通過改進(jìn)A*算法給出AGV的行駛路線如式(10)和式(11)所示:

Pathj={Rj1,Rj2,Rj3,…,RjN},

(10)

Stepj={Pj1,Pj2,Pj3,…,PjS}。

(11)

其中:Pathj和Stepj分別表示j號AGV的規(guī)劃行駛路段和路徑節(jié)點(diǎn),RjN表示j號AGV經(jīng)過的路段,PjS表示j號AGV經(jīng)過的路徑節(jié)點(diǎn),N表示對應(yīng)的AGV經(jīng)過的路段數(shù)量,S表示對應(yīng)的AGV經(jīng)過的路徑節(jié)點(diǎn)數(shù)量。路徑節(jié)點(diǎn)與路段屬于映射關(guān)系,每個(gè)路徑節(jié)點(diǎn)都有唯一的路段與之對應(yīng)(交叉節(jié)點(diǎn)只計(jì)算一次)。

在多AGV系統(tǒng)的作業(yè)場景中,有路段數(shù)量為NR的集合,如式(12)所示:

Roads={R1,R2,R3,...,Ri,...,RNR}。

(12)

已知在當(dāng)前時(shí)刻T0,有Nm個(gè)任務(wù)處于執(zhí)行狀態(tài),Na個(gè)任務(wù)處于接受狀態(tài),Nv臺AGV正在運(yùn)行中。T0時(shí)刻,對于j號AGV來說,其路徑節(jié)點(diǎn)如式(11),此時(shí)位于節(jié)點(diǎn)Pjk(1≤k≤S),AGV的平均速度V(單位:m/s)以及節(jié)點(diǎn)之間的距離Sp(單位:m),可以預(yù)測在未來一段時(shí)間t(單位:s)內(nèi),j號AGV行駛節(jié)點(diǎn)數(shù)n至節(jié)點(diǎn)Pj(k+n),節(jié)點(diǎn)數(shù)

n=V×t/Sp。

(13)

由于節(jié)點(diǎn)Pjk到節(jié)點(diǎn)Pj(k+n)與式中的各路段相對應(yīng),對于路段Rk來說,經(jīng)過路段的AGV數(shù)量可以由式(14)和式(15)給出:

(14)

(15)

Nr個(gè)新增待接受任務(wù){(diào)O1,O2,O3,…,Oi,…,ONr-1,ONr}隨機(jī)分配給空閑的數(shù)量為Nagv-Nv的AGV,通過改進(jìn)A*算法得到如式(10)和式(11)的模擬路徑方案,重復(fù)上述過程,在未來一段時(shí)間t內(nèi),路段Rk的新增經(jīng)過的AGV數(shù)量ΔNAGVk由式(15)和式(16)給出:

(16)

上述Nr個(gè)新增任務(wù)得到模擬路徑方案,每個(gè)方案中節(jié)點(diǎn)移動耗時(shí)為tp,

tp=Sp/V。

(17)

若該節(jié)點(diǎn)為拐點(diǎn),由式(1)可知耗時(shí)為ta,則這Nagv-Nv個(gè)AGV的沖突節(jié)點(diǎn)數(shù)量

(18)

其中:Smin為路徑方案中的最小值;Ti和Tj分別表示不同AGV模擬走過相同數(shù)量節(jié)點(diǎn)時(shí)所花費(fèi)的時(shí)間,有:

Ti=tp×s+ta×Kis,

(19)

Tj=tp×s+ta×Kjs。

(20)

其中:s為AGV模擬走過的節(jié)點(diǎn)數(shù)量;Kis為第i輛AGV模擬走過的拐點(diǎn)數(shù)量;Kjs為第j輛AGV模擬走過的拐點(diǎn)數(shù)量;根據(jù)式(19),記Ti(i=1,2,3,…,Nagv-Nv) 中的最大值為Tmax,即為AGV最大完成時(shí)間,由于同時(shí)進(jìn)行路徑規(guī)劃,最大完成時(shí)間也為該批新增任務(wù)完成總時(shí)間。

因此,對于路段AGV通行量NAGV有方差S2,

(21)

多AGV路徑規(guī)劃方法目標(biāo)函數(shù):

(22)

約束條件為:

(22)

多AGV路徑規(guī)劃方法綜合評價(jià)函數(shù)LM:

LM=ξ1×(Tmax+Nc×tb)+ξ2×S2。

(23)

式(22)和式(23)中:tb為每個(gè)沖突節(jié)點(diǎn)帶來的時(shí)間損耗;Nc為沖突節(jié)點(diǎn)數(shù)量;ξ1為時(shí)間權(quán)重;ξ2為方差權(quán)重。

時(shí)間權(quán)重ξ1和方差權(quán)重ξ2的取值與任務(wù)數(shù)量Nr和AGV數(shù)量(Nagv-Nv)有關(guān),應(yīng)使時(shí)間和方差兩者取權(quán)重后數(shù)量級基本一致,具體取值視具體模型而定。式(22)為基于系統(tǒng)短期狀態(tài)預(yù)測的多AGV路徑規(guī)劃方法的目標(biāo)函數(shù):一是最小化多AGV中的最大完成時(shí)間(任務(wù)完成總時(shí)間),二是最小化各路段資源AGV經(jīng)過次數(shù)的方差,以優(yōu)化資源使用不平衡現(xiàn)象。式(23)為基于短期狀態(tài)預(yù)測的多AGV路徑規(guī)劃方法綜合評價(jià)函數(shù),函數(shù)值越小,說明優(yōu)化效果越好。

4 實(shí)驗(yàn)分析

4.1 實(shí)驗(yàn)場景

為了驗(yàn)證本文提出的改進(jìn)A*算法以及多AGV路徑規(guī)劃方法的有效性,采用C#語言在Visual Studio 2019上搭建仿真實(shí)驗(yàn)平臺。如圖14所示為智慧物流倉儲AGV實(shí)驗(yàn)平臺。

實(shí)驗(yàn)場景為智慧物流中“貨到人”分揀系統(tǒng),即一次搬運(yùn)任務(wù)中,AGV需要將目標(biāo)貨架搬運(yùn)至指定分揀臺進(jìn)行分揀作業(yè),待分揀完成后再將貨架搬運(yùn)回原位置,進(jìn)行下一次任務(wù)。圖14中黃色柵格為貨架區(qū),白色柵格為AGV初始區(qū)域,灰色柵格為分揀臺區(qū)域。

4.2 仿真分析

單AGV路徑規(guī)劃中,為了驗(yàn)證改進(jìn)A*算法的有效性,對比傳統(tǒng)A*算法。實(shí)驗(yàn)條件如表1所示,實(shí)驗(yàn)為1臺AGV分別執(zhí)行不同數(shù)量的任務(wù),對比算法為傳統(tǒng)A*算法、Dijkstra算法以及改進(jìn)A*算法。Dijkstra算法屬于廣度優(yōu)先算法,由于需要處理的節(jié)點(diǎn)很多,運(yùn)行耗時(shí)比A*算法長,但能保證找到一條最短路徑,同時(shí)和傳統(tǒng)A*算法一樣,沒有考慮到轉(zhuǎn)彎次數(shù)對AGV總行駛時(shí)間的影響。結(jié)果如圖15和圖16以及表2和表3所示。

表1 算法對比實(shí)驗(yàn)參數(shù)表

表2 算法對比實(shí)驗(yàn)結(jié)果1

表3 算法對比實(shí)驗(yàn)結(jié)果2

如圖15所示,隨著任務(wù)數(shù)量的增多,改進(jìn)A*算法在減少AGV的轉(zhuǎn)彎次數(shù)上效果越來越顯著;由表2可知,改進(jìn)A*算法的每任務(wù)平均轉(zhuǎn)彎次數(shù)相較于傳統(tǒng)A*算法和Dijkstra算法分別降低了25.6%和28.4%;從圖16和表3可以看出,改進(jìn)A*算法在降低AGV總行駛時(shí)間方面顯著優(yōu)于傳統(tǒng)A*算法和Dijkstra算法,相較于后兩者,改進(jìn)A*算法在總行駛時(shí)間上分別降低了21.1%和11.2%。

為了驗(yàn)證基于系統(tǒng)短期狀態(tài)預(yù)測的多AGV路徑規(guī)劃方法的有效性,與最短路徑規(guī)劃方法對比。最短路徑規(guī)劃方法是以完成所有任務(wù)時(shí)AGV總行程最少為目標(biāo)。實(shí)驗(yàn)參數(shù)如表4所示。

表4 基于短期狀態(tài)預(yù)測多AGV路徑規(guī)劃方法實(shí)驗(yàn)參數(shù)表

設(shè)定系統(tǒng)不斷生成總計(jì)100個(gè)任務(wù),由2臺、4臺、6臺等依次遞增的AGV執(zhí)行任務(wù),記錄它們完成任務(wù)時(shí)的沖突節(jié)點(diǎn)個(gè)數(shù)以及總時(shí)間進(jìn)行對比,實(shí)驗(yàn)結(jié)果如圖17和圖18以及表5和表6所示。

表5 基于短期狀態(tài)預(yù)測多AGV路徑規(guī)劃方法實(shí)驗(yàn)結(jié)果1

表6 基于短期狀態(tài)預(yù)測多AGV路徑規(guī)劃方法實(shí)驗(yàn)結(jié)果2

從圖17和表5可以看出,相比于最短路徑多AGV規(guī)劃方法,基于短期狀態(tài)預(yù)測多AGV路徑規(guī)劃方法的AGV平均沖突節(jié)點(diǎn)個(gè)數(shù)降低了23.1%;從圖18和表6可知,在任務(wù)總完成時(shí)間上,基于短期狀態(tài)預(yù)測路徑規(guī)劃方法比最短路徑規(guī)劃方法減少了8.8%。因此,基于短期狀態(tài)預(yù)測路徑規(guī)劃方法可以有效降低AGV之間的沖突節(jié)點(diǎn)個(gè)數(shù)和任務(wù)總完成時(shí)間。

5 結(jié)束語

本文針對多AGV系統(tǒng)在路徑規(guī)劃中存在的轉(zhuǎn)彎次數(shù)多、沖突節(jié)點(diǎn)多的問題提出了基于改進(jìn)A*算法和基于系統(tǒng)短期狀態(tài)預(yù)測路徑規(guī)劃方法,實(shí)驗(yàn)結(jié)果表明,改進(jìn)A*算法相比于傳統(tǒng)A*算法能夠有效減少轉(zhuǎn)彎次數(shù),降低AGV行駛總時(shí)間;系統(tǒng)短期狀態(tài)預(yù)測多AGV路徑規(guī)劃方法相比于最短路徑規(guī)劃方法能夠有效降低多AGV在路徑中的沖突節(jié)點(diǎn)個(gè)數(shù)和任務(wù)總完成時(shí)間。其中短期狀態(tài)預(yù)測路徑規(guī)劃方法中將AGV所在節(jié)點(diǎn)位置、AGV平均速度以及每轉(zhuǎn)彎耗時(shí),與時(shí)間軸相結(jié)合來預(yù)測未來一段時(shí)間內(nèi)的各路段AGV通行量,雖然足夠精確,但由于計(jì)算量較大,導(dǎo)致運(yùn)行效率不高,仍有較大改進(jìn)空間,在未來的工作中,可以考慮引入LSTM(long short-term memory)模型預(yù)測,提高程序運(yùn)行效率。