低采樣率浮動車的路況計算精度優(yōu)化

孫衛(wèi)真,邱皓月,向 勇,張 禹

1(首都師范大學(xué) 信息工程學(xué)院 計算機(jī)科學(xué)與技術(shù)系,北京 100048) 2(清華大學(xué) 計算機(jī)科學(xué)與技術(shù)系 網(wǎng)絡(luò)所,北京 100084) 3(北京理工大學(xué) 計算機(jī)學(xué)院,北京 100081)

1 引 言

近些年來隨著城市化進(jìn)程的推進(jìn)與智能交通系統(tǒng)(Intelligent Transportation Systems,ITS)的快速發(fā)展,對于路況精度的要求越來越高,城市的車輛導(dǎo)航、交通管理[1]等都需要路況計算來提供支持.目前國內(nèi)外路況計算的數(shù)據(jù)來源主要是固定探測器[2,3]和浮動車[4].浮動車相比于固定探測器,具有造價低、覆蓋范圍廣的優(yōu)勢,能夠提供精確的車輛定位和行駛信息[5],因此逐漸成為探測城市路況的重要數(shù)據(jù)來源.但由于數(shù)據(jù)采集能耗及傳輸成本原因,目前的車輛數(shù)據(jù)采樣間隔通常大于30秒,采樣率普遍較低[6],軌跡點(diǎn)的稀疏性導(dǎo)致同一輛車連續(xù)兩個軌跡點(diǎn)通常不在同一條道路上.與此同時城市路網(wǎng)越來越復(fù)雜,路口、立交橋的日益增多導(dǎo)致車輛在路口處的轉(zhuǎn)向時間消耗難以忽略.現(xiàn)有研究[7]表明車輛在路口消耗的時間占全部行駛時間的25%以上,這對交通數(shù)據(jù)分析也帶來了極大的挑戰(zhàn).

目前針對低采樣率導(dǎo)致軌跡點(diǎn)間路由增多的問題,解決方法主要是利用軌跡點(diǎn)的間平均速度[8]、歷史道路速度[9]等對道路速度進(jìn)行加權(quán)分配,但是沒有考慮路口的轉(zhuǎn)向時間消耗.而針對路網(wǎng)的復(fù)雜性,一些學(xué)者通過劃定統(tǒng)一的路口范圍[10,11],將車輛行駛時間劃分為道路行駛時間和路口轉(zhuǎn)向時間,但這種方法只考慮到了普通路口,在路況計算中對立交橋這種大型復(fù)雜路口的處理鮮有研究.Zhang[12]沒有劃定路口范圍,而是引入了虛擬的路口轉(zhuǎn)向時間,使用基于歷史路況的行程時間分配算法進(jìn)行路況探測,該方法有效的解決了低采樣率下普通路口的轉(zhuǎn)向時間計算問題.但當(dāng)車輛處于立交橋內(nèi)部時,不僅道路匹配存在較大的不確定性,而且立交橋內(nèi)部的一條道路被劃分成了多段道路和多個路口,路況的計算精度也會受到一定影響.因此在基于低采樣率數(shù)據(jù)的路況計算中,為了提高路況計算精度,既需要對立交橋進(jìn)行有效處理,也需要充分利用路口前后的車輛信息.

本文的工作概括如下:

1)將立交橋視為一個路口,利用北京市OpenStreetMap的數(shù)據(jù),對立交橋進(jìn)行了自動化定位,并劃定了其路口范圍.

2)充分利用路口前后的車輛信息來精確推導(dǎo)相關(guān)道路和路口路況,并與行程時間分配算法進(jìn)行了有效結(jié)合.

3)利用2.7萬輛以上的北京市出租車軌跡數(shù)據(jù)進(jìn)行了計算,結(jié)果表明路況計算優(yōu)化算法比行程時間分配算法整體提高了4.32%的路況精度.

2 相關(guān)工作

本文工作重心是提高低采樣率下的路況計算精度,因此道路速度、路口范圍劃分以及轉(zhuǎn)向時間的計算都與本文的工作相關(guān).

