一種倉儲AGV路徑規(guī)劃最優(yōu)策略方法的實現(xiàn)

王海霞

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

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

中圖分類號：TP23 文獻標志碼：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的應用需求日漸增多，因其柔性好、可靠性高、適用性強的特點，并且能實現(xiàn)生產(chǎn)搬運功能的集成和自動化，在各個行業(yè)中都得到廣泛應用，其需求量正以井噴式的勢頭增長，如智能立體庫、智能工廠、海港及碼頭等，隨著自動化立體倉庫和柔性制造系統(tǒng)的廣泛應用，AGV作為智能物流系統(tǒng)連續(xù)化的重要組成部分，其精確性和高效性起著至關(guān)重要的作用[1]。

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

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

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

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

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

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

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

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

①不必掃描1-n，只需遍歷由pos頂點可以到達的頂點即可，使用vector存儲圖，或者使用鏈式前向星;

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

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

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

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

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

主要流程如下：

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

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

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

④同時在啟動任務中設置充電和停靠任務并綁定所有車輛，根據(jù)三段式電量百分比指標對車輛進行充電指示;當車輛完成裝卸且無新住務后，按照就近停靠原則停泊。

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

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

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

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

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

4結(jié)束語

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

參考文獻

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

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

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

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

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

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