，，

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

0 引言

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

針對(duì)目前停車誘導(dǎo)系統(tǒng)的不完善、車位利用率以及停車效率低[4]等問題，本文以大型停車場(chǎng)的內(nèi)部結(jié)構(gòu)模型為應(yīng)用實(shí)例，把動(dòng)態(tài)泊車導(dǎo)致的停車效率問題轉(zhuǎn)化為泊車概率問題，通過對(duì)目前路徑規(guī)劃算法比較[5]最終選擇A*算法并進(jìn)行了優(yōu)化，最后在VC++6.0環(huán)境下對(duì)優(yōu)化后的算法做仿真和實(shí)驗(yàn)驗(yàn)證。

1 停車場(chǎng)結(jié)構(gòu)及車位模型

1.1 停車場(chǎng)結(jié)構(gòu)模型分析

停車用戶在停車時(shí)往往遇到很多問題，其中停車效率、停車舒適性、駕駛以及行走距離等問題是影響停車用戶體驗(yàn)的主要因素，本文結(jié)合圖1地下停車場(chǎng)內(nèi)部車位結(jié)構(gòu)特點(diǎn)對(duì)以上問題進(jìn)行了分析，從圖中可以知道，地下停車場(chǎng)的車位分布具有以下三個(gè)主要的特點(diǎn)[6]。

1)停車場(chǎng)的車位大部分具有對(duì)稱分布特性。

2)停車場(chǎng)內(nèi)部的道路分支一般較多，一排車位的兩端必定為道路的交叉口或者拐點(diǎn)，另外目前地下停車場(chǎng)的入口有很多，包括車輛駛?cè)胍约半娞莸戎饕肟?。停車位置的選擇很大程度上決定了停車舒適性[8]、駕駛以及行走的距離，所以將圖1中的道路交叉口、電梯、停車場(chǎng)車輛駛?cè)肟诘葮?biāo)記為點(diǎn)，以便用戶更加直觀靈活的選擇停車位。

3)停車場(chǎng)內(nèi)部大部分的車位呈區(qū)域性密集分布，當(dāng)泊車用戶行駛到一個(gè)停車區(qū)域內(nèi)時(shí)，可以明顯的觀察到某個(gè)車位附近的所有可用空車位從而使泊車用戶車位的選擇具有多樣性，利用車位的這種密集分布特性我們可以大大挺高用戶的動(dòng)態(tài)泊車概率，進(jìn)而增加停車效率。

圖1 地下停車場(chǎng)車位分布示意圖

1.2 停車位模型

為了更具體化的研究A*算法在動(dòng)態(tài)停車路徑規(guī)劃中的應(yīng)用，需將道路交叉口、電梯、停車位、停車場(chǎng)車輛駛?cè)肟诤?jiǎn)化為節(jié)點(diǎn)，于是，停車場(chǎng)整體的網(wǎng)絡(luò)結(jié)構(gòu)就轉(zhuǎn)化為有向(無向)帶權(quán)圖[6-7]，如圖2所示。其中，阿拉伯?dāng)?shù)字(0～99)表示停車位的節(jié)點(diǎn)集合，Ci表示電梯、路口拐點(diǎn)、停車場(chǎng)車輛入口的節(jié)點(diǎn)集合，任意兩個(gè)節(jié)點(diǎn)間的路段為邊，邊的權(quán)值另行存儲(chǔ)，不在帶權(quán)圖中顯示。結(jié)合圖1停車場(chǎng)內(nèi)部車位對(duì)稱性的特點(diǎn)，將部分路段的上下兩排車位節(jié)點(diǎn)合并成一排，以減少需要遍歷的總節(jié)點(diǎn)數(shù)。

針對(duì)節(jié)點(diǎn)信息的存儲(chǔ)，所有節(jié)點(diǎn)都按照(x,y)坐標(biāo)的形式進(jìn)行標(biāo)記,將相鄰兩個(gè)節(jié)點(diǎn)間對(duì)應(yīng)的x,y坐標(biāo)差的絕對(duì)值之和作為表征兩個(gè)節(jié)點(diǎn)間邊的權(quán)值量化[9]，權(quán)值為A*算法路徑規(guī)劃做數(shù)據(jù)支撐，其數(shù)據(jù)準(zhǔn)確性在一定程度上決定了算法精確度。

