武英豪，李成名，吳 政，武鵬達(dá)

(1. 聊城大學(xué)，山東 聊城 252000； 2. 中國(guó)測(cè)繪科學(xué)研究院，北京 100036)

通行時(shí)間隱含道路交通狀況信息，是居民出行關(guān)注的重要問(wèn)題。通行時(shí)間估計(jì)同時(shí)也被廣泛應(yīng)用于出行路線規(guī)劃、交通狀況監(jiān)控[1]、出行輔助決策、車(chē)輛調(diào)度[2]等各大基于位置的服務(wù)。浮動(dòng)車(chē)軌跡覆蓋范圍廣，可持續(xù)大量獲取，是交通狀態(tài)挖掘和通行時(shí)間估計(jì)的典型數(shù)據(jù)源[3-7]。

基于浮動(dòng)車(chē)歷史軌跡估計(jì)路徑通行時(shí)間，核心思想是用一組通過(guò)指定路徑的歷史軌跡的通行時(shí)間估計(jì)該路徑的通行時(shí)間。受數(shù)據(jù)時(shí)空分布特征影響，在指定時(shí)隙和路徑通常很難找到一組完整的歷史軌跡，因此需要對(duì)路徑進(jìn)行剖分?，F(xiàn)有研究包括兩種典型方法：基于路網(wǎng)節(jié)點(diǎn)劃分和基于規(guī)則格網(wǎng)劃分。文獻(xiàn)[8]基于支持向量回歸模型，通過(guò)統(tǒng)計(jì)歷史時(shí)段車(chē)輛穿過(guò)道路兩端所用時(shí)間估計(jì)了路徑通行時(shí)間。文獻(xiàn)[9]采用規(guī)則格網(wǎng)劃分地理空間，基于稀疏軌跡結(jié)合POI興趣點(diǎn)、天氣狀況等信息，通過(guò)動(dòng)態(tài)規(guī)劃尋找最佳級(jí)聯(lián)和構(gòu)建三階張量模型估計(jì)了路徑通行時(shí)間[9]。然而這些研究并未考慮海量數(shù)據(jù)的高效管理，算法完成多在本地計(jì)算機(jī)實(shí)現(xiàn)，雖然規(guī)則格網(wǎng)劃分較路網(wǎng)節(jié)點(diǎn)劃分具有更高的計(jì)算效率，但軌跡數(shù)據(jù)量巨大時(shí)計(jì)算機(jī)計(jì)算過(guò)程仍具有較大壓力。

本文從軌跡數(shù)據(jù)和相關(guān)基礎(chǔ)數(shù)據(jù)高效一體化管理的角度研究路徑通行時(shí)間，依托于Apache平臺(tái)Cassandra數(shù)據(jù)庫(kù)設(shè)計(jì)數(shù)據(jù)索引策略和高效檢索算法，利用分布式數(shù)據(jù)庫(kù)存儲(chǔ)及索引策略降低通行時(shí)間估計(jì)的計(jì)算壓力；基于Google S2[10]索引格網(wǎng)單元?jiǎng)澐周壽E段和路段，挖掘歷史軌跡在Cell中的停留時(shí)間，構(gòu)建模式知識(shí)庫(kù)；將復(fù)雜路線分解為一組路段模式，利用歷史時(shí)隙相似路段模式估計(jì)車(chē)輛通行時(shí)間。

1 數(shù)據(jù)清洗及模式庫(kù)構(gòu)建

1.1 軌跡數(shù)據(jù)清洗

軌跡數(shù)據(jù)清洗包括以下3部分：

