基于公交車軌跡數據的道路GPS環境友好性評估

馬連韜 王亞沙 彭廣舉 趙宇昕 何遠舵 高敬月

1(高可信軟件技術教育部重點實驗室(北京大學) 北京 100871)2(北京大學信息科學技術學院 北京 100871)3(軟件工程國家工程研究中心(北京大學) 北京 100871)4(北京大學(天津濱海)新一代信息技術研究院 天津 300450)(malt@pku.edu.cn)

?

基于公交車軌跡數據的道路GPS環境友好性評估

馬連韜1,2,4王亞沙1,3,4彭廣舉1,2趙宇昕1,2何遠舵1,2高敬月1,2

1(高可信軟件技術教育部重點實驗室(北京大學) 北京 100871)2(北京大學信息科學技術學院 北京 100871)3(軟件工程國家工程研究中心(北京大學) 北京 100871)4(北京大學(天津濱海)新一代信息技術研究院 天津 300450)(malt@pku.edu.cn)

GPS是應用最為廣泛的室外定位系統，隨著技術的發展精度不斷提升.然而城市中，由于GPS衛星信號被建筑遮擋，仍然可能產生較大的多徑誤差.此類誤差已稱為城市GPS定位誤差的主要成分.評估城市道路中環境對GPS精度的負面影響，即環境的GPS友好度，將有助于對不同地段GPS的誤差范圍進行預判，從而提升位置服務相關應用的用戶體驗，并為理解環境特征與多徑誤差的關系，確定在何處部署輔助定位的設備提供支持.為此，提出了1種通過處理和分析海量公交車GPS軌跡歷史數據，從而評估城市主要路段的環境友好性的方法.該方法充分利用公交車運行線路固定的特點，大幅提升數據處理的效率；針對路網數據可能存在的錯誤，提出了容錯性的方案；利用相同車輛及相同路段在GPS誤差上存在的內在關聯，對缺失數據進行補全；并充分考慮到不同質量GPS端設備對環境友好性評估的影響，確定了基于端設備質量加權的評估計算策略.利用成都市二環內的4 869輛公交車1個月的數據，對共計5 648個不同路段的環境友好性進行了評估，并通過衛星地圖和街景照片，分析驗證了方法結果的合理性.

位置服務；GPS誤差；數據分析；地圖匹配；智慧城市

隨著智慧城市建設的深入，定位技術在交通、旅游、社交等眾多領域獲得了廣泛的應用.而GPS(global positioning system)作為一種精度高、適用范圍廣、終端設備造價低廉、免費提供服務的定位系統，已經得到廣泛應用，GPS終端廣泛嵌入到智能手機、腕表、車載裝置等移動智能終端中，成為了室外定位技術的事實標準[1-2].然而，GPS的定位精度卻受到端設備、定位過程中衛星的空間位置和地面環境的影響，波動較大.特別是在城市環境中，受高樓、立交橋等地面建筑的遮擋，衛星信號常常無法以直線的可視路徑(line of sight)傳播到終端設備，而是通過建筑或地表反射后，通過多條反射路徑被終端設備接收，形成多徑(multipath)現象.由于GPS終端設備無法區分接受到的衛星信號是通過可視路徑還是反射路徑到達設備的，統一按照可視路徑計算衛星與設備之間的距離，從而導致計算終端設備位置時出現較大偏差.實測數據表明，城市環境中GPS的定位誤差從空曠地段的數米，到多徑環境中超過80 m不等.關于GPS誤差原因分析和城市中環境對GPS精度影響的研究顯示，由于衛星信號被建筑遮擋所產生的多徑誤差是GPS定位誤差最主要的組成部分[2-4]，而且此類誤差分布和偏差往往未知，難以消除[5].針對GPS在部分環境中精度不高的問題，研究者提出了一系列利用慣性、視頻、WiFi(wireless-fidelity)等其他技術與GPS相結合的組合定位技術與系統，在多徑環境中，利用其他定位設備的數據對GPS定位數據進行校準，顯著提高了定位的精度.然而，這些組合定位技術，大多需要在城市環境中部署額外的輔助設備(如WiFi熱點)或者采集額外的數據(如采集城市環境的視頻、WiFi指紋等).

在此背景下，我們提出一種利用城市中公交車的GPS定位軌跡歷史數據，分析評估城市道路環境對GPS定位精度產生負面影響程度的方法，并將評估指標稱為“GPS環境友好性”.環境對GPS精度產生的負面影響越嚴重、造成誤差越大，則環境友好性越差，反之則越佳.

雖然GPS定位的絕對誤差，受端設備質量、天氣情況、衛星位置、地面環境等多方面因素綜合作用的影響，在無真值的條件下難以準確估計[3,6].但是，考慮到城市中建筑遮擋等環境因素造成的多徑誤差是誤差的主要組成部分，因此對城市GPS環境友好性的評估將有助于輔助估計GPS誤差的范圍，另外也可以幫助用戶建立起諸如“哪些路段的定位誤差比另一些路段更大”這樣的相對概念，從而提高用戶滿意度和用戶體驗.例如，近年來在國內興起的實時公交APP(application)，通過處理和分析公交車GPS的數據，為移動用戶提供公交車實時位置播報及到站時間預測等服務.此類軟件需求量很大，在各大城市得到了廣泛應用，然而卻也因為其提供的數據準確性較差，普遍受到媒體的詬病[7].通過與部分APP研發團隊的交流，我們發現城市部分路段GPS定位精度差，是影響此類服務數據準確性的主要原因.如果能事先評估不同路段的環境友好性，據此估計車輛位置數據的誤差范圍，并在發布給用戶的數據中用顏色、字體等形式區分數據的精度和可信度，則可以幫助用戶做出更合理的決策，顯著提高用戶體驗.

除此以外，評估道路環境友好性，還將有助于識別城市中GPS誤差較大的區域，為采用WiFi、視頻等多種技術提升GPS精度的復合系統，提供部署設備、采集數據的選址優化決策依據.另外，受到采樣數量的局限，當前針對多徑誤差與環境特征之間關聯關系的研究，一般僅基于較小的數據集進行.而由于公交車軌跡對城市公路實現了大范圍的覆蓋，因此本文工作將得到不同道路環境友好性評估的大批量化結果.這些數據為GPS多徑誤差的分析提供了大量數據，并可能為揭示GPS誤差受環境影響而變化的內在規律提供支持.