路況計算需要使用道路的平均速度,一些學(xué)者利用車輛的瞬時速度信息[13]進(jìn)行計算,比較典型的是以瞬時車速[14]和以車輛速度曲線中平滑路段的速度作為道路速度參考值[15],然而車輛的瞬時速度并不一定是穩(wěn)定和可靠的,尤其是在路口擁堵或受交通燈影響時會減速或等待一段時間,并且在真實(shí)場景中,浮動車數(shù)據(jù)采樣率較低,瞬時速度信息并不能代表道路速度.因此為了提高低采樣率數(shù)據(jù)下的路況計算精度,Fabritiis等人[8,16]使用軌跡點(diǎn)的平均速度作為路由上的道路速度參考值.Liu[9]使用歷史道路速度通過加權(quán)的方式計算浮動車在路由中每一條道路上的時間消耗,但他們的缺點(diǎn)在于沒有考慮車輛在路口的轉(zhuǎn)向時間消耗.

路口和立交橋是城市路網(wǎng)的重要組成部分,現(xiàn)有的工作大多是針對普通路口來劃定路口范圍,如[10,17]分別以距離路口中心100米和160米作為路口范圍.其缺點(diǎn)在于城市道路長度不一,將路口范圍設(shè)為統(tǒng)一值是不合適的.Yue[6]根據(jù)歷史的路口車輛等待長度和道路級別來設(shè)置路口范圍,但該道路模型假設(shè)兩軌跡點(diǎn)間只能跨越一個路口,局限性較大.Zhang[12]引入了虛擬的路口轉(zhuǎn)向時間,以<道路A,道路B,路口轉(zhuǎn)向時間>三元組的形式來描述路口轉(zhuǎn)向時間開銷,解決了連續(xù)兩個軌跡點(diǎn)跨越多個路口的情況.

目前學(xué)者們在路況計算中只考慮到了普通路口,但對于立交橋這種大型復(fù)雜的路口鮮有研究.而立交橋道路結(jié)構(gòu)復(fù)雜,內(nèi)部縱橫交錯,和普通路口存在較大差別,需要單獨(dú)區(qū)分.在路況計算中針對立交橋的研究需要涉及定位及路口范圍劃分問題,關(guān)于立交橋的定位研究,現(xiàn)有大多數(shù)的嘗試是基于幾何統(tǒng)計學(xué)相關(guān)的知識進(jìn)行提取,如基于改進(jìn)霍夫變換的城市立交橋檢測方法[18]和基于拓?fù)潢P(guān)系與道路分類的立交橋識別方法[19],但其缺點(diǎn)是需要依賴遙感系統(tǒng)和圖形庫.Ma[20]通過聚類算法對城市部分地區(qū)的復(fù)雜交叉口進(jìn)行了定位,但并沒有應(yīng)用于城市整體,且將立交橋的路口范圍劃分為圓形,包括了很多非立交區(qū)域的道路,對于形狀不規(guī)則的立交橋并不適用.因此在路況計算前,會將立交橋簡化抽象為一個路口,忽略其內(nèi)部細(xì)節(jié),對立交橋進(jìn)行自動化定位,并確定其路口范圍.

在考慮路口轉(zhuǎn)向時間的路況計算方面,現(xiàn)在已有不少研究,如基于路口下游路段浮動車數(shù)據(jù)[21]和基于模糊C均值聚類的方法[22]來估計路段行程時間.Yue[6]將道路劃分為平滑路段與路口路段,能夠?qū)⒁徊糠值缆仿窙r分離到路口.而Zhang[12]對于連續(xù)軌跡點(diǎn)之間的路由,先根據(jù)歷史路況得出道路和路口行駛時間的估計值并使用每個道路和路口上的時間開銷在該估計值中所占的比例作為權(quán)重,對真實(shí)的行駛時間進(jìn)行了加權(quán)分配.但以上文獻(xiàn)都沒有對立交橋進(jìn)行區(qū)分處理.

本文的最終目的是提高低采樣率車輛下的路況計算精度,因此普通路口和立交橋都會作為路口參與計算.我們將充分利用同一輛車通過路口前后的軌跡點(diǎn)信息來精確推導(dǎo)相關(guān)道路和路口路況,借鑒行程時間分配算法[12],根據(jù)路口前后軌跡點(diǎn)數(shù)目設(shè)置不同的影響因子來對道路行駛速度和路口轉(zhuǎn)向時間進(jìn)行計算和更新.

3 路況計算系統(tǒng)框架

