基于GIS路網(wǎng)的公交路線軌跡算法①

鐘會(huì)玲,金紅達(dá),沈建惠,沈 斌,徐 夢(mèng)

(浙江浙大中控信息技術(shù)有限公司,杭州 310052)

基于GIS路網(wǎng)的公交路線軌跡算法①

鐘會(huì)玲,金紅達(dá),沈建惠,沈 斌,徐 夢(mèng)

(浙江浙大中控信息技術(shù)有限公司,杭州 310052)

為解決公交路線軌跡偏移路網(wǎng)以及在GIS路網(wǎng)信息缺失尤其是鄉(xiāng)村道路情況下的公交軌跡描繪.論文首先通過深入分析公交車輛GPS數(shù)據(jù),分別聚類出線路上下行軌跡點(diǎn);其次,軌跡點(diǎn)清洗并排序;再次,結(jié)合GIS路網(wǎng)基礎(chǔ)信息進(jìn)行地圖匹配;最后,根據(jù)改進(jìn)的Dijkstra算法解決路網(wǎng)拓?fù)浣Y(jié)構(gòu)缺失情況下制作出公交路線軌跡.將該算法實(shí)施在A市35條公交線路上,線路匹配成功率為85%,未匹配成功線路由于樣本缺失或者路網(wǎng)基礎(chǔ)信息錯(cuò)誤導(dǎo)致,可見該算法具有較好的準(zhǔn)確率和實(shí)用性.

Dijkstra算法;公交;GIS;地圖匹配;軌跡偏移

?

如今,大部分城市的公交車輛安裝了GPS定位終端設(shè)備,從而能夠?qū)崿F(xiàn)實(shí)時(shí)對(duì)公交車輛進(jìn)行位置監(jiān)控.有學(xué)者利用GPS定位數(shù)據(jù)聚類研究公交路線軌跡,也有將軌跡點(diǎn)根據(jù)已有GIS路網(wǎng)信息匹配路網(wǎng),董俊等人利用改進(jìn)Dijkstra算法在GIS導(dǎo)航應(yīng)用中最短路徑搜索研究,該改進(jìn)的算法雖然效率較傳統(tǒng)算法有所提高,但能在GIS導(dǎo)航中應(yīng)用前提是路網(wǎng)基礎(chǔ)信息完整,而且針對(duì)GIS路網(wǎng)信息缺失尤其是鄉(xiāng)村道路的情況未給出具體解決方案,得出公交車輛的行駛軌跡,能提取出公交線路,從而能夠?qū)痪€路尤其是新開公交線路進(jìn)行快速數(shù)字化,公交線路軌跡有助于公交線路車輛上下行、進(jìn)出站時(shí)間和班次計(jì)算,公交軌跡數(shù)據(jù)是路網(wǎng)的拓?fù)浣Y(jié)及完善路網(wǎng)信息的終于參考依據(jù),同時(shí)也能直觀反映公交路網(wǎng)結(jié)構(gòu)供決策者決策使用.

因此本文利用大量的歷史GPS軌跡數(shù)據(jù),對(duì)GPS軌跡數(shù)據(jù)聚類,并結(jié)合路網(wǎng)基礎(chǔ)信息進(jìn)行地圖匹配,提高公交路線精度.

1 方法與算法論述

1.1 方法

1.1.1K-means算法

K-means算法是MacQueen(1967)在Cox(1957)、Fisher(1958)、Sebestyen(1962)等人的研究基礎(chǔ)上提出的,k-means算法是一種較為簡單也最為常用的迭代聚類算法,迭代過程中不斷更新簇的聚類中心,每個(gè)簇的聚類中心用該簇中對(duì)象的平均值表示.經(jīng)過k-means算法得到的簇,相同簇中對(duì)象的相似度較高,不同簇中對(duì)象的相似度較低.GPS軌跡聚類的處理過程如下:

② 每次迭代將xi分配到最近的聚類中心,同時(shí)將所在的聚類簇選擇新的聚類中心點(diǎn).

