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

馬連韜 王亞沙 彭廣舉 趙宇昕 何遠(yuǎn)舵 高敬月

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

?

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

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

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

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

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

隨著智慧城市建設(shè)的深入，定位技術(shù)在交通、旅游、社交等眾多領(lǐng)域獲得了廣泛的應(yīng)用.而GPS(global positioning system)作為一種精度高、適用范圍廣、終端設(shè)備造價(jià)低廉、免費(fèi)提供服務(wù)的定位系統(tǒng)，已經(jīng)得到廣泛應(yīng)用，GPS終端廣泛嵌入到智能手機(jī)、腕表、車載裝置等移動智能終端中，成為了室外定位技術(shù)的事實(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)星信號是通過可視路徑還是反射路徑到達(dá)設(shè)備的，統(tǒng)一按照可視路徑計(jì)算衛(wèi)星與設(shè)備之間的距離，從而導(dǎo)致計(jì)算終端設(shè)備位置時(shí)出現(xiàn)較大偏差.實(shí)測數(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ù)進(jìn)行校準(zhǔn)，顯著提高了定位的精度.然而，這些組合定位技術(shù)，大多需要在城市環(huán)境中部署額外的輔助設(shè)備(如WiFi熱點(diǎn))或者采集額外的數(shù)據(jù)(如采集城市環(huán)境的視頻、WiFi指紋等).

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

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

除此以外，評估道路環(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ù)集進(jìn)行.而由于公交車軌跡對城市公路實(shí)現(xiàn)了大范圍的覆蓋，因此本文工作將得到不同道路環(huán)境友好性評估的大批量化結(jié)果.這些數(shù)據(jù)為GPS多徑誤差的分析提供了大量數(shù)據(jù)，并可能為揭示GPS誤差受環(huán)境影響而變化的內(nèi)在規(guī)律提供支持.

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

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

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

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

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

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

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

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

3) 如何考慮不同車載設(shè)備質(zhì)量的差異，對所有路段的環(huán)境友好性做出公平的評估？通過對成都公交車GPS軌跡歷史數(shù)據(jù)的初步觀察和分析，我們發(fā)現(xiàn)不同車輛轉(zhuǎn)配的GPS端設(shè)備，質(zhì)量存在明顯差異.圖1顯示了2輛不同的公交車在相同的時(shí)段，通過相同路段的GPS報(bào)告位置分布情況.可以直觀地看到，圖1(a)中車輛GPS位置點(diǎn)較之圖1(b)中另一輛車明顯更加分散、距離道路更遠(yuǎn)、誤差也更大.這一現(xiàn)象與公交公司在不同時(shí)間、向不同供貨商采購的GPS設(shè)備質(zhì)量存在差異有關(guān).根據(jù)公交車運(yùn)行的規(guī)律，1輛車僅通過城市中的少量路段，而1個(gè)路段上也僅有部分車輛通過.設(shè)想A，B兩個(gè)環(huán)境友好性完全相同的路段，就途徑此2條路段的公交車載GPS端設(shè)備的質(zhì)量而言，路段B中設(shè)備的質(zhì)量明顯優(yōu)于路段A.如果僅觀察匹配到路段上的GPS記錄的誤差，認(rèn)為平均誤差越小，則環(huán)境友好性就更好，則很容易得出路段B的環(huán)境友好性優(yōu)于路徑A的錯(cuò)誤結(jié)論.在此條件下，如何考慮不同車輛車載GPS端設(shè)備的差異、公平的評估不同路段上的環(huán)境友好性是本文面臨的第3個(gè)挑戰(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位置報(bào)告誤差較大數(shù)據(jù)集合，發(fā)現(xiàn)地圖可能存在錯(cuò)誤的區(qū)域，并通過擬合GPS位置點(diǎn)的軌跡路徑，補(bǔ)充地圖缺失的道路，實(shí)現(xiàn)對地圖路網(wǎng)數(shù)據(jù)錯(cuò)誤的容錯(cuò).3)構(gòu)造誤差矩陣，每一行表達(dá)1輛車的誤差向量，每一列表達(dá)1個(gè)路段的誤差向量，矩陣元素為某輛車在某個(gè)路段上1個(gè)月的誤差均值，由于每輛車僅途徑少量路段，因此誤差矩陣顯然具有稀疏性.另外，從行向量的視角看，端設(shè)備質(zhì)量較高的車輛較之端設(shè)備質(zhì)量較差的車輛，在相同的路段上誤差均值傾向于更??；同理，從列向量的視角看，相同的車輛途徑環(huán)境友好性較好的路段，較之環(huán)境友好性較差的路段，其誤差均值也傾向于更小.也就是說，此稀疏矩陣中的數(shù)據(jù)元素之間存在信息冗余，亦即，數(shù)據(jù)元素之間存在深層的相關(guān)性.利用這種相關(guān)關(guān)系，可以運(yùn)用矩陣補(bǔ)全的算法，對矩陣缺失的數(shù)據(jù)進(jìn)行估計(jì)和補(bǔ)全.補(bǔ)全后，每個(gè)路段中包含了所有車在此路段中的平均誤差.4)基于上述補(bǔ)全后的矩陣，根據(jù)車輛GPS終端的質(zhì)量，對各個(gè)路段上不同車輛誤差的均值進(jìn)行加權(quán)平均，并以此加權(quán)平均值作為最終路段環(huán)境友好性的評估結(jié)果.本文利用衛(wèi)星地圖和街景照片，對URFE在成都二環(huán)內(nèi)路段中的地圖補(bǔ)全和環(huán)境友好性評估結(jié)果進(jìn)行了分析，發(fā)現(xiàn)了道路寬度、地面建筑高度等環(huán)境特征與環(huán)境友好性評估結(jié)果之間存在的相關(guān)性，驗(yàn)證了評估結(jié)果的合理性.