(1) 異常點(diǎn)及運(yùn)動(dòng)狀態(tài)提取。設(shè)置時(shí)間閾值φT為軌跡最大采樣間隔，當(dāng)前軌跡點(diǎn)與前一點(diǎn)時(shí)間間隔為Δt、空間距離為Δs，空間閾值φS=120Δt。當(dāng)Δt>φT時(shí)，當(dāng)前軌跡點(diǎn)作為新的軌跡段的起點(diǎn)；當(dāng)Δt≤φT且Δs>φS時(shí)，該點(diǎn)作為異常點(diǎn)剔除。當(dāng)Δs<5 m時(shí)，軌跡運(yùn)動(dòng)狀態(tài)為靜止，標(biāo)記State=1；否則，標(biāo)記State=0。

(2) 濾波[11]。分別將軌跡數(shù)據(jù)坐標(biāo)值和運(yùn)動(dòng)狀態(tài)作為輸入值進(jìn)行中值濾波，消除軌跡點(diǎn)噪聲及異常運(yùn)動(dòng)狀態(tài)判斷。設(shè)置窗口大小m=5，將窗口內(nèi)中心點(diǎn)的值Yi用窗口內(nèi)各點(diǎn)的中值代替。

Yi=Med{fi-v,…,fi-1,fi,fi+1,…,fi+v}

(1)

式中,i∈N；v=(m-1)/2。

設(shè)置時(shí)間閾值為30 min，當(dāng)一組軌跡點(diǎn)在連續(xù)超過(guò)30 min的時(shí)段內(nèi)State=1時(shí)，當(dāng)前該組連續(xù)狀態(tài)為1的軌跡點(diǎn)的中心點(diǎn)為靜止點(diǎn)，對(duì)軌跡進(jìn)行切分，產(chǎn)生新的軌跡段。用軌跡ID標(biāo)識(shí)切分后的軌跡段，軌跡ID的編碼方式為“車(chē)輛編號(hào)@軌跡段編號(hào)”。

(3) 地圖匹配。采用隱馬爾可夫模型[12-13]實(shí)現(xiàn)地圖匹配，獲取軌跡點(diǎn)對(duì)應(yīng)的路段。

1.2 模式庫(kù)構(gòu)建

基于Google S2索引生成的地理格網(wǎng)對(duì)路網(wǎng)進(jìn)行分割，單個(gè)Cell中的路網(wǎng)拓?fù)渲貥?gòu)后獲得Cell所對(duì)應(yīng)的路段模式(Pattern)。以Cell為單位編碼組織路段模式，構(gòu)建模式知識(shí)庫(kù)。知識(shí)庫(kù)中每條路段模式的歷史通行時(shí)間由一系列歷史軌跡綜合計(jì)算獲得。圖1為空間索引編碼為“35f198f”的Cell中的全部路段模式示例(部分路段為單行道)。

2 模型及方法

本文通行時(shí)間估計(jì)模型的關(guān)鍵為時(shí)空索引構(gòu)建和基于索引的軌跡及路網(wǎng)劃分，模型如圖2所示。

2.1 時(shí)空索引構(gòu)建

非關(guān)系型Cassandra數(shù)據(jù)庫(kù)具有較快的讀寫(xiě)性能，能夠高效管理復(fù)雜的高動(dòng)態(tài)高實(shí)時(shí)軌跡數(shù)據(jù)。其P2P去中心化架構(gòu)及一致性Hash環(huán)保證了數(shù)據(jù)的安全性、最終一致性和負(fù)載均衡性。Cassandra數(shù)據(jù)庫(kù)為Key-Value數(shù)據(jù)庫(kù)，由分區(qū)鍵和排序鍵組成Row Key，通過(guò)Hash值確定要素在分布式Hash環(huán)中存儲(chǔ)的位置，具有相同分區(qū)鍵的數(shù)據(jù)存儲(chǔ)在同一個(gè)節(jié)點(diǎn)上[14-15]，工作原理如圖3所示。本文采用時(shí)空劃分的方式通過(guò)設(shè)計(jì)分區(qū)鍵和排序鍵構(gòu)建時(shí)空索引。

