基于A*優化算法的停車場動態泊車研究

，，

(浙江工業大學 信息工程學院，杭州 310023)

0 引言

隨著城市發展和人民生活水平的提高，中國汽車保有量呈直線上升趨勢，由此導致的城市停車難、停車效率低等一系列問題也加速了停車誘導系統的發展，其中常用的路徑規劃算法有Dijkstra算法、A*算法等。在動態網絡路徑規劃算法的研究中，國外Chabini[1]等人首次引入A*算法，國內晏克非教授[2]團隊結合改進的A*算法，將整個路徑規劃過程分成一段段按時間連續的分段，并對每個分段內的動態路網信息做靜態化處理，以此解決了具有變化因素的動態路徑規劃問題。目前城市停車誘導系統大都應用于交通路網中車輛的路徑誘導和規劃，僅僅把泊車用戶引導到車庫的門口，針對大型停車場內部停車誘導問題的研究相對缺乏[3]。尤其是隨著城市現代停車場結構的大型化和復雜化，在停車高峰期由于車位狀態是實時變化的，停泊用戶需要不斷盲目的尋找車位，此類動態泊車問題大大增加了用戶的停車時間，降低了停車效率。

針對目前停車誘導系統的不完善、車位利用率以及停車效率低[4]等問題，本文以大型停車場的內部結構模型為應用實例，把動態泊車導致的停車效率問題轉化為泊車概率問題，通過對目前路徑規劃算法比較[5]最終選擇A*算法并進行了優化，最后在VC++6.0環境下對優化后的算法做仿真和實驗驗證。

1 停車場結構及車位模型

1.1 停車場結構模型分析

停車用戶在停車時往往遇到很多問題，其中停車效率、停車舒適性、駕駛以及行走距離等問題是影響停車用戶體驗的主要因素，本文結合圖1地下停車場內部車位結構特點對以上問題進行了分析，從圖中可以知道，地下停車場的車位分布具有以下三個主要的特點[6]。

1)停車場的車位大部分具有對稱分布特性。

2)停車場內部的道路分支一般較多，一排車位的兩端必定為道路的交叉口或者拐點，另外目前地下停車場的入口有很多，包括車輛駛入以及電梯等主要入口。停車位置的選擇很大程度上決定了停車舒適性[8]、駕駛以及行走的距離，所以將圖1中的道路交叉口、電梯、停車場車輛駛入口等標記為點，以便用戶更加直觀靈活的選擇停車位。

3)停車場內部大部分的車位呈區域性密集分布，當泊車用戶行駛到一個停車區域內時，可以明顯的觀察到某個車位附近的所有可用空車位從而使泊車用戶車位的選擇具有多樣性，利用車位的這種密集分布特性我們可以大大挺高用戶的動態泊車概率，進而增加停車效率。

圖1 地下停車場車位分布示意圖

1.2 停車位模型

為了更具體化的研究A*算法在動態停車路徑規劃中的應用，需將道路交叉口、電梯、停車位、停車場車輛駛入口簡化為節點，于是，停車場整體的網絡結構就轉化為有向(無向)帶權圖[6-7]，如圖2所示。其中，阿拉伯數字(0～99)表示停車位的節點集合，Ci表示電梯、路口拐點、停車場車輛入口的節點集合，任意兩個節點間的路段為邊，邊的權值另行存儲，不在帶權圖中顯示。結合圖1停車場內部車位對稱性的特點，將部分路段的上下兩排車位節點合并成一排，以減少需要遍歷的總節點數。

針對節點信息的存儲，所有節點都按照(x,y)坐標的形式進行標記,將相鄰兩個節點間對應的x,y坐標差的絕對值之和作為表征兩個節點間邊的權值量化[9]，權值為A*算法路徑規劃做數據支撐，其數據準確性在一定程度上決定了算法精確度。

圖2 停車位及路段帶權圖

2 路徑規劃算法選擇

目前，地下停車場中常用的路徑規劃算法主要有Dijkstra算法、A*算法等。

