陳寧，梁歡歡，孔祥希，胡立渝，韓吉

（南京農(nóng)業(yè)大學(xué)工學(xué)院，南京 210000）

針對智能停車庫中的運輸車輛機器人AGV，首先根據(jù)停車場結(jié)構(gòu)示意圖，對某一時刻停車場實際路網(wǎng)進行抽象，將要求的路徑優(yōu)化問題轉(zhuǎn)化為最短路徑問題。與實際問題相結(jié)合確定停車場AGV 路徑優(yōu)化的算法為Dijkstra 算法，最后通過MATLAB 軟件編程算法并進行求解，算出每個空閑車位相對應(yīng)的最短的存取車路徑及距離總和，提高AGV存取車效率，節(jié)省時間。結(jié)果證明Dijkstra 算法在AGV 存取車路徑優(yōu)化中的可行性和實用性。

智能停車庫；運輸車輛機器人；最短路徑；Dijkstra 算法

0 引言

隨著當今社會經(jīng)濟的快速發(fā)展，全國汽車的保有量也在不斷上升。汽車的持有量急劇增長與停車位稀缺的矛盾亟需解決[1]。最直接的解決方法就是建立停車場，但相對應(yīng)的停車場內(nèi)部的車位更加擁堵，使得停車變成了候車過程久、停車過程亂、取車過程忙的現(xiàn)象。為了解決這種現(xiàn)象，建立一種高性能的智能化停車場成為一種必然趨勢。當前市面上應(yīng)運而生了很多種類的智能停車庫，例如智能立體停車庫、半自動立體停車庫以及基于運輸車輛機器人的智能化停車庫等?；贏GV 的智能停車庫與別的類型停車庫相比，具有占地面積小、車位利用率高、性價比及可靠性高等特點[2]。在實際中調(diào)查中我們發(fā)現(xiàn)運輸車輛機器人AGV 在存取車路徑的選擇上還存在問題，大部分是依靠人工在后臺控制，并不能智能選擇最優(yōu)路徑使得存取車路徑最短而減少工作耗時。解決運輸車輛機器人存取車路徑優(yōu)化算法問題，是發(fā)展AGV 智能車庫的基礎(chǔ)。針對路徑優(yōu)化問題，隨著算法的不斷發(fā)展，Dijkstra 算法、A*算法、遺傳算法以及蟻群算法等也被廣泛用于解決各領(lǐng)域路徑規(guī)劃問題[3]。

在分析了智能停車場的系統(tǒng)組成和運輸車輛機器人的工作原理后，本文著重研究運輸機器人的路徑優(yōu)化問題，該問題的優(yōu)化使得運輸機器人在較短的時間內(nèi)走最短的存取雙向路線，即AGV 將待取車從取車車位運輸?shù)匠鋈肟?，再將待存車從出入口運輸?shù)阶罱哲囄?。此?yōu)化方法將為我們節(jié)省更多的存取車時間，提高智能停車場的運行效率，減少運輸車輛機器人的耗能。針對智能停車庫中AGV 存取車路徑優(yōu)化問題，建立模型車車場模型，本文研究了幾種算法后進行比較，最后選取較為適合的算法作為本文的主要研究算法，編寫程序進行求解，從而得出優(yōu)化后的該選擇的路徑。

1 AGV在智能停車場的應(yīng)用

本文所涉及的AGV 智能停車場系統(tǒng)主要包括機械系統(tǒng)、管理系統(tǒng)、監(jiān)控系統(tǒng)及其他系統(tǒng)等如圖1所示。

智能停車場中，在正常的電磁導(dǎo)引系統(tǒng)環(huán)境和車載通訊系統(tǒng)環(huán)境下，AGV 處于待機狀態(tài)。當有車輛要求停車時，地面管理調(diào)度系統(tǒng)通過機載通訊系統(tǒng)向運輸車輛機器人下達作業(yè)指令，通過上位機系統(tǒng)比對停車場內(nèi)車位、車輛停放信息，然后智能停車場管理系統(tǒng)的主控計算機通過算法可迅速得到最佳車位并進行路徑的規(guī)劃，車載計算器接受其他系統(tǒng)獲取到的環(huán)境信息和路徑信息以及上位機系統(tǒng)控制信號所規(guī)劃的路徑。在接受到運輸任務(wù)后，AGV 開始執(zhí)行任務(wù)，驅(qū)動系統(tǒng)驅(qū)動AGV 運輸車輛實現(xiàn)AGV 的沿著所規(guī)劃的路徑進行運行，將車運送到所指定的位置。