圖2 停車位及路段帶權(quán)圖

2 路徑規(guī)劃算法選擇

目前，地下停車場(chǎng)中常用的路徑規(guī)劃算法主要有Dijkstra算法、A*算法等。

Dijkstra[7-10]算法是經(jīng)典的最短路徑算法，用于求任意兩個(gè)節(jié)點(diǎn)間的最短路徑。算法的基本思想為：把帶權(quán)圖中所有的車位節(jié)點(diǎn)集合分成兩個(gè)組，第一組為所有未遍歷頂點(diǎn)集合N，第二組為已求出最短路徑的頂點(diǎn)集合G，初始時(shí)G中只有源節(jié)點(diǎn)，對(duì)與G相連的節(jié)點(diǎn)進(jìn)行擴(kuò)展，選擇代價(jià)最小的路徑，就將它對(duì)應(yīng)的頂點(diǎn)放入到集合G中，循環(huán)擴(kuò)展直到全部頂點(diǎn)都放入到G中。

A*算法[13]是基于經(jīng)典Dijkstra的一種啟發(fā)式搜索算法，通過估價(jià)函數(shù)來約束其搜索方向，可定義A*算法的估價(jià)函數(shù)為[11]

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

(1)

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

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

1)當(dāng)h(n)小于臨時(shí)節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)的實(shí)際路徑代價(jià)時(shí)，搜索的車位節(jié)點(diǎn)數(shù)多，算法搜索效率低，但能求得最優(yōu)解。

2)當(dāng)h(n)等于臨時(shí)節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)的實(shí)際路徑代價(jià)時(shí)，搜索將嚴(yán)格按照最短路徑進(jìn)行，此時(shí)的算法搜索效率最高。

3)當(dāng)h(n)大于臨時(shí)節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)的實(shí)際路徑代價(jià)時(shí)，搜索的車位節(jié)點(diǎn)很少，算法搜索效率高，但是不保證求得最優(yōu)解。

結(jié)合停車位及路段帶權(quán)圖，考慮到節(jié)點(diǎn)的坐標(biāo)存儲(chǔ)特性，故啟發(fā)式函數(shù)h(n)采用曼哈頓(Manhattan)距離[14]，其表達(dá)式為：

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

(2)

其中：(xA,yA)表示臨時(shí)節(jié)點(diǎn)A的坐標(biāo)值；(xB,yB)表示目標(biāo)節(jié)點(diǎn)B的坐標(biāo)值。

由圖2的結(jié)構(gòu)可知，h(n)總是小于等于臨時(shí)節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)的實(shí)際路徑代價(jià)，因此保證泊車用戶能按照最優(yōu)路徑進(jìn)行泊車。綜合以上分析，本文采用A*算法進(jìn)行動(dòng)態(tài)泊車試驗(yàn)的研究。

3 A*算法的優(yōu)化和實(shí)現(xiàn)

3.1 優(yōu)化A*算法

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

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

Pa=1-(m)na

(3)

3.2 A*優(yōu)化算法的實(shí)現(xiàn)

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

算法實(shí)現(xiàn)的具體步驟如下。

Step 1：對(duì)空車位分布比較密集的區(qū)域分別進(jìn)行矩形限定并標(biāo)記，隨機(jī)選取一個(gè)矩形限定區(qū)域，將此區(qū)域中具有最小x坐標(biāo)的節(jié)點(diǎn)作為目標(biāo)節(jié)點(diǎn)。

Step 2：創(chuàng)建空的OPEN、CLOSED表，并將初始節(jié)點(diǎn)S放入OPEN表中，設(shè)f(c1)=0。

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

Step 4：將初始節(jié)點(diǎn)S記為算法規(guī)劃的第一個(gè)節(jié)點(diǎn)BestNode，并將其放入CLOSED表中。

