張亞茹，趙海濤，劉南杰，黃 波，李大鵬

(南京郵電大學(xué) 通信與信息工程學(xué)院，江蘇 南京 210003)

基于GPS數(shù)據(jù)的交通擁堵檢測

張亞茹，趙海濤，劉南杰，黃 波，李大鵬

(南京郵電大學(xué) 通信與信息工程學(xué)院，江蘇 南京 210003)

隨著交通擁堵問題的日益突出，如何有效檢測區(qū)域內(nèi)實(shí)時的交通狀態(tài)是城市交通發(fā)展中的研究熱點(diǎn)。為了實(shí)現(xiàn)對區(qū)域內(nèi)交通狀態(tài)進(jìn)行有效的檢測，提出了一種基于多源GPS數(shù)據(jù)交通擁堵的檢測方法。首先，剔除原始GPS數(shù)據(jù)中的異常數(shù)據(jù)并且對缺失的數(shù)據(jù)進(jìn)行修復(fù)，以保證GPS數(shù)據(jù)的合理性，對采集的原始GPS數(shù)據(jù)進(jìn)行了預(yù)處理；其次，在保證采集的交通信息完整性的基礎(chǔ)上，利用GPS數(shù)據(jù)的時空特性，使用k-means算法對GPS數(shù)據(jù)進(jìn)行聚類分析，實(shí)現(xiàn)了不同簇下的研究區(qū)域的劃分；最后，為獲取每個簇的實(shí)時交通狀態(tài)，采用了一種基于簇內(nèi)樣本數(shù)量進(jìn)行隨機(jī)抽樣的交通狀態(tài)檢測方法。仿真結(jié)果表明，所提算法可以實(shí)現(xiàn)對區(qū)域內(nèi)交通狀態(tài)的有效檢測且算法時效性得到了有效提升。

GPS；交通擁堵；預(yù)處理；k-means；抽樣

0 引 言

道路擁堵早已成為一個不容忽視的問題，尤其在大城市擁堵則更為嚴(yán)重。隨著人們生活水平的快速提高及城市化進(jìn)程的不斷推進(jìn)，城市機(jī)動車的數(shù)量隨之急劇增加，這與滯后的城市基礎(chǔ)設(shè)施建設(shè)和城市管理水平形成了劇烈的矛盾和沖突，導(dǎo)致道路擁堵問題日益頻繁與嚴(yán)重[1]。嚴(yán)重的道路擁堵問題會帶來很多的負(fù)面問題，比如增加燃料的消耗、浪費(fèi)出行人員的時間以及帶來的環(huán)境污染問題等，這些問題都會阻礙城市的發(fā)展，影響人們的日常生活。這些現(xiàn)象在一些大城市則更為突出，比如北京、上海以及廣州等地，每天都會因?yàn)閾矶聠栴}而帶來巨大的經(jīng)濟(jì)損失。因此，解決交通擁堵問題迫在眉睫。

如果人們在出行的過程中能夠及時了解前方道路的擁堵情況，那么出行者就可以選擇其他線路。這樣不僅可以有效緩解交通擁堵，而且還可以節(jié)約出行者的出行時間?，F(xiàn)在社會各界越來越注重對交通擁堵問題的研究，而且已經(jīng)提出了很多對道路擁堵情況進(jìn)行檢測的技術(shù)。文獻(xiàn)[2]介紹了智能實(shí)時路況系統(tǒng)建設(shè)過程中的關(guān)鍵技術(shù)。在之前對路況的信息采集技術(shù)主要有波頻檢測、磁頻檢測和視頻檢測等[3]。然而近年來GPS技術(shù)的迅速發(fā)展給交通擁堵檢測帶來了數(shù)據(jù)量龐大的時空數(shù)據(jù)。文中提出了一種基于GPS數(shù)據(jù)的擁堵檢測方法，通過預(yù)處理—聚類—抽樣來完成對道路擁堵的檢測，該方法過程簡單且具有一定的可行性。

1 數(shù)據(jù)預(yù)處理

