基于公交車軌跡數(shù)據(jù)的道路GPS環(huán)境友好性評估

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

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

?

基于公交車軌跡數(shù)據(jù)的道路GPS環(huán)境友好性評估

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

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

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

位置服務(wù)；GPS誤差；數(shù)據(jù)分析；地圖匹配；智慧城市

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

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

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

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

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

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

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

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

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

以上2階段方案并不簡單，面臨3個方面挑戰(zhàn)：

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

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

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

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

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

1 相關(guān)工作

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

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

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

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

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

1.2 道路匹配與矩陣補全技術(shù)

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

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

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

1.3 基于車輛GPS的智慧城市數(shù)據(jù)挖掘應(yīng)用

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

2 方法框架

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

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

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

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

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

3 兼容路網(wǎng)數(shù)據(jù)錯誤的高效地圖匹配算法

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

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

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

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

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

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

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

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

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

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

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

③ fori=0 toT-1 do*對誤差較大區(qū)間內(nèi) 的匹配結(jié)果進行臨近路段重匹配*

④ 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 基于局部加權(quán)線性回歸的路網(wǎng)修正

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

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

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

基于局部加權(quán)線性回歸的路網(wǎng)修正偽代碼如算法2：

算法2. 基于局部加權(quán)線性回歸的路網(wǎng)修正.

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

② forOGinOGPSdo

③ 將OG中的坐標(biāo)點旋轉(zhuǎn)直到x軸方向上每個小區(qū)間中y值分布的標(biāo)準(zhǔn)差的均值最小；

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

⑤ 更新MR；

⑥ endfor

⑦ returnMR.

3.3 實驗結(jié)果與分析

1) 2級地圖匹配結(jié)果

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

Table 1 Result of 2-Phase Map Matching

2) 算法效率提升

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

3) 路網(wǎng)修正結(jié)果

本文基于局部加權(quán)線性回歸的路網(wǎng)修正算法，對OSM路網(wǎng)地圖在成都市二環(huán)內(nèi)共補充路段20條，其中2條路段的修正結(jié)果如圖3所示.

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

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地圖缺失路段補充結(jié)果(慶云南街與雙橋子北)

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

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

4.1 GPS定位誤差矩陣構(gòu)造

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

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

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

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

4.2 誤差矩陣分解與補全

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

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

算法參數(shù): 矩陣分解的中間維度k，由經(jīng)驗法給出.

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

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

非負矩陣分解算法中的目標(biāo)函數(shù)定義為

算法采用梯度下降方法在迭代過程中不斷降低目標(biāo)函數(shù)值，最終求得矩陣L,R.迭代公式經(jīng)推導(dǎo)得到：

在非負矩陣分解算法中，每輪迭代需要按照上述公式進行矩陣運算.以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)次浮點運算，時間復(fù)雜度為O(m×k×n).設(shè)定進行T輪迭代，則整體時間復(fù)雜度為O(T×m×k×n).此外，根據(jù)分解得到L,R,恢復(fù)原有矩陣需要一次矩陣乘法，其時間復(fù)雜度為O(m×k×n).

4.3 實驗結(jié)果與分析

本文采用三次10折交叉驗證法，驗證矩陣補全結(jié)果準(zhǔn)確性.

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

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

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

5 基于設(shè)備質(zhì)量加權(quán)的路段環(huán)境友好性評估

5.1 加權(quán)迭代排序

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

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

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

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

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

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

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

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

Bus_Rank_Dt=

Road_Rank_Dt=

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

算法3. 加權(quán)迭代排序.

① 初始公交車權(quán)重Bus_W0,i；

② 初始路段權(quán)重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，則表明排序穩(wěn)定，評估結(jié)果不再發(fā)生變化，算法停止.或者若達到最大迭代次數(shù)，算法停止.否則，按照低誤差車輛、路段權(quán)重高，反之權(quán)重低的原則，重新計算權(quán)值：

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

5.2 實驗結(jié)果與分析

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

Table 3 Evaluation Results of Road Friendliness

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

Table 4 Evaluation Degree Comparison

Fig. 4 Environment friendliness evaluation of road segments inside the 2-ring road in Chengdu.圖4 成都市二環(huán)以內(nèi)路段環(huán)境友好性分級結(jié)果

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

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

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

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

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

(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 環(huán)境友好性不同級別路段的街景圖示例

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

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

Fig. 6 Street view of good GPS environment friendliness.圖6 GPS環(huán)境友好街景驗證

6 結(jié) 論

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

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

[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

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

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

TP391