基于向量識(shí)別的啟發(fā)式路徑推測(cè)算法(

1、基于向量識(shí)別的啟發(fā)式路徑推測(cè)算法*Supported by the National High-Tech Research and Development Plan of China Under Grant No.2006AA12Z315 (國(guó)家高技術(shù)研究發(fā)展計(jì)劃(863) and the Next Generation Internet Demonstrated Project of China Under Grant No.CNGI-04-15-5A(3-8-002)(中國(guó)下一代互聯(lián)網(wǎng)項(xiàng)目(CNGI).作者簡(jiǎn)介: 呂衛(wèi)鋒, 男,山東日照人,博士,副教授,主要研究領(lǐng)域?yàn)橹悄芙煌ㄏ到y(tǒng),網(wǎng)絡(luò)管理

2、;吳東東,男,碩士,主要研究領(lǐng)域?yàn)橹悄芙煌ㄏ到y(tǒng);諸彤宇,男,博士,副教授,主要研究領(lǐng)域?yàn)橹悄芙煌ㄏ到y(tǒng). 呂衛(wèi)鋒1+，吳東東2，諸彤宇3（北京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室 北京 100083）A Heuristic Path-Estimating Algorithm by Using Vector-Based RecognitionLv Wei-Feng 1+, Wu Dong-Dong 2, Zhu Tong-Yu 3(National Lab of Software Development Environment, Beihang University, Beijing 10008

3、3, China) + Corresponding author: Phn: +86-10-8233-8667, Fax: +86-10-8233-8582, E-mail: lwfAbstract:Floating Car Data (FCD) is an important material for a broad range of application such as traffic management and control, traffic conditions computation and so on. However, the original data exists er

4、ror, and the data must be handled by path-estimating and be related to the road. The traditional path-estimating algorithms mainly use two methods: the incremental method and the global method. Both of them have advantages and disadvantages of themselves: while the global map-matching algorithm prod

5、uces better matching results, the incremental algorithm produces results of lower quality faster. All things considering the two traditional algorithms, this paper proposes a heuristic path-estimating algorithm by using vector-based recognition. Firstly, the algorithm uses the heuristic search metho

6、d, and it makes use of geometric operation to form the restriction, and make the comparison between the vector formed with the vehicular GPS points and the special road network model to search and select the vehicular possible traveling routes. Secondly, it globally compares all the vehicular possib

7、le traveling routes, and then chooses the optimal one. The result of testing demonstrates the efficiency of the algorithm both at accuracy and computational speed when handling the large-scale data of GPS tracking data even under the complex road network conditions.Key words:Path-Estimating; Floatin

8、g Car Data (FCD) ; GPS; Heuristic search摘 要:浮動(dòng)車數(shù)據(jù)主要是由車輛的軌跡點(diǎn)數(shù)據(jù)組成，是一種重要的原始數(shù)據(jù)，可以廣泛的用于各種交通應(yīng)用，如交通管理和控制，路況計(jì)算等. 但是原始的車輛GPS數(shù)據(jù)存在定位誤差，必須經(jīng)過路徑推測(cè)的修正處理才可以應(yīng)用.傳統(tǒng)的路徑推測(cè)算法主要采用兩種方法：漸增式和全局式.兩種方法各有優(yōu)缺點(diǎn)，漸增式方法計(jì)算速度快但準(zhǔn)確性差，全局式方法準(zhǔn)確性好但計(jì)算速度慢.通過綜合考慮兩種傳統(tǒng)算法，本文提出了一種基于向量識(shí)別的啟發(fā)式路徑推測(cè)算法，該算法采用了啟發(fā)式圖搜索方式，導(dǎo)入幾何運(yùn)算的約束條件，根據(jù)車輛軌跡點(diǎn)所形成的向量與路網(wǎng)模型比較來進(jìn)行啟發(fā)

