秦 澄 徐雪峰
(淮安信息職業(yè)技術(shù)學(xué)院,江蘇 淮安 223003)
停車誘導(dǎo)信息系統(tǒng)(PGIS)在國(guó)內(nèi)的起步較晚,接近上世紀(jì)末才呈現(xiàn)雛形。經(jīng)過近十年努力,雖然取得較大的進(jìn)步,但由于系統(tǒng)投入資金較大,動(dòng)輒上百萬(wàn),并且其應(yīng)用范圍比較窄,僅在北京、上海、廣州、深圳等大城市的大型停車場(chǎng)得到應(yīng)用。同時(shí),停車誘導(dǎo)信息系統(tǒng)存在許多問題:停車誘導(dǎo)過程重查詢、輕預(yù)訂,停車過程中仍然存在一定的盲目性;缺乏低成本實(shí)現(xiàn)的、滿足個(gè)性化需求的誘導(dǎo)發(fā)布手段;停車誘導(dǎo)缺乏統(tǒng)一電子支付平臺(tái)和支付手段;停車誘導(dǎo)范圍多僅限于停車場(chǎng)外誘導(dǎo),較少涉及停車場(chǎng)內(nèi)誘導(dǎo),造成停車場(chǎng)內(nèi)擁堵和無(wú)序停車;停車后,駕駛者與車位/車失去聯(lián)系,大型停車場(chǎng)面臨尋車?yán)щy等等。
本項(xiàng)目正是在這樣的背景下,開發(fā)智能停車誘導(dǎo)系統(tǒng),它大大降低系統(tǒng)建設(shè)成本,以滿足中小型停車場(chǎng)需要,將停車車位查詢和預(yù)訂相結(jié)合,方便地將停車場(chǎng)車位和預(yù)訂信息提供給駕駛者,以現(xiàn)代電子支付平臺(tái)和支付手段相結(jié)合,便于提供通用、快速、方便的結(jié)算服務(wù),同時(shí)也符合未來(lái)智能交通技術(shù)發(fā)展的趨勢(shì)。
系統(tǒng)總體結(jié)構(gòu)如圖1所示。
圖1 智能停車誘導(dǎo)系統(tǒng)總體方案
首先,利用無(wú)線信息采集系統(tǒng)將傳感器信號(hào)傳送到主控模塊,主控模塊進(jìn)行相關(guān)的信息處理;然后,將信息通過GPRS/3G傳輸?shù)叫畔l(fā)布系統(tǒng)進(jìn)行顯示,從而實(shí)現(xiàn)車位誘導(dǎo)的功能。
停車場(chǎng)信息采集系統(tǒng)是通過每個(gè)停車場(chǎng)裝置的信息采集終端,對(duì)停車場(chǎng)的使用狀況信息實(shí)時(shí)采集,采集停車場(chǎng)車位使用情況、停車時(shí)間等動(dòng)態(tài)信息,并用無(wú)線傳的方式將相關(guān)數(shù)據(jù)傳輸?shù)街鲃?dòng)系統(tǒng)中系統(tǒng)。
本系統(tǒng)各單元之間的信息傳輸采用無(wú)線傳感網(wǎng)技術(shù)。無(wú)線傳輸模塊采用市場(chǎng)上廣泛應(yīng)用的專用無(wú)線傳輸模塊。此系統(tǒng)是整個(gè)系統(tǒng)的經(jīng)脈,如果此系統(tǒng)不能正常工作、本系統(tǒng)工作不穩(wěn)定或信息傳輸不可靠。整個(gè)系統(tǒng)也將無(wú)法正常工作。
信息顯示系統(tǒng)分為兩類:一是室外信息發(fā)布顯示系統(tǒng);二是停車場(chǎng)內(nèi)的用于車位誘導(dǎo)的路徑引導(dǎo)顯示系統(tǒng);兩者的顯示信息均來(lái)自主控系統(tǒng)。
主控系統(tǒng)是智能停車誘導(dǎo)系統(tǒng)的大腦,它實(shí)時(shí)搜集各個(gè)車位的停車信息,車輛進(jìn)場(chǎng)情況。綜合分析,給出各種控制信息。比如控制室外的信息發(fā)布顯示屏(一級(jí)停車誘導(dǎo)屏),顯示停車場(chǎng)的信息,同時(shí)根據(jù)車輛進(jìn)場(chǎng)情況給出進(jìn)場(chǎng)路徑引導(dǎo)、出場(chǎng)路徑引導(dǎo)、停車時(shí)間等信息。供二級(jí)誘導(dǎo)屏接收處理和收費(fèi)系統(tǒng)用于收費(fèi)的計(jì)時(shí)時(shí)間。
駕駛?cè)巳ネ\噲?chǎng)停車跟用儲(chǔ)物柜保存物品具有相似性,故可以將儲(chǔ)物柜的思想應(yīng)用于停車場(chǎng)車位誘導(dǎo)上來(lái)。駕駛?cè)藢ふ铱胀\囄贿M(jìn)行停車,過段時(shí)間再回來(lái)取車的過程跟用戶用儲(chǔ)物柜進(jìn)行存/取物品的過程是相通的,所不同的是存物的場(chǎng)所以及所存的物品不同。
可以將每個(gè)停車位看作是一個(gè)獨(dú)立的存儲(chǔ)單元,整個(gè)停車場(chǎng)看作是一個(gè)完整的系統(tǒng)。將駕駛員存/取車的過程看作是存/取物的過程。同時(shí)結(jié)合最佳車位模型,可以做到最佳車位誘導(dǎo)。其工作流程如圖2所示。
圖2 車位誘導(dǎo)系統(tǒng)工作流程
要實(shí)現(xiàn)基于自動(dòng)儲(chǔ)物柜原理的停車位誘導(dǎo)系統(tǒng)的建立,其中最關(guān)鍵的問題是當(dāng)用戶有停車需求時(shí),系統(tǒng)給用戶指定哪個(gè)空停車位是最合理的,即對(duì)于用戶來(lái)說(shuō)哪個(gè)車位是最佳的。本文將根據(jù)停車路徑最短的準(zhǔn)則來(lái)確定最佳車位,基于對(duì)尋找空閑車位過程的分析,建立基于停車場(chǎng)車位分布圖的最佳車位數(shù)學(xué)模型,并將此模型轉(zhuǎn)化為最短路徑問題,將用蟻群算法作為車位誘導(dǎo)算法,對(duì)模型進(jìn)行尋優(yōu)。
假設(shè)某停車場(chǎng)有一個(gè)入口,n個(gè)空閑車位。將停車場(chǎng)入口、行車交叉路口、空閑車位各看成一個(gè)頂點(diǎn),每一條行車方向上的路徑對(duì)應(yīng)一條邊,邊上的權(quán)值為連續(xù)兩頂點(diǎn)之間的路徑長(zhǎng)度。于是,停車場(chǎng)空閑車位分布就轉(zhuǎn)化為一帶權(quán)有向圖G=(V,E,L)。其中V是頂點(diǎn)的有窮非空集合;E是邊集;L是路權(quán)集。
根據(jù)帶權(quán)有向圖,可生成包含l條邊的標(biāo)號(hào)矩陣a和對(duì)應(yīng)的路權(quán)矩陣d,ai1為第i條邊的起點(diǎn),ai2為終點(diǎn)。記從入口處到某個(gè)空閑車位pj的最短路徑為dm(ai2=pj)(即第i條邊的終點(diǎn)就是某個(gè)空閑的車位),則最佳車位所對(duì)應(yīng)的最短路徑即為:
其中:i=1,…,1;j=1,…,n。
要確定最佳車位,首先需要計(jì)算出從入口處到每一個(gè)空閑車位的最短路徑。在已給出停車場(chǎng)空閑車位分布帶權(quán)有向圖的前提下,尋找出一條從入口處到空閑車位之間的最短路徑的方法有好多,如經(jīng)典的Dijkstra算法、啟發(fā)式搜索算法、神經(jīng)網(wǎng)絡(luò)、遺傳算法等等。本文在綜合考慮了各種因素后選用了蟻群算法來(lái)對(duì)最短路徑進(jìn)行求解。
1)預(yù)處理
當(dāng)有較多的空停車位時(shí),可以首先對(duì)空停車位進(jìn)行一些預(yù)處理,以簡(jiǎn)化問題:設(shè)停車場(chǎng)入121處的位置坐標(biāo)為S(x,y)。以點(diǎn)S為中心,R為半徑畫圓,此圓所包含的停車場(chǎng)區(qū)域?yàn)檫M(jìn)入停車場(chǎng)車輛的附近區(qū)域,記該區(qū)域內(nèi)的空停車位集合為P,初始值為空。不斷增大半徑R 的值,直至搜索到 11 個(gè)空閑車位,此時(shí) P={p1,p2,…,pn},則帶權(quán)有向圖G為僅含起始點(diǎn)即停車場(chǎng)入口處、行車交叉路口和這n個(gè)空閑車位的帶權(quán)有向圖。
2)初始化
根據(jù)空閑車位帶權(quán)有向圖,按輸入順序依次生成路徑標(biāo)號(hào)矩陣口和對(duì)應(yīng)的路權(quán)矩陣d,以及初始信息素矩陣τ。由于螞蟻在初始選擇行車路徑時(shí),對(duì)于每條路徑的選擇概率是相等的,因此τ可設(shè)為單位矩陣。取目標(biāo)車位點(diǎn)為p1。
3)轉(zhuǎn)移概率
取中間變量temp和矩陣c,temp的初始值為S,在路徑標(biāo)號(hào)矩陣a中搜索起始點(diǎn)為ai1=temp的所有邊,并記相對(duì)應(yīng)的邊集為vk(k為可選節(jié)點(diǎn)的個(gè)數(shù)),且令 cj=ai2(j=1,…,k),根據(jù)邊(ai1,ai2)的路徑長(zhǎng)度 di1和信息素濃度τi1,令ηi1=1/di1(表示啟發(fā)信息)。則人工螞蟻從節(jié)點(diǎn)ai1轉(zhuǎn)移到節(jié)ai2的選擇概率為:
其中,參數(shù)α和β分別用來(lái)控制信息素濃度和啟發(fā)信息的相對(duì)重要程度。
4)信息素的揮發(fā)
隨著時(shí)間的推移,留在路徑上的信息素濃度會(huì)逐漸消逝。在螞蟻選中路徑(ai1,ai2)后,對(duì)信息量作如下更新和調(diào)整:
ρ表示殘留信息素的相對(duì)重要程度。Δτi1表示該螞蟻在路徑(ai1,ai2)增加的信息素濃度,其實(shí)現(xiàn)方法有3種,分別稱為Ant-Cycle,Ant-Density,Ant-Quantity算法。根據(jù)文獻(xiàn)中對(duì)3種方法的比較,本文選取Δτi1=Q/di1,其中是 Q 常量,可取 1。
5)判斷
如果當(dāng)前螞蟻所在的節(jié)點(diǎn)ai1=p1,則本次搜索結(jié)束,并保存搜索過程中經(jīng)過的節(jié)點(diǎn)和總的路徑長(zhǎng)度,以便與后面的結(jié)果作比較,第二只螞蟻開始從S點(diǎn)進(jìn)行新一輪的搜索;否則令temp=ai2,繼續(xù)進(jìn)行轉(zhuǎn)移和迭代。
6)得到從S點(diǎn)到P。的最短路徑dm(ai2=p1)后,替換目標(biāo)車位點(diǎn),進(jìn)行新一輪的計(jì)算通過以上算法計(jì)算出從始點(diǎn)至各個(gè)空閑車位的最短路徑后,進(jìn)行比較,最小值所對(duì)應(yīng)的最短路徑的終點(diǎn)即為所求的最佳車位。
在以上算法中,參數(shù)m、α、β、ρ、Q的恰當(dāng)組合對(duì)算法的性能有至關(guān)重要的影響,其選取方法和原則參考文獻(xiàn)蟻群算法中有關(guān)算法參數(shù)的最優(yōu)選擇,取
[1]王旭,崔平遠(yuǎn),陳陽(yáng)舟.基于蟻群算法求路徑規(guī)劃問題的新方法及仿真[J].計(jì)算機(jī)仿真,2005,22(7).
[2]秦固.基于蟻群優(yōu)化的多物流配送中心選址算法[J].系統(tǒng)工程理論與實(shí)踐,2006(4).
[3]王一軍,陶杰.現(xiàn)代大型停車場(chǎng)車位誘導(dǎo)優(yōu)化算法及仿真[J].計(jì)算機(jī)仿真,2007,24(11).
[4]李文仲,段朝玉,等.ZigBee無(wú)線網(wǎng)絡(luò)與無(wú)線定位實(shí)戰(zhàn)[M].北京:北京航空航天大學(xué)出版社,2008,4.