本文采用了2015年11月成都市二環線以內共計184條公交線路、4 869輛公交車，約6 300萬條公交車GPS位置軌跡數據以及公交線路數據和開放地圖*OSM是由志愿者自愿貢獻數據，旨在建立全球范圍免費地圖的合作項目.相關資源可以通過訪問網址：https://www.openstreetmap.org/得到.(open street map, OSM)中的路網數據對公交車軌跡覆蓋的5 648個不同的路段進行了GPS環境友好性評估.評估過程大致可分為2個階段：

1) 計算所有GPS數據的定位誤差.為了描述方便，本文稱GPS上報數據中標明的位置為報告位置，而車輛實際所在位置為真實位置，真實位置與報告位置之間的直線距離即為GPS定位誤差.若將GPS定位誤差分解為與道路平行和垂直2個方向的正交分量，研究表明，定位誤差可以近似地用垂直道路方向的誤差分量表示.原因是城市中建筑一般都位于道路兩側，而沿道路方向則一般沒有建筑，因此由建筑遮擋所導致的多徑誤差中，平行道路方向的分量遠小于垂直道路方向的分量，可以忽略[2-3].本階段過程可以進一步分解為2個步驟：

步驟1. 地圖匹配(map matching)，即為每一條GPS數據的報告位置，在地圖中找到其真實位置所處的道路；

步驟2. 誤差計算，即計算報告位置到匹配路段的垂直距離，并以此作為其定位誤差的估計值.

2) 針對每一路段，綜合所有GPS數據的誤差，評估其總體的環境友好性.

以上2階段方案并不簡單，面臨3個方面挑戰：

1) 如何為海量GPS數據記錄的地圖匹配，提供一套高準確性且高效率的算法?本文提出的方法對地圖匹配的準確性要求較高.一方面，因為前文所述的GPS定位誤差計算方法中，準確的地圖匹配是計算GPS定位誤差的基礎，對環境友好性評估效果有重要影響；另一方面，對GPS環境友好性的評估，要求對路網做較高分辨率的劃分.因為GPS環境友好性與道路寬度、地形地勢、路邊建筑高度甚至樹冠遮蓋等環境因素密切相關.地圖路網數據中，路段通常按照路網拓撲結構切分，存在大量長度超過100 m的較長路段.考慮到在1個長路段內，環境因素可能明顯改變，不可作為評估環境友好性的原子單元，需要對長路段進行切分.在本文法中，經過切分將所有路段長度控制在20～100 m之間.而路段較短將導致落入每個路段的GPS報告較少，因此對地圖匹配錯誤容忍的程度也會降低(即少量匹配錯誤，將對路段評估結果產生較大影響).地圖匹配算法是GPS數據處理中1個較為成熟的研究領域，研究者們提出了一系列算法.考慮到問題的需求，我們選擇了準確性較高但計算量也較大基于隱Markov模型的地圖匹配算法[8-9]，作為本文地圖匹配的算法原型.如何在此算法原型的基礎上進行改進，使其能夠在可接受的時間內處理城市級的海量GPS定位記錄是本文面臨的第1個挑戰.

2) 如何兼容地圖路網數據中存在的錯誤，提高GPS定位誤差計算的準確率？OSM作為開源地圖數據源，在研究領域得到了非常廣泛的應用，本文也采用了此數據源中的路網數據.然而，實踐中，我們發現OSM路網數據中存在部分路段數據缺失的情況[10-12].而缺失路段數據將導致地圖匹配算法將本應匹配到此“缺失路段”上的所有GPS點都不得不匹配到其他路段上，并引發這些GPS點定位誤差計算出錯，并進而導致缺失路段附近其他路段出現GPS誤差普遍較高、環境友好性較差的“假象”.如何解決利用GPS軌跡和路網數據發現并定位地圖中缺失的道路，并補全這些道路避免上述錯誤，是本文面臨的第2個挑戰.

3) 如何考慮不同車載設備質量的差異，對所有路段的環境友好性做出公平的評估？通過對成都公交車GPS軌跡歷史數據的初步觀察和分析，我們發現不同車輛轉配的GPS端設備，質量存在明顯差異.圖1顯示了2輛不同的公交車在相同的時段，通過相同路段的GPS報告位置分布情況.可以直觀地看到，圖1(a)中車輛GPS位置點較之圖1(b)中另一輛車明顯更加分散、距離道路更遠、誤差也更大.這一現象與公交公司在不同時間、向不同供貨商采購的GPS設備質量存在差異有關.根據公交車運行的規律，1輛車僅通過城市中的少量路段，而1個路段上也僅有部分車輛通過.設想A，B兩個環境友好性完全相同的路段，就途徑此2條路段的公交車載GPS端設備的質量而言，路段B中設備的質量明顯優于路段A.如果僅觀察匹配到路段上的GPS記錄的誤差，認為平均誤差越小，則環境友好性就更好，則很容易得出路段B的環境友好性優于路徑A的錯誤結論.在此條件下，如何考慮不同車輛車載GPS端設備的差異、公平的評估不同路段上的環境友好性是本文面臨的第3個挑戰.

Fig. 1 GPS error of different cars on the same road.圖1 相同路段不同車輛定位誤差差距明顯

針對這3種挑戰，本文提出了一套基于公交車軌跡數據的城市道路GPS環境友好性評估方法.在此方法中，1)利用公交車行駛路線固定的規律，縮小地圖匹配中搜索的范圍，顯著提高了地圖匹配的效率.2)分析相鄰GPS位置報告誤差較大數據集合，發現地圖可能存在錯誤的區域，并通過擬合GPS位置點的軌跡路徑，補充地圖缺失的道路，實現對地圖路網數據錯誤的容錯.3)構造誤差矩陣，每一行表達1輛車的誤差向量，每一列表達1個路段的誤差向量，矩陣元素為某輛車在某個路段上1個月的誤差均值，由于每輛車僅途徑少量路段，因此誤差矩陣顯然具有稀疏性.另外，從行向量的視角看，端設備質量較高的車輛較之端設備質量較差的車輛，在相同的路段上誤差均值傾向于更小；同理，從列向量的視角看，相同的車輛途徑環境友好性較好的路段，較之環境友好性較差的路段，其誤差均值也傾向于更小.也就是說，此稀疏矩陣中的數據元素之間存在信息冗余，亦即，數據元素之間存在深層的相關性.利用這種相關關系，可以運用矩陣補全的算法，對矩陣缺失的數據進行估計和補全.補全后，每個路段中包含了所有車在此路段中的平均誤差.4)基于上述補全后的矩陣，根據車輛GPS終端的質量，對各個路段上不同車輛誤差的均值進行加權平均，并以此加權平均值作為最終路段環境友好性的評估結果.本文利用衛星地圖和街景照片，對URFE在成都二環內路段中的地圖補全和環境友好性評估結果進行了分析，發現了道路寬度、地面建筑高度等環境特征與環境友好性評估結果之間存在的相關性，驗證了評估結果的合理性.