9、式搜索，并選擇車輛所有可能行駛的候選路徑.根據(jù)全局擇優(yōu)的方式從整體進(jìn)行比較，確定車輛最有可能的行駛路徑.實(shí)驗(yàn)結(jié)果表明，這種算法能夠在復(fù)雜路網(wǎng)下，比較準(zhǔn)確地推測(cè)距離間隔較大的車輛軌跡點(diǎn)，并且能夠?qū)崟r(shí)高效地處理大規(guī)模數(shù)據(jù).關(guān)鍵詞:路徑推測(cè); 浮動(dòng)車數(shù)據(jù); GPS; 啟發(fā)式搜索中圖法分類號(hào): TP301文獻(xiàn)標(biāo)識(shí)碼: A 在智能交通領(lǐng)域，實(shí)時(shí)和動(dòng)態(tài)的交通信息能為車輛出行，交通運(yùn)輸?shù)忍峁┯行У慕煌ㄕT導(dǎo)和出行規(guī)劃信息，從而達(dá)到節(jié)省出行時(shí)間、減少尾氣排放等目的.為了實(shí)現(xiàn)上述目標(biāo)，一個(gè)重要研究課題是高效處理實(shí)時(shí)、動(dòng)態(tài)的交通信息.浮動(dòng)車（Float Car Data）技術(shù)，也被稱作“探測(cè)車（Probe car）

10、”，是近年來國(guó)際智能交通系統(tǒng)（ITS）中所采用的獲取道路交通信息的先進(jìn)技術(shù)手段之一.其基本原理是：根據(jù)裝備車載全球定位系統(tǒng)（GPS）的浮動(dòng)車在車輛行駛過程中定期記錄的車輛位置，方向和速度信息，應(yīng)用包括路徑推測(cè)和道路交通擁堵信息計(jì)算等相關(guān)的計(jì)算模型和算法進(jìn)行處理，從而使浮動(dòng)車位置數(shù)據(jù)和城市道路在時(shí)間和空間上關(guān)聯(lián)起來，最終得到浮動(dòng)車所經(jīng)過道路的車輛行駛速度以及道路的行車旅行時(shí)間等交通擁堵信息4.如果在城市中部署足夠數(shù)量的浮動(dòng)車，并將這些浮動(dòng)車的位置數(shù)據(jù)通過無線通訊系統(tǒng)定期、實(shí)時(shí)地傳輸?shù)叫畔⑻幚碇行?，?jīng)過綜合處理，就可以獲得整個(gè)城市動(dòng)態(tài)、實(shí)時(shí)的交通擁堵信息.浮動(dòng)車數(shù)據(jù)處理主要存在兩個(gè)方面的問題，一方

11、面，在定位數(shù)據(jù)的準(zhǔn)確性上，由于浮動(dòng)車所采用的GPS設(shè)備一般會(huì)有15米以上的圓周誤差9，在推測(cè)過程中存在將軌跡點(diǎn)匹配到多條道路上的可能性.另一方面，在計(jì)算效率上，浮動(dòng)車采集GPS軌跡點(diǎn)數(shù)據(jù)的采樣率較低，一般在5300秒之間（實(shí)際應(yīng)用中多為30120秒），造成兩個(gè)連續(xù)軌跡點(diǎn)跨越了較長(zhǎng)距離，兩個(gè)軌跡點(diǎn)間有可能存在多條可行駛的路徑.因此，應(yīng)用于浮動(dòng)車信息系統(tǒng)的路徑推測(cè)算法既要有高效的計(jì)算速度，又要有較高的準(zhǔn)確性.傳統(tǒng)的方法無法很好適用于這種應(yīng)用.基于此，本文設(shè)計(jì)了采用啟發(fā)式搜索路徑的路徑推測(cè)算法.首先在算法的計(jì)算速度上，為了滿足實(shí)時(shí)性的要求，采用了漸增式方法，一方面，重新設(shè)計(jì)了路網(wǎng)模型和路網(wǎng)拓?fù)?，將?/p>

12、與算法進(jìn)行整合3.另一方面，利用啟發(fā)式搜索方式，算法在特殊的路網(wǎng)模型支持下，利用車輛軌跡點(diǎn)所形成的向量與路網(wǎng)相比較，導(dǎo)入三角形的幾何理論作為約束，采用啟發(fā)式的圖搜索方式快速的搜索浮動(dòng)車可能行駛的候選道路.兩方面相結(jié)合有效的提高了算法的計(jì)算速度.其次，在算法的準(zhǔn)確性上，采用全局擇優(yōu)的方法，通過樹結(jié)構(gòu)保存與車輛軌跡相符合的所有候選路徑，然后比較每條路徑上軌跡點(diǎn)的匹配權(quán)值，從整體上選擇最接近車輛軌跡的一條路徑作為推測(cè)結(jié)果.本文第1節(jié)給出了相關(guān)研究，第2節(jié)介紹了算法使用的路網(wǎng)模型和路網(wǎng)拓?fù)?，?節(jié)對(duì)問題進(jìn)行了描述與分析，第4節(jié)描述了算法的設(shè)計(jì)，第5節(jié)分析了實(shí)驗(yàn)測(cè)試的結(jié)果，最后對(duì)本文進(jìn)行了總結(jié)，并給出了