Dijkstra[7-10]算法是經典的最短路徑算法，用于求任意兩個節點間的最短路徑。算法的基本思想為：把帶權圖中所有的車位節點集合分成兩個組，第一組為所有未遍歷頂點集合N，第二組為已求出最短路徑的頂點集合G，初始時G中只有源節點，對與G相連的節點進行擴展，選擇代價最小的路徑，就將它對應的頂點放入到集合G中，循環擴展直到全部頂點都放入到G中。

A*算法[13]是基于經典Dijkstra的一種啟發式搜索算法，通過估價函數來約束其搜索方向，可定義A*算法的估價函數為[11]

f(n)=g(n)+h(n)

(1)

式中,f(n)為當前節點的路徑代價估計；g(n)為初始節點到臨時節點n的實際路徑代價；h(n)為臨時節點n到目標節點的路徑代價估計。A*算法的基本思想為[12]：創建OPEN表、CLOSED表，OPEN表用以保存所有擴展的節點，CLOSED表用以記錄已訪問過的節點。初始時將源節點S放入OPEN 表中，對與S相連的節點進行擴展并放入OPEN表，取出OPEN表中具有最小估價函數值的臨時節點n并放入CLOSED表中，循環擴展臨時節點n直到目標節點放入CLOSED中。

綜上所述，相比于經典Dijkstra算法的全節點遍歷，得益于A*算法啟發函數的約束，A*算法更加靈活的按照其估價函數進行啟發式搜索，從而大大減少其遍歷的節點數，提高了算法搜索效率。在路徑最優解方面，Dijkstra算法保證找到最優路徑，而啟發式函數h(n)的選取決定了A*算法的精確度[11]，h(n)的選取主要有以下三種情況：

1)當h(n)小于臨時節點n到目標節點的實際路徑代價時，搜索的車位節點數多，算法搜索效率低，但能求得最優解。

2)當h(n)等于臨時節點n到目標節點的實際路徑代價時，搜索將嚴格按照最短路徑進行，此時的算法搜索效率最高。

3)當h(n)大于臨時節點n到目標節點的實際路徑代價時，搜索的車位節點很少，算法搜索效率高，但是不保證求得最優解。

結合停車位及路段帶權圖，考慮到節點的坐標存儲特性，故啟發式函數h(n)采用曼哈頓(Manhattan)距離[14]，其表達式為：

h(n)=|xA-xB|+|yA-yB|

(2)

其中：(xA,yA)表示臨時節點A的坐標值；(xB,yB)表示目標節點B的坐標值。

由圖2的結構可知，h(n)總是小于等于臨時節點n到目標節點的實際路徑代價，因此保證泊車用戶能按照最優路徑進行泊車。綜合以上分析，本文采用A*算法進行動態泊車試驗的研究。

3 A*算法的優化和實現

3.1 優化A*算法

在正常泊車的過程中由于空車位的實時變動性以及隨機分布性，當泊車用戶隨機選取單個空車位作為目標節點進行路徑規劃時，車位的頻繁變更直接影響泊車用戶的泊車成功概率以及體驗。針對這一問題，本文提出了帶約束條件的A*優化算法，基本思想：由獲知的空停車位信息以及節點的坐標特性，對空車位比較密集的不同矩形區域分別進行限定[15-17]，并選取矩形區域中具有最小x坐標的節點作為此區域的目標節點。此最小x坐標的節點代表整個矩形區域中所有可用的空車位節點，由帶權圖2可知，從入口初始節點C1開始搜索時，只需要搜索到具有最小x坐標的節點即可，故在進行路徑規劃時選其作為目標節點很大程度上減少了遍歷節點的總數，提高了算法搜索效率。同時按照停車場車位密集分布特性，矩形區域之內可用的空車位較多，在停車位具有動態變化因素的情況下，大大增加了泊車用戶的泊車成功概率，保證了泊車用戶車位選擇的多樣性和泊車體驗。

由停車位的概率分布特性，泊車成功概率可定義為：

Pa=1-(m)na

(3)

3.2 A*優化算法的實現

由仿真給定的空車位的實時信息，根據車位節點之間的坐標特性，將相鄰空車位節點間坐標差值的絕對值作為矩形區域限定的度量依據，分別對空車位分布較密集的區域進行限定，最終選擇目標節點并進行路徑規劃，通過不斷擴展具有最小估價函數值f(n)=Min{f(n)}的臨時節點BestNode，直至目標節點并輸出目標節點的泊車概率和遍歷節點總數。