1 相關工作

相關工作主要包括3個方面： GPS定位精度估計以及影響因素研究、道路匹配與矩陣補全相關技術以及基于車輛GPS數據挖掘和分析的應用.

1.1 GPS定位精度估計及影響因素研究

文獻[1,12-15]等工作從GPS定位原理的角度，對影響GPS采樣數據精度的因素進行剖析.文獻[1]根據衛星定位的原理，給出了表達GPS定位誤差組成部分的模型，闡明了導致誤差的3類主要原因：1)衛星誤差，即衛星星歷誤差；2)傳輸誤差，包括電離層誤差、對流層誤差以及多徑效應誤差；3)端設備誤差，即接收端時鐘偏差和接收端測量噪聲.文獻[1,6,14-15]等在文獻[13]的基礎上通過實測給出了量化誤差估計和改進方案.如文獻[14-15]提出衛星星歷誤差通常約為3 m，而電離層誤差和對流層造成的誤差分別約為5 m和2 m.文獻[6]提出一種差分GPS技術，可以極大地減小衛星星歷、大氣層、端設備時鐘帶來的誤差.文獻[1]則指出影響GPS定位精度的主要因素是端設備質量和多徑效應.

近些年來，文獻[2-4]等工作在城市環境中，進行了一系列與GPS定位誤差相關的現場實驗，探究影響定位精度的要素.例如文獻[3]利用不同種類設備，在1個中等大小城市的4 000多個參考點，分別進行了定位實驗.依據采樣數據、周圍環境和設備質量參數，分析得出在城市中影響GPS精度的主要原因是樓宇建筑對衛星信號的遮擋造成的多徑誤差.文獻[2]則在挑選的城市多徑現象較少開闊區域和建筑物較為集中的市中心區域，分別收集了6 000余個GPS采樣數據，并結合GPS系統的相關采樣參數(例如速度、衛星數量等)，評估某個GPS采樣數據的精確度等級，發現市中心GPS精度較開闊地帶明顯下降.文獻[4]同樣利用在城市的幾個典型區域進行現場實驗的方式，分析得出影響GPS定位精度的影響要素包括：端設備質量、樓宇建筑、端設備移動的速度和朝向等.

總結以上工作可見：GPS的定位精度受到端設備、定位過程中衛星的空間位置和以及地面環境的影響，且波動較大.近年來，隨著定位算法的改進和端設備電子器件質量的提高，星歷誤差、端設備時鐘偏差、平流層和對流層誤差等逐漸減小，GPS定位精度不斷提高.但是，在城市環境中，受高樓、立交橋等地面建筑的遮擋，多徑現象仍然十分常見，多徑誤差尚未獲得較好的改進方案，多徑誤差成為GPS誤差最主要的組成成分.以上工作為本文研究城市道路環境友好性評估提供了啟發和依據，然而這些工作都是在城市中的少量區域進行針對性的采樣和實驗，數據較少，覆蓋范圍有限，無法形成對城市范圍內環境對GPS精度影響的全局視角.本文上述工作在研究思路上明顯不同，利用覆蓋城市絕大多數主要道路的公交車GPS軌跡歷史數據以及其他補充信息，通過數據的分析挖掘，將形成城市中道路環境友好性較為完整的視圖.

1.2 道路匹配與矩陣補全技術

本文研究內容涉及2項關鍵技術：1)如何將GPS采樣點映射到路網地圖上的1條道路；2)基于矩陣補全技術完成道路GPS友好程度評估.因此，下面對道路匹配和矩陣補全分別進行簡要介紹.

道路匹配技術將車輛GPS數據映射到路段上，從而確定車輛在道路上的位置.常用的匹配算法包括幾何匹配算法、拓撲匹配算法、統計匹配算法和高級匹配算法等.幾何匹配算法只考慮道路的幾何信息，實現簡單，但是路況復雜時容易誤判[2]；而拓撲匹配算法還利用了路網的拓撲結構，提高了匹配準確率[16-17]；統計匹配算法基于車輛GPS概率密度選擇候選路段進行匹配，常用于實時導航的道路匹配，不適合對大規模定位數據進行道路匹配計算[18-19]；高級匹配算法包括基于隱Markov模型的道路匹配算法、卡爾曼濾波道路匹配算法[19-20]、基于模糊邏輯的道路匹配算法等[19-20]，考慮到問題的需求，我們選擇了準確性較高但計算量卻也較大的基于隱Markov模型的地圖匹配算法.為減少計算量，本文利用公交車行駛線路固定的規律，縮小地圖匹配中搜索的范圍，顯著提高了地圖匹配的效率.

矩陣補全的常用技術包括K-NN算法(K-nearest neighbors,K-NN)、壓縮感知、非負矩陣分解等.基于K-NN的矩陣補全技術利用了相鄰數據間的相關性，尋找缺失數據的最相鄰的K個數據點，對這些數據點與待補全點之間的距離加權平均，從而實現缺失數據的補全[21]；基于壓縮感知的補全算法利用數據中存在的內在聯系與冗余信息對初始矩陣進行重構，并且在補全的同時還能保持補全矩陣的低秩特性[22]；非負矩陣分解通過最小化補全矩陣與初始矩陣的歐氏距離或者Kullback-Leibler散度來實現缺失元素補全，該技術保證了補全數據的物理意義，即非負性，在推薦系統等現實場景中有廣泛應用[23].本文的目標補全矩陣是1個非負矩陣，每一個元素是車輛GPS點到匹配路段上的平均偏差，因此本文選用了非負矩陣分解技術進行矩陣補全.

1.3 基于車輛GPS的智慧城市數據挖掘應用

近年來有很多基于車輛GPS的數據挖掘相關工作，它們大多結合了城市內其他多源異構數據(如POI、人群移動等)，綜合使用多種機器學習技術，分析挖掘與城市相關知識，解決智慧城市建設中的相關問題.例如文獻[24-25]基于對城市中大量公交GPS數據的模式挖掘，實時監測和預測城市道路的交通情況；文獻[26]基于車載GPS數據分析車輛移動的軌跡模式，從而改進車聯網中的路由算法；文獻[27]則基于張量分解補全技術，利用出租車的GPS數據估計在城市任意2點之間乘車所消耗的時間；而文獻[28]等利用出租車軌跡數據檢測分析異常的載客線路.以上工作雖然也采用了城市規模的車載GPS數據，然而研究問題與本文不同.