要判斷一個道路是否擁堵，可以根據(jù)行駛在這條道路上的汽車的行駛數(shù)據(jù)來判斷。然而GPS數(shù)據(jù)的來源各式各樣，而人們所需要的只是行駛在道路上的汽車數(shù)據(jù)，所以要去除那些非行駛在道路上的汽車數(shù)據(jù)。2G和3G的發(fā)展促進(jìn)了GPS設(shè)備的發(fā)展，可以采集到大量的時空數(shù)據(jù)集[4]，而且采集到的數(shù)據(jù)中還會存在一些異常數(shù)據(jù)，對于這些數(shù)據(jù)要進(jìn)行一定的舍棄和修復(fù)工作。文獻(xiàn)[5]是基于GPS數(shù)據(jù)對高速公路的實(shí)時路況狀態(tài)進(jìn)行研究。

1.1 道路上車輛行駛信息的獲取

假設(shè)要獲取某路段上的道路擁堵情況，就要獲取該路段上車輛的行駛信息。地球上的每一個位置都有自己的經(jīng)緯度，同樣每一條道路也都有它自己的經(jīng)緯度范圍，而要獲取到這些信息也是輕而易舉的。同時獲取到的GPS數(shù)據(jù)Gi中包括GPS數(shù)據(jù)源所處位置的經(jīng)緯度。這樣可以把被檢測道路的經(jīng)緯度范圍看作是一個集合R，然后通過判斷所獲取的GPS的經(jīng)緯度是否屬于這個集合來判斷數(shù)據(jù)源是否來自于這條道路，以確保所獲得的GPS數(shù)據(jù)都屬于這條道路，保證最后結(jié)果的可靠性[6]。如果GPS的經(jīng)緯度包含于R，則保留該條數(shù)據(jù)，否則去除這條數(shù)據(jù)。

對于上面獲取的數(shù)據(jù)，還需要做進(jìn)一步地處理。因?yàn)镚PS數(shù)據(jù)來源于不同的設(shè)備，比如汽車、手機(jī)或者平板電腦等。假如當(dāng)GPS數(shù)據(jù)來自于路上行人的手機(jī)時，而這些人正處于追趕公交車的狀態(tài)，這時獲取的GPS數(shù)據(jù)會對最終的判斷結(jié)果有一定的影響。這是因?yàn)檫@些人的交通模式改變了，從起初的步行模式到后來的乘車模式，其中步行時期的數(shù)據(jù)會對擁堵判斷造成一定的誤差。那么如何來去除那些步行數(shù)據(jù)呢？首先需要根據(jù)獲取到的GPS數(shù)據(jù)得到每一個數(shù)據(jù)源的總體運(yùn)動軌跡C?？傮w來說，由于運(yùn)動模式的不同，獲得的運(yùn)動軌跡應(yīng)該是不連續(xù)且分段的。然后得到每一個軌跡的運(yùn)動區(qū)域，假如該區(qū)域在道路內(nèi)則保留，否則丟棄。最后再對上面保留的GPS數(shù)據(jù)日志進(jìn)行處理，若交通模式發(fā)生改變，則求出它的每一段軌跡的平均速度，若速度小于設(shè)定值T，則判別為步行。這樣就能去除其中的步行數(shù)據(jù)，使結(jié)果更準(zhǔn)確。

具體處理流程如圖1所示。

圖1 行駛在道路上的車輛信息的獲取

1.2 異常數(shù)據(jù)的處理

上面獲取的數(shù)據(jù)中可能會存在一些速度為負(fù)值的數(shù)據(jù)，很明顯這些數(shù)據(jù)肯定是錯誤的，這時就要把這些數(shù)據(jù)篩選出來，然后這些負(fù)值用0來代替。有時由于交通事故和天氣等突發(fā)性因素，采集到的車輛速度可能會偏離正常的速度范圍，因?yàn)楫惓?shù)據(jù)的存在在一定程度上會影響后面交通狀態(tài)的檢測精度，因此在數(shù)據(jù)的預(yù)處理過程中必須舍棄此類異常數(shù)據(jù)。

在數(shù)據(jù)的采集過程中經(jīng)常會出現(xiàn)數(shù)據(jù)丟失的現(xiàn)象，再加上對異常數(shù)據(jù)的丟棄，這些都導(dǎo)致了數(shù)據(jù)的不全面性，因此需要對缺失的數(shù)據(jù)進(jìn)行修復(fù)。文中采用權(quán)值平均方法，分別針對孤立的數(shù)據(jù)丟失和連續(xù)的數(shù)據(jù)丟失兩種情況進(jìn)行修復(fù)。具體公式[7]如下：

(1)

