運(yùn)輸車輛機(jī)器人存取車路徑優(yōu)化算法研究

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

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

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

智能停車庫(kù)；運(yùn)輸車輛機(jī)器人；最短路徑；Dijkstra 算法

0 引言

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

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

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

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

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

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

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

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

2 問(wèn)題描述與建模

2.1 問(wèn)題描述

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

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

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

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

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

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

表1 坐標(biāo)點(diǎn)

2.3 最佳車位模型

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

則運(yùn)輸車輛機(jī)器人存取車過(guò)程對(duì)應(yīng)的整個(gè)最短路徑長(zhǎng)度為：

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

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

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

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

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

3 Dijkstra算法

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

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

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

算法步驟如下：

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

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

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

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

4 MATLAB編程求解

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

圖5 H15到達(dá)S的最短路徑及長(zhǎng)度

采用本算法進(jìn)行實(shí)驗(yàn)可以求出AGV 從H15 到達(dá)出入口，再?gòu)某鋈肟诎汛孳嚨竭_(dá)所有空閑車位的最短路徑，如表2 所示。

表2 最短路徑及總長(zhǎng)

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

5 結(jié)語(yǔ)

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