軌跡和路網(wǎng)數(shù)據(jù)空間劃分采用Google S2索引，該索引提供了一種分級(jí)的全球格網(wǎng)劃分和編碼方案。采用S2算法對(duì)軌跡數(shù)據(jù)和路網(wǎng)數(shù)據(jù)進(jìn)行編碼，采用12級(jí)地理格網(wǎng)編碼索引軌跡數(shù)據(jù)，14級(jí)地理格網(wǎng)編碼索引路網(wǎng)數(shù)據(jù)。12級(jí)的地理格網(wǎng)面積約為5.07 km2，索引次數(shù)引發(fā)的時(shí)間復(fù)雜度和去除冗余查詢結(jié)果產(chǎn)生的時(shí)間消耗相對(duì)平衡，具有較好的查詢性能。14級(jí)地理格網(wǎng)覆蓋面積約為0.32 km2，格網(wǎng)內(nèi)路網(wǎng)結(jié)構(gòu)簡(jiǎn)單，軌跡分布適中，能夠減少不確定性因素，保證通行時(shí)間估計(jì)的效率及準(zhǔn)確性。圖4為分級(jí)格網(wǎng)索引示意圖。軌跡數(shù)據(jù)存儲(chǔ)表結(jié)構(gòu)見(jiàn)表1。數(shù)據(jù)時(shí)間以1 h為間隔進(jìn)行劃分，組合空間和時(shí)間編碼為分區(qū)鍵。將清洗和路網(wǎng)匹配后的軌跡數(shù)據(jù)按表1的結(jié)構(gòu)構(gòu)建索引存儲(chǔ)。模式知識(shí)庫(kù)存儲(chǔ)結(jié)構(gòu)見(jiàn)表2。

表1 軌跡數(shù)據(jù)存儲(chǔ)表結(jié)構(gòu)

表2 路段模式數(shù)據(jù)存儲(chǔ)表結(jié)構(gòu)

2.2 通行時(shí)間估計(jì)

通行時(shí)間估計(jì)算法通過(guò)計(jì)算歷史通行時(shí)間完善路徑模式知識(shí)庫(kù)，利用知識(shí)庫(kù)實(shí)現(xiàn)任意時(shí)段任意路徑的通行時(shí)間估計(jì)。

生成覆蓋研究區(qū)域和歷史時(shí)段的時(shí)空索引值檢索全部軌跡數(shù)據(jù)。以軌跡ID為單位按時(shí)間排序組織軌跡數(shù)據(jù)。地理格網(wǎng)將每一條軌跡劃分為一組軌跡段，Cell中的每一個(gè)軌跡段對(duì)應(yīng)模式庫(kù)中的一個(gè)路段模式。軌跡段時(shí)間維度以小時(shí)為單位進(jìn)行劃分。每個(gè)時(shí)段Cell中路段模式的通行時(shí)間由與該路段模式對(duì)應(yīng)的一組軌跡中對(duì)應(yīng)時(shí)段的數(shù)據(jù)綜合計(jì)算獲得。受出行特征影響，對(duì)工作日和休息日分別進(jìn)行計(jì)算。匹配Cell中軌跡段和路段模式的算法如下：①獲取當(dāng)前軌跡段Tri的最小外包矩形MBRTri；②檢索數(shù)據(jù)庫(kù)獲取當(dāng)前Cell中的全部路段模式，計(jì)算每個(gè)模式的最小外包矩形MBRPTj，若MBRTri≥MBRPTj，將該模式存入候選結(jié)果集合Cand1；③對(duì)Cand1中的路段模式作緩沖區(qū)Buffer，若Buffer包含當(dāng)前軌跡段，且長(zhǎng)度差小于閾值，則將該模式存入候選結(jié)果集Cand2；④若Cand2為空，求取Cell中與當(dāng)前軌跡段最相似的路段模式為當(dāng)前軌跡段對(duì)應(yīng)的Pattern，否則求取Cand2中與當(dāng)前軌跡段最相似的路段模式作為當(dāng)前軌跡段對(duì)應(yīng)的Pattern。定義軌跡和路段模式的相似距離函數(shù)如下