圖1是路況計算系統(tǒng)框架,在路況計算前會對地圖數(shù)據(jù)進(jìn)行預(yù)處理,包括將雙向道路拆分成兩條單向道路和對立交橋的定位與路口范圍劃分,并存入到地圖數(shù)據(jù)庫中.該系統(tǒng)以低采樣率浮動車數(shù)據(jù)和地圖數(shù)據(jù)作為輸入,經(jīng)過道路匹配、路況計算后將路況更新到路況數(shù)據(jù)庫中.本文按車輛的真實(shí)發(fā)送時間差模擬了軌跡數(shù)據(jù)的發(fā)送并進(jìn)行處理.當(dāng)車輛軌跡數(shù)據(jù)到達(dá)時,首先經(jīng)過數(shù)據(jù)清洗去除錯誤和重復(fù)的軌跡點(diǎn),然后將車輛匹配到道路上.本文使用的道路匹配基于OHMM(Online Hidden Markov Model)地圖匹配[23]算法它基于變長滑動窗口的馬爾科夫匹配模型,考慮匹配點(diǎn)的上下文環(huán)境,計算每一個軌跡點(diǎn)所在的道路,并給出車輛從前一個軌跡點(diǎn)到當(dāng)前軌跡點(diǎn)的路由信息.

圖1 路況計算系統(tǒng)框架Fig.1 Framework of traffic situation calculation system

在路況計算階段,本文借鑒Zhang[12]的工作,提出了一種改進(jìn)的路況計算優(yōu)化方法.它基于路口前后軌跡點(diǎn)位置及數(shù)量精確計算了道路行駛速度和路口轉(zhuǎn)向時間,通過設(shè)置影響因子,與行程時間分配算法相結(jié)合來提高路況精度.生成的實(shí)時路況又會作為歷史數(shù)據(jù)參與到下一批次的路況計算中,具體細(xì)節(jié)將在第5節(jié)進(jìn)行說明.在路況匯總與更新階段,以5分鐘為一個時間片,將計算出的路況(道路速度和轉(zhuǎn)向時間信息)存儲到路況數(shù)據(jù)庫中.在此系統(tǒng)中本文的工作重點(diǎn)是立交橋定位、路口范圍劃分與提高路況計算精度.

4 立交橋的定位與路口范圍劃分

立交橋作為城市主干道的重要連接點(diǎn),在路況計算中需要考慮其對路況精度造成的影響.但其形態(tài)種類繁多,內(nèi)部縱橫交錯,分別對其建模將十分低效,因此本文將整個立交橋區(qū)域視作一個路口,在地圖中對其進(jìn)行自動化定位并確定路口范圍.然后將這些屬于立交橋路口范圍內(nèi)的道路與該立交橋進(jìn)行關(guān)聯(lián),存儲到地圖數(shù)據(jù)庫中,用于路況計算優(yōu)化.

4.1 利用聚類算法對立交橋進(jìn)行定位

OpenStreetMap的道路數(shù)據(jù)包括了道路級別信息,本文直接利用高等級道路(高速公路連接路和主干道連接路)這種自發(fā)地理信息的數(shù)據(jù),基于道路連接點(diǎn)的密度對立交橋進(jìn)行定位.考慮到以下幾個原因,本文決定選用DBSCAN(Density-Based Spatial Clustering of Applications with Noise)算法進(jìn)行聚類:

1)北京市立交橋的數(shù)量、形狀及位置分布在OpenStreetMap中是沒有標(biāo)注的,而DBSCAN算法不需要事先知道要形成的簇的數(shù)量,能夠自動確定聚類的個數(shù),并且可以構(gòu)成任意形狀的區(qū)域.

2)并不是所有的道路連接點(diǎn)都屬于某個立交橋區(qū)域,在OpenStreetMap中有大量道路連接點(diǎn)屬于噪聲點(diǎn),而DBSCAN根據(jù)密度可以很好地識別出這些噪聲點(diǎn).

4.1.1 DBSCAN簡介及算法改進(jìn)

DBSCAN算法是一種典型的基于密度的聚類算法,它將簇定義為密度相連的點(diǎn)的最大集合,能夠把具有足夠高密度的區(qū)域劃分為簇.其基本原理是通過檢查數(shù)據(jù)集中每個點(diǎn)的給定半徑Eps鄰域來搜索簇,如果點(diǎn)p的Eps鄰域包含的點(diǎn)多于最小包含點(diǎn)數(shù)MinPts,則創(chuàng)建一個以p為核心對象的簇;然后迭代地聚集從這些核心對象直接密度可達(dá)的對象,這個過程可能涉及一些密度可達(dá)簇的合并;當(dāng)沒有新的點(diǎn)添加到任何簇時,該過程結(jié)束.