算法實現的具體步驟如下。

Step 1：對空車位分布比較密集的區域分別進行矩形限定并標記，隨機選取一個矩形限定區域，將此區域中具有最小x坐標的節點作為目標節點。

Step 2：創建空的OPEN、CLOSED表，并將初始節點S放入OPEN表中，設f(c1)=0。

Step 3：若OPEN表為空，初始化失敗，退出程序。

Step 4：將初始節點S記為算法規劃的第一個節點BestNode，并將其放入CLOSED表中。

Step 5：判斷第一個節點BestNode是否為目標節點，若是則輸出最短路徑、停車成功概率以及遍歷的節點數，否則執行下一步。

Step 6：擴展BestNode節點，選擇f(n)=Min{f(n)}的節點作為下一個BestNode。

Step 7：判斷當前的節點BestNode是否為目標節點，若是則輸出最短路徑、停車成功概率以及遍歷的節點數，否則執行第6步。

Step 8：循環第6、7步直到目標節點放入到CLOSED表中，輸出最短路徑、泊車成功概率以及遍歷的節點數。

4 仿真結果與實驗分析

基于優化后的A*算法，以VC++6.0環境為實驗平臺，結合實際停車場中空車位的不確定性和動態性，對停車場泊車成功概率以及算法搜索效率進行了研究。通過存儲的車位以及交叉路口等節點信息畫出節點圖，仿真給定隨機空車位的信息，并由隨機空車位的節點坐標信息進行矩形區域限定，隨機選取其中一個區域限定的目標節點，最終進行動態泊車路徑規劃，同時由所選矩形區域中的可用節點數計算出泊車成功概率和算法搜索效率。其中規劃的最短路徑用綠色線條標出，限定區域用矩形標出，最終仿真結果如圖3所示。

圖3 仿真結果示意圖

由上面的概率定義可知，Pr、Pa分別為優化前和優化后的泊車成功概率，其實驗結果如下表所示。

表1 A*算法優化前與優化后的泊車成功概率比較

表2 A*算法優化前與優化后的泊車成功概率比較

表3 A*算法優化前與優化后的遍歷節點數比較

在停車場動態泊車時，停車場的繁忙程度決定著車位占用概率即m值的大小，結合實際停車情況，本文分別取表征不同停車繁忙程度的m值為2/3和1/2來驗證泊車成功概率，從上表1、2的橫向對比實驗數據看出，優化后的A*算法在動態泊車路徑規劃中的應用大大提高了泊車成功概率，且隨著m取值的增大泊車成功概率提升幅度亦增大，表明優化后的A*算法對解決停車高峰期動態泊車問題的優化效果更加明顯，從而提高了車位的利用率以及減少了用戶的泊車時間。而從表3看出，相比于Dijkstra 算法的全節點遍歷，A*算法的遍歷節點最多為35個約等于總節點數的1/3。從圖3的動態路徑規劃示意圖可知，矩形區域中有37、42等多個可用空車位節點，結合空車位的密集分布特性，文中采用最小x坐標的42號節點作為動態路徑規劃的目標節點進一步減少了遍歷節點的總數，很大程度的提高了算法的運行效率。

5 結語

本文從實際停車問題出發，結合停車效率以及路徑規劃提出了泊車成功概率概念，以泊車成功概率和算法搜索效率為主要評價指標，通過矩形限定區域約束法對A*算法進行優化，將動態泊車導致的停車效率問題轉化為泊車概率問題，圍繞車位實時變化情況下的動態路徑規劃問題展開研究。實驗結果顯示，優化后的算法提高了泊車成功概率和算法運行效率，這將大大減少用戶在停車高峰期不斷盲目尋找車位的時間，保證泊車用戶能夠以最短的規劃路徑且較高的泊車概率進行泊車，進而提高停車用戶的停車體驗以及停車位的利用率，具有一定的實用研究價值。但此算法仍有一定的缺點，由于空車位的隨機分布性，泊車成功概率較高的目標區域距離初始節點的路徑花費有可能較高，泊車成功概率與路徑花費的權衡可以作為A*算法在停車場動態泊車應用中的一個研究方向。