2 方法框架

方法的總體框架如圖2所示.研究中所用到的3個數據集:1)數據集1是“公交車GPS軌跡歷史數據”,這部分數據包括了2015-11-01—2015-11-30，共計30 d中，成都市二環以內全部184條公交線路、4 869輛公交車的GPS報站軌跡數據.每輛公交車在其運營期間，1 min內產生2～4條定位數據記錄，所有GPS定位數據記錄共計62 783 111條，平均每天約210萬條；2)數據集2是“公交車線路路徑數據”,這部分數據集由公交公司提供的一系列人工標注的位置點組成，相鄰位置點之間的距離不超過150 m，用于標明上述184條公交線路從首發站到結束站的運行路徑,然而，由于城市道路建設、公交線路重新規劃等問題，以上標示的線路并非完全準確，其中有約5%的位置點與公交車實際運行的軌跡不符;3)數據集3是“OSM路網數據”，是從OSM地圖中獲得成都市二環以內的路網數據，其中存在部分路徑缺失的情況.如引言所述，為了提高路徑環境友好性評估的合理性，我們對OSM路網數據中的長路徑進行了切割，將公交車軌跡覆蓋的所有道路分割成20～100 m長度的共計5 648個路段，每個路段作為環境友好性評估的1個原子單元.

Fig. 2 Framework of the URFE approach.圖2 URFE方法的整體框架

方法整體上由3個核心算法組成，分別為兼容路網數據錯誤的高效地圖匹配算法、基于非負矩陣分解的GPS定位誤差矩陣補全算法以及基于設備質量加權的路段環境友好性評估算法.算法1的目標是高效準確地實現所有GPS數據的地圖匹配.具體而言包括2個模塊.其中，“基于隱Markov模型的2階段地圖匹配”模塊，利用公交車大部分情況下運行路徑固定的特點，縮減基于隱Markov模型的地圖匹配算法的搜索空間，提高算法效率.另外，針對OMS地圖存在缺失路段的問題，利用GPS軌跡歷史數據發現并擬合缺失路徑，修訂地圖路網中的錯誤，并對新增路徑附近的GPS點執行重新匹配.

地圖匹配完成后，可以計算得到每個GPS記錄的定位誤差并構造1個誤差矩陣，每一行表達1輛車的誤差向量，每表達1個路段的誤差向量，矩陣元素為某輛車在某個路段上的平均誤差.之后調用“基于NMF的GPS定位誤差矩陣補全算法”，采用非負矩陣分解技術，利用矩陣元素之間的相關性，對缺失元素進行補全.

補全后的GPS定位誤差矩陣中，可以利用行向量的模長衡量車中端設備的質量，而利用列向量的模長衡量路段的環境友好性.考慮到質量更好的端設備在衡量路段環境友好性時，應該享有更高的權重，因此“基于設備質量加權的路段環境更友好性評估算法”根據車輛端設備的質量加權計算得到路段的加權平均誤差，并以此作為路段的環境友好性評估的依據.

3 兼容路網數據錯誤的高效地圖匹配算法

3.1 基于隱Markov模型的2級地圖匹配

由于本文方法對地圖匹配準確性要求較高，因此采用基于隱Markov模型的地圖匹配算法作為算法原型.基于隱Markov模型的地圖匹配算法基于2條規則：1)某個GPS采樣數據與某條路段的匹配概率，與該GPS采樣的經緯度坐標位置到路段的偏移距離相關，距離越短，概率越大；2)由于車輛是連續前進的，因此當前GPS采樣數據對應的路段應該與上一時刻采樣數據對應的路段距離相近.基于以上這2條規則，算法以動態規劃策略求解出具有最大概率的前進路徑.

然而，若在本文的數據集中直接應用上述算法原型，計算量較大.實際上，相比于其他車輛軌跡數據(例如出租車數據)，公交軌跡數據有其自身的特點，基本固定不變的公交線路信息可以為道路匹配提供重要的補充信息，從而大大減少可能匹配的候選道路的數量.因此，本文根據公交數據本身的特點，提出2階段算法以提高道路匹配的效率.

階段1. 基于公交線路路徑數據的地圖匹配.每一個GPS點所關聯計算的路段可由地圖附近路段縮減至公交車指定線路，進而提高效率.其中，公交車線路同樣由GPS指定，因此需要先將線網數據通過地圖匹配算法匹配至路網，獲得公交線路路段.隨后將公交車GPS數據匹配至公交線路路段.

階段2. 基于地圖路網數據的地圖匹配.與公交線路初步匹配后的公交車GPS數據仍然存在較多具有較高誤差的點，即與所有公交線路路段都相距很遠.主要原因是公交車并非完全按照給定的線路路徑行駛，具體原因包括3個方面：1)因為道路施工臨時改道、線路調整后路徑數據未及時更新等原因，導致公交公司提供的線路路徑數據并非完全準確；2)公交車可能因為檢修、加油等原因，未按線路路徑行駛；3)某個線路的公交車被臨時調度開另一個線路.針對上述3個原因，首先根據第1階段匹配結果，篩選出明顯偏離匹配路段的GPS點集合，并分析GPS點與公交線路偏離的起始點，在此位置附近搜索地圖上的其他路段，仍然采用基于隱Markov模型的地圖匹配原型算法選擇最佳匹配結果.

基于隱Markov模型的2級地圖匹配算法具體算法描述如下：

輸入: GPS序列G={gt|t=0,1,…,T-1}，其中gt為第t條GPS數據，包含經緯度坐標、時間戳等；公交車線路軌跡點序列B={bi|i=0,1,…,T-1}，其中bi為第i個線路軌跡點，包含經緯度坐標；路網數據NE={Nodes,Edges}，其中Nodes={ni|i=0,1,…,M-1}為節點集合，每個節點是地理上的坐標點，表示交叉路口、道路上拐點等，Edges={ri|i=0,1,…,N-1}為邊集合，即路段集，每條邊是2個節點之間的直線路段；

輸出: 每條GPS數據與路段的映射關系以及偏移路段的距離MR={(rt,dt)|t=0,1,…,T-1}.偽代碼如算法1所示.

算法1. 基于HMM的2階段地圖匹配.

