王海霞

摘要：路徑規(guī)劃是自動導(dǎo)引車系統(tǒng)（ AGVS）路徑管理系統(tǒng)的關(guān)鍵技術(shù)，主要用來規(guī)劃智能倉儲中單臺或多臺自動導(dǎo)引車（ AGV）的作業(yè)路徑。研究并檢驗(yàn)了一種基于迪杰斯特拉算法的堆優(yōu)化路徑規(guī)劃策略方法，通過倉庫多臺AGV路徑規(guī)劃案例，表明可以實(shí)現(xiàn)最優(yōu)的單車及多車路徑規(guī)劃策略，縮短了車輛在倉庫中的作業(yè)時(shí)間，提高了AGV的使用效率。

關(guān)鍵詞：自動導(dǎo)引車系統(tǒng)路徑管理系統(tǒng);迪杰斯特拉算法;優(yōu)化策略

中圖分類號：TP23 文獻(xiàn)標(biāo)志碼：A 文章編號：1008-1739（ 2021）09-63-4

Application of an Optimal Strategy Method for Warehouse

AGV Path Planning

WANG Haixia

（School of Application Technology， Suzhou Universiy. Kunshan 215325， China）

Abstract： The path planning is a key technology in the path management system of Automatic Guided Vehicle System （AGVS），which is mainly used to plan the operation path of single or multiple Automatic Guided Vehicles （AGV）s in intelligent storage. A pathplanning strategy for heap optimization based on Dijkstra algorithm is studied and tested. Through a path planning case of multipleAGVs in a warehouse. it is verified that this method can achieve the optimal path planning strategy for single vehicle and multiplevehicles. shorten the operation time of the vehicle in the warehouse. and improve the use efficiency of AGVs.

Keywwds： AGVS path management system; Dijkstra algorithm; optimizing strategy

O引言

目前國內(nèi)對AGV的應(yīng)用需求日漸增多，因其柔性好、可靠性高、適用性強(qiáng)的特點(diǎn)，并且能實(shí)現(xiàn)生產(chǎn)搬運(yùn)功能的集成和自動化，在各個(gè)行業(yè)中都得到廣泛應(yīng)用，其需求量正以井噴式的勢頭增長，如智能立體庫、智能工廠、海港及碼頭等，隨著自動化立體倉庫和柔性制造系統(tǒng)的廣泛應(yīng)用，AGV作為智能物流系統(tǒng)連續(xù)化的重要組成部分，其精確性和高效性起著至關(guān)重要的作用[1]。

倉儲AGV路徑規(guī)劃的最優(yōu)策略方法，能夠?qū)GV進(jìn)行最優(yōu)策略下的單車調(diào)度和多車調(diào)度，提高了AGV運(yùn)行效率。目前這種調(diào)度方法成功用于倉儲智能化物流系統(tǒng)，經(jīng)現(xiàn)場證實(shí)，這種路徑規(guī)劃策略快速、準(zhǔn)確、有效，比普通方法減少耗時(shí)15%以上。文中最優(yōu)策略方法的實(shí)現(xiàn)采用了基于Dijkstra的堆優(yōu)化算法，是最短路徑優(yōu)化算法之一，結(jié)合路徑管理系統(tǒng)的starPlantOverview程序，能夠?qū)崿F(xiàn)AGV在智能倉儲中的應(yīng)用。

1倉儲AGV路徑管理系統(tǒng)的功能

倉儲AGV路徑管理系統(tǒng)有以下幾個(gè)功能：監(jiān)控管理、路徑規(guī)劃、交通調(diào)度控制、車隊(duì)管理和智能交互，功能描述如表1所示，主要目的是管理、監(jiān)控和調(diào)度AGV執(zhí)行搬運(yùn)作業(yè)任務(wù)。系統(tǒng)接收工廠信息管理系統(tǒng)（ ERPIMESIWMS）的作業(yè)任務(wù)，對AGV進(jìn)行自動交通管理、監(jiān)控和接收AGV的狀態(tài)信息，并向工廠信息管理系統(tǒng)反饋任務(wù)執(zhí)行情況。AGV則通過無線網(wǎng)絡(luò)與系統(tǒng)通信，按照規(guī)劃的路徑執(zhí)行作業(yè)任務(wù)。

