摘 要： 機動車數(shù)量日益增多為交通、環(huán)境、能源等帶來了巨大的壓力，為此提出一種改進的路徑規(guī)劃算法——膠囊形限制搜索區(qū)域路徑規(guī)劃算法。該方法在很大程度上減少了傳統(tǒng)路徑規(guī)劃方法的搜索范圍，并且通過設(shè)置動態(tài)搜索參數(shù)保證了最短路徑規(guī)劃的成功率。以拓撲結(jié)構(gòu)路網(wǎng)數(shù)據(jù)為實驗載體，對橢圓限制區(qū)域算法及改進算法進行了深入的對比和研究，并通過實驗驗證了改進算法的高效性和穩(wěn)定性。最后，給出了中心監(jiān)控式車載導(dǎo)航系統(tǒng)的初步設(shè)計方案，其由監(jiān)控中心子系統(tǒng)、車載子系統(tǒng)和通信子系統(tǒng)三部分組成。

關(guān)鍵詞： 車載導(dǎo)航系統(tǒng)； 電子地圖； 拓撲結(jié)構(gòu)； 路徑規(guī)劃； 限制搜索區(qū)域

中圖分類號： TN96?34； TM417 文獻標(biāo)識碼： A 文章編號： 1004?373X（2016）13?0133?04

Abstract： The increasing quantity of motor vehicles brings huge pressure for traffic， environment， energy， etc. An improved path planning algorithm is proposed， which is called capsule?like restricted searching area path planning algorithm. This method can greatly reduce the searching range of traditional path planning methods， and ensure the success rate of shortest path planning by means of setting the dynamic searching parameter. The ellipse restricted area algorithm and improved algorithm are deeply compared and studied by taking the road network data of the topology structure as the experimental platform. The high efficiency and stability of the improved algorthm were verified by experiment. The preliminary design scheme of the vehicle?mounted navigation system with center mo?nitoring is given， which is composed of monitoring center subsystem， vehicle?mounted subsystem and communication subsystem.

Keywords： vehicle?mounted navigation system； electronic map； topology structure； path planning； restricted searching area

僅僅通過道路基礎(chǔ)設(shè)施建設(shè)來解決交通問題，已經(jīng)不能滿足快速增長的機動車數(shù)量對交通的需求，而智能交通系統(tǒng)的出現(xiàn)大大改善了交通狀況，合理利用現(xiàn)有道路資源，就可以大幅度提高路網(wǎng)的使用率和使用質(zhì)量，從而達到減少交通堵塞現(xiàn)象的目的。車載導(dǎo)航系統(tǒng)，作為ITS的關(guān)鍵組成部分之一，不僅能夠為用戶準(zhǔn)確地提供一條前往目標(biāo)地點的合理道路，還使得單個車體與城市交通系統(tǒng)網(wǎng)絡(luò)有機融合，從而能夠順利避開堵塞的道路，使得外出效率大為提高。

1 車載導(dǎo)航系統(tǒng)電子地圖的實現(xiàn)

1.1 電子地圖中道路網(wǎng)絡(luò)數(shù)據(jù)模型

道路網(wǎng)絡(luò)的數(shù)據(jù)模型是生成具有拓撲結(jié)構(gòu)道路網(wǎng)絡(luò)的基礎(chǔ)。車載導(dǎo)航電子地圖是由點、線和面三個基本元素組成。整個道路網(wǎng)絡(luò)的表示一般采用Arc?Node模型，該模型的特點是易于表達實際路網(wǎng)的拓撲關(guān)系，且形式簡潔?？紤]到實際電子地圖的面是由弧段組成，故可以將路網(wǎng)歸結(jié)為節(jié)點和弧段兩個基本元素的組合。Arc?Node模型的基本原理是在一定的精度范圍之內(nèi)，采用以直代曲的思想，由連續(xù)的小段直線代替和逼近真實的道路曲線，這樣就形成了Arc?Node數(shù)據(jù)模型，其形式化定義為：

式中：為路網(wǎng)；為路網(wǎng)的節(jié)點集；為路網(wǎng)的有向路段集；和為路段的起點和終點；為路段的屬性集，可表示為距離、時間和花費等。

