秦 澄 徐雪峰

（淮安信息職業(yè)技術(shù)學(xué)院，江蘇 淮安 223003）

0 引言

停車誘導(dǎo)信息系統(tǒng)（PGIS）在國內(nèi)的起步較晚，接近上世紀末才呈現(xiàn)雛形。經(jīng)過近十年努力，雖然取得較大的進步，但由于系統(tǒng)投入資金較大，動輒上百萬，并且其應(yīng)用范圍比較窄，僅在北京、上海、廣州、深圳等大城市的大型停車場得到應(yīng)用。同時，停車誘導(dǎo)信息系統(tǒng)存在許多問題：停車誘導(dǎo)過程重查詢、輕預(yù)訂，停車過程中仍然存在一定的盲目性；缺乏低成本實現(xiàn)的、滿足個性化需求的誘導(dǎo)發(fā)布手段；停車誘導(dǎo)缺乏統(tǒng)一電子支付平臺和支付手段；停車誘導(dǎo)范圍多僅限于停車場外誘導(dǎo)，較少涉及停車場內(nèi)誘導(dǎo)，造成停車場內(nèi)擁堵和無序停車；停車后，駕駛者與車位／車失去聯(lián)系，大型停車場面臨尋車困難等等。

本項目正是在這樣的背景下，開發(fā)智能停車誘導(dǎo)系統(tǒng)，它大大降低系統(tǒng)建設(shè)成本，以滿足中小型停車場需要，將停車車位查詢和預(yù)訂相結(jié)合，方便地將停車場車位和預(yù)訂信息提供給駕駛者，以現(xiàn)代電子支付平臺和支付手段相結(jié)合，便于提供通用、快速、方便的結(jié)算服務(wù)，同時也符合未來智能交通技術(shù)發(fā)展的趨勢。

1 總體方案設(shè)計

系統(tǒng)總體結(jié)構(gòu)如圖1所示。

圖1 智能停車誘導(dǎo)系統(tǒng)總體方案

首先，利用無線信息采集系統(tǒng)將傳感器信號傳送到主控模塊，主控模塊進行相關(guān)的信息處理；然后，將信息通過GPRS/3G傳輸?shù)叫畔l(fā)布系統(tǒng)進行顯示，從而實現(xiàn)車位誘導(dǎo)的功能。

1.1 信息采集系統(tǒng)

停車場信息采集系統(tǒng)是通過每個停車場裝置的信息采集終端，對停車場的使用狀況信息實時采集，采集停車場車位使用情況、停車時間等動態(tài)信息，并用無線傳的方式將相關(guān)數(shù)據(jù)傳輸?shù)街鲃酉到y(tǒng)中系統(tǒng)。

1.2 信息傳輸系統(tǒng)

本系統(tǒng)各單元之間的信息傳輸采用無線傳感網(wǎng)技術(shù)。無線傳輸模塊采用市場上廣泛應(yīng)用的專用無線傳輸模塊。此系統(tǒng)是整個系統(tǒng)的經(jīng)脈，如果此系統(tǒng)不能正常工作、本系統(tǒng)工作不穩(wěn)定或信息傳輸不可靠。整個系統(tǒng)也將無法正常工作。

1.3 信息顯示系統(tǒng)

信息顯示系統(tǒng)分為兩類：一是室外信息發(fā)布顯示系統(tǒng)；二是停車場內(nèi)的用于車位誘導(dǎo)的路徑引導(dǎo)顯示系統(tǒng)；兩者的顯示信息均來自主控系統(tǒng)。

1.4 主控系統(tǒng)

主控系統(tǒng)是智能停車誘導(dǎo)系統(tǒng)的大腦，它實時搜集各個車位的停車信息，車輛進場情況。綜合分析，給出各種控制信息。比如控制室外的信息發(fā)布顯示屏（一級停車誘導(dǎo)屏），顯示停車場的信息，同時根據(jù)車輛進場情況給出進場路徑引導(dǎo)、出場路徑引導(dǎo)、停車時間等信息。供二級誘導(dǎo)屏接收處理和收費系統(tǒng)用于收費的計時時間。

2 車位誘導(dǎo)系統(tǒng)工作原理

駕駛?cè)巳ネ＼噲鐾＼嚫脙ξ锕癖４嫖锲肪哂邢嗨菩?，故可以將儲物柜的思想?yīng)用于停車場車位誘導(dǎo)上來。駕駛?cè)藢ふ铱胀＼囄贿M行停車，過段時間再回來取車的過程跟用戶用儲物柜進行存／取物品的過程是相通的，所不同的是存物的場所以及所存的物品不同。

可以將每個停車位看作是一個獨立的存儲單元，整個停車場看作是一個完整的系統(tǒng)。將駕駛員存／取車的過程看作是存／取物的過程。同時結(jié)合最佳車位模型，可以做到最佳車位誘導(dǎo)。其工作流程如圖2所示。

圖2 車位誘導(dǎo)系統(tǒng)工作流程

3 車位優(yōu)化模型設(shè)計與算法實現(xiàn)

要實現(xiàn)基于自動儲物柜原理的停車位誘導(dǎo)系統(tǒng)的建立，其中最關(guān)鍵的問題是當用戶有停車需求時，系統(tǒng)給用戶指定哪個空停車位是最合理的，即對于用戶來說哪個車位是最佳的。本文將根據(jù)停車路徑最短的準則來確定最佳車位，基于對尋找空閑車位過程的分析，建立基于停車場車位分布圖的最佳車位數(shù)學(xué)模型，并將此模型轉(zhuǎn)化為最短路徑問題，將用蟻群算法作為車位誘導(dǎo)算法，對模型進行尋優(yōu)。