③ 迭代達(dá)到以下收斂條件是終止.

對(duì)每個(gè)經(jīng)緯度樣本i,

如圖1為三次迭代中每次聚類中心點(diǎn)位置,圖1(a)中聚類中心點(diǎn)離樣本點(diǎn)平均距離未達(dá)到收斂,因此繼續(xù)迭代,圖1(b)中為第二次迭代聚類中心點(diǎn)位置,圖1(c)為三次迭代后,各聚類簇平均距離達(dá)到預(yù)設(shè)閾值,且所有數(shù)據(jù)單元都收斂迭代終止.

圖1 三次迭代聚類中心點(diǎn)位置

1.1.2改進(jìn)的Dijkstra算法

Dijkstra算法是典型的單源最短路徑算法,用于計(jì)算一個(gè)節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑.主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展,直到擴(kuò)展到終點(diǎn)為止.

Dijkstra算法是典型的單源最短路徑算法,用于計(jì)算一個(gè)節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑.主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展,直到擴(kuò)展到終點(diǎn)為止,按路徑長度遞增次序產(chǎn)生最短路徑算法.

Dijkstra算法不能計(jì)算中間線段截?cái)嗟那闆r,將軌跡點(diǎn)匹配到路網(wǎng)時(shí),通常情況下如果路段a與路段b相鄰,路段a的終點(diǎn)應(yīng)為路段b的起點(diǎn),進(jìn)而形成路網(wǎng)拓?fù)浣Y(jié)構(gòu),當(dāng)由于路網(wǎng)基礎(chǔ)信息缺失導(dǎo)致路段a與路段b未連接,且中間無其他任何路段信息,此時(shí)僅僅利

用Dijkstra算法不能解決問題.

改進(jìn)的算法偽代碼如下.

因此本文改進(jìn)Dijkstra算法,尋找路網(wǎng)拓?fù)涔?jié)點(diǎn)與尋找鄰近路段同時(shí)進(jìn)行,從起點(diǎn)找到終點(diǎn)完成路網(wǎng)匹配.

1.2 算法步驟

聚類后樣本點(diǎn)結(jié)合線路上下行起點(diǎn)和終點(diǎn),得出帶順序的軌跡點(diǎn),該軌跡點(diǎn)可初步作為線路軌跡,軌跡點(diǎn)匹配路網(wǎng),將距離和角度賦值不同的權(quán)重,選擇可信度最大的作為被匹配路段,最后根據(jù)改進(jìn)的Dijkstra算法,起點(diǎn)路段選擇鄰近路段,選擇依據(jù)是尋找有拓?fù)浣Y(jié)構(gòu)的所有相鄰路段計(jì)算距離,如果無相鄰路段,根據(jù)匹配路段與最近路段夾角和被匹配路段軌跡數(shù)二者結(jié)合起來,作為下一個(gè)路段選擇依據(jù).包括5個(gè)步驟.

步驟一.利用k-means,將同一個(gè)站點(diǎn)名稱對(duì)應(yīng)兩個(gè)以上不同經(jīng)緯度信息數(shù)據(jù)聚類,設(shè)置聚類半徑閾值a,超出閾值a范圍部分單獨(dú)聚類形成站點(diǎn),目的是線路基礎(chǔ)站點(diǎn)信息統(tǒng)一化.

步驟二.選擇各線路分方向一周GPS樣本數(shù)據(jù),利用k-means,設(shè)置聚類半徑閾值b和迭代次數(shù)閾值c,達(dá)到閾值b或者迭代次數(shù)達(dá)到迭代次數(shù)閾值c為迭代終止條件,得到聚類后數(shù)據(jù)集A

步驟三.根據(jù)起點(diǎn)找到數(shù)據(jù)集A中最近的點(diǎn),根據(jù)夾角和距離選擇鄰近軌跡點(diǎn),直到找到終點(diǎn)附近一定距離范圍結(jié)束.得到帶序號(hào)的軌跡點(diǎn)集B