其中，wk為權(quán)值系數(shù)；W為所有權(quán)值系數(shù)之和；T為需要進(jìn)行數(shù)據(jù)修復(fù)的最大時間間隔。

式(1)對孤立的丟失數(shù)據(jù)xt的修復(fù)。值得注意的是，與數(shù)據(jù)修復(fù)點(diǎn)的時間相差越遠(yuǎn)，wk越小。連續(xù)丟失的數(shù)據(jù)可以通過如下的二次指數(shù)平滑法進(jìn)行修復(fù)：

(2)

其中，at和bt可以通過下式確定：

(3)

(4)

此外，可以通過交通信息的空間相似性改善數(shù)據(jù)修復(fù)的質(zhì)量。

2 聚類分析

很早就有對交通模式的研究。在1967年，文獻(xiàn)[8]就提出了對交通信號燈的系統(tǒng)控制。2002年，文獻(xiàn)[9]使用地圖劃分法將一個城市分為不同的集群來對用戶的位置進(jìn)行預(yù)測。文獻(xiàn)[10]使用機(jī)器學(xué)習(xí)方法來估計(jì)交通條件和速度模式?，F(xiàn)在在對數(shù)據(jù)的挖掘過程中提出了很多方法，而且學(xué)者們對這些方法都進(jìn)行了改進(jìn)。文獻(xiàn)[11-12]使用了聚類方法對交通狀態(tài)進(jìn)行檢測。聚類分析是數(shù)據(jù)挖掘中的一種重要方法，它可以把具有相同特征的事物聚為一個類，能夠更簡潔清晰地了解到整體的一個狀態(tài)。

為了簡單起見，這里以一段路段來進(jìn)行聚類分析。獲取的GPS中包括的參數(shù)有經(jīng)度L、緯度W、時間t和行駛速度v，則取向量G=(L,W,t,v)。以G為樣本，根據(jù)k-means算法，首先確定簇的個數(shù)k。但是k往往不好確定，這也是k-means算法的一個局限。然后隨機(jī)選取k個質(zhì)心，初始地代表一個簇，對于剩下的樣本則要根據(jù)它們與這些聚類中心的相似度，分別將它們分配給與其最相似的聚類[13]。再計(jì)算每個所獲得的新聚類的聚類中心(該聚類中所有對象的均值)，不斷重復(fù)這一過程，直至新的質(zhì)心與原質(zhì)心相等或小于指定閾值，則算法結(jié)束。k-means算法的最終結(jié)果是要使每個簇內(nèi)的元素盡量緊湊，簇之間要盡可能分開。這里也可以根據(jù)實(shí)際情況設(shè)定每個簇的大小，比如設(shè)定半徑值。該算法的一個缺點(diǎn)是對一些孤立點(diǎn)等臟數(shù)據(jù)比較敏感，因此一定要做好數(shù)據(jù)的預(yù)處理。某一時刻路段的聚類效果如圖2所示。使用算法的公式如下：

(5)

其中，k為簇的個數(shù)；Gi為一個GPS數(shù)據(jù)；R為道路的經(jīng)緯度集合；V為非質(zhì)心元素與質(zhì)心元素的距離。

圖2 聚類效果圖

3 擁堵等級判別

目前常用于衡量路段擁堵情況的參數(shù)主要有車流密度、路段平均速度。文中通過計(jì)算路段平均速度實(shí)現(xiàn)對交通擁堵等級的劃分。根據(jù)不同等級道路的平均速度，可以將道路的擁堵狀況分為3個等級:

(1)暢通：城市快速路和聯(lián)絡(luò)線平均速度高于50km/h，主干道平均交通速度大于20km/h；

(2)緩行：城市快速路和聯(lián)絡(luò)線平均速度高于20km/h、低于50km/h，主干道平均交通速度高于10km/h、低于20km/h；

(3)擁擠：城市快速路和聯(lián)絡(luò)線平均速度低于20km/h，主干道平均交通速度低于10km/h[14]。

