AGV智能停車庫車位規劃算法研究

李飛飛

（上海海事大學信息工程學院，上海 201306）

0 引言

當前，越來越多的人將汽車作為代步工具，隨之而來的是停車場車位嚴重不足、存取車效率低等問題，嚴重影響了人們自駕出行的體驗感。基于此種社會背景下，對于如何緩解泊車壓力已成為提高社會生活舒適性的關鍵問題。因此基于自動導引運輸車（AGV）的自動化停車場應運而生。AGV智能停車具有空間利用率高、存取車過程更加安全等優點。近年來，產生了多種基于多AGV進行路徑規劃以提高存取車效率的方法。文獻[1-3]采用時間窗以及優先級策略或者Dijka?tra算法去規劃泊車系統的最佳行駛路徑，結果表明，所提出的路徑規劃方法有效解決了目前多AGV路徑規劃柔性差、易出現死鎖碰撞沖突等問題。文獻[4-6]采用一種基于遺傳算法的路徑搜索方法，此方法提高了全局的搜索能力。以上文獻所提及的方法都是在原有停車場車位分布不變的情況下，旨在通過規劃路徑去提高存取車的效率。

本文嘗試通過去規劃停車場的最佳物理車位的分布位置，以期從源頭上縮短存取車路徑等問題。

1 問題描述及數學抽象

本文是在一個空白停車場背景下去探索車位物理分布的方法，由于AGV的行車道路比普通停車場窄，一般寬度和車位寬度一致即可，故可將空白停車場的初始狀態全都規劃為大小一致的長方形并且所有的長方形除去出入口之外都為待規劃車位。此時，空白停車場的初始狀態如圖1所示：

圖1 空白停車場初始車位狀態

其中，五邊形填充的為停車場的出入口，長方形填充的為所有待選車位。

本文需要通過尋找車位位置的算法從所有待選車位中選出最大的可使用的車位數量，被選中的待選車位點設置為一個車位，未被選中的待選車位點設置為道路，同時需確保每一個車位點都能夠成功到達出入口。

將圖1中的矩形待選車位和六邊形出入口都抽象形成一個點，那么便可以將停車場地圖信息抽象成網格圖的形式，可將網格圖表示成矩陣如下所示：

其中，矩陣中的元素代表圖1中矩形停車場所抽象成的待規劃車位以及停車場的出入口。若待規劃車位未被選定為車位，則代表道路信息。利用車位尋找算法去確定所有待規劃車位點中哪些為車位、哪些為道路。

2 基于Dijkstra算法的部分最優車位規劃算法的實現

Dijkstra算法是由荷蘭計算機科學家狄克斯特拉于1959年提出的。是從一個頂點到其余各頂點的最路徑算法，解決的是有向圖中最短路徑問題。Dijkstra算法主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。

本文中基于Dijkstra的部分最優車位規劃算法的內容如下：

（1）將停車場地圖信息抽象為圖2中所示的矩陣形式。

（2）從所有待規劃車位點（00,01,02…0n;10,11,12…1n；…；m0,m1,m2…mn）中（去除出口、入口）隨機選擇 t（t＜＜m*n）個沒有任何偏好的車位點作為初始車位組合，記為 G=（a1,a2,a3,…,at）,并確保 t個車位點都能避開阻礙到達出入口。

（3）在初始車位組合的基礎上篩選下一個最優車位點，過程如下：

將去除初始車位點及出入口點后的每一個待規劃車位點逐一添加入車位初始組合中，每添加一個點進入初始車位點后計算初始車位組合中所有點到達出口及入口的距離和，按照從小到大的順序排列，記為（at+1,at+2,at+3,at+4,…,amn-2）,將距離和最小的加入車位組合中，即將at+1加入G中，驗證車位組合G中的點是否都能避開阻礙到達出入口，若組合中的所有點都能成功到達出入口，則為可用點，加入到車位組合G中并將此點從地圖信息中刪除掉繼續尋找下一個車位點，依次循環直到所有點都為不可用點則找到了所有的車位組合G。尋找下一個車位點的公式如下：

其中，anext_q表示尋找到的下一個車位點，si表示點到出入口的距離之和，q表示尋找到的第j個車位點，t表示隨機選出的沒有任何偏好的初始車位點的個數。