在路況計算應(yīng)用中,為了對立交橋進(jìn)行定位,對DBSCAN算法做了以下改進(jìn):

1)為了提高聚類質(zhì)量,對直接聚類和合并聚類的半徑設(shè)置了不同的參數(shù).聚類半徑為所有點(diǎn)到核心點(diǎn)的空間距離閾值.如果半徑設(shè)置很大,則相鄰的密度較大的簇將有很大概率被合并為同一個簇,它們之間的差異將被忽略;如果半徑設(shè)置過小,則一個相對比較稀疏的簇可能被劃分為多個相似的簇.因此為了減少距離閾值造成的差異,對直接聚類半徑(eps1)和合并聚類半徑(eps2)分別進(jìn)行設(shè)置.

2)北京市的市中心區(qū)域與周邊區(qū)域的立交橋密度差異很大,而DBSCAN算法不適合反映密度變化較大的數(shù)據(jù)集,因此采取的辦法是將北京地圖分為兩部分:市中心區(qū)域和周邊區(qū)域.以不同的密度來對這兩類區(qū)域分別進(jìn)行聚類.如圖6,市中心區(qū)域在粗線邊框內(nèi)部,定義緯度區(qū)間為39.843到39.925,經(jīng)度區(qū)間為116.250到116.465.周邊區(qū)域則在其外部(粗線邊框與細(xì)線邊框之間),這樣劃分能夠很好地將市中心區(qū)域和周邊區(qū)域的不同密度的立交橋分開,同時又能避免對立交橋本身的切割.

4.1.2 去除線形噪聲區(qū)域

并不是所有的滿足密度條件的簇都能構(gòu)成立交橋,圖2所示的是六里橋與麗澤橋之間的西三環(huán)南路部分路段.在半徑范圍內(nèi)的道路連接點(diǎn)滿足了密度條件,但立交橋作為疏導(dǎo)交通的關(guān)鍵區(qū)域,是與多條方向各異的主干道相連接的,縱橫交錯,而不會是這種線形區(qū)域.

圖2 線形區(qū)域Fig.2 Linear area

為了排除滿足密度條件的條帶狀噪聲區(qū)域,需要對聚類起來的簇判斷形狀.具體做法是利用線性回歸對簇中所有道路連接點(diǎn)擬合出一條直線,如果這些點(diǎn)中最遠(yuǎn)的點(diǎn)到直線的距離小于一定距離,則取消此聚類.每一個簇中的點(diǎn)集被記作:{(lati,loni),i=1,2,…,n},其中l(wèi)ati代表坐標(biāo)點(diǎn)的緯度值,loni代表經(jīng)度值.在本文中線性回歸公式為

slope*lat-lon+intercept=0

(1)

其中slope代表擬合直線的斜率,intercept代表截距.線性回歸通常是根據(jù)各點(diǎn)與回歸直線的接近程度來判斷相關(guān)關(guān)系的強(qiáng)弱,當(dāng)各點(diǎn)很接近回歸直線時,兩變量的相關(guān)關(guān)系越強(qiáng),反映在地圖上則越接近為條帶狀區(qū)域.由于每個簇中點(diǎn)的數(shù)量不同,位置分布也不同,無法給所有簇定義一個統(tǒng)一的相近點(diǎn)數(shù)量來判斷是否是條帶狀區(qū)域.本文的解決辦法是計算簇中各點(diǎn)與回歸直線的距離d,若所有點(diǎn)到直線的距離都小于距離上限,則該簇為條帶狀區(qū)域,取消該簇的聚類.其中簇中某一個坐標(biāo)點(diǎn)(lati,loni)到回歸直線的距離d的計算公式為

(2)

經(jīng)過以上的聚類處理后,便可以有效確定立交橋的位置了.

4.2 立交橋路口范圍劃分

4.2.1 計算凸包