Step 5：判斷第一個(gè)節(jié)點(diǎn)BestNode是否為目標(biāo)節(jié)點(diǎn)，若是則輸出最短路徑、停車成功概率以及遍歷的節(jié)點(diǎn)數(shù)，否則執(zhí)行下一步。

Step 6：擴(kuò)展BestNode節(jié)點(diǎn)，選擇f(n)=Min{f(n)}的節(jié)點(diǎn)作為下一個(gè)BestNode。

Step 7：判斷當(dāng)前的節(jié)點(diǎn)BestNode是否為目標(biāo)節(jié)點(diǎn)，若是則輸出最短路徑、停車成功概率以及遍歷的節(jié)點(diǎn)數(shù)，否則執(zhí)行第6步。

Step 8：循環(huán)第6、7步直到目標(biāo)節(jié)點(diǎn)放入到CLOSED表中，輸出最短路徑、泊車成功概率以及遍歷的節(jié)點(diǎn)數(shù)。

4 仿真結(jié)果與實(shí)驗(yàn)分析

基于優(yōu)化后的A*算法，以VC++6.0環(huán)境為實(shí)驗(yàn)平臺(tái)，結(jié)合實(shí)際停車場(chǎng)中空車位的不確定性和動(dòng)態(tài)性，對(duì)停車場(chǎng)泊車成功概率以及算法搜索效率進(jìn)行了研究。通過存儲(chǔ)的車位以及交叉路口等節(jié)點(diǎn)信息畫出節(jié)點(diǎn)圖，仿真給定隨機(jī)空車位的信息，并由隨機(jī)空車位的節(jié)點(diǎn)坐標(biāo)信息進(jìn)行矩形區(qū)域限定，隨機(jī)選取其中一個(gè)區(qū)域限定的目標(biāo)節(jié)點(diǎn)，最終進(jìn)行動(dòng)態(tài)泊車路徑規(guī)劃，同時(shí)由所選矩形區(qū)域中的可用節(jié)點(diǎn)數(shù)計(jì)算出泊車成功概率和算法搜索效率。其中規(guī)劃的最短路徑用綠色線條標(biāo)出，限定區(qū)域用矩形標(biāo)出，最終仿真結(jié)果如圖3所示。

圖3 仿真結(jié)果示意圖

由上面的概率定義可知，Pr、Pa分別為優(yōu)化前和優(yōu)化后的泊車成功概率，其實(shí)驗(yàn)結(jié)果如下表所示。

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

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

表3 A*算法優(yōu)化前與優(yōu)化后的遍歷節(jié)點(diǎn)數(shù)比較

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

5 結(jié)語

本文從實(shí)際停車問題出發(fā)，結(jié)合停車效率以及路徑規(guī)劃提出了泊車成功概率概念，以泊車成功概率和算法搜索效率為主要評(píng)價(jià)指標(biāo)，通過矩形限定區(qū)域約束法對(duì)A*算法進(jìn)行優(yōu)化，將動(dòng)態(tài)泊車導(dǎo)致的停車效率問題轉(zhuǎn)化為泊車概率問題，圍繞車位實(shí)時(shí)變化情況下的動(dòng)態(tài)路徑規(guī)劃問題展開研究。實(shí)驗(yàn)結(jié)果顯示，優(yōu)化后的算法提高了泊車成功概率和算法運(yùn)行效率，這將大大減少用戶在停車高峰期不斷盲目尋找車位的時(shí)間，保證泊車用戶能夠以最短的規(guī)劃路徑且較高的泊車概率進(jìn)行泊車，進(jìn)而提高停車用戶的停車體驗(yàn)以及停車位的利用率，具有一定的實(shí)用研究?jī)r(jià)值。但此算法仍有一定的缺點(diǎn)，由于空車位的隨機(jī)分布性，泊車成功概率較高的目標(biāo)區(qū)域距離初始節(jié)點(diǎn)的路徑花費(fèi)有可能較高，泊車成功概率與路徑花費(fèi)的權(quán)衡可以作為A*算法在停車場(chǎng)動(dòng)態(tài)泊車應(yīng)用中的一個(gè)研究方向。