以南京市內(nèi)的某一主干道路段進(jìn)行研究。如圖2所示，為了得到較精確的結(jié)果，首先獲取每個簇內(nèi)車輛的加權(quán)平均速度，然后把該速度作為衡量交通擁堵狀況的主要參數(shù)。由于城市道路網(wǎng)中車輛分布的不均勻性，因此道路上每個簇內(nèi)采集的樣本點(diǎn)分布也不均勻，即有的簇內(nèi)樣本點(diǎn)較少，有的則較多。對樣本點(diǎn)較少的簇，通過對簇內(nèi)所有樣本點(diǎn)求加權(quán)平均來表示該簇的速度；對樣本點(diǎn)較多的簇，通過隨機(jī)取樣的方法來獲取該簇的速度。因?yàn)橛纱氐亩x可知，同一個簇內(nèi)樣本點(diǎn)的相似度很高，因此可以認(rèn)為抽取的部分樣本能夠真實(shí)地反映整體水平。

若簇內(nèi)的樣本數(shù)量小于等于10，則對所有的樣本點(diǎn)速度加權(quán)求平均值；若簇內(nèi)樣本數(shù)量大于10且小于30，則應(yīng)隨機(jī)抽取樣本數(shù)量的80%來求得平均速度；若簇內(nèi)的樣本數(shù)量大于30且小于50，則應(yīng)隨機(jī)抽取樣本數(shù)量的75%進(jìn)行評估；若簇內(nèi)的樣本數(shù)量大于50，則應(yīng)隨機(jī)抽取樣本數(shù)量的70%進(jìn)行計(jì)算。從整個城市道路網(wǎng)的交通擁堵檢測的層次上來看，提出的基于簇內(nèi)樣本數(shù)量計(jì)算平均速度的方法，可以在保證檢測結(jié)果精度的前提下達(dá)到簡化計(jì)算的目的。

4 仿真分析

將獲取的GPS數(shù)據(jù)經(jīng)過預(yù)處理和聚類之后，再計(jì)算每個簇內(nèi)的平均速度，然后根據(jù)平均速度來判斷路段的擁堵情況。文中模擬了某一時刻道路通暢、緩行和擁堵的三種場景，而且對這三種場景進(jìn)行了仿真，如圖3所示。區(qū)域1中汽車平均速度大于20km/h，代表的是通暢，其中有兩個異常數(shù)據(jù)在預(yù)處理之后被丟棄；區(qū)域2中汽車平均速度大于10km/h且小于20km/h，代表的是緩行；區(qū)域3中汽車平均速度小于10km/h，表示的是擁堵。“*”表示每個簇的質(zhì)心，對應(yīng)的橫坐標(biāo)是其編號；折線表示的是處理后的平均速度。圖4為圖3對應(yīng)的速度折線圖，該圖可以較好地顯示道路的擁堵等級。

圖3 交通擁堵分布圖

圖4 車輛平均速度折線圖

5 結(jié)束語

在GPS技術(shù)快速發(fā)展和GPS數(shù)據(jù)廣泛應(yīng)用的基礎(chǔ)上，提出了一種基于多源GPS數(shù)據(jù)的道路擁堵檢測方法。由于道路交通的突發(fā)性和偶然性，采集的交通信息中存在一定的異常數(shù)據(jù)。為剔除其中的異常數(shù)據(jù)，提高城市道路擁塞區(qū)域的檢測精度，對采集的樣本數(shù)據(jù)進(jìn)行預(yù)處理。在保證數(shù)據(jù)完整性的基礎(chǔ)上，使用k-means算法對樣本數(shù)據(jù)進(jìn)行聚類。針對每個簇中的樣本數(shù)據(jù)，提出了一種基于簇內(nèi)樣本數(shù)量計(jì)算簇內(nèi)交通情況的方法，以獲取的簇內(nèi)平均速度作為衡量每個簇的交通狀況的主要參數(shù)。仿真結(jié)果表明，該方法可以準(zhǔn)確檢測交通的擁堵狀況。

[1] 林樹寬,于伶姿,喬建忠,等.基于GPS軌跡數(shù)據(jù)的擁堵路段的檢測[J].東北大學(xué)學(xué)報(bào)：自然科學(xué)版,2015,36(11):1530-1534.

[2] 吳 飛.智能實(shí)時路況系統(tǒng)的關(guān)鍵技術(shù)研究[J].測繪與空間地理信息,2013,36(8):95-97.

[3] 姚敏杰.基于車輛聯(lián)網(wǎng)的實(shí)時路況信息系統(tǒng)研究[D].杭州:浙江工業(yè)大學(xué),2012.