13、下一步研究工作.1 相關(guān)研究路徑推測(cè)是浮動(dòng)車信息系統(tǒng)的關(guān)鍵技術(shù)，是正確計(jì)算道路交通狀況的基礎(chǔ).路徑推測(cè)是通過匹配車輛較大間隔的行駛軌跡點(diǎn)數(shù)據(jù)，搜索車輛正確行駛路徑的技術(shù)，是地圖匹配的一種處理方法.傳統(tǒng)的路徑推測(cè)算法主要采用兩種方式：漸增式3和全局式1.漸增式方法分別對(duì)每個(gè)軌跡點(diǎn)進(jìn)行路網(wǎng)搜索，計(jì)算軌跡點(diǎn)與其附近的道路的距離，選擇與軌跡點(diǎn)距離最小的道路作為匹配結(jié)果.全局式方法則使用曲線匹配的方式，連接連續(xù)的多個(gè)軌跡點(diǎn)形成軌跡曲線，與路網(wǎng)中的路徑做幾何曲線匹配，通過計(jì)算Fréchet距離的方法選擇相似的道路作為匹配結(jié)果.漸增式方法計(jì)算簡(jiǎn)單，因此處理速度快，但是準(zhǔn)確性差；全局式方法從整體上進(jìn)

14、行考慮，因此準(zhǔn)確性好，但是由于計(jì)算復(fù)雜，處理速度慢1.兩種方法均不能很好的支持對(duì)大規(guī)模浮動(dòng)車數(shù)據(jù)的實(shí)時(shí)處理.2 路網(wǎng)模型和路網(wǎng)拓?fù)渎肪W(wǎng)數(shù)據(jù)是路徑推測(cè)的基礎(chǔ)，同時(shí)高效的路徑推測(cè)算法應(yīng)該整合相適應(yīng)的路網(wǎng)模型和拓?fù)?但是，常見的電子地圖路網(wǎng)模型一般是由基于桌面GIS (地理信息系統(tǒng)) 的路網(wǎng)模型改進(jìn)得來.這種模型的缺陷在于難以表達(dá)復(fù)雜道路的拓?fù)潢P(guān)系，對(duì)路網(wǎng)的描述比較單一，無法滿足針對(duì)大規(guī)模浮動(dòng)車數(shù)據(jù)處理的需求.因此，必須對(duì)原有路網(wǎng)模型進(jìn)行改進(jìn)，以適應(yīng)高效路徑推測(cè)的要求.基于此，本文通過對(duì)數(shù)據(jù)的分層處理和抽象，建立了新型的路網(wǎng)模型構(gòu)和路網(wǎng)拓?fù)?2.1 路網(wǎng)模型路網(wǎng)模型用于描述區(qū)域內(nèi)的道路網(wǎng)，是由車輛軌

15、跡點(diǎn)進(jìn)行路徑推測(cè)的基礎(chǔ).圖1顯示了路網(wǎng)模型的基本元素，包括節(jié)點(diǎn)和路段.整個(gè)路網(wǎng)模型可以表述為 （1）（1）式中代表道路網(wǎng)絡(luò).代表節(jié)點(diǎn)集，表示路網(wǎng)中構(gòu)成道路的坐標(biāo)點(diǎn)集合，其元素為經(jīng)緯度值對(duì)；代表路網(wǎng)的路段集合，其元素是有序?qū)?，表示存在一條有向直線道路s，其起始節(jié)點(diǎn)，終止節(jié)點(diǎn)，且s上不存在其他節(jié)點(diǎn)，如圖1中，節(jié)點(diǎn)1和節(jié)點(diǎn)2之間存在著路段1;若在路網(wǎng)中，存在一個(gè)路段的序列，其中每條路段的終止節(jié)點(diǎn)是下一個(gè)路段的起始節(jié)點(diǎn)，則此序列代表路網(wǎng)上的一條有向通路，如圖1中，路段1、2、3和4構(gòu)成一條通路.圖1 路網(wǎng)模型中的基本元素2.2 路網(wǎng)拓?fù)浣Y(jié)構(gòu)假設(shè)是路網(wǎng)中的一個(gè)節(jié)點(diǎn).出度表示以為起始節(jié)點(diǎn)的路段的個(gè)數(shù)；入度

