基于蟻群算法的智能停車場引導(dǎo)系統(tǒng)①

張晶晶, 薛 偉

(江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院, 無錫 214122)

1 引言

現(xiàn)在許多大型停車場依舊是傳統(tǒng)的人工管理停車場方式, 而人工管理停車場存在很多問題. 停車場內(nèi)剩余車位信息“不透明”, 沒有被占用的車位位置不明確,車主停車時無法及時找到空余停車位, 這就造成停車場利用率低下[1]. 除此之外, 駕駛員在停車場內(nèi)迂回地尋找車位一方面容易造成停車場內(nèi)車輛擁堵, 另一方面大量汽車在尋找車位時排放的汽車尾氣容易造成空氣污染[2]. 本文針對這一問題, 設(shè)計了智能停車場. 智能停車場內(nèi)的每個車位上空放置超聲波車位傳感器采集車位信息, 并通過ZigBee無線網(wǎng)絡(luò)傳輸信息[3]. 停車場內(nèi)的管理系統(tǒng)[4]采用Microsoft Visual Studio平臺設(shè)計,主要完成車位信息的處理和存儲. 停車場內(nèi)岔路口處有方向顯示屏, 顯示左、前、右方向信息, 指引泊車者行進(jìn)方向, 將車停至最佳停車位置. 這個智能停車誘導(dǎo)系統(tǒng)就能避免泊車者在停車場盲目尋找車位, 減少了汽車在尋找車位時在道路上迂回浪費的時間, 緩解道路空間, 節(jié)約資源, 同時也減輕工作人員的負(fù)擔(dān), 降低人工成本, 提高停車場的利用率.

2 系統(tǒng)總體設(shè)計

本文提出了一種基于蟻群算法的智能停車誘導(dǎo)系統(tǒng), 該系統(tǒng)采用的技術(shù)方案包括超聲波車位檢測,ZigBee無線傳輸協(xié)議, VS平臺軟件開發(fā). 該智能停車場系統(tǒng)包括上位機(jī)綜合管理, 空車位檢測, 車輛引導(dǎo)等功能. 總體結(jié)構(gòu)框圖如圖1所示.

圖1 系統(tǒng)總體框架圖

2.1 ZigBee無線模塊與超聲波車位探測

超聲波車位傳感是基于ZigBee終端模塊設(shè)計的,采用HC-SR04超聲波測距模塊檢測距離, 放置在距離車位上空3.5 m處的位置. 模塊的發(fā)射器發(fā)送8個40 kHz的方波自動檢測, 如果發(fā)現(xiàn)有障礙物則接收器接受返回的信號. 汽車高度范圍在1.3–2.2 m之間, 所以如果檢測到1.3–2.2 m處有障礙物代表車位有車紅燈亮, 否則綠燈亮.

ZigBee無線模塊包括終端、路由器、協(xié)調(diào)器都是采用TI公司生產(chǎn)的以CC2530芯片為核心, CC2530芯片[5]支持IEEE802.15.4標(biāo)準(zhǔn)、ZigBee標(biāo)準(zhǔn)、ZigBee RF4CE標(biāo)準(zhǔn)的無線傳感器網(wǎng)絡(luò)協(xié)議, 具有優(yōu)秀的接收器靈敏度和健壯抗干擾性, 支持低功耗的無線通信.

無線傳輸網(wǎng)絡(luò)采用Z-Stack協(xié)議棧, Z-Stack包含了網(wǎng)狀拓?fù)涞膸缀跞抗δ艿膮f(xié)議棧, 開發(fā)者可以很容易地開發(fā)出具體的應(yīng)用程序. 在本系統(tǒng)選擇了樹狀網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu), 首先協(xié)調(diào)器節(jié)點負(fù)責(zé)建立一個網(wǎng)絡(luò)和整合數(shù)據(jù)信息, 終端節(jié)點負(fù)責(zé)加入網(wǎng)絡(luò)和通過無線傳輸?shù)姆绞綄⒔邮盏某暡ㄜ囄粰z測信息上傳至父節(jié)點,經(jīng)過路由器節(jié)點上傳至協(xié)調(diào)器. 如圖2包括終端(即基于ZigBee模塊的超聲波車位傳感器)、路由器、協(xié)調(diào)器.

圖2 ZigBee模塊

2.2 改進(jìn)蟻群算法與管理員平臺

2.2.1 改進(jìn)蟻群算法

如圖3所示的簡易停車場平面結(jié)構(gòu)圖, 根據(jù)圖顯示的停車場平面圖建立停車場抽象模型. 為建立停車場車位模型將圖中的有兩條及以上行車方向的交叉路口, 以及各個停車位作為節(jié)點. 將各個可相通的交叉路口之間的路段和各個停車位到與之相通的交叉路口的路段作為邊.

圖3 停車場平面結(jié)構(gòu)圖