[4]WeiS,WynterL.Real-timeroadtrafficfusionandpredictionwithGPSandfixed-sensordata[C]//Internationalconferenceoninformationfusion.[s.l.]:[s.n.],2012:1468-1475.

[5] 周 洋.基于GPS浮動車的高速公路實(shí)時路況系統(tǒng)的研究[D].南昌：南昌航空大學(xué)，2012.

[6]GuptaA,ChoudharyS.DTC:aframeworktodetecttrafficcongestionbyminingversatileGPSdata[C]//Emergingtrendsandapplicationsincomputerscience.[s.l.]:[s.n.],2013:97-103.

[7]ZhangZ,YangD,ZhangT,etal.Astudyonthemethodforcleaningandrepairingtheprobevehicledata[J].IEEETransactionsonIntelligentTransportationSystems,2013,14(1):419-427.

[8]InoseH,FujisakiH,HamadaT.Theoryofroad-trafficcontrolbasedonmacroscopictrafficmodel[J].ElectronicsLetters,1967,3(8):385-386.

[9]AshbrookD.LearningsignificantlocationsandpredictingusermovementwithGPS[C]//Sixthinternationalsymposiumonwearablecomputers.[s.l.]:IEEE,2002:101-108.

[10]HoYH,WuYC,ChenMC,etal.GPSdatabasedurbanguidance[C]//Internationalconferenceonadvancesinsocialnetworksanalysisandmining.[s.l.]:IEEE,2011:703-708.

[11]AmeliaA,SaptawatiGAP.Detectionofpotentialtrafficjambasedontrafficcharacteristicdataanalysis[C]//Internationalconferenceondataandsoftwareengineering.[s.l.]:IEEE,2014:1-5.

[12] 劉瑤杰.基于實(shí)時路況的交通擁堵時空聚類分析[D].北京:首都師范大學(xué),2014.

[13] 魯小丫,宋志豪,徐 柱,等.利用實(shí)時路況數(shù)據(jù)聚類方法檢測城市交通擁堵點(diǎn)[J].地球信息科學(xué)學(xué)報(bào),2012,14(6):775-780.

[14] 賈 森.基于實(shí)時信息的城市道路交通狀態(tài)判別方法研究[D].北京:北京交通大學(xué),2007.

Detection of Traffic Congestion Based on GPS Data

ZHANG Ya-ru,ZHAO Hai-tao,LIU Nan-jie,HUANG Bo,LI Da-peng

(College of Telecommunications and Information Engineering,Nanjing University of Posts and Telecommunications,Nanjing 210003,China)

With traffic congestion becoming increasingly serious,how to effectively detect the real-time traffic status has become a research hotspot in the field of urban transportation.For effective detection of traffic area,a detection method based on multi-source GPS data is proposed.Firstly,in order to eliminate abnormal data and ensure the rationality of data,the method makes a preprocessing of GPS data to eliminate abnormal data and repair missing data.Secondly,on the basis of ensuring the integrity of data,the method usesk-means algorithm to cluster GPS data in accordance with the temporal-spatial characteristics of GPS data,and then divides the study area into different clusters.Finally,for obtaining the real-time traffic conditions of each cluster,a sampling algorithm based on the number of samples within each cluster is used to detect the traffic conditions.Simulation results show that the proposed algorithm with simple process can effectively detect the state of traffic within the region.

GPS;traffic congestion;preprocessing;k-means;sampling

2016-03-07

2016-06-16

時間：2017-01-04

國家自然科學(xué)基金資助項(xiàng)目(61302100；61471203)；教育部博士點(diǎn)基金(20133223120002)；江蘇省產(chǎn)學(xué)研項(xiàng)目(BY2015011-1)

張亞茹(1992-)，女，碩士研究生，研究方向?yàn)橐苿油ㄐ排c無線技術(shù)；趙海濤，博士，副教授，研究方向?yàn)檐嚶?lián)網(wǎng)資源優(yōu)化；劉南杰，博士，教授，研究方向?yàn)榉涸谕ㄐ拧④嚶?lián)網(wǎng)、智能交通；黃 波,博士，講師，研究方向?yàn)樾l(wèi)星通信與導(dǎo)航、信號處理。

http://www.cnki.net/kcms/detail/61.1450.TP.20170104.1028.042.html

TP

A

1673-629X(2017)01-0139-04

10.3969/j.issn.1673-629X.2017.01.031