2路徑優(yōu)化算法策略

路徑管理系統(tǒng)的關(guān)鍵技術(shù)是路徑規(guī)劃，在進(jìn)行路徑選擇時(shí)必須高效規(guī)劃出一條從起始位置到目標(biāo)位置的最優(yōu)路徑，通常采用最短路徑的策略，在一個(gè)賦權(quán)圖中找到一個(gè)節(jié)點(diǎn)到周圍所有節(jié)點(diǎn)具有最小權(quán)的路徑。這是因?yàn)樵诰€路優(yōu)化中，如果優(yōu)化指標(biāo)與路程的相關(guān)性較強(qiáng)，而與其他因素相關(guān)性較弱時(shí)，即以最短路程為準(zhǔn)則[2]。比如倉儲或車間運(yùn)輸線路選取時(shí)，從出發(fā)地到目的地之間有多種線路可以選取，效率指數(shù)在預(yù)測概率相等時(shí)，考慮以最短路徑為準(zhǔn)則[3]。 本文路徑規(guī)劃使用的是在迪杰斯特拉算法基礎(chǔ)上的優(yōu)化算法。DIJ算法是求解單源最短路徑問題的經(jīng)典算法，常用于智能車在非結(jié)構(gòu)化靜態(tài)環(huán)境中進(jìn)行路徑規(guī)劃，是一種按路徑長度遞增的次序產(chǎn)生最短路徑的算法，核心思想是以遍歷形式找到圖中所有節(jié)點(diǎn)的最短路徑，可求單源有權(quán)圖中的最短路[4-6]。

DIJ算法時(shí)間復(fù)雜度為O（（m+n ）logn），m表示邊數(shù)，n表示點(diǎn)數(shù)，在實(shí)際應(yīng)用中速度慢、效率低。但如果使用優(yōu)先隊(duì)列進(jìn)行堆優(yōu)化，優(yōu)化后每次調(diào)整的時(shí)間復(fù)雜度降為0（ elogn），其中e為頂點(diǎn)邊數(shù)，這種優(yōu)化時(shí)效}生較好。堆優(yōu)化的原則是使用小根堆，用優(yōu)先隊(duì)列來維護(hù)這個(gè)最小的點(diǎn)，從而大大減少DIJ算法的時(shí)間復(fù)雜度，算法步驟如表2所示。 堆優(yōu)化是利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法（此處針對小根堆），每次將堆頂提出，即為當(dāng)前最小值，將堆的末端子節(jié)點(diǎn)放到堆首，之后與左右節(jié)點(diǎn)比對，與其中較小的交換，直到堆中的最小值位于根節(jié)點(diǎn)重新成為小根堆。

在堆中假設(shè)s為源點(diǎn)，t為終點(diǎn)，u為邊界點(diǎn)，v為內(nèi)部點(diǎn)。首先將源點(diǎn)設(shè)為邊界點(diǎn)dis，令其為O，其余點(diǎn)為外部點(diǎn)。將所有邊界點(diǎn)加入堆中，每次取堆頂元素（非邊界點(diǎn)而是內(nèi)部點(diǎn)），每個(gè)點(diǎn)的dis值會更新多次，每次入堆最小的dis值最先出堆，出堆時(shí)更新其周圍點(diǎn)的dis值，并將其加入到內(nèi)部點(diǎn)中，繼續(xù)循環(huán)，直到找到終點(diǎn)的最短路徑就可以提前退出循環(huán)，這其中一個(gè)點(diǎn)的dis值會被更新多次并多次入堆，直接在堆里更改它的dis值，并重排堆元素，時(shí)間復(fù)雜度仍舊是O（logn）。

基于DIJ堆優(yōu)化算法程序流程如圖1所示，其特點(diǎn)在于：

①不必掃描1-n，只需遍歷由pos頂點(diǎn)可以到達(dá)的頂點(diǎn)即可，使用vector存儲圖，或者使用鏈?zhǔn)角跋蛐?