最終尋找到的可有效規劃的車位總數公式G'如下：

3 基于部分最優車位尋找算法的尋找流程

（1）設置初始車位點組合參數；

（2）通過算法模型求得基于初始參數的車位組合G；

（3）依據算法模型中的初始車位點參數去執行算法模型求得最大車位的數量及位置分布。

4 實驗仿真及結果分析

本文通過有效的實驗仿真來驗證基于Dijkstra的部分最優車位規劃算法能夠根據初始車位點組合完成自動尋找最佳停車位位置的功能。本實驗的硬件環境是Win7系統的Dell臺式電腦，采用Python2.7軟件進行仿真編程實驗。本實驗采用一種可動態調整矩陣大小的停車場地圖信息方案，根據停車場的具體信息去設定矩陣的參數值。

本文選取停車場地圖信息的矩陣參數為8×8，設定矩陣中的點（0,0）位停車場的入口，設定矩陣中的點（0,7）為停車場的出口,其余點為待規劃的車位點，實驗中將隨機初始車位點設定為6進行實驗，選取其中五組實驗數據記錄在表1中，如下所示：

表1 當初始車位為6時，最終的車位數量

表1中的數據顯示，當隨機的初始車位點的數量為6時，所尋找出的最終車位數量呈現出穩定于某一個數值范圍。

取表1中的序列號1為例，當初始車位組合參數坐標為[（6,1）,（4,0）,（7,6）,（0,4）,（1,0）,（6,3）]，尋找到的最終車位坐標為[（6,1）,（4,0）,（7,6）,（0,4）,（1,0）,（6,3）,（1,7）,（2,5）,（2,4）,（2,3）,（2,2）,（0,5）,（0,3）,（0,2）,（3,5）,（2,7）,（2,0）,（4,5）,（3,7）,（3,0）,（5,5）,（4,7）,（4,2）,（5,7）,（5,3）,（5,0）,（4,3）,（7,5）,（7,4）,（6,7）,（7,2）,（5,4）,（4,4）]，將坐標呈現于圖上如圖2所示：

圖2 初始車位組合參數為6時所尋找到的車位分布

將普通停車場的車位分布方式中一種方案圖表示為如圖3所示：

圖3 一種普通停車場車位分布圖

圖2和圖3分別展示了一次實驗中所有車位點的分布位置，其中使用矩陣塊填充的代表車位的位置，五邊形填充的代表停車場的出口和入口。由圖2的車位分布圖可得知：本文中采用此算法所得到的總的車位數量為33，由圖3的車位分布圖可知，這種普通停車場容納的車位數量為30，通過對比發現，本文中的車位規劃方案略具有優勢，同時，從圖2中可知，本文中所用方案得到的車位道路可選擇性更多靈活性更高，并且，圖3中的停車場車位方案排布依據路徑最短算法得出，在總路徑長度上具有短的優勢。

5 結語

為了改善傳統停車場車位靈活性以及效率低的問題，提出一種基于Dijkstra的部分最優車位規劃算法，車位的分布更具合理性，效率更高，本文提出的方法為智能新型停車場提供了新的思路，為未來泊車系統提供了新的探索。

在仿真實驗中發現，初始車位組合中的初始車位點坐標不同時，所尋找到的最終車位分布坐標有很大的不同，但初始車位點的最佳坐標并沒有給出標準，希望以后的探索能夠改善此不足。

[1]施劍烽,楊勇生.基于改進的Dijkstra算法AGV路徑規劃研究[J].科技視界，2016（20）:111-112.

[2]陳志剛,盧山.時間窗約束下基于概率模型的AGV路徑研究[J].物流工程與管理，2017，39（10）:65-67+32.

[3]凌劍.復雜環境下AGVS調度系統設計[D].東南大學,2016.

[4]苑光明,翟云飛,丁承君,張鵬.基于改進遺傳算法的AGV路徑規劃[J].北京聯合大學學報，2018，32（01）:65-69.

[5]王松濤.基于優化的遺傳算子改進蟻群算法AGV路徑規劃[J].自動化應用，2017（03）:47-49.

[6]井治財,史恩秀.基于免疫遺傳算法的AGV路徑規劃方法研究[J].科技與企業，2016（5）:224-225.DOI:10.3969/j.issn.1004-9207.2016.05.196.