基于GPS數據的交通擁堵檢測

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

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

基于GPS數據的交通擁堵檢測

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

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

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

GPS；交通擁堵；預處理；k-means；抽樣

0 引 言

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

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

1 數據預處理

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

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

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

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

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

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

1.2 異常數據的處理

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

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

(1)

其中，wk為權值系數；W為所有權值系數之和；T為需要進行數據修復的最大時間間隔。

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

(2)

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

(3)

(4)

此外，可以通過交通信息的空間相似性改善數據修復的質量。

2 聚類分析

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

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

(5)

其中，k為簇的個數；Gi為一個GPS數據；R為道路的經緯度集合；V為非質心元素與質心元素的距離。

圖2 聚類效果圖

3 擁堵等級判別

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

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

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

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

以南京市內的某一主干道路段進行研究。如圖2所示，為了得到較精確的結果，首先獲取每個簇內車輛的加權平均速度，然后把該速度作為衡量交通擁堵狀況的主要參數。由于城市道路網中車輛分布的不均勻性，因此道路上每個簇內采集的樣本點分布也不均勻，即有的簇內樣本點較少，有的則較多。對樣本點較少的簇，通過對簇內所有樣本點求加權平均來表示該簇的速度；對樣本點較多的簇，通過隨機取樣的方法來獲取該簇的速度。因為由簇的定義可知，同一個簇內樣本點的相似度很高，因此可以認為抽取的部分樣本能夠真實地反映整體水平。

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

4 仿真分析

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

圖3 交通擁堵分布圖

圖4 車輛平均速度折線圖

5 結束語

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

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

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

[3] 姚敏杰.基于車輛聯網的實時路況信息系統研究[D].杭州:浙江工業大學,2012.

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

[5] 周 洋.基于GPS浮動車的高速公路實時路況系統的研究[D].南昌：南昌航空大學，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] 劉瑤杰.基于實時路況的交通擁堵時空聚類分析[D].北京:首都師范大學,2014.

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

[14] 賈 森.基于實時信息的城市道路交通狀態判別方法研究[D].北京:北京交通大學,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

國家自然科學基金資助項目(61302100；61471203)；教育部博士點基金(20133223120002)；江蘇省產學研項目(BY2015011-1)

張亞茹(1992-)，女，碩士研究生，研究方向為移動通信與無線技術；趙海濤，博士，副教授，研究方向為車聯網資源優化；劉南杰，博士，教授，研究方向為泛在通信、車聯網、智能交通；黃 波,博士，講師，研究方向為衛星通信與導航、信號處理。

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