同時，根據(jù)實際交通網(wǎng)絡(luò)的特點，做如下的分析假設(shè)：所有的邊都是線段，對于彎曲弧度數(shù)較大的路段，可通過在該路段上插入一系列節(jié)點使該路段由一些弧度較小的路段構(gòu)成，把弧度較小的路段假設(shè)為一條線段。如圖1所示，節(jié)點1和2之間的路徑弧度較大，在原路徑上插入節(jié)點3和4，將原路段分割成弧度相對較小的三個路段。邊長通常是雙向可通的，邊的權(quán)值為正值。

網(wǎng)絡(luò)中有較多的節(jié)點和邊，與節(jié)點相關(guān)聯(lián)的邊數(shù)為常數(shù)，且遠小于網(wǎng)絡(luò)中總的節(jié)點數(shù)。

1.2 導(dǎo)航電子地圖中折線網(wǎng)絡(luò)拓撲化算法實現(xiàn)

算法實現(xiàn)的原理可以簡單的描述為：依據(jù)折線道路網(wǎng)絡(luò)的組成特點及Arc?Node數(shù)據(jù)模型，由給定的折線道路網(wǎng)絡(luò)生成表示其拓撲結(jié)構(gòu)的Arc?Node數(shù)據(jù)模型。生成過程基本可以分成兩個步驟：第一步是完善給定的折線道路網(wǎng)絡(luò)數(shù)據(jù)，即對1.1節(jié)中介紹的道路網(wǎng)絡(luò)的幾個情況進行相應(yīng)的處理；第二步是在第一步的基礎(chǔ)上，由完善后的折線數(shù)據(jù)網(wǎng)絡(luò)數(shù)據(jù)生成表示其拓撲結(jié)構(gòu)的Arc?Node數(shù)據(jù)結(jié)構(gòu)。整個算法流程如圖2所示。

2 車載導(dǎo)航系統(tǒng)路徑規(guī)劃搜索算法

2.1 橢圓限制搜索區(qū)域路徑規(guī)劃算法

橢圓限制區(qū)域的最短路徑算法思想如下：以起始點和終點為焦點，以為長軸長畫一個橢圓，然后在橢圓區(qū)域內(nèi)的站點間尋找最短路徑。其中，為起始點到終點的歐式距離，是一個與城市路網(wǎng)信息有關(guān)的統(tǒng)計參數(shù)。所以，橢圓限制區(qū)域的最短路徑算法是依賴于城市的統(tǒng)計參數(shù)的，統(tǒng)計數(shù)據(jù)表明對于北京路網(wǎng)的值為1.417。構(gòu)造橢圓限制區(qū)域的方法如下：

（1） 建立直角坐標(biāo)系：軸為軸為與其垂直的方向。

（2） 以起始點為圓心，的連線為半徑，作圓該圓內(nèi)的區(qū)域就是傳統(tǒng)最短路徑規(guī)劃算法Dijkstra算法的搜索區(qū)域。

（3） 以起始點終點為焦點，作橢圓橢圓內(nèi)的區(qū)域就是橢圓限制搜索區(qū)域路徑規(guī)劃算法的搜索區(qū)域。其中橢圓的長半軸與橢圓相交于點和點形成的橢圓陰影區(qū)域就是算法的搜索范圍。

橢圓限制搜索區(qū)域路徑規(guī)劃算法的實現(xiàn)步驟比較簡單，具體如下：輸入起始點終點完成道路的網(wǎng)絡(luò)數(shù)據(jù)加載及程序運行環(huán)境設(shè)置等；根據(jù)起始點構(gòu)造橢圓限制搜索的區(qū)域；在構(gòu)造的限制搜索區(qū)域內(nèi)，調(diào)用Dijkstra算法進行最短路徑計算；輸出起始點和終點之間的最短路徑。

2.2 改進的限制搜索區(qū)域路徑規(guī)劃算法