16、表示以為終止節(jié)點(diǎn)的路段的個(gè)數(shù)，如圖1中節(jié)點(diǎn)1的入度為1，出度為2.路網(wǎng)中的節(jié)點(diǎn)，當(dāng)或時(shí)，稱為連通性節(jié)點(diǎn).在路網(wǎng)中，存在一條通路，若的起始節(jié)點(diǎn)和的終止節(jié)點(diǎn)均為連通性節(jié)點(diǎn)，且其他路段的節(jié)點(diǎn)的入度和出度均為1，則此路段的序列稱為一條路鏈，路鏈的集合為.在路網(wǎng)模型的基礎(chǔ)上，根據(jù)道路網(wǎng)絡(luò)的連通性和路鏈結(jié)構(gòu)，建立路鏈間的拓?fù)浣Y(jié)構(gòu)圖，其中，表示在路網(wǎng)上的路鏈集合，E則是根據(jù)道路的連通性建立的路鏈之間的連通關(guān)系.按照路鏈之間的連接性，路鏈的駛?cè)肼锋湻Q為此路鏈的前繼路鏈，路鏈的駛出路鏈稱為此路鏈的后繼路鏈，表示link是link的前繼路鏈，而link是link的后繼路鏈.如圖2中所示，.圖2 十字交叉路口拓?fù)浣Y(jié)

17、構(gòu)示意圖2.3 向量在地圖上取一坐標(biāo)點(diǎn)（為點(diǎn)的經(jīng)度，為點(diǎn)的緯度），從出發(fā)向某點(diǎn)（為點(diǎn)的經(jīng)度，為點(diǎn)的緯度）引一條線段，有方向且有長(zhǎng)度，這種有向線段稱為向量，記做，它的長(zhǎng)度記作，表示與之間的距離，它的方向記作，表示為與正北方向的夾角（順時(shí)針方向，方向值取值0360）.對(duì)于中的任一路鏈，其向量長(zhǎng)度記為表示路鏈起點(diǎn)與路鏈終點(diǎn)所構(gòu)成有向線段的距離，其向量方向記作，表示路鏈起點(diǎn)與路鏈終點(diǎn)所構(gòu)成有向線段的方向.3 問題描述和問題分析3.1 問題描述在路網(wǎng)中，假設(shè)由其形成的路網(wǎng)拓?fù)錇镚，運(yùn)動(dòng)車輛在一個(gè)時(shí)間段T內(nèi)的連續(xù)GPS軌跡點(diǎn)集合表示為，(為車輛定位坐標(biāo)點(diǎn) ，為車行方向)， .假設(shè)車輛在T內(nèi)所行駛過的通路為

18、，如何將軌跡點(diǎn)集合映射為，就是路徑推測(cè)所要解決的最主要問題，即 （2）通過構(gòu)建匹配函數(shù)，完成與的推測(cè)計(jì)算得到車輛的正確行駛路徑.3.2 車輛行駛規(guī)律分析3.2.1 車輛GPS軌跡點(diǎn)的匹配在對(duì)車輛的行駛位置進(jìn)行定位時(shí)，車載GPS設(shè)備一般會(huì)有15米以上的圓周誤差，車輛的GPS軌跡點(diǎn)需要投影到實(shí)際描述道路的路段上，才可以確定車輛的真實(shí)位置.因此，路鏈作為道路的抽象，不能完成對(duì)車輛實(shí)際位置的匹配支持.車輛軌跡點(diǎn)到道路的投影計(jì)算必須通過路段來完成.圖3 車輛軌跡點(diǎn)的匹配示意3.2.2 車輛行駛狀態(tài)分析 車輛在短時(shí)間內(nèi)的行駛軌跡具有一定的相似性，通過對(duì)車輛的行駛狀態(tài)分析歸納，可以掌握車輛的行駛規(guī)律，再與路

