AGV智能停車庫車位規(guī)劃算法研究

李飛飛

（上海海事大學(xué)信息工程學(xué)院，上海 201306）

0 引言

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

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

1 問題描述及數(shù)學(xué)抽象

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

圖1 空白停車場初始車位狀態(tài)

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

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

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

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

2 基于Dijkstra算法的部分最優(yōu)車位規(guī)劃算法的實現(xiàn)

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

本文中基于Dijkstra的部分最優(yōu)車位規(guī)劃算法的內(nèi)容如下：

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

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

（3）在初始車位組合的基礎(chǔ)上篩選下一個最優(yōu)車位點，過程如下：

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

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

最終尋找到的可有效規(guī)劃的車位總數(shù)公式G'如下：

3 基于部分最優(yōu)車位尋找算法的尋找流程

（1）設(shè)置初始車位點組合參數(shù)；

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

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

4 實驗仿真及結(jié)果分析

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

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

表1 當(dāng)初始車位為6時，最終的車位數(shù)量

表1中的數(shù)據(jù)顯示，當(dāng)隨機(jī)的初始車位點的數(shù)量為6時，所尋找出的最終車位數(shù)量呈現(xiàn)出穩(wěn)定于某一個數(shù)值范圍。

取表1中的序列號1為例，當(dāng)初始車位組合參數(shù)坐標(biāo)為[（6,1）,（4,0）,（7,6）,（0,4）,（1,0）,（6,3）]，尋找到的最終車位坐標(biāo)為[（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）]，將坐標(biāo)呈現(xiàn)于圖上如圖2所示：

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

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

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

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

5 結(jié)語

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

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

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

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

[3]凌劍.復(fù)雜環(huán)境下AGVS調(diào)度系統(tǒng)設(shè)計[D].東南大學(xué),2016.

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

[5]王松濤.基于優(yōu)化的遺傳算子改進(jìn)蟻群算法AGV路徑規(guī)劃[J].自動化應(yīng)用，2017（03）:47-49.

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