膠囊形限制搜索區(qū)域路徑規(guī)劃算法的原理與橢圓限制搜索區(qū)域路徑規(guī)劃算法類似，搜索起始點到終點的最短路徑時，只需要考慮中間膠囊形陰影部分的路段和節(jié)點，該膠囊形限制搜索區(qū)域路徑規(guī)劃算法的搜索范圍比Dijkstra搜索算法和橢圓限制搜索區(qū)域算法都大大縮小；并且以線段作為上下邊界的限制，在一定程度上減少了判定節(jié)點是否落在限制區(qū)域內(nèi)時橢圓算法需要進行的大量乘積和開方運算，從而提高了整個搜索過程的效率。具體的搜索區(qū)域設(shè)置方法如下：

（1） 軸為軸為與其垂直的方向，以起始點為原點建立一個直角坐標(biāo)系；

（2） 以起始點為圓心，的連線為半徑，作圓該圓內(nèi)的區(qū)域就是傳統(tǒng)最短路徑規(guī)劃算法Dijkstra算法的搜索區(qū)域；

（3） 以起始點終點為焦點，作橢圓橢圓內(nèi)的區(qū)域就是橢圓限制搜索區(qū)域路徑規(guī)劃算法的搜索區(qū)域。其中橢圓的長半軸與橢圓相交于點和點

（4） 分別以起始點終點為圓心，線段AS（DK）為半徑作兩個半圓EAF和VKG，連接點和點形成了如圖3所示的陰影的膠囊形限制區(qū)域，該區(qū)域即為改進算法的路徑規(guī)劃搜索范圍。

由上面提到的道路路網(wǎng)統(tǒng)計參數(shù)可知，橢圓限制搜索區(qū)域路徑規(guī)劃算法搜索的成功建立在95%的置信水平之上，也就是還有5%的可能性，實際最短路徑上的節(jié)點落在限制區(qū)域之外，這就可能導(dǎo)致搜索的失敗，膠囊形限制搜索區(qū)域路徑規(guī)劃跟橢圓限制搜索區(qū)域路徑規(guī)劃存在同樣可能導(dǎo)致搜索失敗的情況，因此就必須通過調(diào)節(jié)半圓的參數(shù)半徑擴大搜索范圍，保證搜索成功，提高算法的可靠性。修正后的算法步驟如下：

第1步：輸入搜索起始點和終點完成拓撲化路網(wǎng)數(shù)據(jù)加載及程序運行環(huán)境設(shè)置等；

第2步：根據(jù)起始點構(gòu)造初始膠囊形限制區(qū)域算法的搜索區(qū)域，閾值半徑為

第3步：在構(gòu)造完成的膠囊形限制區(qū)域中調(diào)用Dijkstra算法，進行最短路徑規(guī)劃，若搜索成功則轉(zhuǎn)步驟5，否則繼續(xù)；

第4步：設(shè)置動態(tài)變化參數(shù)以起始點終點為圓心，以上一次搜索的閾值半徑加上為半圓半徑構(gòu)造新的膠囊形限制搜索區(qū)域，如圖4中虛線包圍區(qū)域所示，構(gòu)造完成后轉(zhuǎn)第3步；

第5步：輸出搜索得出的最短路徑，算法結(jié)束。

3 中心監(jiān)控式車載導(dǎo)航系統(tǒng)初步設(shè)計

3.1 中心監(jiān)控式車載導(dǎo)航系統(tǒng)構(gòu)成

中心監(jiān)控式車載導(dǎo)航系統(tǒng)除具有導(dǎo)航功能外，通過借助通信網(wǎng)絡(luò)，還能夠采集信息、分析信息，路徑規(guī)劃在中心根據(jù)實時交通情況完成。實際應(yīng)用時，通常需要根據(jù)車載終端的具體需要進行配置，通常至少應(yīng)包含監(jiān)控中心子系統(tǒng)、車載子系統(tǒng)和通信子系統(tǒng)三部分。

監(jiān)控中心子系統(tǒng)：系統(tǒng)接收車載子系統(tǒng)發(fā)送的車輛速度、位置、報警等信息，然后在導(dǎo)航電子地圖拓撲路網(wǎng)基礎(chǔ)上對車輛狀態(tài)進行實時顯示、并且進行車載子系統(tǒng)的路徑查詢、數(shù)據(jù)分析處理要求。處理完成之后，并對系統(tǒng)和車載子系統(tǒng)進行參數(shù)設(shè)置及控制。

