基于車載導航系統的路徑規劃方法研究

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

關鍵詞： 車載導航系統； 電子地圖； 拓撲結構； 路徑規劃； 限制搜索區域

中圖分類號： TN96?34； TM417 文獻標識碼： 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

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

1 車載導航系統電子地圖的實現

1.1 電子地圖中道路網絡數據模型

道路網絡的數據模型是生成具有拓撲結構道路網絡的基礎。車載導航電子地圖是由點、線和面三個基本元素組成。整個道路網絡的表示一般采用Arc?Node模型，該模型的特點是易于表達實際路網的拓撲關系，且形式簡潔。考慮到實際電子地圖的面是由弧段組成，故可以將路網歸結為節點和弧段兩個基本元素的組合。Arc?Node模型的基本原理是在一定的精度范圍之內，采用以直代曲的思想，由連續的小段直線代替和逼近真實的道路曲線，這樣就形成了Arc?Node數據模型，其形式化定義為：

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

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

網絡中有較多的節點和邊，與節點相關聯的邊數為常數，且遠小于網絡中總的節點數。

1.2 導航電子地圖中折線網絡拓撲化算法實現

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

2 車載導航系統路徑規劃搜索算法

2.1 橢圓限制搜索區域路徑規劃算法

橢圓限制區域的最短路徑算法思想如下：以起始點和終點為焦點，以為長軸長畫一個橢圓，然后在橢圓區域內的站點間尋找最短路徑。其中，為起始點到終點的歐式距離，是一個與城市路網信息有關的統計參數。所以，橢圓限制區域的最短路徑算法是依賴于城市的統計參數的，統計數據表明對于北京路網的值為1.417。構造橢圓限制區域的方法如下：

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

（2） 以起始點為圓心，的連線為半徑，作圓該圓內的區域就是傳統最短路徑規劃算法Dijkstra算法的搜索區域。

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

橢圓限制搜索區域路徑規劃算法的實現步驟比較簡單，具體如下：輸入起始點終點完成道路的網絡數據加載及程序運行環境設置等；根據起始點構造橢圓限制搜索的區域；在構造的限制搜索區域內，調用Dijkstra算法進行最短路徑計算；輸出起始點和終點之間的最短路徑。

2.2 改進的限制搜索區域路徑規劃算法

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

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

（2） 以起始點為圓心，的連線為半徑，作圓該圓內的區域就是傳統最短路徑規劃算法Dijkstra算法的搜索區域；

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

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

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

第1步：輸入搜索起始點和終點完成拓撲化路網數據加載及程序運行環境設置等；

第2步：根據起始點構造初始膠囊形限制區域算法的搜索區域，閾值半徑為

第3步：在構造完成的膠囊形限制區域中調用Dijkstra算法，進行最短路徑規劃，若搜索成功則轉步驟5，否則繼續；

第4步：設置動態變化參數以起始點終點為圓心，以上一次搜索的閾值半徑加上為半圓半徑構造新的膠囊形限制搜索區域，如圖4中虛線包圍區域所示，構造完成后轉第3步；

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

3 中心監控式車載導航系統初步設計

3.1 中心監控式車載導航系統構成

中心監控式車載導航系統除具有導航功能外，通過借助通信網絡，還能夠采集信息、分析信息，路徑規劃在中心根據實時交通情況完成。實際應用時，通常需要根據車載終端的具體需要進行配置，通常至少應包含監控中心子系統、車載子系統和通信子系統三部分。

監控中心子系統：系統接收車載子系統發送的車輛速度、位置、報警等信息，然后在導航電子地圖拓撲路網基礎上對車輛狀態進行實時顯示、并且進行車載子系統的路徑查詢、數據分析處理要求。處理完成之后，并對系統和車載子系統進行參數設置及控制。

車載子系統：車載子系統負責與監控中心子系統通信，把車輛位置信息、報警狀態發送給監控中心子系統，同時接收監控中心子系統的反饋指令對車輛進行相關控制。車載子系統結構組成如圖5所示。

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

3.2 中心監控式車載導航工作原理

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

3.3 中心監控式車載導航軟件實現

中心監控式車載導航系統的軟件設計具有良好的人機交互界面和數據處理能力。首先構建一個客戶端/服務器結構，數據庫安裝在控制中心子系統上，數據庫管理采用結構化查詢語言，客戶端采用Windows操作系統，應用程序采用VC 2010進行開發。中心監控式導航監控中心軟件設計通常要考慮5個功能模塊組成：

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

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

數據顯示模塊：解碼信息顯示于終端；

指令下載模塊：將路徑導航指令實時下載到車載終端；

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

4 實驗驗證及結果分析

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

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

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

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

5 結 論

本文在拓撲化路網數據基礎上，提出了一種改進的路徑規劃算法——膠囊形限制搜索區域路徑規劃算法。該方法在很大程度上減少了傳統路徑規劃方法的搜索范圍，再通過設置動態搜索參數保證了路徑規劃的成功率。并且以拓撲結構路網數據為實驗載體，對橢圓限制區域算法及提出的改進算法進行了深入的對比和研究，通過實驗驗證了改進算法的高效性和穩定性。最后，給出了中心監控式車載導航系統的初步設計方案。

參考文獻

[1] 屈展.車載導航系統中路徑規劃問題的研究[D].蘭州：蘭州理工大學，2012：253?257.

[2] 高星.淺論車載導航系統的現狀及發展趨勢[J].計算機光盤軟件與應用，2011（6）：76?77.

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

[4] 尹路明，張志恒，張小朋.一種新型GPS/DR組合導航系統[J].現代電子技術，2014，37（13）：136?138.

[5] 羅國青.車輛定位導航系統動態路徑規劃研究[D].長沙：湖南大學，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.