DTri,PTj=∑p∈Tridmin(p,PTj)

(2)

dmin(p,PTj)=min{d(p,S)}S∈PTj

(3)

(4)

式中，p為軌跡Tri上的軌跡點(diǎn)；PTj為Cell中的一條路段模式；dmin(p,PTj)為軌跡段Tri上的軌跡點(diǎn)p與某一路段模式PTj的最短距離。PTj由一組直線段S組成，a、b表示S的端點(diǎn)，點(diǎn)c為軌跡點(diǎn)p在直線段S上的投影。軌跡段和模式的相似距離DTri,PTj為軌跡段上全部軌跡點(diǎn)與PTj的最短距離和，其值越小相似性越高。

匹配Cell中軌跡段和模式后，模式知識(shí)庫(kù)中每一條Pattern在特定的時(shí)隙均有一組軌跡作為其訓(xùn)練樣本。計(jì)算該組歷史軌跡在Cell中的停留時(shí)間，作為車(chē)輛穿過(guò)該P(yáng)attern所需的時(shí)間。無(wú)歷史軌跡經(jīng)過(guò)的路段采用限速計(jì)算其通行時(shí)間，標(biāo)識(shí)該路段的通行時(shí)間為理想狀態(tài)通行時(shí)間。本文上節(jié)中的索引具有實(shí)時(shí)性，能夠?qū)崿F(xiàn)模式知識(shí)庫(kù)通行時(shí)間的迅速寫(xiě)入和更新。

由模式知識(shí)庫(kù)中模式的通行時(shí)間估計(jì)車(chē)輛從某一時(shí)刻起通過(guò)指定路徑R所需的時(shí)間算法如下：①生成覆蓋路徑R的地理格網(wǎng)編碼和時(shí)隙編碼集合；②地理格網(wǎng)將R劃分為一組落在Cell中的路段，每條路段對(duì)應(yīng)一條Pattern，如圖5兩點(diǎn)之間路徑R為一組路段Pattern的集合，R={Pattern1,Pattern2,…,Patternn}，路徑R的預(yù)測(cè)通行時(shí)間為集合中全部Pattern通行時(shí)間之和；③組合空間編碼和時(shí)間編碼為分區(qū)鍵，檢索知識(shí)庫(kù)；④搜索知識(shí)庫(kù)中歷史同時(shí)隙與Patterni對(duì)應(yīng)的路段模式，獲取歷史通行時(shí)間；⑤若Patterni在歷史同時(shí)段無(wú)車(chē)輛通過(guò)，搜索當(dāng)前Cell中道路等級(jí)與當(dāng)前路段相似的距離最近的路段模式；⑥若仍無(wú)歷史軌跡通過(guò)，以理想狀態(tài)計(jì)算。

3 試驗(yàn)與結(jié)果分析

采用北京市10 000輛出租車(chē)一周內(nèi)采集的約1500萬(wàn)個(gè)軌跡點(diǎn)及OpenStreetMap開(kāi)源的路網(wǎng)數(shù)據(jù)完成試驗(yàn)。清洗和匹配全部軌跡數(shù)據(jù)，篩選出采樣間隔小于等于30 s、時(shí)間跨度在周一至周五內(nèi)的車(chē)輛軌跡，按照上文的索引策略入庫(kù)。分割重構(gòu)路網(wǎng)數(shù)據(jù)構(gòu)建模式知識(shí)庫(kù)。選擇周一至周四4 d的歷史軌跡作為計(jì)算模式知識(shí)庫(kù)中每一個(gè)模式在1 d 24個(gè)時(shí)段各自通行時(shí)間的樣本。使用周五的軌跡數(shù)據(jù)驗(yàn)證通行時(shí)間估計(jì)結(jié)果的準(zhǔn)確性。

(5)

(6)