①BMR=HMM_MapMatching(B,NE)；*公交線路路段*

②start=-1,end=-1；*初步匹配后仍 然誤差較大的區間的起始、結束位置*

③ fori=0 toT-1 do*對誤差較大區間內 的匹配結果進行臨近路段重匹配*

④ ifMRi偏離距離超過50 m andstart=-1 then

⑤start=i；

⑥ endif

⑦ ifMRi偏離距離小于50 m andstart≠-1 then

⑧end=i-1；

⑨MRstart→end=HMM_MapMatching(Gstart→end,NE);*將誤差較大的 點匹配至臨近路段*

⑩start=-1；

3.2 基于局部加權線性回歸的路網修正

以OSM為代表的路網地圖含有缺失路段等錯誤,導致GPS點無法全部定位至地圖已有路段上，從而錯誤地計算出大量匹配誤差.本文提出了基于局部回歸的路網修正算法，在基于臨近路段重匹配的線路錯誤誤差消除的結果上，挑選出GPS定位誤差較仍然大的路段，將該路段上的全部GPS點進行局部加權的線性回歸，進而以較小的計算量補充路段校準地圖.

局部加權線性回歸算法是一種常用的曲線擬合算法[29].其賦予每個數據點以一定的權值，以此為基礎利用最小均方差來進行普通線性回歸.相比于普通線性回歸，局部加權線性回歸可以無參地進行曲線擬合，緩解欠擬合問題.

但由于城市路段形狀不定且局部加權線性回歸對坐標系方向敏感，因此在進行路段擬合前還需要進行預處理，選取合適的坐標系方向.本文所采用的方法為：遍歷嘗試不同坐標系方向，在x軸上每5 m劃定1個區間，計算該區間內全部公交GPS點的y值方差，最終計算全部區間內的平均y值方差，并選取最小平均方差所對應的坐標系.

基于局部加權線性回歸的路網修正偽代碼如算法2：

算法2. 基于局部加權線性回歸的路網修正.

①OGPS←MR中偏離距離仍然超過50 m的 GPS點集合區間的集合；

② forOGinOGPSdo

③ 將OG中的坐標點旋轉直到x軸方向上每個小區間中y值分布的標準差的均值最小；

④ 將OG中點做局部加權線性回歸，擬合出一條新的路；

⑤ 更新MR；

⑥ endfor

⑦ returnMR.

3.3 實驗結果與分析

1) 2級地圖匹配結果

第1級地圖匹配中，已有80.90%的公交車GPS數據點在誤差閾值限定下匹配至公交線路，但仍有19.10%的定位點存在較大誤差;第2級地圖匹配將該部分GPS點利用路網數據進行重匹配，該部分數據中約81.09%在誤差閾值限定下匹配至臨近路段，至此全部GPS數據點的96.39%已完成地圖匹配，結果如表1所示.剩余仍然誤差較大的數據點將在路網修正后進一步匹配.

Table 1 Result of 2-Phase Map Matching

2) 算法效率提升

實驗使用的服務器配置為Intel?Xeon?CPU E5-2650 v2 @ 2.60 GHz，32核，128 GB內存.我們開啟15線程，對普通地圖匹配算法(即將所有公交車GPS點直接在OSM地圖上進行基于隱Markov模型的道路匹配)以及本文改進后的2級地圖匹配算法效率進行了測試.結果如表2所示，本文算法極大地縮減匹配過程中候選路段的數量，提升了算法的效率.

3) 路網修正結果

本文基于局部加權線性回歸的路網修正算法，對OSM路網地圖在成都市二環內共補充路段20條，其中2條路段的修正結果如圖3所示.

圖3依次展示了2條缺失路段的原始OSM地圖、對應的經過2級地圖匹配后依然誤差較大的公交車GPS數據、局部回歸擬合后的補充道路(綠色線條)以及衛星對照圖(紅色標注部分為對應道路).

Table 2 Efficiency Comparison

(a)OriginalOSM(missingsegmentsaremarkedwithredcircles) (b)GPSdataofbuses (c)Roadsegmentscompletedbyourmethod(markedwithgreenlines) (d)Satellitephotos(completedsegmentsaremarkedwithredcircles)

Fig. 3 Results of supplement missing road segments of OSM (Qingyun South Street and North of Shuangqiaozi).
圖3 OSM地圖缺失路段補充結果(慶云南街與雙橋子北)

根據對照結果可見，基于局部回歸的路網修正算法借助公交車GPS數據，成功識別并擬合出了OSM地圖上部分缺失的道路.

4 基于NMF的GPS定位誤差矩陣補全算法

4.1 GPS定位誤差矩陣構造

地圖匹配完成后，可以通過計算每個GPS點位置與匹配路段的垂直距離作為該條GPS數據的定位誤差.考慮到GPS定位誤差不僅包括環境友好性的影響還涉及星座等隨機因素，我們對每一輛公交車在其30 d內經過的每一個路段上的多次GPS定位記錄計算誤差平均值.如果某輛公交車在某條路段上的GPS數據記錄少于20條，則該部分數據被視為不可靠數據拋棄.

至此我們可以進行誤差矩陣的構造.該矩陣每一行表達1輛公交車的誤差向量，每表達1個路段的誤差向量，矩陣元素表示某輛車在某路段上的平均誤差.由于成都市二環內有4 869輛不同的公交車且公交車軌跡共覆蓋5 648個不同的路段，而每輛公交車經過的路段僅為總路段中的一小部分，因此將構造出1個4 869×5 648的非負稀疏矩陣.

我們試圖利用該誤差矩陣評估每條路段的GPS環境友好性.一個直觀的想法是直接計算每條路段上所經過公交車的GPS平均偏差值，以此評估該路段的GPS環境友好性.但公交車的GPS端設備質量并不一致，如果通過某一路段的公交車所搭載的GPS設備普遍質量較差，則無論該路段是否GPS環境友好均會得到相對較高的GPS平均偏差值，即評估有失公平.

因此，本文引入非負矩陣分解技術進行矩陣補全，計算得到所有公交車在所有路段上的GPS偏差推測值，進而實現使用不同質量的端設備客觀評估環境對誤差的影響.

4.2 誤差矩陣分解與補全

非負矩陣分解(non-negative matrix factorization, NMF)是在矩陣中所有元素均為非負數約束條件之下的經典矩陣分解方法.其利用矩陣元素之間的相關性，將任意非負矩陣分解為2個非負矩陣乘積的形式，進而重構原矩陣達到填補空缺值的效果，實現矩陣補全.