車載子系統(tǒng)：車載子系統(tǒng)負責(zé)與監(jiān)控中心子系統(tǒng)通信，把車輛位置信息、報警狀態(tài)發(fā)送給監(jiān)控中心子系統(tǒng)，同時接收監(jiān)控中心子系統(tǒng)的反饋指令對車輛進行相關(guān)控制。車載子系統(tǒng)結(jié)構(gòu)組成如圖5所示。

通信子系統(tǒng)：中心監(jiān)控式車載導(dǎo)航系統(tǒng)的關(guān)鍵部分之一。選擇正確的通信方式，連接車載子系統(tǒng)和監(jiān)控中心子系統(tǒng)十分重要。首先必須考慮到通信系統(tǒng)網(wǎng)覆蓋范圍，其次還必須考慮車輛行駛過程中可能遭遇的惡劣環(huán)境影響。

3.2 中心監(jiān)控式車載導(dǎo)航工作原理

車載GPS接收機接收定位衛(wèi)星發(fā)來的定位數(shù)據(jù)，并且根據(jù)4顆不同衛(wèi)星發(fā)來的星歷數(shù)據(jù)計算出自身所處地理位置的坐標(biāo)，該坐標(biāo)數(shù)據(jù)通過符合GSM標(biāo)準(zhǔn)的無線模塊，采用SMS形式，由車載終端將車輛的位置狀態(tài)、報警器輸入信息發(fā)送至GSM網(wǎng)，GSM網(wǎng)將接收到的車輛定位信息通過互聯(lián)網(wǎng)或者通信接發(fā)設(shè)備送至中心控制子系統(tǒng)，以便監(jiān)控中心及時掌握車輛的動態(tài)位置信息，進一步控制車載終端。其中的定位信息傳輸功能實現(xiàn)所需軟件為通信服務(wù)器軟件，主要完成車輛和監(jiān)控中心之間的數(shù)據(jù)傳輸與通信，實現(xiàn)數(shù)據(jù)收發(fā)、編碼、解碼、數(shù)據(jù)入庫等工作。監(jiān)控中心則完成車輛位置信息的可視化、車輛行駛的最優(yōu)路徑規(guī)劃及各種控制指令的發(fā)送等功能?；贕PS和GSM短消息業(yè)務(wù)的中心監(jiān)控式車載導(dǎo)航系統(tǒng)的工作示意圖如圖6所示。

3.3 中心監(jiān)控式車載導(dǎo)航軟件實現(xiàn)

中心監(jiān)控式車載導(dǎo)航系統(tǒng)的軟件設(shè)計具有良好的人機交互界面和數(shù)據(jù)處理能力。首先構(gòu)建一個客戶端/服務(wù)器結(jié)構(gòu)，數(shù)據(jù)庫安裝在控制中心子系統(tǒng)上，數(shù)據(jù)庫管理采用結(jié)構(gòu)化查詢語言，客戶端采用Windows操作系統(tǒng)，應(yīng)用程序采用VC 2010進行開發(fā)。中心監(jiān)控式導(dǎo)航監(jiān)控中心軟件設(shè)計通常要考慮5個功能模塊組成：

地圖顯示模塊：為達到對車輛監(jiān)控的目的，能夠顯示車輛軌跡、車速等；

信息點管理模塊：信息點被分類存儲后，在管理用戶界面中體現(xiàn)，用戶可以對信息點數(shù)據(jù)庫進行管理，如刪除、添加或修改等；

數(shù)據(jù)顯示模塊：解碼信息顯示于終端；

指令下載模塊：將路徑導(dǎo)航指令實時下載到車載終端；

系統(tǒng)隱私保護模塊：車輛管理數(shù)據(jù)庫，存有車輛的電子編號用于計算機檢索和處理，保證車輛信息的安全。

4 實驗驗證及結(jié)果分析