步驟四.軌跡點(diǎn)匹配路段,如果投影到路段(且非路段延長線)距離超過距離設(shè)置范圍,軌跡點(diǎn)作為路段樣本集保留,得到候選路段集C

步驟五.用軌跡點(diǎn)起點(diǎn)從候選路段集C中匹配最近的路段作為線路起點(diǎn)路段,起點(diǎn)路段根據(jù)改進(jìn)Dijkstra算法尋找有拓?fù)浣Y(jié)構(gòu)的所有相鄰路段計(jì)算距離,如果無相鄰路段,根據(jù)匹配路段與最近路段夾角和被匹配路段軌跡數(shù)二者結(jié)合起來,作為下一個(gè)路段選擇依據(jù),直到被匹配到的路段在終點(diǎn)站附近一定范圍終止,最終得到帶順序的路段,即為路線軌跡.

2 實(shí)驗(yàn)分析

2.1 數(shù)據(jù)

2.1.1公交GPS數(shù)據(jù)

為了驗(yàn)證所提算法的有效性,以2017年1月份浙江省A市35條公交線路GPS數(shù)據(jù)為實(shí)驗(yàn)對(duì)象,正常情況下,每條線路每天數(shù)據(jù)量約3萬行,選擇一條線路一周GPS數(shù)據(jù),每輛車GPS數(shù)據(jù),與對(duì)應(yīng)線路站點(diǎn)起點(diǎn)和終點(diǎn)比對(duì)分離出線路上下行然后分方向清洗異常點(diǎn),得到帶方向的樣本數(shù)據(jù).

2.1.2線路基礎(chǔ)站點(diǎn)

線路基礎(chǔ)站點(diǎn)經(jīng)緯度信息是隨公交車采集,會(huì)存在多條線路同過一個(gè)站點(diǎn)但出現(xiàn)不同經(jīng)緯度情況,因此需要采用聚類方法,將多站點(diǎn)信息同一化,聚類后得到所有站點(diǎn)基礎(chǔ)信息為一個(gè)站點(diǎn)對(duì)應(yīng)一個(gè)經(jīng)緯度,上下行為兩個(gè)經(jīng)緯度.

2.1.3A市地圖數(shù)據(jù)

根據(jù)高德地圖底圖信息,地圖信息存在節(jié)點(diǎn)信息未顯示,利用arcgis處理后將道路以及路段中所有節(jié)點(diǎn)經(jīng)緯度信息全部導(dǎo)入到數(shù)據(jù)庫.

2.2 實(shí)驗(yàn)結(jié)果

基于GIS路網(wǎng)的公交路線軌跡算法,在各階段實(shí)驗(yàn)結(jié)果如圖2.以線路KI路上行方向?yàn)槔?公交gps樣本點(diǎn)聚類,初始聚類中心為上行方向31個(gè)站點(diǎn)經(jīng)緯度,聚類樣本為線路KI所有上行g(shù)ps點(diǎn);每次迭代將樣本gps點(diǎn)分配到最近的聚類中心,同時(shí)將所在的聚類簇重新選擇新的聚類中心點(diǎn),當(dāng)聚類簇c聚類中心為時(shí),重新計(jì)算聚類半徑ci,如果ci大于半徑閾值(此處設(shè)置為100米)則增加一個(gè)聚類中心,簇c內(nèi)部迭代尋找新的,以此類推,直到所有cilt;=100,為達(dá)到算法效率設(shè)置各簇內(nèi)迭代lt;=10次.最終聚類中心個(gè)數(shù)為166,結(jié)果如圖2(a),圖中166個(gè)聚類中心基本展現(xiàn)聚類后線路軌跡,此時(shí)聚類中心點(diǎn)為無序軌跡樣本點(diǎn),圖2(a)中能清晰看出中出現(xiàn)個(gè)別異常離散點(diǎn);根據(jù)點(diǎn)與左右鄰近點(diǎn)間形成的向量夾角angle,如果angle＞110.,去除點(diǎn),并根據(jù)鄰近距離原則將軌跡點(diǎn)排序,形成帶順序軌跡點(diǎn)結(jié)果如圖2(b),圖2(b)為arcgis地圖軟件打開的路網(wǎng)信息,然后在該基礎(chǔ)上導(dǎo)入帶順序軌跡點(diǎn),且相鄰軌跡點(diǎn)用直線連接后的效果圖,路網(wǎng)信息坐標(biāo)與軌跡點(diǎn)坐標(biāo)均為WGS84坐標(biāo),圖2(c)為圖2(b)放大后拐角效果圖,雖然路網(wǎng)信息坐標(biāo)與軌跡點(diǎn)坐標(biāo)均為WGS84坐標(biāo),但是疊加顯示時(shí)對(duì)比有明顯誤差,原因由于存在GPS數(shù)據(jù)本身會(huì)出現(xiàn)30-50米精度誤差,而且路網(wǎng)信息為道路中心線與公交車實(shí)際行走軌跡必然存在不重合情況,由圖2(c)可見在拐角處明顯出現(xiàn)偏離道路.因此需要與GIS底圖數(shù)據(jù)匹配,與底圖匹配根式(3):