②每次找出一個(gè)距離源點(diǎn)最短的頂點(diǎn)，然后把這些點(diǎn)存起來，按照距離關(guān)鍵字進(jìn)行查找;

③內(nèi)部實(shí)現(xiàn)為小根堆，滿足動態(tài)的插入，在0（1）的時(shí)間內(nèi)直接取出最小點(diǎn)并結(jié)合①，使得總時(shí)間復(fù)雜度從O（nX2）降到O（Vlogn+VE），對稀疏圖很有效果。

3基于堆優(yōu)化策略的項(xiàng)目應(yīng)用

本路徑管理系統(tǒng)優(yōu)化策略在多個(gè)項(xiàng)目中使用，在管理軟件中運(yùn)行starPlantOverview程序，完成項(xiàng)目路徑制作，系統(tǒng)對接工廠制造執(zhí)行計(jì)劃系統(tǒng)ERP和智能化倉儲系統(tǒng)WMS，按照存儲要求，實(shí)現(xiàn)生產(chǎn)原料和成品的自動出入庫。以系統(tǒng)在智能化倉儲系統(tǒng)項(xiàng)目中的具體應(yīng)用來說明堆優(yōu)化實(shí)際應(yīng)用，該倉庫由新舊2間立體庫組成，總建筑面積650 1112，如圖2所示。其物流系統(tǒng)主要采用AGV方式和人工入庫方式相結(jié)合，項(xiàng)目使用了3臺激光導(dǎo)向AGV系統(tǒng)，貨架通道設(shè)置為2.8 m，行駛通道設(shè)為3m。

當(dāng)路徑管理系統(tǒng)接收到ERP/MES/WMS的有效任務(wù)指令后，系統(tǒng)按照DIJ堆優(yōu)化原則選擇AGV最優(yōu)路徑，分配作業(yè)任務(wù)給空閑AGV，同時(shí)生成有效路徑圖，如圖3所示，AGV按照系統(tǒng)路徑指令執(zhí)行任務(wù)，任務(wù)流程如圖4所示。當(dāng)3臺AGV同時(shí)工作時(shí)，按照入貨口分開原則并遵循特定的路徑規(guī)劃策略，以確保AGV不會發(fā)生碰撞，規(guī)劃策略主要有速率調(diào)整法、交通規(guī)則法和優(yōu)先級法。

主要流程如下：

①當(dāng)兩車在十字路口相遇時(shí)，根據(jù)時(shí)間優(yōu)先法進(jìn)行車輛選擇，先申請占用點(diǎn)位的車輛通過路口，后申請車輛采用速率調(diào)整法在原點(diǎn)位等待，當(dāng)前車通過后，隔離區(qū)解除再行通過。

②當(dāng)兩車占用一條路線時(shí)，通過枚舉重疊進(jìn)行相同方向和交叉路口構(gòu)建重疊路線的交通規(guī)則來進(jìn)行避撞。

③按照入貨口產(chǎn)品和原料的狀態(tài)要求，為每臺AGV制定優(yōu)先級。當(dāng)優(yōu)先級低的AGV遇到優(yōu)先級高的AGV時(shí)，低者給高者讓路并在重疊路徑最近點(diǎn)位進(jìn)行等待。

④同時(shí)在啟動任務(wù)中設(shè)置充電和停靠任務(wù)并綁定所有車輛，根據(jù)三段式電量百分比指標(biāo)對車輛進(jìn)行充電指示;當(dāng)車輛完成裝卸且無新住務(wù)后，按照就近?？吭瓌t停泊。

