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

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

1 引 言

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

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

本文的工作概括如下:

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

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

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

2 相關(guān)工作

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

為了排除滿足密度條件的條帶狀噪聲區(qū)域,需要對(duì)聚類起來(lái)的簇判斷形狀.具體做法是利用線性回歸對(duì)簇中所有道路連接點(diǎn)擬合出一條直線,如果這些點(diǎn)中最遠(yuǎn)的點(diǎn)到直線的距離小于一定距離,則取消此聚類.每一個(gè)簇中的點(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)與回歸直線的接近程度來(lái)判斷相關(guān)關(guān)系的強(qiáng)弱,當(dāng)各點(diǎn)很接近回歸直線時(shí),兩變量的相關(guān)關(guān)系越強(qiáng),反映在地圖上則越接近為條帶狀區(qū)域.由于每個(gè)簇中點(diǎn)的數(shù)量不同,位置分布也不同,無(wú)法給所有簇定義一個(gè)統(tǒng)一的相近點(diǎn)數(shù)量來(lái)判斷是否是條帶狀區(qū)域.本文的解決辦法是計(jì)算簇中各點(diǎn)與回歸直線的距離d,若所有點(diǎn)到直線的距離都小于距離上限,則該簇為條帶狀區(qū)域,取消該簇的聚類.其中簇中某一個(gè)坐標(biāo)點(diǎn)(lati,loni)到回歸直線的距離d的計(jì)算公式為

(2)

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

4.2 立交橋路口范圍劃分

4.2.1 計(jì)算凸包

事實(shí)上,立交橋并非圓形,而是不規(guī)則的多邊形區(qū)域,因此需要進(jìn)一步計(jì)算立交橋的路口范圍,為此本文將利用Jarvis步進(jìn)法[25]來(lái)計(jì)算每一個(gè)簇中的坐標(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軸正方向射線順時(shí)針掃描,找到旋轉(zhuǎn)角最小時(shí)掃描到的點(diǎn),記為B點(diǎn).

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

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

4.2.2 路口范圍修正

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

1)修正范圍過(guò)小的立交橋:道路連接點(diǎn)是道路的起點(diǎn)和終點(diǎn),它們的連線并不一定能完整地覆蓋整條道路,尤其是彎曲的道路.如圖3(a)顯示的公主墳區(qū)域,只有道路連接點(diǎn)的凸包算法并不能完整地覆蓋立交橋.OpenStreetMap數(shù)據(jù)庫(kù)中對(duì)于道路的劃分粒度已經(jīng)很細(xì),但通過(guò)對(duì)道路表中的the_geom字段進(jìn)行分析,發(fā)現(xiàn)道路標(biāo)識(shí)除了起點(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)之后計(jì)算凸包,便可以解決道路連接點(diǎn)覆蓋范圍不全的問(wèn)題.

(a) (b)

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

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

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

5.1 立交橋路況計(jì)算模型

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

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

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

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

(3)

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

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

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

圖5 4種場(chǎng)景下的路況計(jì)算Fig.5 Calculation of road conditions under four scenarios

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

(4)

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

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

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

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

表1 4種場(chǎng)景
Table 1 Four scenarios

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

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

6 評(píng)估與分析

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

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

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

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

表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 路況計(jì)算效果

6.2.1 立交橋局部路況計(jì)算效果

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

表3 局部行駛時(shí)間對(duì)比
Table 3 Comparison of local running time

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

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

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

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

(5)

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

圖7 錯(cuò)誤率柱狀圖Fig.7 Error rate histogram

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

表4 累積錯(cuò)誤率表
Table 4 Cumulative error rate table

錯(cuò)誤率行程時(shí)間分配算法路況計(jì)算優(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)為行程時(shí)間分配算法[12]存在系統(tǒng)性偏差,探測(cè)出的道路速度總體偏快,在使用改進(jìn)的路況計(jì)算優(yōu)化算法后,道路速度普遍降低.但道路速度曲線的變化趨勢(shì)是基本一致的,在早高峰和晚高峰時(shí)道路速度都會(huì)有所下降.

7 結(jié)束語(yǔ)

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

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