基于地理格網的復雜路線車輛通行時間估算方法

武英豪，李成名，吳 政，武鵬達

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

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

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

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

1 數據清洗及模式庫構建

1.1 軌跡數據清洗

軌跡數據清洗包括以下3部分：

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

(2) 濾波[11]。分別將軌跡數據坐標值和運動狀態作為輸入值進行中值濾波，消除軌跡點噪聲及異常運動狀態判斷。設置窗口大小m=5，將窗口內中心點的值Yi用窗口內各點的中值代替。

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

(1)

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

設置時間閾值為30 min，當一組軌跡點在連續超過30 min的時段內State=1時，當前該組連續狀態為1的軌跡點的中心點為靜止點，對軌跡進行切分，產生新的軌跡段。用軌跡ID標識切分后的軌跡段，軌跡ID的編碼方式為“車輛編號@軌跡段編號”。

(3) 地圖匹配。采用隱馬爾可夫模型[12-13]實現地圖匹配，獲取軌跡點對應的路段。

1.2 模式庫構建

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

2 模型及方法

本文通行時間估計模型的關鍵為時空索引構建和基于索引的軌跡及路網劃分，模型如圖2所示。

2.1 時空索引構建

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

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

表1 軌跡數據存儲表結構

表2 路段模式數據存儲表結構

2.2 通行時間估計

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

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

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

(2)

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

(3)

(4)

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

匹配Cell中軌跡段和模式后，模式知識庫中每一條Pattern在特定的時隙均有一組軌跡作為其訓練樣本。計算該組歷史軌跡在Cell中的停留時間，作為車輛穿過該Pattern所需的時間。無歷史軌跡經過的路段采用限速計算其通行時間，標識該路段的通行時間為理想狀態通行時間。本文上節中的索引具有實時性，能夠實現模式知識庫通行時間的迅速寫入和更新。

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

3 試驗與結果分析

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

(5)

(6)

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

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

表3 模型方法耗時

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

4 結 語

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