基于車載導(dǎo)航系統(tǒng)的路徑規(guī)劃方法研究

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

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

中圖分類號(hào)： TN96?34； TM417 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 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)不能滿足快速增長(zhǎng)的機(jī)動(dòng)車數(shù)量對(duì)交通的需求，而智能交通系統(tǒng)的出現(xiàn)大大改善了交通狀況，合理利用現(xiàn)有道路資源，就可以大幅度提高路網(wǎng)的使用率和使用質(zhì)量，從而達(dá)到減少交通堵塞現(xiàn)象的目的。車載導(dǎo)航系統(tǒng)，作為ITS的關(guān)鍵組成部分之一，不僅能夠?yàn)橛脩魷?zhǔn)確地提供一條前往目標(biāo)地點(diǎn)的合理道路，還使得單個(gè)車體與城市交通系統(tǒng)網(wǎng)絡(luò)有機(jī)融合，從而能夠順利避開堵塞的道路，使得外出效率大為提高。

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

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

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

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

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

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

1.2 導(dǎo)航電子地圖中折線網(wǎng)絡(luò)拓?fù)浠惴▽?shí)現(xiàn)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

第1步：輸入搜索起始點(diǎn)和終點(diǎn)完成拓?fù)浠肪W(wǎng)數(shù)據(jù)加載及程序運(yùn)行環(huán)境設(shè)置等；

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

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

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

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

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

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

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

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

車載子系統(tǒng)：車載子系統(tǒng)負(fù)責(zé)與監(jiān)控中心子系統(tǒng)通信，把車輛位置信息、報(bào)警狀態(tài)發(fā)送給監(jiān)控中心子系統(tǒng)，同時(shí)接收監(jiān)控中心子系統(tǒng)的反饋指令對(duì)車輛進(jìn)行相關(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接收機(jī)接收定位衛(wèi)星發(fā)來的定位數(shù)據(jù)，并且根據(jù)4顆不同衛(wèi)星發(fā)來的星歷數(shù)據(jù)計(jì)算出自身所處地理位置的坐標(biāo)，該坐標(biāo)數(shù)據(jù)通過符合GSM標(biāo)準(zhǔn)的無線模塊，采用SMS形式，由車載終端將車輛的位置狀態(tài)、報(bào)警器輸入信息發(fā)送至GSM網(wǎng)，GSM網(wǎng)將接收到的車輛定位信息通過互聯(lián)網(wǎng)或者通信接發(fā)設(shè)備送至中心控制子系統(tǒng)，以便監(jiān)控中心及時(shí)掌握車輛的動(dòng)態(tài)位置信息，進(jìn)一步控制車載終端。其中的定位信息傳輸功能實(shí)現(xiàn)所需軟件為通信服務(wù)器軟件，主要完成車輛和監(jiān)控中心之間的數(shù)據(jù)傳輸與通信，實(shí)現(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)航軟件實(shí)現(xiàn)

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

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

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

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

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

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

4 實(shí)驗(yàn)驗(yàn)證及結(jié)果分析

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

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

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

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

5 結(jié) 論

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

參考文獻(xiàn)

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

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

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

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

[5] 羅國(guó)青.車輛定位導(dǎo)航系統(tǒng)動(dòng)態(tài)路徑規(guī)劃研究[D].長(zhǎng)沙：湖南大學(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.