算法輸入: 非負稀疏誤差矩陣Mm×n,其中m表示總公交車數量，n表示全部路段數，矩陣每一行表達1輛車的誤差向量，每表達1個路段的誤差向量，矩陣元素Mi,j為第i輛公交車在第j個路段上的GPS平均定位誤差.若Mi,j=0,則表示該車未經過該路段，沒有相關數據.

算法參數: 矩陣分解的中間維度k，由經驗法給出.

算法輸出: 2個非負矩陣Lm×n,Rk×n.

由于NMF算法中并未考慮待分解矩陣M包含空缺值的情況，為此本文定義標識矩陣D：

非負矩陣分解算法中的目標函數定義為

算法采用梯度下降方法在迭代過程中不斷降低目標函數值，最終求得矩陣L,R.迭代公式經推導得到：

在非負矩陣分解算法中，每輪迭代需要按照上述公式進行矩陣運算.以L的更新為例，計算MRT,LR,(D·LR)RT都各需要m×n×k次浮點運算(只考慮乘除)，計算D與LR的矩陣點乘需要m×n次浮點運算，計算L,MRT,1(D·LR)RT三者的矩陣點乘需要2×m×n次浮點運算，對R的更新與之相似，因此每輪迭代需要6(m×k×n)次浮點運算，時間復雜度為O(m×k×n).設定進行T輪迭代，則整體時間復雜度為O(T×m×k×n).此外，根據分解得到L,R,恢復原有矩陣需要一次矩陣乘法，其時間復雜度為O(m×k×n).

4.3 實驗結果與分析

本文采用三次10折交叉驗證法，驗證矩陣補全結果準確性.

將矩陣M中非零位置隨機劃分為相同大小的10個部分(P1,P2,…,P10)，對于每個部分Pi，遮蓋住這一部分(將相應位置的元素值設為0)，保留其余9個部分，對M′進行1次補全，對于本次補全得到的矩陣L′R′計算偏差率(estimate-error)如下：

對所有部分分別進行遮蓋后得到最終的偏差率：

重新將非零部分進行劃分，上述步驟重復3次后將每次得到的偏差率求和取平均，最終求得偏差率18.28%.根據文獻[22-23]該偏差率處于較低范圍，驗證了基于NMF的GPS定位誤差矩陣補全算法的有效性與準確性.

5 基于設備質量加權的路段環境友好性評估

5.1 加權迭代排序

通過補全GPS定位誤差矩陣，我們已經獲得了每輛公交車在每個路段的大致GPS定位誤差.矩陣中的行向量模長可以衡量車中端設備的質量，而利用列向量的模長可以衡量路段的環境友好性.

考慮到質量較差的端設備在GPS定位時具有較高不確定性，質量更好的端設備在衡量路段環境友好性時應該享有更高的權重.同樣，GPS環境友好的路段在衡量公交車端設備質量時，也應具有較高的權重.本文據此提出了加權迭代排序算法,該算法根據公交車GPS定位加權誤差、路段上加權誤差的高低排名賦予公交車與路段不同的權值，并以此重新計算全部車輛與路段的加權定位誤差.通過不斷迭代直至算法收斂，即全部車輛與路段的排序趨于穩定,最終獲得全部路段的加權誤差以及排序結果，并以此作為路段的環境友好性評估的依據.

算法輸入: 補全后的誤差矩陣Mm×n、最多迭代次數Maxlt.

算法輸出: 車的排序結果Bus_Rank，路的排序結果Road_Rank.

算法描述如下，流程如算法3所示.

初始給予所有車以及路段相同的權重.以Bus_Wt,i表示第i輛車在第t次迭代時的權重，以Road_Wt,j表示第j條路段在第t次迭代時的權重，則：

根據當前權重計算所有車、路的誤差值.以Bus_Distt,i表示第i輛車在第t次迭代時的誤差加權均值，Road_Distt,i表示第j條路段在第t次迭代時的誤差加權值，則：

根據上述誤差加權均值分別對車和路排序，并計算與上一次迭代后排序結果的偏差.以Bus_Rank_Dt表示第t次迭代后車輛排序的變動狀況，Road_Rank_Dt表示第t次迭代后路段排序的變動狀況，則：

Bus_Rank_Dt=

Road_Rank_Dt=

其中，Bus_Rankt,i表示第i輛車在第t次迭代結束后的排名，Road_Rankt,j表示第j條路段在第t次迭代后的排名.

算法3. 加權迭代排序.

① 初始公交車權重Bus_W0,i；

② 初始路段權重Road_W0,j；

③ 初始公交車排名Bus_Rank0={0,1,…,m-1}；

④ 初始路段排名Road_Rank0={0,1,…,n-1}；

⑤ fort←1 toMaxItdo

⑥ fori←0 tom-1 do

⑦ UpdateBus_Distt,i；

⑧ endfor

⑨ forj←0 ton-1 do

⑩ UpdateRoad_Distt,j；

如果Bus_Rank_Dt與Road_Rank_Dt同時為0，則表明排序穩定，評估結果不再發生變化，算法停止.或者若達到最大迭代次數，算法停止.否則，按照低誤差車輛、路段權重高，反之權重低的原則，重新計算權值：

進入下一輪迭代，直至滿足停止條件.

5.2 實驗結果與分析

本文基于設備質量加權的路段環境友好性評估算法考慮不同車載設備的質量差異對路段環境友好性評估的影響，通過端設備權值計算與路段GPS友好性評估的多次迭代計算，得到最終結果.我們還設置了簡單的對比方法，通過GPS誤差矩陣構造得到稀疏誤差矩陣后，直接利用已有數據對所有路段求得平均誤差，并以此評判路段的GPS環境友好性.2個方法的結果如表3所示：

Table 3 Evaluation Results of Road Friendliness

我們按照誤差范圍，將路段劃分至3個級別，并統計出路段數量，如表4所示.誤差小于20 m定為GPS環境友好性較高(在圖4線路中以綠色標注)，誤差20～30 m之間定為GPS友好性中等(以黃色標注)，誤差大于30 m定為環境友好性較差(紅色標注).

Table 4 Evaluation Degree Comparison

Fig. 4 Environment friendliness evaluation of road segments inside the 2-ring road in Chengdu.圖4 成都市二環以內路段環境友好性分級結果

GPS信號質量良好的路段，相對而言路況簡單并且視野開闊，一般道路寬度比較寬，位于城市主干道路或者快速路高架橋上，環境遮蔽物通常相距較遠或只位于道路單側，整體受環境遮蔽物影響小.