19、網(wǎng)模型相結(jié)合，進(jìn)一步得到了路徑搜索的啟發(fā)式條件.下面通過實(shí)例的方式對(duì)車輛在路網(wǎng)上的行駛狀態(tài)進(jìn)行分析，并歸納路徑推測(cè)算法的啟發(fā)式搜索條件.1) 車輛在單一路鏈行駛車輛的連續(xù)軌跡點(diǎn)位于同一路鏈上.如圖4中，p1在link1上的匹配點(diǎn)m1與p2構(gòu)成的向量其長(zhǎng)度小于m1與link1的終點(diǎn)構(gòu)成的向量長(zhǎng)度，即<（e1=end（link1）且.圖4 車輛在單一路鏈上行駛2) 車輛跨路鏈行駛車輛的連續(xù)軌跡點(diǎn)跨越了兩條或兩條以上路鏈，車輛基本存在了兩種行車狀態(tài)：一種是保持直行，如圖5所示；另一種是轉(zhuǎn)彎行駛，如圖6a和圖6b分別所示.圖5 車輛跨路鏈直行在示意車輛跨路鏈直行的圖5中 < + + <

20、; 2*（e1=end（link1），s3=begin(link3)）且、.轉(zhuǎn)彎的情況比較復(fù)雜，如圖6a和圖6b所示，向量vector和車輛所行駛過的軌跡路鏈可以形成類三角形，.圖 6a 車輛跨路鏈轉(zhuǎn)彎行駛圖 6b車輛跨路鏈轉(zhuǎn)彎行駛在普通的路網(wǎng)中，交叉道路的夾角幅度一般會(huì)在60°-180°之間.假設(shè)三角形的三邊分別為a、b和c，其中a、b兩邊的夾角C大于60°，根據(jù)三角形余弦定理和極限定理有下式： . 則有： . 即當(dāng)三角形中兩邊的夾角大于60時(shí)，此兩邊之和小于第三邊的2倍.由此可得，在圖6中，車輛的軌跡點(diǎn)p1的匹配點(diǎn)m1到link1的終點(diǎn)距離，link2的向量長(zhǎng)

21、度與link3的起點(diǎn)s3到軌跡點(diǎn)p2的距離之和小于2*，即2* > + + .另外，在方向上，車輛行駛路鏈的方向與向量的方向值必定會(huì)小于90°.因此，車輛行駛時(shí)滿足的約束條件可以歸納如下：1. 路鏈的方向與匹配點(diǎn)和車輛軌跡點(diǎn)形成向量的方向值之差小于90°，即 （3）2. 車輛行駛經(jīng)過路鏈的累計(jì)向量長(zhǎng)度之和小于匹配點(diǎn)與車輛軌跡點(diǎn)形成向量的長(zhǎng)度的2倍，即2 * > + + + + （4）4 算法設(shè)計(jì)4.1 路徑搜索樹為了提高搜索效率，采用啟發(fā)式搜索思想，其中路徑搜索樹定義為，其中U是路網(wǎng)拓?fù)渲蠽的非空子集，A為U集合中邊的關(guān)系.依據(jù)GPS定位的車輛軌跡，車輛在一段時(shí)

22、間內(nèi)的所有可能行駛路徑都保存在路徑搜索樹中.當(dāng)依據(jù)路網(wǎng)拓?fù)浜蛙囕v的定位數(shù)據(jù)，對(duì)車輛的行駛路徑進(jìn)行搜索時(shí)，這顆樹的深度和廣度就會(huì)不斷的增加，樹節(jié)點(diǎn)里保存著車輛可能行駛過的路鏈.從路徑搜索樹中得到算法的輸出，是車輛記錄的GPS定位數(shù)據(jù)的時(shí)間范圍內(nèi)所行駛的路徑，表現(xiàn)為若干條相連的路鏈.4.2 車輛行駛路徑搜索4.2.1 初始化對(duì)于給定的任一GPS軌跡點(diǎn)p，它在路鏈l上的匹配點(diǎn)被定義為與路鏈上的路段投影距離最小的點(diǎn)，且其到點(diǎn)p的距離小于最大匹配誤差值，記作且，其中z為p在上的匹配點(diǎn).每個(gè)GPS軌跡點(diǎn)均可以通過點(diǎn)匹配得到其在路網(wǎng)上的匹配路鏈集合，表述如下 （5）路徑搜索樹將根據(jù)匹配路鏈集合的不同，進(jìn)行不