圖2 基于GIS路網(wǎng)的公交路線軌跡算法各階段實(shí)驗(yàn)結(jié)果

對(duì)路段集Vertex v利用上文改進(jìn)的Dijkstra算法,從起點(diǎn)站點(diǎn)所在路段s尋找鄰近路段w,如果路段w與s連通,則直接用Dijkstra算法計(jì)算w的s到當(dāng)前點(diǎn)最短路徑長度cvw,如果未連通,計(jì)算路段s的e_v到所有路段s_v距離及夾角d(j),an(j)以及各路段集v可信度ppd,選擇可信度最大的路段為連通邊,然后對(duì)連通邊使用Dijkstra算法,經(jīng)過基于GIS路網(wǎng)的公交路線軌跡算法后,k1線路軌跡結(jié)果如圖2(e),圖2(e)為線路吸附道路軌跡,可見路網(wǎng)信息坐標(biāo)與軌跡點(diǎn)坐標(biāo)重合,未出現(xiàn)軌跡點(diǎn)偏移路網(wǎng)道路,圖2(f)為環(huán)線吸附道路軌跡效果圖,環(huán)線與非環(huán)線均能很好適應(yīng)該算法,實(shí)現(xiàn)軌跡點(diǎn)與路網(wǎng)信息完全匹配.

3 討論

首先聚類后樣本點(diǎn)結(jié)合線路上下行起點(diǎn)和終點(diǎn),得出帶順序的軌跡點(diǎn),該軌跡點(diǎn)可初步作為線路軌跡,當(dāng)然在拐角出現(xiàn)漂移軌跡情況,原因是聚類粒度導(dǎo)致,但是聚類過程中如果聚類粒度太小會(huì)導(dǎo)致軌跡離散點(diǎn)過多,清洗困難,且需要消耗機(jī)器大量內(nèi)存,浪費(fèi)資源.

其次在處理環(huán)線過程中將復(fù)雜問題簡單化,將環(huán)線根據(jù)站點(diǎn)信息從中間站點(diǎn)處截?cái)?上半部分為上行,下半部分為下行,能有效處理重復(fù)軌跡相反方向以及繞圈情況.

再次根據(jù)改進(jìn)Dijkstra算法尋找有拓?fù)浣Y(jié)構(gòu)的所有相鄰路段計(jì)算距離,如果無相鄰路段,根據(jù)匹配路段與最近路段夾角和被匹配路段軌跡數(shù)二者結(jié)合起來,作為下一個(gè)路段選擇依據(jù),該方法能解決路網(wǎng)信息丟失以及路段斷開情況.

4 結(jié)語