在該項(xiàng)目中假設(shè)源點(diǎn)為s點(diǎn)并將它設(shè)為邊界點(diǎn)，dis[s]-0，其余點(diǎn)為外部點(diǎn)，將所有邊界點(diǎn)加入堆中，建立2個(gè)數(shù)組dis和VIS，dis[i]表示從源點(diǎn)出發(fā)到編號為i點(diǎn)的距離，即DP1一{v}，DP（n）包含除s外的其他DP點(diǎn)，DP（n）的dis值為無窮大，如果找到一條s到達(dá)點(diǎn)j的更短路徑，dis[J]將更新為這條更短路徑的距離，vis[j]表示j點(diǎn)的dis[j]，vis[j]=true表示j點(diǎn)的dis值已經(jīng)確定是最小值，初始時(shí)所有點(diǎn)的VIS值都為false。每次取堆頂元素，最小的那個(gè)dis值最先出堆，出堆時(shí)更新其周圍點(diǎn)的dis值，并將其加入到內(nèi)部點(diǎn)中，只要找到終點(diǎn)的最短路徑則提前退出，如果沒有繼續(xù)用遞歸算法使根節(jié)點(diǎn)為最小值，重復(fù)以上步驟，直至所有點(diǎn)的VIS值都為true。

項(xiàng)目實(shí)施過程中，分別采用了Dijkstra算法路徑規(guī)劃和基于Dijkstra的堆優(yōu)化算法路徑規(guī)劃進(jìn)行AGV作業(yè)測試，調(diào)度分2種情況：

①規(guī)劃20個(gè)DP點(diǎn)：堆優(yōu)化算法耗時(shí)比DIJ算法的調(diào)度系統(tǒng)少（m一2）[（ L1/S1）+（ L2/S2）]。

②規(guī)劃20個(gè)DP點(diǎn)、5個(gè)轉(zhuǎn)彎，堆優(yōu)化算法耗時(shí)比DIJ算法的調(diào)度系統(tǒng)少（m一2）[（L1/S1）]+（ L2/S2 ）l+Tt。其中，L1為減速距離;S1為減速度;L2為加速距離;S2為加速度;T1為可能產(chǎn)生的多余轉(zhuǎn)彎耗時(shí)。

根據(jù)現(xiàn)場統(tǒng)計(jì)，在相同DP點(diǎn)個(gè)數(shù)情況下，該算法可以節(jié)約時(shí)間4 sl點(diǎn);在相同個(gè)數(shù)DP點(diǎn)情況下和相同轉(zhuǎn)彎個(gè)數(shù)情況下，該算法可以節(jié)約時(shí)間4 sl點(diǎn)+5 s（多余轉(zhuǎn)彎耗時(shí)）。

4結(jié)束語

針對智能立體庫AGV路徑規(guī)劃問題，介紹了一種AGV路徑規(guī)劃最優(yōu)策略方法在實(shí)際項(xiàng)目中的應(yīng)用。以堆優(yōu)化算法彌補(bǔ)了DIJ算法耗時(shí)長效率低的缺點(diǎn)，并通過某倉儲智能物流路徑規(guī)劃在車輛調(diào)度中的實(shí)際應(yīng)用，驗(yàn)證了優(yōu)化算法時(shí)間復(fù)雜度的降低，提高了AGV的執(zhí)行效率。

參考文獻(xiàn)

[1]李煒文.自動化立體倉庫AGV路徑規(guī)劃研究[D].長春：吉林大學(xué)，2020.

[2]余娜娜，李鐵克，王柏琳，等.自動化分揀倉庫中多AGV調(diào)度與路徑規(guī)劃算法[J].計(jì)算機(jī)集成制造系統(tǒng)，2020，26（1）：171-180.

[3]吳家琴.基于迪克斯特洛模型的物流運(yùn)輸最短路徑選擇[J].物流技術(shù)，2013，32（21）：193-195.

[4]李全勇，李波，張瑞，等.基于改進(jìn)Dijkstra算法的AGV路徑規(guī)劃研究[J].機(jī)械工程與自動化，2021（1）：23-25.

[5]郭亞銘，武照云，張中偉，等.柔性制造車間單AGV節(jié)能路徑規(guī)劃研究[J]組合機(jī)床與自動化加工技術(shù)，2020（10）：181-184.

[6]姜辰凱，李智，盤書寶，等.基于改進(jìn)Dijkstra算法的AGVs無碰撞路徑規(guī)劃[J].計(jì)算機(jī)科學(xué)，2020，47（8）：272-277.