23、同的初始化：1. 如果候選匹配路鏈集合的元素只有一個(gè)，則以匹配路鏈建立根節(jié)點(diǎn)，即；2. 如果候選匹配路鏈集合的元素大于1，則建立一個(gè)空節(jié)點(diǎn)作為根節(jié)點(diǎn)，以每條候選匹配點(diǎn)路鏈分別建立根節(jié)點(diǎn)的子節(jié)點(diǎn)，即.4.2.2 的生成初始化路徑搜索樹后，就要根據(jù)后續(xù)GPS軌跡點(diǎn)搜索車輛可能行駛過的路鏈，生成路徑推測(cè)樹.算法根據(jù)車輛的后續(xù)GPS軌跡點(diǎn)，將前一個(gè)軌跡點(diǎn)在路鏈上的匹配點(diǎn)作為起點(diǎn)，下一個(gè)GPS軌跡點(diǎn)作為終點(diǎn)建立一條向量，計(jì)算這條向量的方向和長(zhǎng)度.向量的方向就是車輛行駛路線的主要方向，向量的長(zhǎng)度就是浮動(dòng)車行駛路線的最小可能距離，在上文分析的約束條件下搜索車輛行駛路徑.為實(shí)現(xiàn)這個(gè)算法需要附設(shè)一個(gè)輔助隊(duì)列Ma

24、tchedlinkqueue，用于記錄軌跡點(diǎn)匹配到的路鏈和在路鏈上的匹配點(diǎn).生成的算法：輸入：路網(wǎng)拓?fù)?、車輛軌跡點(diǎn)集合輸出：車輛的若干條最有可能行駛路徑(1) 通過點(diǎn)匹配得到的匹配路鏈集合，完成路徑搜索樹和Matchedlinkqueue的初始化；(2) 對(duì)從開始的每?jī)蓚€(gè)連續(xù)車輛軌跡點(diǎn)進(jìn)行路徑搜索，置迭代次數(shù)=1，取車輛軌跡點(diǎn)；(3) 置迭代次數(shù)i = sizeof( Matchedlinkqueue )，計(jì)數(shù)器j=i；(4) 獲取Matchedlinkqueue隊(duì)頭元素h同時(shí)出隊(duì)列，j=j-1，h中記錄的前一車輛軌跡點(diǎn)的匹配點(diǎn)m作為起點(diǎn)與建立一條向量；(5) 遍歷m中記錄的路鏈的后續(xù)路鏈集合

25、L=，進(jìn)行約束條件1的比較，若，則進(jìn)行與的匹配計(jì)算，若且，則說明搜索到一條車輛可能行駛路鏈，加入中的U，與之間的邊加入A，同時(shí)和z入隊(duì)列Matchedlinkqueue；(6) 若沒有計(jì)算到匹配點(diǎn)，則進(jìn)行約束條件2的比較，若2* > + ，加入，根據(jù)對(duì)的后續(xù)路鏈進(jìn)行深度遍歷，將滿足約束條件1并計(jì)算得到匹配點(diǎn)的路鏈加入和Matchedlinkqueue，將同時(shí)滿足約束條件1和2的路鏈加入，直到?jīng)]有路鏈可以同時(shí)滿足約束條件1和2；(7) 重復(fù)步驟(4)至(6)，直到j(luò)=0；(8) 取下一個(gè)車輛軌跡點(diǎn)和Matchedlinkqueue，置l = l + 1，重復(fù)步驟(3)至(8)，直到l =