如圖4所示的停車場抽象模型, 邊權(quán)構(gòu)成網(wǎng)狀結(jié)構(gòu)圖轉(zhuǎn)化為帶權(quán)有向圖G=(V, E), 其中V是包含所有節(jié)點的集合, E表示所有包含邊(弧段)的集合. 圖中Ri(1≤i≤6)是停車場的各個岔路口節(jié)點, 其中R1作為

停車場的入口節(jié)點, R3作為停車場的出口節(jié)點, 圖中的P29, P32等代表的是剩余空車位節(jié)點. 蟻群算法計算從停車場入口R1到各個空余停車位的距離, 然后進(jìn)行比較得出最短路徑, 獲得最優(yōu)停車位以及到達(dá)該停車位的路線, 所以建立邊權(quán)的權(quán)值就是各個部分的實際距離. 邊權(quán)的構(gòu)建包含兩個方面, 一個是各個交叉路口之間的邊權(quán)(即交叉路口之間的距離), 采用符號W＜Ri, Rj＞(1≤i,j≤6)表示; 另一個是交叉路口到具體停車位的邊權(quán)采用符號W＜Ri, Pk＞(1≤i≤6)(k=1, 2, 3,…)表示.

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

基本蟻群算法是一種源于大自然生物世界的新的仿生進(jìn)化算法, 模擬自然界中螞蟻集體尋徑行為而提出的一種基于種群的啟發(fā)式隨機(jī)搜索算法[6]. 螞蟻在尋找食物的行進(jìn)過程中在其走過的路徑上釋放信息素,隨著時間的推移, 路徑上的信息素會揮發(fā), 后來的螞蟻會根據(jù)信息素的強(qiáng)度來決定選擇該路徑的概率. 根據(jù)真實蟻群在搜索食物時解決最短路徑的問題的方式,可以構(gòu)建人工蟻群解決本文的最短路徑問題.

基本蟻群算法應(yīng)用在停車場的應(yīng)用中會出現(xiàn)一些問題, 例如死鎖, 停滯, 甚至無解(即無法到達(dá)指定終點無法得出結(jié)果)的情況. 針對上述問題并且為了更好地應(yīng)用于停車場的情況, 對傳統(tǒng)蟻群算法進(jìn)行改進(jìn), 主要包括三個方面: MAX-MIN Ant System[7](最大-最小螞蟻系統(tǒng)), 局部信息素更新[8]和撤退方法. 這樣既能搜索更大的解空間, 又能使系統(tǒng)陷入局部最優(yōu)后跳出停滯狀態(tài). 而為了增加螞蟻的全局搜索性, 并且能夠有機(jī)會選擇更多的路徑方向, 在選擇下一步的轉(zhuǎn)移規(guī)則中增加輪盤賭算法.

(1) MAX-MIN Ant System

最大最小螞蟻系統(tǒng)為了充分利用當(dāng)前循環(huán)中的最優(yōu)解, 在每次循環(huán)之后, 得到的最優(yōu)解的螞蟻走過的路徑進(jìn)行信息素更新. 除此之后, 將每條路徑上的信息素的值域范圍限制在[τmin,τmax]區(qū)間內(nèi), 這就避免過多螞蟻行進(jìn)相同路徑而使得路徑上的信息素遠(yuǎn)遠(yuǎn)高于其他邊, 而導(dǎo)致再次吸引更多的螞蟻在同路徑上行進(jìn).

(2) 局部信息素更新

最大最小螞蟻系統(tǒng)中, 只更新每次循環(huán)中最優(yōu)解路徑上的信息素, 而為了更好地搜索到最優(yōu)解, 本文在系統(tǒng)中增加局部更新規(guī)則, 如式(1)所示:

其中,τ0表示是各個路徑的信息素的初始值, 那么全局最優(yōu)螞蟻的信息素的更新規(guī)則如式(2)所示:

其中,Lbest表示最優(yōu)路徑的長度.

(3) 撤退方法

蟻群算法在停車場結(jié)構(gòu)圖的應(yīng)用中易出現(xiàn)無解的情況, 例如一個路徑的終點是R3, 而螞蟻在行動中走的路線是R1→R2→R5→R4, 蟻群算法在運(yùn)行中要求一個節(jié)點只能走一次, 那么如果出現(xiàn)上述的路線, 螞蟻將無法走到終點R3. 為了解決這個問題提出了撤退方法, 如果過程中出現(xiàn)上述類似問題, 將螞蟻的走向退回到R5節(jié)點, 并且將R5→R4路段上的信息素更新為零,利用輪盤賭算法再次為螞蟻重新選擇下一節(jié)點, 避免螞蟻重復(fù)上述路段, 直至有路線能夠到達(dá)終點.

2.2.2 算法執(zhí)行步驟及實驗結(jié)果

Step1. 建立停車場平面圖模型, 利用貪婪算法規(guī)劃出一條從初始點到終點的初始路徑, 然后計算出τ0.

Step2. 蟻群參數(shù)初始化, 設(shè)置參數(shù)m,α,β,ρ,Q的值, 令循環(huán)次數(shù)Nc=0和τ=τmax, 設(shè)置最大迭代次數(shù)G,將m只螞蟻置于初始節(jié)點.