事實(shí)上,立交橋并非圓形,而是不規(guī)則的多邊形區(qū)域,因此需要進(jìn)一步計算立交橋的路口范圍,為此本文將利用Jarvis步進(jìn)法[25]來計算每一個簇中的坐標(biāo)點(diǎn)所組成的凸包.算法思路如下:

1)建立坐標(biāo)軸,X軸代表經(jīng)度軸,Y軸代表緯度軸.

2)緯度最大的前提下,盡量使經(jīng)度最小的點(diǎn),記為A點(diǎn).

3)以A點(diǎn)為起始點(diǎn),X軸正方向射線順時針掃描,找到旋轉(zhuǎn)角最小時掃描到的點(diǎn),記為B點(diǎn).

4)以B為起始點(diǎn),AB方向射線順時針掃描,找到旋轉(zhuǎn)角最小時掃描到的點(diǎn),記為C點(diǎn).

5)以此類推,直到找到起始點(diǎn)A.

4.2.2 路口范圍修正

只由聚類后的道路連接點(diǎn)組成的立交橋路口仍然存在范圍過小或過大的問題,需要進(jìn)行修正.

1)修正范圍過小的立交橋:道路連接點(diǎn)是道路的起點(diǎn)和終點(diǎn),它們的連線并不一定能完整地覆蓋整條道路,尤其是彎曲的道路.如圖3(a)顯示的公主墳區(qū)域,只有道路連接點(diǎn)的凸包算法并不能完整地覆蓋立交橋.OpenStreetMap數(shù)據(jù)庫中對于道路的劃分粒度已經(jīng)很細(xì),但通過對道路表中的the_geom字段進(jìn)行分析,發(fā)現(xiàn)道路標(biāo)識除了起點(diǎn)和終點(diǎn)以外,還包括道路中的折線點(diǎn).示例字段如下:(′LINESTRING(116.4645492 39.9530732,116.4645886 39.952977,116.4650889 39.9512556)′,).字段中除了起始點(diǎn)位置的坐標(biāo),其余坐標(biāo)均為折線點(diǎn).如圖3(b),加入折線點(diǎn)之后計算凸包,便可以解決道路連接點(diǎn)覆蓋范圍不全的問題.

(a) (b)

2)修正范圍過大的立交橋:有的道路連接點(diǎn)構(gòu)成的路口范圍明顯過大,為了將立交橋限制在一定范圍內(nèi),首先去掉了連接低等級道路的點(diǎn).然后計算了每個簇的質(zhì)心,并設(shè)置區(qū)域半徑限制為600米,刪除了距離質(zhì)心超過600米的點(diǎn).

5 路口計算精度優(yōu)化

在路況計算中,本文利用同一輛車通過路口前后的軌跡點(diǎn)信息來精確推導(dǎo)相關(guān)道路和路口的路況,通過與行程時間分配算法[12]相結(jié)合來進(jìn)行路況計算精度的優(yōu)化.行程時間分片算法將道路路口視作虛擬路口,根據(jù)歷史的道路行駛時間或轉(zhuǎn)向時間在歷史總時間中所占的比重,對真實(shí)的行駛時間進(jìn)行加權(quán)分配,得出當(dāng)前道路行程時間和道路轉(zhuǎn)向時間.該算法可以處理兩軌跡點(diǎn)間跨越多條道路的情況,將一部分道路路況分離到路口.

5.1 立交橋路況計算模型

行程時間分配算法對普通路口具有較大適用性.但由于立交橋的道路結(jié)構(gòu)復(fù)雜,車輛不僅在立交橋內(nèi)的道路匹配存在較大的不確定性,而且道路劃分粒度細(xì),將立交橋內(nèi)一條道路劃分成多段道路并設(shè)置多個路口是不合適的,會影響路況計算的精度.為了正確探測立交橋的路口路況,本文將立交橋抽象為一個路口,單獨(dú)計算立交橋各個方向的轉(zhuǎn)向時間.本文將立交橋轉(zhuǎn)向時間定義為車輛從進(jìn)入立交橋前到駛離立交橋后的時間差.