圖1 智能停車場系統(tǒng)結(jié)構(gòu)圖

運輸車輛機器人結(jié)構(gòu)圖如圖2 所示。

圖2 停車AGV結(jié)構(gòu)圖

2 問題描述與建模

2.1 問題描述

智能停車場系統(tǒng)通過檢測裝置來獲取車庫中停車位的占用情況，根據(jù)AGV 當前狀態(tài)，快速地為AGV 找到一個最佳車位并規(guī)劃出從當前車位到該車位的最優(yōu)路徑，保證AGV 在較短時間內(nèi)完成車輛存取車任務(wù)，以便提高運輸車輛機器人的運輸效率。

本文假定：①停車場的出口與入口在同一位置；②運輸車輛機器人完成存車命令后將在該車位處待機，等待下一命令；③行車道寬度滿足AGV 最大轉(zhuǎn)彎半徑，道路寬度需保證單個AGV 正常行駛；④忽略AGV 實際大小，把AGV 和停車位視為質(zhì)點。

2.2 停車場抽象結(jié)構(gòu)模型

假設(shè)停車位寬為3 米，長為6 米，行車道寬度為6米，這里將智能停車場中位置信息，例如空車位、交叉口、出入口等抽象為節(jié)點[4]。智能停車場入（出）口為S（1），交叉路口為2-10，當前空閑車位為P1-P10，表示可以用來存放車輛，其余的車位均已被占用。編號標記如圖3 所示。

圖3 停車場結(jié)構(gòu)示意圖

以O(shè) 點為原點建立坐標系，把每個車位看作一個質(zhì)點，每個質(zhì)點的坐標為該車位中心點的坐標[5]，每個交叉路口點的坐標為該交叉路口中心點的坐標，圖中的入口、出口、有效停車位以及交叉路口的坐標就可以被確定如表1 所示。下一步的研究工作將以此模型為基礎(chǔ)，研究運輸車輛機器人最優(yōu)路徑規(guī)劃算法問題。

表1 坐標點

2.3 最佳車位模型

根據(jù)上述可知，本文所研究的尋找最優(yōu)路徑的問題就是運輸車輛機器人把待取車運送到出入口后，再將待存車運進停車場時，對余下的空車位按照設(shè)定的計算規(guī)則進行分析處理，得到一個最合適的停車位，并找到該車位的最短路徑。若某個空閑車位為Pi（i=1，2，...，n），運輸車輛機器人把某一固定車位的待取車運送到出入口的最短路徑為path（P，s），運輸機器人把待存車送到某空閑車位對應(yīng)的入場過程的最短路徑為path（s，Pi）。

則運輸車輛機器人存取車過程對應(yīng)的整個最短路徑長度為：

則最佳車位所對應(yīng)的最短路徑的長度可表示為：

2.4 路網(wǎng)的構(gòu)建

按照圖論[6，7]的構(gòu)圖方法，某一時刻停車場路網(wǎng)是靜態(tài)的，結(jié)合上述停車場的結(jié)構(gòu)示意圖和停車場內(nèi)空閑車位的信息，可以把圖示停車場結(jié)構(gòu)示意圖的構(gòu)建成為一個帶權(quán)的有向圖，AGV 在停車場靜態(tài)路網(wǎng)里的存取車路徑優(yōu)化問題就可轉(zhuǎn)換成求解帶權(quán)圖中任意指定的節(jié)點間到其他點的最短路徑問題。

停車場內(nèi)路網(wǎng)有向圖可以用如下來表示：

圖中停車場內(nèi)的出入口（S）、行車道交叉路口、空閑車位可以構(gòu)成一個頂點集V，每一條路徑對應(yīng)一條弧E，連接兩頂點之間的路徑長度看作為弧的權(quán)值，用W 表示，如果兩個頂點之間沒有連通的道路，那么權(quán)值可以用∞表示，所轉(zhuǎn)化成為的賦權(quán)圖如圖4 所示。

3 Dijkstra算法

有很多算法都可以用來求出在某個賦權(quán)有向圖中的任意兩個結(jié)點之間的最短路徑，如蟻群算法[8]、遺傳算法、Dijkstra[9]算法等。由于本文研究的是應(yīng)用在停車場中最短路徑問題，所以賦權(quán)圖中的各條邊的權(quán)值均為非負，相對于其他算法而言，Dijkstra 算法更適用于此場景下最短路徑的問題研究。Dijkstra 算法由荷蘭E.W.Dijkstra 提出的一個典型的單源最短路徑算法，用于計算賦權(quán)圖上一個節(jié)點到其他所有節(jié)點的最短路徑。算法從起始點開逐個搜索下一鄰接點，直到搜索到終點為止。Dijkstra 是很具有代表性、經(jīng)典的最短路徑算法，并且在實際中應(yīng)用廣泛。1969年Zhan 等使用實際交通網(wǎng)絡(luò)測試了15 種不同的最短路徑算法，結(jié)果表明，Dijkstra 算法計算某一點到其他點的最短路徑最快捷[10]。