隨機(jī)抽取100條不同時(shí)段不同長(zhǎng)度的軌跡段，將軌跡的起始時(shí)刻作為時(shí)間估計(jì)的起始時(shí)刻，軌跡經(jīng)過(guò)的路徑作為時(shí)間估計(jì)的路徑，軌跡的實(shí)際通行時(shí)間作為真實(shí)值與估計(jì)結(jié)果對(duì)照，計(jì)算MAE和MRE。圖6(a)和圖6(b)為軌跡起始時(shí)刻落在7～17 h之間的不同時(shí)段時(shí)估計(jì)結(jié)果的MAE和MRE。結(jié)果顯示，路徑通行時(shí)間估計(jì)的整體平均絕對(duì)誤差在10 min左右，非高峰時(shí)段誤差相對(duì)較小，高峰時(shí)段受交通狀況不確定性影響誤差增大；平均相對(duì)誤差趨近0.20，具有一定的整體精度。圖6(c)和圖6(d)隨著估計(jì)路徑數(shù)量的增加，MAE和MRE穩(wěn)定在10 min和0.20。隨機(jī)抽取平均長(zhǎng)度分別為7.5、15、30和60 km的4組軌跡，每組50條，估計(jì)通行時(shí)間并計(jì)算MAE和MRE。圖6(e)和圖6(f)隨著路徑長(zhǎng)度的增大，MAE小幅度增加但仍穩(wěn)定在10 min左右，MRE大幅度減小。因此，對(duì)于較長(zhǎng)的復(fù)雜路線，本文方法具有較高的估計(jì)精度。

表3統(tǒng)計(jì)了本文通行時(shí)間估計(jì)模型的方法耗時(shí)。利用10 000輛出租車(chē)周一至周四的歷史軌跡構(gòu)建知識(shí)庫(kù)的所需時(shí)間為13.68 min。隨著路徑長(zhǎng)度的增加，需要從知識(shí)庫(kù)中檢索的路段模式也增加，估計(jì)通行時(shí)間的耗時(shí)小幅度增加。長(zhǎng)度在30 km內(nèi)的路徑，通行時(shí)間估計(jì)平均耗時(shí)穩(wěn)定在3 s內(nèi)。因此，對(duì)估算較長(zhǎng)路徑上車(chē)輛的通行時(shí)間，本文方法具有較高的估算效率。

表3 模型方法耗時(shí)

通行時(shí)間估計(jì)結(jié)果準(zhǔn)確性評(píng)估及方法效率評(píng)估表明：空間維度引入地理格網(wǎng)、組合空間和時(shí)間信息構(gòu)建時(shí)空復(fù)合索引，能夠減輕海量歷史軌跡的管理和計(jì)算壓力；地理格網(wǎng)劃分軌跡和路網(wǎng)，將全局通行狀況的挖掘轉(zhuǎn)換為局部狀況的分析和累積，能夠最大化地挖掘歷史軌跡的通行狀況，提高較長(zhǎng)路徑車(chē)輛通行時(shí)間估計(jì)的準(zhǔn)確性和效率。

4 結(jié) 語(yǔ)

本文提出了一種基于地理格網(wǎng)的復(fù)雜路線車(chē)輛通行時(shí)間估計(jì)方法，利用地理格網(wǎng)劃分歷史軌跡和路網(wǎng)挖掘歷史交通狀態(tài)，較好地完成了指定路徑車(chē)輛通行時(shí)間估計(jì)，通過(guò)索引構(gòu)建和相似軌跡搜索算法提高了數(shù)據(jù)檢索效率。時(shí)間估計(jì)模型依托于軌跡數(shù)據(jù)和基礎(chǔ)數(shù)據(jù)的高效一體化管理，減輕了計(jì)算機(jī)計(jì)算壓力。此外，路徑通行時(shí)間通常受各種復(fù)雜因素的影響，今后的研究將綜合考慮各種不確定性因素，完善本文提出的通行時(shí)間估計(jì)模型，在軌跡數(shù)據(jù)高效管理的基礎(chǔ)上挖掘數(shù)據(jù)的其他價(jià)值。