3.1 最佳車位模型

假設(shè)某停車場有一個入口，n個空閑車位。將停車場入口、行車交叉路口、空閑車位各看成一個頂點，每一條行車方向上的路徑對應(yīng)一條邊，邊上的權(quán)值為連續(xù)兩頂點之間的路徑長度。于是，停車場空閑車位分布就轉(zhuǎn)化為一帶權(quán)有向圖G=（V，E，L）。其中V是頂點的有窮非空集合；E是邊集；L是路權(quán)集。

根據(jù)帶權(quán)有向圖，可生成包含l條邊的標號矩陣a和對應(yīng)的路權(quán)矩陣d，ai1為第i條邊的起點，ai2為終點。記從入口處到某個空閑車位pj的最短路徑為dm（ai2＝pj）（即第i條邊的終點就是某個空閑的車位），則最佳車位所對應(yīng)的最短路徑即為：

其中：i=1，…，1；j=1，…，n。

3.2 車位優(yōu)化算法

要確定最佳車位，首先需要計算出從入口處到每一個空閑車位的最短路徑。在已給出停車場空閑車位分布帶權(quán)有向圖的前提下，尋找出一條從入口處到空閑車位之間的最短路徑的方法有好多，如經(jīng)典的Dijkstra算法、啟發(fā)式搜索算法、神經(jīng)網(wǎng)絡(luò)、遺傳算法等等。本文在綜合考慮了各種因素后選用了蟻群算法來對最短路徑進行求解。

1）預(yù)處理

當有較多的空停車位時，可以首先對空停車位進行一些預(yù)處理，以簡化問題：設(shè)停車場入121處的位置坐標為S（x，y）。以點S為中心，R為半徑畫圓，此圓所包含的停車場區(qū)域為進入停車場車輛的附近區(qū)域，記該區(qū)域內(nèi)的空停車位集合為P，初始值為空。不斷增大半徑R 的值，直至搜索到 11 個空閑車位，此時 P=｛p1，p2，…，pn｝，則帶權(quán)有向圖G為僅含起始點即停車場入口處、行車交叉路口和這n個空閑車位的帶權(quán)有向圖。

2）初始化

根據(jù)空閑車位帶權(quán)有向圖，按輸入順序依次生成路徑標號矩陣口和對應(yīng)的路權(quán)矩陣d，以及初始信息素矩陣τ。由于螞蟻在初始選擇行車路徑時，對于每條路徑的選擇概率是相等的，因此τ可設(shè)為單位矩陣。取目標車位點為p1。

3）轉(zhuǎn)移概率

取中間變量temp和矩陣c，temp的初始值為S，在路徑標號矩陣a中搜索起始點為ai1=temp的所有邊，并記相對應(yīng)的邊集為vk（k為可選節(jié)點的個數(shù)），且令 cj＝ai2（j=1，…，k），根據(jù)邊（ai1，ai2）的路徑長度 di1和信息素濃度τi1，令ηi1＝1／di1（表示啟發(fā)信息）。則人工螞蟻從節(jié)點ai1轉(zhuǎn)移到節(jié)ai2的選擇概率為：

其中，參數(shù)α和β分別用來控制信息素濃度和啟發(fā)信息的相對重要程度。

4）信息素的揮發(fā)

隨著時間的推移，留在路徑上的信息素濃度會逐漸消逝。在螞蟻選中路徑（ai1，ai2）后，對信息量作如下更新和調(diào)整：

ρ表示殘留信息素的相對重要程度。Δτi1表示該螞蟻在路徑（ai1，ai2）增加的信息素濃度，其實現(xiàn)方法有3種，分別稱為Ant-Cycle，Ant-Density，Ant-Quantity算法。根據(jù)文獻中對3種方法的比較，本文選取Δτi1=Q/di1，其中是 Q 常量，可取 1。

5）判斷

如果當前螞蟻所在的節(jié)點ai1=p1，則本次搜索結(jié)束，并保存搜索過程中經(jīng)過的節(jié)點和總的路徑長度，以便與后面的結(jié)果作比較，第二只螞蟻開始從S點進行新一輪的搜索；否則令temp=ai2，繼續(xù)進行轉(zhuǎn)移和迭代。

6）得到從S點到P。的最短路徑dm（ai2=p1）后，替換目標車位點，進行新一輪的計算通過以上算法計算出從始點至各個空閑車位的最短路徑后，進行比較，最小值所對應(yīng)的最短路徑的終點即為所求的最佳車位。

在以上算法中，參數(shù)m、α、β、ρ、Q的恰當組合對算法的性能有至關(guān)重要的影響，其選取方法和原則參考文獻蟻群算法中有關(guān)算法參數(shù)的最優(yōu)選擇，取

［1］王旭，崔平遠，陳陽舟.基于蟻群算法求路徑規(guī)劃問題的新方法及仿真[J].計算機仿真，2005，22(7).

［2］秦固.基于蟻群優(yōu)化的多物流配送中心選址算法[J].系統(tǒng)工程理論與實踐，2006(4).

［3］王一軍，陶杰.現(xiàn)代大型停車場車位誘導(dǎo)優(yōu)化算法及仿真[J].計算機仿真，2007，24(11).

［4］李文仲，段朝玉，等.ZigBee無線網(wǎng)絡(luò)與無線定位實戰(zhàn)[M].北京：北京航空航天大學(xué)出版社，2008，4.