26、n.完成擴(kuò)展后，車輛在所形成的軌跡之間的所有可能路徑均保存在中.4.3 車輛行駛路徑選擇在軌跡點(diǎn)匹配中，如果有多條道路滿足匹配的條件，則可以使用計(jì)算匹配點(diǎn)權(quán)值的方法挑選出最有可能的一個(gè).GPS 軌跡點(diǎn)向附近所有道路做投影后，計(jì)算GPS 點(diǎn)與各道路間的投影距離 ，及車輛行駛方向與路段方向間的夾角 .計(jì)算各候選匹配點(diǎn)對(duì)應(yīng)路鏈的權(quán)值 : = · + · ，其中和分別是投影距離和方向夾角的權(quán)值計(jì)算參數(shù)，且 =1.保存每個(gè)候選匹配點(diǎn)權(quán)值.生成最終的后，如果有多個(gè)葉節(jié)點(diǎn)保存是中最后一個(gè)軌跡點(diǎn)的匹配路鏈，則表明車輛可能存在多條行駛路徑，每個(gè)包含匹配路鏈的葉節(jié)點(diǎn)向上回溯到根節(jié)點(diǎn)對(duì)應(yīng)一條可能

27、行駛的路徑.累計(jì)每條路徑上的候選匹配點(diǎn)的權(quán)值，選擇累計(jì)權(quán)值最小的一條路徑作為最終的路徑推測(cè)結(jié)果.此外，由于在中保存了車輛的多條候選行駛路徑，可以根據(jù)實(shí)際需要通過不同的權(quán)值計(jì)算方法對(duì)候選路徑進(jìn)行評(píng)估，選擇車輛的最佳行駛路徑.4.4 算法時(shí)間復(fù)雜度分析在路徑推測(cè)中，算法的性能主要體現(xiàn)在對(duì)路網(wǎng)的搜索效率上，通過對(duì)算法的路徑搜索效率進(jìn)行分析得到算法的計(jì)算性能.設(shè)車輛在一個(gè)時(shí)間段T內(nèi)共采集到n個(gè)GPS軌跡點(diǎn)，每2個(gè)軌跡點(diǎn)之間進(jìn)行一輪路徑搜索.假設(shè)前一匹配點(diǎn)和后續(xù)的軌跡點(diǎn)所建立的向量平均長(zhǎng)度為d，路鏈的平均長(zhǎng)度為l，路鏈的后續(xù)路鏈數(shù)平均為3，滿足約束條件（1）的路鏈數(shù)平均為2.假設(shè)路徑搜索的候選路徑數(shù)平均

28、為t，每?jī)牲c(diǎn)之間的路徑搜索所花費(fèi)的時(shí)間為，因此，算法的時(shí)間復(fù)雜度為.其中向量平均長(zhǎng)度d，路鏈的平均長(zhǎng)度l，路徑搜索的候選路徑數(shù)t均可考慮為常數(shù)值.4.5 生成示例圖7示出了車輛在一段時(shí)間內(nèi)的5條GPS定位數(shù)據(jù)記錄的軌跡點(diǎn)在路網(wǎng)地圖上的分布情況，軌跡點(diǎn)按照時(shí)間順序記為g1、g2、g3、g4、g5，路網(wǎng)上的道路被分成了路鏈并被編號(hào)，圖中的黑色正方形代表了車輛位置點(diǎn)，紅色圓點(diǎn)代表了車輛位置點(diǎn)在路鏈上的匹配點(diǎn)，紅色有向線段代表了匹配點(diǎn)和下一個(gè)車輛軌跡點(diǎn)構(gòu)成的向量，綠色路線代表車輛的行駛路徑.圖8示出了使用基于向量識(shí)別的啟發(fā)式路徑推測(cè)算法對(duì)圖7中的車輛軌跡點(diǎn)進(jìn)行處理而生成路徑搜索樹的過程.圖8中的a，b

29、，c，d，e，子圖分別示出了浮動(dòng)車軌跡點(diǎn)g1、g2、g3、g4、g5處理后所生成的路徑搜索樹.圖8e為生成的最終路徑搜索樹，從中可以提取出兩條路徑作為車輛的候選行駛路徑，通過比較匹配權(quán)值可以確定唯一的一條路徑作為匹配結(jié)果.圖7 浮動(dòng)車的軌跡點(diǎn)在路網(wǎng)上的分布示意圖圖8 的生成示意圖5 實(shí)驗(yàn)分析為了驗(yàn)證本文提出的算法，作者使用了北京市的導(dǎo)航電子地圖（包括57000條路鏈）和3500輛出租車發(fā)回的以60120秒為間隔的GPS數(shù)據(jù)作為浮動(dòng)車數(shù)據(jù)進(jìn)行了實(shí)驗(yàn).5.1 準(zhǔn)確性為了驗(yàn)證算法推測(cè)車輛行駛路線的準(zhǔn)確性，在實(shí)驗(yàn)中作者抽取了三輛出租車，在正常運(yùn)營(yíng)時(shí)間范圍內(nèi)選取了北京市的主要道路作為規(guī)定的行車路線，然后