本文介紹了GPS軌跡聚類算法,在軌跡點(diǎn)、路段夾角和被匹配路段軌跡數(shù)信息數(shù)據(jù)基礎(chǔ)上結(jié)合改進(jìn)的Dijkstra算法,最終得到與路網(wǎng)匹配的線路軌跡數(shù)據(jù).在A市交通項(xiàng)目中取得較好效果,該算法結(jié)果是公交實(shí)時(shí)到站算法的基礎(chǔ),為后續(xù)公交相關(guān)算法提供完整的線路信息.

本文研究的線路適合在少量路網(wǎng)信息缺失情況下,可利用軌跡點(diǎn)完善路網(wǎng)信息,但如果出現(xiàn)大量基礎(chǔ)路網(wǎng)信息缺失,算法準(zhǔn)確率將降低,后續(xù)研究將利用所有線路軌跡點(diǎn)完善路網(wǎng)基礎(chǔ)信息.

1 李清泉,黃練.基于GPS軌跡數(shù)據(jù)的地圖匹配算法.測繪學(xué)報(bào),2010,39(2):207–212.

2 王祖超,袁曉如.軌跡數(shù)據(jù)可視分析研究.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),2015,(1):9–25.

3 李桃迎.交通領(lǐng)域中的聚類分析方法研究[博士學(xué)位論文].大連:大連海事大學(xué),2010.

4 董俊,黃傳河.改進(jìn)Dijkstra算法在GIS導(dǎo)航應(yīng)用中最短路徑搜索研究.計(jì)算機(jī)科學(xué),2012,39(10):245–247,257.[doi:10.3969/j.issn.1002-137X.2012.10.055]

5 姜波.一種基于GPS軌跡的路線規(guī)劃方法.軟件工程師,2012,(3):43–46.

6 周建武,楊彬.一種公交班次行駛軌跡精確計(jì)算算法的研究及應(yīng)用.計(jì)算機(jī)應(yīng)用與軟件,2014,31(8):100–103,117.

7 王佳,符卓,杜靖毅.基于遺傳算法的城市公交骨架線網(wǎng)優(yōu)化設(shè)計(jì).計(jì)算機(jī)應(yīng)用研究,2012,29(12):4518–4521.[doi:10.3969/j.issn.1001-3695.2012.12.030]

8 張扶桑,金蓓弘,汪兆洋,等.基于軌跡挖掘的公交車自組織網(wǎng)絡(luò)路由機(jī)制.計(jì)算機(jī)學(xué)報(bào),2015,38(3):648–662.

Algorithm of Bus Route Trajectory Based on GIS Road Network

ZHONG Hui-Ling,JIN Hong-Da,SHEN Jian-Hui,SHEN Bin,XU Meng
(Zhejiang Supcon Information Technology Co.Ltd.,Hangzhou 310052,China)

In order to solve the bus trail problem that bus route trajectory offset road network and GIS road network information is missing,especially on the rural roads,this paper proposes an algorithm of bus route trajectory based on GIS road networks.Firstly,it makes an in-depth analysis of bus GPS data,clustering line up and down track points respectively.Secondly,it cleans the track points and sort.Thirdly,it combines with GIS road network information for map matching.Finally,according to the improved Dijkstra algorithm,it solves the bus trail problem that GIS road network information is missing.The algorithm is applied in City A with 35 bus lines.The successful match rate is 85%.Unsuccessful matches are due to missing samples or wrong road network information.It can be seen that the algorithm has good accuracy and practicability.

Dijkstra algorithm;bus;GIS;map matching;trajectory offset

鐘會(huì)玲,金紅達(dá),沈建惠,沈斌,徐夢(mèng).基于GIS路網(wǎng)的公交路線軌跡算法.計(jì)算機(jī)系統(tǒng)應(yīng)用,2017,26(11):182–186.http://www.c-sa.org.cn/1003-3254/6054.html

浙江省科技計(jì)劃項(xiàng)目(2017C01016)

2017-02-23;修改時(shí)間:2017-03-09;采用時(shí)間:2017-03-20

?