1 相關(guān)工作

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

1.1 GPS定位精度估計(jì)及影響因素研究

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

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

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

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

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

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

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

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

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

2 方法框架

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

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

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

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

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

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

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

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

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

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

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

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

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

輸出: 每條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é)果進(jìn)行臨近路段重匹配*

④ 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);*將誤差較大的 點(diǎn)匹配至臨近路段*

⑩start=-1；

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

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

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

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

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

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

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

② forOGinOGPSdo

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

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

⑤ 更新MR；

⑥ endfor

⑦ returnMR.

3.3 實(shí)驗(yàn)結(jié)果與分析

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

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

Table 1 Result of 2-Phase Map Matching

2) 算法效率提升

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

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

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

圖3依次展示了2條缺失路段的原始OSM地圖、對應(yīng)的經(jīng)過2級地圖匹配后依然誤差較大的公交車GPS數(shù)據(jù)、局部回歸擬合后的補(bǔ)充道路(綠色線條)以及衛(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地圖缺失路段補(bǔ)充結(jié)果(慶云南街與雙橋子北)

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

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

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

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

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

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

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

4.2 誤差矩陣分解與補(bǔ)全

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

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

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

算法輸出: 2個(gè)非負(fù)矩陣Lm×n,Rk×n.

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

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

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

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

4.3 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

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

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

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

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

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

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

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

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

根據(jù)上述誤差加權(quán)均值分別對車和路排序，并計(jì)算與上一次迭代后排序結(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同時(shí)為0，則表明排序穩(wěn)定，評估結(jié)果不再發(fā)生變化，算法停止.或者若達(dá)到最大迭代次數(shù)，算法停止.否則，按照低誤差車輛、路段權(quán)重高，反之權(quán)重低的原則，重新計(jì)算權(quán)值：

進(jìn)入下一輪迭代，直至滿足停止條件.

5.2 實(shí)驗(yàn)結(jié)果與分析

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

Table 3 Evaluation Results of Road Friendliness

我們按照誤差范圍，將路段劃分至3個(gè)級別，并統(tǒng)計(jì)出路段數(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)境遮蔽物通常相距較遠(yuǎ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)境友好性評估算法將誤差矩陣補(bǔ)全，根據(jù)車輛端設(shè)備的質(zhì)量加權(quán)計(jì)算得到路段的加權(quán)平均誤差，進(jì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.對比方法計(jì)算其平均誤差為42 m，環(huán)境友好性被評估為不友好.但本文提出算法計(jì)算其誤差加權(quán)均值為15 m，環(huán)境友好性被評估為友好.

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

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

6 結(jié) 論

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

未來工作主要關(guān)注3個(gè)方面：1)實(shí)地測量和驗(yàn)證.本文目前通過查看部分路段的百度街景地圖對結(jié)果的合理性進(jìn)行分析和驗(yàn)證.未來我們將前往成都市，并攜帶相應(yīng)GPS端設(shè)備進(jìn)行實(shí)地測量，進(jìn)一步驗(yàn)證方法結(jié)果的合理性.2)基于本文中車輛端設(shè)備質(zhì)量和道路環(huán)境友好性評估結(jié)果，為實(shí)時(shí)公交APP等應(yīng)用，建立公交車實(shí)時(shí)位置及到站時(shí)間預(yù)測等分析結(jié)果的可信性評估模型，并利用評估結(jié)果提高此類應(yīng)用的用戶體驗(yàn).3)將環(huán)境友好性評估結(jié)果作為訓(xùn)練數(shù)據(jù)，利用城市街景圖片，提取環(huán)境特征，對沒有公交軌跡數(shù)據(jù)的城市路段的GPS環(huán)境友好性進(jì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)(田陽, 劉冕. 公交實(shí)時(shí)軟件大多不靠譜[N]. 中國日報(bào), 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é)基金重點(diǎn)項(xiàng)目(91546203) This work was supported by the Key Program of the National Natural Science Foundation of China (91546203).

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

TP391