如圖4所示,多邊形區(qū)域代表立交橋,第4節(jié)中已經(jīng)劃定了路口范圍,并存儲了屬于立交橋的道路,需要注意的是立交橋的范圍實(shí)際上是不規(guī)則區(qū)域,而不是圓形區(qū)域.它連接了多個方向的道路,因此有多個不同的轉(zhuǎn)向時間.以圖4中從右向左行駛的車輛為例,真實(shí)行駛時間為TR1+TR1,R2+TR2,其中TRi代表車輛在道路Ri上的行駛時間,TR1,R2代表車輛經(jīng)過立交橋的轉(zhuǎn)向時間.這樣的道路模型可以忽略立交橋內(nèi)部復(fù)雜的道路細(xì)節(jié),只需計算立交橋外的道路速度,即可獲得轉(zhuǎn)向時間,并且還可以避免當(dāng)車輛處于立交橋內(nèi)部時引起的道路匹配錯誤,進(jìn)一步提高精度.以圖4為例,對于每一條車輛軌跡,記錄該車輛進(jìn)入立交橋前的連續(xù)兩個軌跡點(diǎn)和駛離立交橋后連續(xù)兩個軌跡點(diǎn).當(dāng)探測出車輛駛離立交橋后的第二個軌跡點(diǎn)時,開始計算立交橋的路況,需要注意的是,軌跡采樣率低,連續(xù)兩個軌跡點(diǎn)很少在同一條道路上,因此按以下兩種條件的道路速度來計算車輛在立交橋的轉(zhuǎn)向時間.

圖4 立交橋路況計算模型Fig.4 Calculation model of overpass traffic situation

1)如果立交橋外的一端有連續(xù)兩個軌跡點(diǎn),其所在的道路路由之間沒有紅綠燈,且不在其他立交橋內(nèi),則將兩個軌跡點(diǎn)之間經(jīng)過的道路連接成一條道路,并將兩軌跡點(diǎn)間道路間轉(zhuǎn)向時間置為0,并可由立交橋外軌跡點(diǎn)的位置及時間戳計算兩個軌跡點(diǎn)間的道路速度,兩個軌跡點(diǎn)之間經(jīng)過的道路被記作R1,…,Rn,軌跡點(diǎn)在所在道路的道路覆蓋率為fi,其長度記作LR1*fi+LR2+…+LRn*fi,時間間隔記作T,則兩軌跡點(diǎn)間所有道路速度VRi的計算公式為

(3)

2)如果不滿足1,則立交橋外的道路速度使用行程時間分配算法計算出的道路速度.

5.2 路口處的路況計算優(yōu)化

將復(fù)雜的立交橋抽象為一個路口后,便可以充分利用軌跡點(diǎn)經(jīng)過路口前后的信息來對路況計算進(jìn)行優(yōu)化了.需要注意的是,為了減少車輛異常緩慢行駛或?？康挠绊?行程時間分配算法引入了速度平滑影響因子α,使用歷史速度vpre對當(dāng)前探測速度進(jìn)行平滑.本文為了最大限度地探測出路口路況,根據(jù)路口前后的車輛數(shù)目分了4種場景進(jìn)行計算,如圖5所示,本文對不同場景下推導(dǎo)出的道路速度v,通過設(shè)置不同的影響因子α,按(4)來計算新的道路速度vnew.具體影響因子的設(shè)置見表1.

圖5 4種場景下的路況計算Fig.5 Calculation of road conditions under four scenarios

α=0.9-|seqcur-seqpre|*0.1
vnew=vpre*α+(1-α)*v

(4)

1)同一輛車在路口前后的道路上各有兩個軌跡點(diǎn),這時路口附近的的道路速度由前后道路上連續(xù)兩個軌跡點(diǎn)的位置及時間戳計算得出,此時以此路況為準(zhǔn),其可信度為100%,因此歷史路況影響因子為0.這種情況下的轉(zhuǎn)向時間的計算相當(dāng)精確,第6節(jié)對此場景下的立交橋路口路況進(jìn)行了驗(yàn)證.

2)同一輛車在路口前的道路上有一個軌跡點(diǎn),路口后的道路上有兩個軌跡點(diǎn),此時路口前的道路速度根據(jù)行程時間分配算法計算得出,其可信度為50%,路口后的道路速度仍舊由兩個連續(xù)的GPS點(diǎn)計算得出,其可信度為100%,因此轉(zhuǎn)向時間可信度為75%,設(shè)置歷史路況影響因子為0.25.

3)同一輛車在路口前的道路上有兩個軌跡點(diǎn),路口后的道路上有一個軌跡點(diǎn),此時路口后道路速度可信度為50%,路口前的道路速度的可信度為100%,因此轉(zhuǎn)向時間可信度為75%,設(shè)置歷史路況影響因子為0.25.