GPS信號質量一般的路段，道路環境介于紅色路段和綠色路段之間，路寬適中，通常存在數種環境遮擋物中的一種或幾種.

GPS信號質量較差的路段，其道路周邊環境會對信號造成較大影響.首先，這些道路寬度一般較窄，往往集中于非主干道路，雙向單車道或雙向雙車道居多；其次，這些道路周圍的環境遮蔽物較為密集，包括建筑物和密集的道旁樹木等，這些路段受多路徑誤差影響大.部分路段街景如圖5所示，其中GPS環境友好的4條路段對應于圖4中圈注G1-G4，友好性中等路段對應于Y1-Y4，友好性較差路段對應于R1-R4.

本文方法與基本方法對比，共有1 355條路段分級發生變化，其中1 279條路段評級變好(590條路段是由紅變綠的、689條路段由紅變黃或由黃變綠)，76條路段評級變壞.

由紅變綠的路段當中，經過車輛平均排名2 331(公交車總數4 869)，即經過這些路段的車大部分端設備質量較差，導致對比方法對路段的GPS環境友好性低估.而基于設備加權的路段環境友好性評估算法將誤差矩陣補全，根據車輛端設備的質量加權計算得到路段的加權平均誤差，進而公平評估路段的環境友好性，使得被對比方法誤判的道路評級上升.

(a)Goodenvironmentfriendliness(markedwithgreeninFig．4(b))(b)Normalenvironmentfriendliness(markedwithyellowinFig．4(b))(c)Badenvironmentfriendliness(markedwithredinFig．4(b))

Fig. 5 Street view of road segments which have different level in environment friendliness evaluation.
圖5 環境友好性不同級別路段的街景圖示例

以某路段為例，其共經過238輛車，平均排名為2 477.對比方法計算其平均誤差為42 m，環境友好性被評估為不友好.但本文提出算法計算其誤差加權均值為15 m，環境友好性被評估為友好.

街景圖6顯示，該路段地勢平坦開闊，沒有高樓、高架橋等建筑物阻擋，GPS環境友好性較高.驗證本文提出算法的有效性.

Fig. 6 Street view of good GPS environment friendliness.圖6 GPS環境友好街景驗證

6 結 論

本文提出了一種基于海量公交車載GPS歷史軌跡數據評估城市主要路段的環境友好性的方法.該方法首先利用公交車運行線路固定的特點，高效地將GPS數據映射到城市的路段上，并針對路網數據可能存在的錯誤，提出了容錯方案.其次，利用相同車輛及相同路段在GPS誤差上存在的內在關聯，對缺失數據進行補全，并充分考慮到不同質量GPS端設備對環境友好性評估的影響，提出了一種基于端設備質量加權的評估計算策略.利用成都市二環內的4 869輛公交車1個月的數據，本文對共計5 648個不同路段的環境友好性進行了評估，并通過衛星地圖和街景照片的分析，驗證了方法的合理性.

未來工作主要關注3個方面：1)實地測量和驗證.本文目前通過查看部分路段的百度街景地圖對結果的合理性進行分析和驗證.未來我們將前往成都市，并攜帶相應GPS端設備進行實地測量，進一步驗證方法結果的合理性.2)基于本文中車輛端設備質量和道路環境友好性評估結果，為實時公交APP等應用，建立公交車實時位置及到站時間預測等分析結果的可信性評估模型，并利用評估結果提高此類應用的用戶體驗.3)將環境友好性評估結果作為訓練數據，利用城市街景圖片，提取環境特征，對沒有公交軌跡數據的城市路段的GPS環境友好性進行預測.

[1]Meguro J, Murata T, Takiguchi J, et al. GPS multipath mitigation for urban area using omnidirectional infrared camera[J]. IEEE Trans on Intelligent Transportation Systems, 2009, 10(1): 22-30

[2]Drawil N M, Amar H M, Basir O A. GPS localization accuracy classification: A context-based approach[J]. IEEE Trans on Intelligent Transportation Systems, 2013, 14(1): 262-273

[3]Modsching M, Kramer R, ten Hagen K. Field trial on GPS accuracy in a medium size city: The influence of built-up[C] //Proc of the 3rd Workshop on Positioning, Navigation and Communication. Hannover: WPNC, 2006: 209-218

[4]Ahlers D, Pielot M, Wichmann D, et al. GNSS quality in pedestrian applications-a developer perspective[C] //Proc of the Workshop on Positioning. Piscataway, NJ: IEEE, 2008:45-54

[5]Syed S, Cannon M E. Fuzzy logic-based map matching algorithm for vehicle navigation system in urban canyons[C] //Proc of the 2004 National Technical Meeting of the Institute of Navigation. San Diego, CA: ION, 2004: 26-28

[6]Han S C, Kwon J H, Jekeli C. Accurate absolute GPS positioning through satellite clock error estimation[J]. Journal of Geodesy, 2001, 75(1): 33-43

[7]Tian Yang, Liu Mian. Bus real-time software is mostly not Reliable[N]. Beijing Daily, 2016-03-16 (in Chinese)(田陽, 劉冕. 公交實時軟件大多不靠譜[N]. 中國日報, 2016-03-16)

[8]Newson P, Krumm J. Hidden Markov map matching through noise and sparseness[C] //Proc of the 17th ACM SIGSPATIAL Int Conf on Advances in Geographic Information Systems. New York: ACM, 2009: 336-343

[9]Ren Ming, Karimi H A. A hidden Markov model-based map-matching algorithm for wheelchair navigation[J]. Journal of Navigation, 2009, 62(3): 383-395

[10]Girres J F, Touya G. Quality assessment of the French OpenStreetMap dataset[J]. Trans in GIS, 2010, 14(4): 435-459

[11]Kounadi O. Assessing the quality of OpenStreetMap data[D]. London: University College of London, Department of Civil, Environmental and Geomatic Engineering, 2009

[12]Haklay M. How good is volunteered geographical information? A comparative study of OpenStreetMap and ordnance survey datasets[J]. Environment and Planning B: Planning and Design, 2010, 37(4): 682-703

[13]Wells D E, Beck N, Delikaraoglou D, et al. Guide to GPS Positioning[M]. Fredericton, NB, Canada: Canadian GPS Associates, 1986

[14]Grewal M S, Weill L R, Andrews A P. Global Positioning Systems, Inertial Navigation, and Integration[M]. New York: John Wiley & Sons, 2007