Step3. 蟻群算法開始搜索, 當(dāng)前螞蟻節(jié)點i，按照如下公式和輪盤賭算法計算下一節(jié)點j:

Step4. 判斷下一節(jié)點j是否確定, 如果無法取得j則選擇撤退方法, 再返回到Step4并且路徑上信息素更新為0. 如果下一節(jié)點j確定, 螞蟻要對剛走過的路徑＜i,j＞上的信息素按照式(1)進(jìn)行局部信息素更新,并將該節(jié)點放入路徑表中.

Step5. 判斷螞蟻是否達(dá)到終點, 若達(dá)到終點則轉(zhuǎn)到Step6, 否則轉(zhuǎn)到Step3.

Step6. 統(tǒng)計當(dāng)前m只螞蟻搜索到的最優(yōu)路徑, 選出最短路徑, 并將此路線上的信息素通過式(2)局部更新和式(3)進(jìn)行全局最優(yōu)螞蟻的信息素更新.

Step7. 若滿足結(jié)束條件, 即循環(huán)次數(shù)Nc≥G, 則程序結(jié)束并輸出最優(yōu)結(jié)果, 否則清空禁忌表并轉(zhuǎn)至Step3.

根據(jù)建立的停車場模型, 搜索最優(yōu)停車位, 編程環(huán)境 VS2013. 設(shè)置m=50,ρ=0.5,α=1,β=2,G=300. 根據(jù)上述步驟得出實驗步驟, 結(jié)果如表1所示.

表1 停車場仿真實驗結(jié)果

實驗結(jié)果表明, 最佳車位是P46, 路線(S)R1→R2→P46.

2.2.3 管理員平臺

管理員平臺作為主控機(jī)一般采用PC機(jī), 放置在中央控制室, 該上位機(jī)主要用來進(jìn)行人機(jī)交互, 并在無線局域網(wǎng)內(nèi)向顯示屏發(fā)送方向命令. 我們采用Visual Studio2013在Windows平臺上對上位機(jī)人機(jī)交互界面進(jìn)行設(shè)計, 使用.Net框架下的TCP傳輸協(xié)議建立TCP通信, 設(shè)置IP地址以及端口號方便與顯示屏建立連接.

具體實現(xiàn)功能, 接收、處理和存儲下位機(jī)上傳的車位信息, 將車位信息內(nèi)容展示在上位機(jī)平臺上, 如圖5的上位機(jī)管理員界面, 紅色(圖中深色著色)代表此車位已被占用, 綠色(圖中淺色著色) 代表車位狀態(tài)是空閑. 上位機(jī)內(nèi)部統(tǒng)計車位節(jié)點信息, 通過改進(jìn)蟻群算法計算出最優(yōu)停車路線并保存在數(shù)據(jù)庫中, 為方向引導(dǎo)屏提供信息支持, 以及顯示剩余車位信息.

圖5 管理員界面

2.3 方向引導(dǎo)屏

采用Visual Studio2013在Windows平臺設(shè)置的顯示屏懸掛在停車場內(nèi)岔路口上方, 顯示屏輸入IP地址與端口號以及所在岔路口的節(jié)點名稱在局域網(wǎng)內(nèi)與服務(wù)器建立通信, 接收從管理員服務(wù)器的信息, 指引駕駛員行駛到達(dá)最優(yōu)的停車位置.

如圖6所示, 圖6的引導(dǎo)屏位于停車場入口的R1位置, 假定停車場先后進(jìn)入兩輛停車場, 獲得兩輛車的車牌號分別為蘇B01010和蘇B02020, 由蟻群算法得出的最優(yōu)的停車位是P29, 所以為第一位駕駛員指向前行駛方向, 指引第一位駕駛員將車停至P29車位.在假定第一停車位已經(jīng)被占用的情況下, 為第二輛車輛分配最佳車位P35, 到達(dá)P35停車位經(jīng)過的拐角路徑是R1→R2, 所以在R1入口處為蘇B02020車輛指引向左行駛方向, 將蘇B02020車輛指引至R2節(jié)點處,再由R2節(jié)點處的引導(dǎo)屏指引車輛停至P35車位.

圖6 方向引導(dǎo)屏

3 結(jié)論

針對停車場內(nèi)停車難問題, 在停車位上方安裝超聲波告訴泊車者車位信息; 提出用蟻群算法解決場內(nèi)最優(yōu)解問題, 針對停車場的模型對蟻群算法進(jìn)行優(yōu)化改進(jìn), 使改進(jìn)后的蟻群算法能更好應(yīng)用在停車場; 上位機(jī)通過改進(jìn)的蟻群算法計算出距離停車場入口最近的空閑停車位, 并得出具體路線, 通過TCP/IP通信方式向方向指引屏傳輸信息誘導(dǎo)駕駛員行駛至最佳停車位.本系統(tǒng)的設(shè)計能夠避免駕駛員在停車場內(nèi)盲目尋找停車位, 實現(xiàn)了對車位智能誘導(dǎo)功能, 有效地提高停車場的運(yùn)行效率.