圖4 帶權(quán)有向圖

Dijkstra 算法思想為：設(shè)G=（V，E，W）是一個賦權(quán)有向圖，把有向圖中頂點集合V 分為兩組，第一組我們就稱它為A 集合，代表已經(jīng)求出源點到該點的最短路的點的集合，開始時A 集合中只包含源點v0。另一個我們稱為B 集合，代表未求出源點到該點的最短路徑的點的集合。找出點集B 中最短路徑的頂點并將其加入到點集A 中，接著更新B 中的頂點及對應(yīng)的最短路徑按，不斷進行以下操作，按照最短路徑長度遞增的順序逐漸把B 集合中的點加入到A 集合中，直到點集B中的點全部轉(zhuǎn)移到點集A 中。

算法步驟如下：

步驟1：初始化行駛的最短路徑集合A，最開始時集合A 只包含始點即出入口設(shè)為v0，除v0之外的其他頂點都在B 集合中。即A={v0}，B={其他頂點}；

步驟2：從集合B 中選取一個距離v0最小的頂點再將vk加入到集合A 中（該選定的距離就是v0到vk的最短路徑長度）。

步驟3：然后對B 中點到源點的距離進行一次更新，就是以vk為中間節(jié)點，修改A 中各頂點到源點的距離。如果經(jīng)過vk，可以使v0到某個未訪問過的頂點距離變小，則修正該最小距離。

步驟4：重復(fù)步驟2 和3 直到所有頂點都包含在集合A 中。

4 MATLAB編程求解

根據(jù)上述算法步驟進行編程，在MATLAB 環(huán)境下實現(xiàn)Dijkstra 算法，驗證算法的合理性和正確性。以圖所示的停車場為實驗場景，假設(shè)H15 號（H 區(qū)從左往右第15 個車位）有一輛車需要取出，向AGV 運輸管理系統(tǒng)發(fā)送任務(wù)請求，運輸車輛機器人把H15 號的車運送到出入口，再將出入口的待存車運送到某一空車位。管理系統(tǒng)在收到任務(wù)后進行路徑的規(guī)劃，并將規(guī)劃的路徑下發(fā)給對應(yīng)AGV，從H15 到達出入口路徑如圖5所示，經(jīng)過路徑即為：H15---9---6---3---2---S（1），最短路徑為：97.5。

圖5 H15到達S的最短路徑及長度

采用本算法進行實驗可以求出AGV 從H15 到達出入口，再從出入口把待存車到達所有空閑車位的最短路徑，如表2 所示。

表2 最短路徑及總長

通過MATLAB 算法編程可以求解出每個空閑車位相對應(yīng)的最短的存取車路徑及距離總和，驗證了算法在智能停車場環(huán)境中的可行性和準確性。這樣，管理系統(tǒng)在接受到運輸任務(wù)后，計算器運行編程好的Dijkstra 算法求出空閑車位中的最佳車位，指令A(yù)GV 的沿著所規(guī)劃的路徑進行運行，將車運快速準確地送到所指定的位置。實現(xiàn)了運輸車輛機器人存取車的高效有序，具有十分重要的意義。

5 結(jié)語

根據(jù)目前的現(xiàn)狀，本文根據(jù)智能車庫中運輸車輛機器人存取車路徑所存在的不足進行研究，對其路徑規(guī)劃算法展開研究?；诋斍吧鐣悄芙煌ǖ陌l(fā)展和停車場的實際情況，建立了停車場結(jié)構(gòu)模型，分析了停車場路網(wǎng)，并將路網(wǎng)抽象成帶權(quán)有向圖，將所求最優(yōu)路徑問題轉(zhuǎn)化為了最短路徑問題。在對幾種最短算法分析比較后，確定了使用Dijkstra 算法進行課題的研究。通過Dijkstra 算法的理論知識和MATLAB 求解，幫助運輸車輛機器人找到了最佳車位，求出了各個車位分別對應(yīng)的最短路徑及距離，使得運輸車輛機器人的系統(tǒng)得到優(yōu)化，極大地縮短了AGV 的工作時間，改善了停車場內(nèi)部的存取車運行效率，節(jié)約耗能和成本。