基于地理格網(wǎng)的復(fù)雜路線車輛通行時間估算方法

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

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

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

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

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

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

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

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

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

(2) 濾波[11]。分別將軌跡數(shù)據(jù)坐標(biāo)值和運(yùn)動狀態(tài)作為輸入值進(jìn)行中值濾波，消除軌跡點(diǎn)噪聲及異常運(yùn)動狀態(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è)置時間閾值為30 min，當(dāng)一組軌跡點(diǎn)在連續(xù)超過30 min的時段內(nèi)State=1時，當(dāng)前該組連續(xù)狀態(tài)為1的軌跡點(diǎn)的中心點(diǎn)為靜止點(diǎn)，對軌跡進(jìn)行切分，產(chǎn)生新的軌跡段。用軌跡ID標(biāo)識切分后的軌跡段，軌跡ID的編碼方式為“車輛編號@軌跡段編號”。

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

1.2 模式庫構(gòu)建

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

2 模型及方法

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

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

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

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

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

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

2.2 通行時間估計

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

生成覆蓋研究區(qū)域和歷史時段的時空索引值檢索全部軌跡數(shù)據(jù)。以軌跡ID為單位按時間排序組織軌跡數(shù)據(jù)。地理格網(wǎng)將每一條軌跡劃分為一組軌跡段，Cell中的每一個軌跡段對應(yīng)模式庫中的一個路段模式。軌跡段時間維度以小時為單位進(jìn)行劃分。每個時段Cell中路段模式的通行時間由與該路段模式對應(yīng)的一組軌跡中對應(yīng)時段的數(shù)據(jù)綜合計算獲得。受出行特征影響，對工作日和休息日分別進(jìn)行計算。匹配Cell中軌跡段和路段模式的算法如下：①獲取當(dāng)前軌跡段Tri的最小外包矩形MBRTri；②檢索數(shù)據(jù)庫獲取當(dāng)前Cell中的全部路段模式，計算每個模式的最小外包矩形MBRPTj，若MBRTri≥MBRPTj，將該模式存入候選結(jié)果集合Cand1；③對Cand1中的路段模式作緩沖區(qū)Buffer，若Buffer包含當(dāng)前軌跡段，且長度差小于閾值，則將該模式存入候選結(jié)果集Cand2；④若Cand2為空，求取Cell中與當(dāng)前軌跡段最相似的路段模式為當(dāng)前軌跡段對應(yīng)的Pattern，否則求取Cand2中與當(dāng)前軌跡段最相似的路段模式作為當(dāng)前軌跡段對應(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中軌跡段和模式后，模式知識庫中每一條Pattern在特定的時隙均有一組軌跡作為其訓(xùn)練樣本。計算該組歷史軌跡在Cell中的停留時間，作為車輛穿過該P(yáng)attern所需的時間。無歷史軌跡經(jīng)過的路段采用限速計算其通行時間，標(biāo)識該路段的通行時間為理想狀態(tài)通行時間。本文上節(jié)中的索引具有實(shí)時性，能夠?qū)崿F(xiàn)模式知識庫通行時間的迅速寫入和更新。

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

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

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

(5)

(6)

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

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

表3 模型方法耗時

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

4 結(jié) 語

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