[15]Rankin J. An error model for sensor simulation GPS and differential GPS[C] //Proc of Position Location and Navigation Symp. Piscataway, NJ: IEEE, 1994:260-266

[16]Greenfeld J S. Matching GPS observations to locations on a digital map[C] //Proc of of the 81st Annual Meeting of the Trans Research Board. Washington, DC: Transportation Research Board, 2002

[17]Quddus M A, Ochieng W Y, Zhao Lin, et al. A general map matching algorithm for transport telematics applications[J]. GPS Solutions, 2003, 7(3): 157-167

[18]Ochieng W Y, Quddus M, Noland R B. Map-matching in complex urban road networks[J]. Revista Brasileira De Cartografia, 2003, 55(2):1-14

[19]Krakiwsky E J, Harris C B, Wong R V C. A Kalman filter for integrating dead reckoning, map matching and GPS positioning[C] //Proc of Position Location and Navigation Symp. Piscataway, NJ: IEEE, 1988: 39-46

[20]Obradovic D, Lenz H, Schupfner M. Fusion of map and sensor data in a modern car navigation system[J]. Journal of VLSI Signal Processing Systems for Signal, Image and Video Technology, 2006, 45(1/2): 111-122

[21]Bell R, Koren Y, Volinsky C. Chasing $1, 000, 000: How we won the Netflix progress prize[J]. ASA Statistical and Computing Graphics Newsletter, 2007, 18(2): 4-12

[22]Zhu Yanmin, Li Zhi, Zhu Hongzi, et al. A compressive sensing approach to urban traffic estimation with probe vehicles[J]. IEEE Trans on Mobile Computing, 2013, 12(11): 2289-2302

[23]Lee D D, Seung H S. Algorithms for non-negative matrix factorization[C] //Advances in Neural Information Processing Systems. La Jolla, CA: NIPS, 2001: 556-562

[24]Zhou Pengfei, Jiang Shiqi, Li Mo. Urban traffic monitoring with the help of bus riders[C] //Proc of Int Conf on Distributed Computing Systems. Piscataway, NJ: IEEE, 2015: 21-30

[25]Wang Yuqi, Cao Jinnong, Li Wengen, et al. Mining traffic congestion correlation between road segments on GPS trajectories[C] //Proc of 2016 IEEE Int Conf on Smart Computing. Los Alamitos, CA: IEEE Computer Society, 2016:1-8

[26]Zhang Fusang, Jin Beihong, Wang Zhaoyong, et al. On geocasting over urban bus-based networks by mining trajectories[J]. IEEE Trans on Intelligent Transportation Systems, 2016, 17(6):1-14

[27]Wang Yilun, Zheng Yu, Xue Yexiang. Travel time estimation of a path using sparse trajectories[C] //Proc of the 20th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2014: 25-34

[28]Zhang Daqing, Li Nan, Zhou Zhihua, et al. iBAT: Detecting anomalous taxi trajectories from GPS traces[C] //Proc of the 13th Int Conf on Ubiquitous Computing. New York: ACM, 2011: 99-108

[29]Harrington P. Machine Learning in Action[M]. Greenwich, CT: Manning, 2012Ma Liantao, born in 1994. PhD candidate in Institute of Software, School of Electronics Engineering and Computer Science, Peking University. His main Research interests include ubiquitous computing, machine learning.

Wang Yasha, born in 1975. Received his PhD degree in Northeastern University, Shenyang, China, in 2003. Professor and associate director of National Engineering Research Center of Software Engineering in Peking University, China. His main research interests include urban data analytics, ubiquitous computing, software reuse, and online software development environment.

Peng Guangju, born in 1995. Postgraduate of the School of Electronics Engineering and Computer Science, Peking University. His main research interest is ubiquitous computing.

Zhao Yuxin, born in 1995. Undergraduate of the School of Electronics Engineering and Computer Science, Peking University. Her main research interests include urban data analytics and ubiquitous computing.

He Yuanduo, born in 1992. Received his bachelor degree in Peking University, Beijing, in 2014. PhD candidate in Institute of Software, School of Electronics Engineering and Computer Science, Peking University. His main research interests include ubiquitous computing, mobile computing, and data mining.

Gao Jingyue, born in 1997. Undergraduate of the School of Electronics Engineering and Computer Science, Peking University. His main research interest include urban data analytics and ubiquitous computing.

Evaluation of GPS-Environment Friendliness of Roads Based on Bus Trajectory Data

Ma Liantao1,2,4, Wang Yasha1,3,4, Peng Guangju1,2, Zhao Yuxin1,2, He Yuanduo1,2, and Gao Jingyue1,2

1(Key Laboratory of High Confidence Software Technologies (Peking University), Ministry of Education, Beijing 100871)2(SchoolofElectronicsEngineeringandComputerScience,PekingUniversity,Beijing100871)3(NationalEngineeringResearchCenterofSoftwareEngineering(PekingUniversity),Beijing100871)4(Beida(Binhai)InformationResearch,Tianjin300450)

GPS is the most widely-used outdoor positioning system. With the advance of relevant technologies, positioning accuracy of GPS has been increasing continuously. However, as the GPS satellite signal can be blocked by buildings, multi-path error becomes the major cause of positioning error in a city. Evaluating the negative effects of GPS error on urban environments, which is referred as environment friendliness in this paper, will help the prediction of GPS error range in different road segments. Furthermore, it enhances user experiences of location-based services, reveals the relationship between environmental characteristics and multi-path error, and helps to determine where to deploy supplementary positioning devices. In this paper, we have proposed an urban road friendliness evaluation (URFE) approach, based on the processing and analyzing of massive historical bus GPS trajectory data. Specifically, URFE first takes full advantage of the unique features of fixed bus routes to significantly improve the efficiency of data processing. Then, it adopts a fault-tolerant method to deal with the possible errors of street maps; Finally, URFE completes the missing data by utilizing the inherent relationship between GPS errors of the same cars and roads, and utilizes an evaluation strategy by taking the influence of different GPS terminal devices’ qualities into account. Using the bus trajectory data within the second ring road of Chengdu during one month, we evaluate the effectiveness of our approach. Environments friendliness of 5648 different road segments has been evaluated, whose rationality has been verified by checking real satellite maps and street views.

location based service; GPS positioning error; data analysis; map matching; smart city

2016-08-16；

2016-10-27

國家自然科學基金重點項目(91546203) This work was supported by the Key Program of the National Natural Science Foundation of China (91546203).

王亞沙(wangyasha@pku.edu.cn)

TP391