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

1、基于向量識別的啟發(fā)式路徑推測算法*Supported by the National High-Tech Research and Development Plan of China Under Grant No.2006AA12Z315 (國家高技術研究發(fā)展計劃(863) and the Next Generation Internet Demonstrated Project of China Under Grant No.CNGI-04-15-5A(3-8-002)(中國下一代互聯(lián)網(wǎng)項目(CNGI).作者簡介: 呂衛(wèi)鋒, 男,山東日照人,博士,副教授,主要研究領域為智能交通系統(tǒng),網(wǎng)絡管理

2、;吳東東,男,碩士,主要研究領域為智能交通系統(tǒng);諸彤宇,男,博士,副教授,主要研究領域為智能交通系統(tǒng). 呂衛(wèi)鋒1+，吳東東2，諸彤宇3（北京航空航天大學軟件開發(fā)環(huá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摘 要:浮動車數(shù)據(jù)主要是由車輛的軌跡點數(shù)據(jù)組成，是一種重要的原始數(shù)據(jù)，可以廣泛的用于各種交通應用，如交通管理和控制，路況計算等. 但是原始的車輛GPS數(shù)據(jù)存在定位誤差，必須經(jīng)過路徑推測的修正處理才可以應用.傳統(tǒng)的路徑推測算法主要采用兩種方法：漸增式和全局式.兩種方法各有優(yōu)缺點，漸增式方法計算速度快但準確性差，全局式方法準確性好但計算速度慢.通過綜合考慮兩種傳統(tǒng)算法，本文提出了一種基于向量識別的啟發(fā)式路徑推測算法，該算法采用了啟發(fā)式圖搜索方式，導入幾何運算的約束條件，根據(jù)車輛軌跡點所形成的向量與路網(wǎng)模型比較來進行啟發(fā)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

32、034103962015min10930ms3625從對算法的運行效率上的測試可以看出算法具有很高的運行效率，可以充分滿足浮動車系統(tǒng)的實時性要求.6 結論綜上所述， 本文提供了一種適用于實時處理大規(guī)模浮動車GPS數(shù)據(jù)的路徑推測算法.它具有啟發(fā)式搜索的特征，算法的效率不受路網(wǎng)的復雜性影響，將路徑搜索的效率進行了有效的提高.通過實際數(shù)據(jù)的測試可以看出，其特點是實時性好， 效率高， 并且具有較好的準確性.下一步，我們將在候選路徑的選擇方法上進行深入的研究和實驗，進一步提高算法的準確性.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.