4)同一輛車連續(xù)兩個軌跡點(diǎn)間只跨越單個路口并且路口前后的道路只有一個軌跡點(diǎn)時的情況,利用行程時間分配算法在該時間片的道路速度,計算出路口的轉(zhuǎn)向時間,轉(zhuǎn)向時間可信度為50%,設(shè)置歷史路況影響因子置為0.5.

表1 4種場景
Table 1 Four scenarios

場景路況前后軌跡點(diǎn)數(shù)量路口前可信度路口后可信度轉(zhuǎn)向時間可信度歷史路況影響因子12-2100%100%100%022-150%100%75%0.2531-2100%50%75%0.2541-150%50%50%0.5

而對于同一輛車的相鄰軌跡點(diǎn)跨越多個路口的情況,仍舊按行程時間分配算法[12]進(jìn)行路況計算和更新.為了與行程時間分配算法相結(jié)合,本文還對立交橋的路口轉(zhuǎn)向時間進(jìn)行了處理,設(shè)置了立交橋內(nèi)的道路標(biāo)準(zhǔn)速度,然后將剩余的轉(zhuǎn)向時間平均分配到了立交橋內(nèi)的道路之間.由于本文融合了行程時間分配算法,歷史路況對當(dāng)前路況會產(chǎn)生影響,因此當(dāng)前時間片的路況也會對后續(xù)時間片的路況計算起到積極的修正作用.

6 評估與分析

這部分首先介紹了聚類算法的參數(shù)設(shè)置以及最終聚類的效果,然后通過處理北京市2.7萬輛出租車的軌跡數(shù)據(jù),驗(yàn)證了改進(jìn)的路況計算優(yōu)化方法的效果.實(shí)驗(yàn)使用的地圖數(shù)據(jù)來源于OpenStreetMap的北京市地圖.地圖區(qū)域的緯度區(qū)間為39.68～40.18,經(jīng)度區(qū)間為116.08～116.77,大約16400平方公里.

6.1 聚類算法的參數(shù)設(shè)置及最終聚類效果

DBSCAN算法對參數(shù)十分敏感,細(xì)微的不同都可能導(dǎo)致結(jié)果差別較大,而參數(shù)的選擇只能靠實(shí)驗(yàn)與觀察確定.改進(jìn)后的DBSCAN算法需要設(shè)置4個參數(shù),直接聚類半徑(eps1)、合并聚類半徑(eps2)、最小包含點(diǎn)數(shù)(minPts)、點(diǎn)到擬合直線的距離上限(dist).表2為市中心區(qū)域和周邊區(qū)域中各參數(shù)的設(shè)置.由表2可以看出市中心區(qū)域比周邊區(qū)域各項(xiàng)參數(shù)都要高,從而也印證了立交橋在不同區(qū)域的密度差異很大,對區(qū)域的劃分是必要的.

如圖6所示,本文將計算凸包的過程放在立交橋路口范圍修正之后,有效地定位了立交橋并劃定了路口范圍.

表2 聚類算法的參數(shù)設(shè)置
Table 2 Parameter setting of clustering algorithm

區(qū)域直接聚類半徑合并聚類半徑最小包含點(diǎn)數(shù)點(diǎn)到擬合直線的距離上限市中心20022080.0006周邊500500120.001

圖6 立交橋及其路口范圍Fig.6 Overpass and it′s intersection range

6.2 路況計算效果

6.2.1 立交橋局部路況計算效果

在立交橋路口前后各有兩點(diǎn)的條件下,本文對一天中經(jīng)過立交橋車輛進(jìn)行了隨機(jī)采樣,用車輛進(jìn)入立交橋前的最后一個軌跡點(diǎn)和駛離立交橋后的第一個軌跡點(diǎn)的時間差作為真實(shí)的行駛時間,對基于行程時間分配算法和路況優(yōu)化算法進(jìn)行了對比.結(jié)果如表3所示,在立交橋路口前后各有兩點(diǎn)這種

表3 局部行駛時間對比
Table 3 Comparison of local running time

采 樣真實(shí)時間(s)行程時間分配算法計算時間(s)路況計算優(yōu)化算法計算時間(s)a180215.58179.99b12249.76122.00c120107.65119.99d121100.85121.00e120127.43120.00f187149.84187.00