為了驗證提出的膠囊形限制搜索區(qū)域路徑規(guī)劃算法的有效性和可靠性，使用125 000比例尺下MapInfo格式的北京2011年交通圖作為電子地圖數(shù)據(jù)源（該地圖道路網(wǎng)絡(luò)共有97 773個地理特征數(shù)量），在WIN 7平臺Microsoft Visual Studio 2010編程環(huán)境下對橢圓限制搜索區(qū)域以及膠囊形限制搜索區(qū)域最短路徑規(guī)劃算法的性能進行測試。為了簡潔，這里用SF1表示橢圓限制搜索區(qū)域路徑規(guī)劃算法；SF2表示膠囊形限制搜索區(qū)域路徑規(guī)劃算法。

為了保證兩種算法的可靠性，反復(fù)給定不同的搜索起點和終點，對比各種算法的搜索時間和規(guī)劃路徑長度等實驗數(shù)據(jù)。考慮到論文篇幅的限制，這里僅給出起點編號為797，終點編號為2 195情況下的算法的實際路徑規(guī)劃結(jié)果圖。圖7表示算法SF1路徑規(guī)劃結(jié)果，圖8表示算法SF2路徑規(guī)劃結(jié)果。

兩種算法的性能對比如表1所示。表中ST表示測試給定的起點，DT表示測試的目標(biāo)終點；分別表示算法SF1，SF2在相同情況下所用的搜索時間（單位：s）。分別表示算法SF1，SF2在相同情況下所規(guī)劃出的最短路徑長度（單位：m）。

由表1可以看出，在相同的起點和終點下，在搜索的高效性方面，啟發(fā)式搜索算法SF2明顯比傳統(tǒng)算法SF1優(yōu)越很多，提出的改進路徑規(guī)劃方法比算法SF1的搜索效率有20%左右的提升；改進算法SF2，通過設(shè)置動態(tài)參數(shù)避免了此種情況的發(fā)生，很好的保證了搜索的可靠性。綜上所述，可見本文提出的改進路徑規(guī)劃算法在搜索效率和搜索可靠性方面都具有相當(dāng)?shù)膬?yōu)越性。

5 結(jié) 論

本文在拓撲化路網(wǎng)數(shù)據(jù)基礎(chǔ)上，提出了一種改進的路徑規(guī)劃算法——膠囊形限制搜索區(qū)域路徑規(guī)劃算法。該方法在很大程度上減少了傳統(tǒng)路徑規(guī)劃方法的搜索范圍，再通過設(shè)置動態(tài)搜索參數(shù)保證了路徑規(guī)劃的成功率。并且以拓撲結(jié)構(gòu)路網(wǎng)數(shù)據(jù)為實驗載體，對橢圓限制區(qū)域算法及提出的改進算法進行了深入的對比和研究，通過實驗驗證了改進算法的高效性和穩(wěn)定性。最后，給出了中心監(jiān)控式車載導(dǎo)航系統(tǒng)的初步設(shè)計方案。

參考文獻

[1] 屈展.車載導(dǎo)航系統(tǒng)中路徑規(guī)劃問題的研究[D].蘭州：蘭州理工大學(xué)，2012：253?257.

[2] 高星.淺論車載導(dǎo)航系統(tǒng)的現(xiàn)狀及發(fā)展趨勢[J].計算機光盤軟件與應(yīng)用，2011（6）：76?77.

[3] 陳圣，董林飛.Dijkstra和A*算法在智能導(dǎo)航中的應(yīng)用分析[J].重慶科技學(xué)院學(xué)報，2010，12（6）：159?161.

[4] 尹路明，張志恒，張小朋.一種新型GPS/DR組合導(dǎo)航系統(tǒng)[J].現(xiàn)代電子技術(shù)，2014，37（13）：136?138.

[5] 羅國青.車輛定位導(dǎo)航系統(tǒng)動態(tài)路徑規(guī)劃研究[D].長沙：湖南大學(xué)，2011：321?323.

[6] CHEN Heping， LI Xianqin， GU Jinguan， et al. Research of path planning algorithms based on vector map data structure [J]. Computer engineering and applications， 2010， 39（19）： 238?245.

[7] ZHAO Yilin. Vehicle location and navigation systems [M]. Boston： Artech House， 2010： 108?111.

[8] ABBOTT E， POWELL D. Land?vehicle navigation using GPS [J]. Proceedings of the IEEE， 1999， 87（1）： 145?162.