30、提取出它們回傳的GPS數(shù)據(jù)（包括車號(hào)，時(shí)間，經(jīng)緯度，方向）輸入算法中進(jìn)行處理.通過推測(cè)出的車輛行駛旅程的正確率作為評(píng)測(cè)的標(biāo)準(zhǔn).正確率的定義如下： (5)在推測(cè)結(jié)果的效果圖9上，綠色代表推測(cè)正確的道路，紅虛色的路線代表車輛正確行駛而算法沒有進(jìn)行正確推測(cè)的道路.通過表1對(duì)測(cè)試結(jié)果的統(tǒng)計(jì)，可發(fā)現(xiàn)算法的準(zhǔn)確率達(dá)到90以上.圖9 測(cè)試路線2的路徑推測(cè)結(jié)果表1 不同測(cè)試路線的匹配準(zhǔn)確率統(tǒng)計(jì)路線路線長(zhǎng)度測(cè)試次數(shù)推測(cè)正確的路徑長(zhǎng)度準(zhǔn)確率 12235032064192.35%2035591.07%2043691.43%21516031442495.14%1435294.67%1425694.03%3327602

31、3008091.81%3010591.89%5.2 計(jì)算速度由于浮動(dòng)車系統(tǒng)是對(duì)最近一段時(shí)間范圍內(nèi)（一般采用515分鐘）采集的全部數(shù)據(jù)進(jìn)行批量處理，因此本文選取早8：00至晚8：00的不同時(shí)間段，分別采用5分鐘，10分鐘，15分鐘的處理周期對(duì)算法的計(jì)算速度進(jìn)行測(cè)試，并對(duì)不同處理周期下的平均計(jì)算時(shí)間做了統(tǒng)計(jì)，如表2所示.測(cè)試環(huán)境為：Pentium(R) 4 CPU 3.20GHz，1GB 內(nèi)存.表 2 不同處理周期的計(jì)算時(shí)間統(tǒng)計(jì)浮動(dòng)車數(shù)量平均GPS記錄數(shù)處理周期平均CPU運(yùn)行時(shí)間平均每秒種處理的GPS記錄數(shù)3410134005min2520ms532034102620010min5850ms448

32、034103962015min10930ms3625從對(duì)算法的運(yùn)行效率上的測(cè)試可以看出算法具有很高的運(yùn)行效率，可以充分滿足浮動(dòng)車系統(tǒng)的實(shí)時(shí)性要求.6 結(jié)論綜上所述， 本文提供了一種適用于實(shí)時(shí)處理大規(guī)模浮動(dòng)車GPS數(shù)據(jù)的路徑推測(cè)算法.它具有啟發(fā)式搜索的特征，算法的效率不受路網(wǎng)的復(fù)雜性影響，將路徑搜索的效率進(jìn)行了有效的提高.通過實(shí)際數(shù)據(jù)的測(cè)試可以看出，其特點(diǎn)是實(shí)時(shí)性好， 效率高， 并且具有較好的準(zhǔn)確性.下一步，我們將在候選路徑的選擇方法上進(jìn)行深入的研究和實(shí)驗(yàn)，進(jìn)一步提高算法的準(zhǔn)確性.References:1 Stoiris Brakatsouls,Dleter Pfoser,Randall Sal

33、as and Carola Wenk. On Map-Matching Vehicle Tracking Data. Proceeding of the 31st VLDB Conference Trondheim, Norway, 2005.2 J.-S. Pyo, D.-H. Shin, and T.-K. Sung. Development of a map matching methodusing the multiple hypothesis technique. IEEE Intelligent Transportation Systems Conference Proceedings, pages 23 27, 2001.3 Marchal, F., J.K. Hackney and K.W. Axhausen (2005) Efficient map-matching of large GPS data sets - Test on a speed monitoring experiment in Zurich, Conference Paper, STRC,Monte Verità.4 S.Brakatsoulas, D.Pfoser, and N.