數(shù)據(jù)量最完整的情況下,路況計算優(yōu)化算法最為準(zhǔn)確,計算效果最好.

6.2.2 北京市路況計算優(yōu)化效果

為了計算探測出的路況精度,并且減少出租車異常行駛行為的影響,實(shí)驗(yàn)選取了北京市4月14日6:00～23:00行駛時間大于10分鐘且處于載客狀態(tài)的出租車進(jìn)行測試,共有27239條軌跡.本文將匹配后的軌跡中第一個點(diǎn)與最后一個點(diǎn)的時間差值作為真實(shí)的車輛行駛時間.然后分別計算了基于行程時間分配算法的估計時間和改進(jìn)的路況計算優(yōu)化算法的估計時間,并將估計時間與真實(shí)時間進(jìn)行比較,得出錯誤率(Error rate).錯誤率的計算方法來自于[12],計算公式為

(5)

由圖7可以看出,改進(jìn)的路況計算優(yōu)化算法在0%～15%錯誤率的數(shù)量上相比于行程時間分配算法有大幅增加,而在15%～100%錯誤率的數(shù)量比基于行程時間分配的數(shù)量則都要少.路況優(yōu)化算法比行程時間分配算法平均降低了4.32%的錯誤率,從16.56%降到了12.24%.其中經(jīng)過立交橋的車輛的錯誤率由16.02%降到了10.99%,這種情況占到了69.09%,即一天中大多數(shù)車輛的行駛路徑都會經(jīng)過立交橋.而車輛不經(jīng)過立交橋,只在普通道路行駛的錯誤率由17.76%降到了15.02%,因此也說明了將立交橋抽象為一個路口并進(jìn)行路況計算優(yōu)化的處理是必要的.

圖7 錯誤率柱狀圖Fig.7 Error rate histogram

表4顯示的是累積的錯誤率表,從表4中可以看出,路況優(yōu)化算法可以將51.51%的軌跡的路況錯誤率限制在10%以內(nèi),且99.06%的軌跡的路況錯誤率不超過50%.實(shí)驗(yàn)結(jié)果表明優(yōu)化算法有效提升了路況計算精度.本文還對錯誤率超過80%的車輛軌跡進(jìn)行了分析,其錯誤率較高的原因在于車輛的異常停止和部分軌跡點(diǎn)的道路匹配錯誤.

表4 累積錯誤率表
Table 4 Cumulative error rate table

錯誤率行程時間分配算法路況計算優(yōu)化算法10%40.17%51.51%20%68.82%81.19%30%84.58%93.38%40%92.87%97.68%50%96.63%99.06%

圖8 所有道路的平均速度Fig.8 Average speed of all roads

圖8顯示了所有道路的平均速度.本文認(rèn)為行程時間分配算法[12]存在系統(tǒng)性偏差,探測出的道路速度總體偏快,在使用改進(jìn)的路況計算優(yōu)化算法后,道路速度普遍降低.但道路速度曲線的變化趨勢是基本一致的,在早高峰和晚高峰時道路速度都會有所下降.

7 結(jié)束語

本文針對復(fù)雜城市道路場景下,以低采樣率車輛軌跡為數(shù)據(jù)來源的路況計算精度較差的問題,考慮到立交橋的影響,將立交橋抽象為一個路口,利用改進(jìn)的DBSCAN算法和Jarvis步進(jìn)法對其進(jìn)行了自動化定位和劃定其路口范圍.并充分利用到了路口前后的車輛位置信息,通過精確推導(dǎo)相關(guān)道路和路口的路況,設(shè)計了一種改進(jìn)的路況計算優(yōu)化算法,相比于行程時間分配算法,有效提高了路況計算精度.

在路況計算中使用平滑因子對異常低速行駛或臨時停車行為進(jìn)行了抑制,但當(dāng)?shù)缆飞先鄙僮銐虻能囕v數(shù)據(jù)時,系統(tǒng)就無法識別這兩種異常行為,路況計算精度會受到一定影響,因此本文還有可以進(jìn)一步改進(jìn)的地方.另外通過與高采樣率車輛計算出的路況數(shù)據(jù)相結(jié)合等也是提高路況計算精度的一個有效方法.