基于城市交通監(jiān)控大數(shù)據(jù)的行程時間估計

李文明，劉芳，呂鵬，于彥偉

1. 煙臺大學(xué)計算機(jī)與控制工程學(xué)院，山東 煙臺 264005；

2. 中國海洋大學(xué)計算機(jī)科學(xué)與技術(shù)系，山東 青島 266100

1 引言

近年來，城市的快速發(fā)展，城市內(nèi)的車輛數(shù)量不斷增加，導(dǎo)致了交通擁堵、交通事故頻發(fā)等一系列的交通問題。在這種環(huán)境下，如何提高日常生活中的城市出行效率成為出行用戶的首要考慮問題，而作為交通服務(wù)中的一項基礎(chǔ)功能，路徑規(guī)劃為人們尤其是不熟悉路況的人提供了重要的出行路線參考。在移動互聯(lián)的大數(shù)據(jù)時代，大數(shù)據(jù)、人工智能、云計算、物聯(lián)網(wǎng)、智能終端等先進(jìn)技術(shù)的不斷發(fā)展，為綜合交通的一體化、智能化、智慧化發(fā)展提供了堅實的資源和技術(shù)支撐[1]。城市交通中的車輛路徑查詢和行程時間估計一直是交通行業(yè)的熱門問題，目前的大部分路線推薦方法利用車輛的GPS軌跡數(shù)據(jù)進(jìn)行車輛的路線規(guī)劃以及行程時間估 計[2]。而隨著城市交通以及智慧交通的發(fā)展，越來越多的監(jiān)控攝像頭被安裝在城市道路路口，以實時監(jiān)控城市的交通狀況，這些智能化的監(jiān)控攝像頭可以實時記錄路口車輛的各種信息，如車牌號、經(jīng)過時間以及行駛方向等。因此，無論車輛是否裝有GPS等定位設(shè)備，相關(guān)人員都能夠通過城市的交通監(jiān)控系統(tǒng)獲取整個城市所有車輛的行駛軌跡信息。利用城市交通監(jiān)控中的攝像頭數(shù)據(jù)進(jìn)行城市出行路線規(guī)劃和行程時間估計成為可能。

雖然城市交通監(jiān)控系統(tǒng)的部署正在逐步完善，但是其安裝和維護(hù)的成本等問題使得交通監(jiān)控攝像頭的數(shù)量及其覆蓋的范圍仍然有限。此外，交通監(jiān)控數(shù)據(jù)是通過固定部署的監(jiān)控攝像頭獲得的，觀察到的車輛軌跡數(shù)據(jù)并不是完整的車輛行駛軌跡。因此利用交通監(jiān)控攝像頭的車輛數(shù)據(jù)進(jìn)行查詢時，會遇到以下3個挑戰(zhàn)。

● 查詢效率問題：路徑推薦和時間估計是從某個范圍區(qū)域內(nèi)所有監(jiān)控攝像頭的車輛歷史數(shù)據(jù)中查找車輛行駛軌跡和時間，涉及的數(shù)據(jù)規(guī)模非常大；此外，城市出行一般為即時查詢，對查詢效率有較高的要求。如果不能在短時間內(nèi)對海量數(shù)據(jù)進(jìn)行查詢處理，就無法實時得到查詢結(jié)果，失去了城市出行的行程時間估計的意義。如何提高查詢效率是使用交通監(jiān)控大數(shù)據(jù)進(jìn)行查詢的一個亟待解決的問題。

● 路線選擇問題：在實際生活中，車輛并不總是簡單地從起始點出發(fā)，直接到達(dá)結(jié)束點，而是存在多條可能的軌跡路線。例如，車輛可能在行駛過程中停留，導(dǎo)致實際行程時間增加。如圖1（a）所示，對于同樣的起始點A和結(jié)束點B，3條軌跡（T1、T2、T3）花費的時間不同，其中T1為正常行駛軌跡，花費300 s；T3由于繞行，花費了600 s。由此可知，并不是任意兩個點之間都存在直接路線。在T2和T1軌跡長度相近的情況下，T2的行駛時間為600 s，耗費的時間遠(yuǎn)大于T1，這很可能是T2的車輛在中途停留，導(dǎo)致行程時間增加。此外，車輛在不同的時間從相同的起始點到相同的結(jié)束點花費的時間也可能不同，這與對應(yīng)路段的道路擁堵程度、交通事故情況以及其他的交通因素有關(guān)。在圖1（b）中，對于同樣的起始點A和結(jié)束點B以及相同的軌跡路線，在8:00出發(fā)比在11:00出發(fā)需要的行程時間更長。在11:00，從A點到B點，T1和T2的行程時間均為300 s；而在8:00，從A點到B點，T3和T4的行程時間分別為400 s和350 s，所花費的時間比11:00時更長。這很可能是因為人們大多集中在8:00去上班，道路擁堵，導(dǎo)致行程時間變長。

圖1 車輛出行的不同情況

● 噪聲問題：由于一些原因，交通監(jiān)控攝像頭獲取到的車輛軌跡信息會存在較多噪聲。例如，在霧天或雨天，車牌號碼識別不準(zhǔn)確，導(dǎo)致車輛信息錯誤；部分?jǐn)z像頭因為故障沒有記錄到經(jīng)過該路段的車輛信息，使得收集的車輛軌跡信息與車輛的真實軌跡不一致或車輛軌跡信息缺失等。

為了解決上述挑戰(zhàn)，本文將城市道路路口的攝像頭數(shù)據(jù)和聚類后的城市路網(wǎng)數(shù)據(jù)結(jié)合，將攝像頭和車輛的軌跡信息匹配到城市路網(wǎng)中對應(yīng)的路口上，形成路網(wǎng)數(shù)據(jù)庫和攝像頭數(shù)據(jù)庫，包括攝像頭的位置、編號，以及車輛ID、經(jīng)過時間等數(shù)據(jù)。然后結(jié)合R樹索引[3]構(gòu)建時空索引和反向索引結(jié)構(gòu)，時空索引用來根據(jù)位置信息和出發(fā)時間進(jìn)行攝像頭數(shù)據(jù)庫的查詢，反向索引用來快速獲取每輛車輛的攝像頭軌跡路線和行程時間。兩種索引極大地提高了查詢效率。當(dāng)給定出發(fā)地和目的地位置信息及出發(fā)時間后，將查詢位置信息與距其最近的攝像頭進(jìn)行匹配，對該攝像頭及其所在路口攝像頭的數(shù)據(jù)進(jìn)行查詢。根據(jù)攝像頭的監(jiān)控數(shù)據(jù)可以得到出發(fā)地和目的地所含有的共同車輛ID，再根據(jù)車輛ID利用反向索引得到其經(jīng)過的攝像頭編號和時間信息，經(jīng)過時間排序，可以得到車輛的推薦路線和行程時間。

綜上所述，本文主要貢獻(xiàn)總結(jié)如下：

● 本文提出了一種基于城市交通監(jiān)控大數(shù)據(jù)的行程時間估計方法UTSD，可以實時進(jìn)行城市出行的路線推薦和行程時間估計；

● 通過對城市監(jiān)控攝像頭數(shù)據(jù)構(gòu)建時空索引和反向索引，加快車輛行駛軌跡的查詢速度，從而快速得到車輛軌跡信息和對應(yīng)的行程時間，極大地提高了監(jiān)控大數(shù)據(jù)查詢和行程時間估計的效率；

● 在某省會城市的真實交通監(jiān)控攝像頭數(shù)據(jù)上的實驗結(jié)果驗證了本文方法的有效性，相比對比算法，本文方法的性能有顯著的提升。

2 相關(guān)工作

與本文相關(guān)的前期工作可以分為兩類：時空數(shù)據(jù)管理和車輛行程時間估計。

2.1 時空數(shù)據(jù)管理

近年來，位置感知傳感器在GPS、4G、5G網(wǎng)絡(luò)等的應(yīng)用中迅速普及，隨著時間的推移，這些應(yīng)用會產(chǎn)生大量的位置數(shù)據(jù)，這就需要合適的索引結(jié)構(gòu)來實現(xiàn)對如此大的位置數(shù)據(jù)集的高效查詢與處理。G樹索引[4]在路網(wǎng)結(jié)構(gòu)中應(yīng)用較多，可以對路網(wǎng)進(jìn)行有效的k近鄰搜索[4]。R樹被廣泛應(yīng)用于二維數(shù)據(jù)的索引[3,5]。同時，R樹也可以將時間作為第三維度，變成三維R樹（3DRtree），如時空R樹（ STR-tree）和軌跡束樹（TB-tree）[6]。而三維R樹通過將時間維度劃分為多個時間間隔，并鏈接到相應(yīng)的空間索引，又衍生出多個版本的R樹，如歷史R樹（HR-tree）[7]。此外，還有一些基于網(wǎng)格的索引，它們可以將一塊區(qū)域空間劃分為多個網(wǎng)格，如扁平起始樹（CSEtree）[8]和可擴(kuò)展的高效軌跡索引（scalable and efficient trajectory index，SETI）[9]。劃分后的網(wǎng)格由四叉樹[10]或多維二叉樹[11]構(gòu)建，時間由混合B+樹[12]或B樹[13]進(jìn)行索引。除了上述數(shù)據(jù)索引，反向索引[14]也是一種有效的軌跡查詢索引。

有了合適的時空索引，才能有效地獲取軌跡數(shù)據(jù)。這對于本文所要解決的城市交通監(jiān)控大數(shù)據(jù)的數(shù)據(jù)查詢問題更為重要。本文結(jié)合R樹索引，構(gòu)建了存儲攝像頭記錄的時空索引，以及由車輛軌跡創(chuàng)建的反向索引，極大地提升了監(jiān)控大數(shù)據(jù)的查詢效率。

2.2 車輛行程時間估計

本文將關(guān)于車輛行程時間估計問題的相關(guān)工作分為3個主要類別：基于鏈路的行程時間估計、基于路徑的行程時間估計和基于軌跡的行程時間估計。

（1）基于鏈路的行程時間估計

基于鏈路的行程時間估計方法是估計路網(wǎng)中車輛行程時間的經(jīng)典方法。這種方法主要適用于靜態(tài)的交通監(jiān)控裝置，如車輛感應(yīng)裝置[15]和攝像頭裝置[16]。對于浮動的車輛數(shù)據(jù)，如GPS數(shù)據(jù)，可以根據(jù)經(jīng)過這些鏈路的車輛軌跡來推斷各個鏈路的行駛時間。例如，Hofleitner A等人[17]基于交通流模型對鏈路的行程時間分布進(jìn)行建模，并估計未來的行程時間。參考文獻(xiàn)[18]使用最小二乘法根據(jù)僅包含結(jié)束點位置和有關(guān)行程的元信息（如行程距離）的出租車行程數(shù)據(jù)來估計鏈路的行程時間。還有一些方法[16-17]可被用來估計未來短期的鏈路行程時間，如動態(tài)貝葉斯網(wǎng)絡(luò)算法[17]、模式匹配算法[16]、梯度增強(qiáng)回歸樹[19]和深度學(xué)習(xí)算法[20]等。

許多研究將估計的鏈路行程時間總和作為路徑的行程時間，這種方法的缺點是沒有考慮鏈路之間的時間花費，如車輛等待紅綠燈的情況。為了有效解決該問題，Rahmani M等人[21]設(shè)計了一個非參數(shù)的鏈路行程時間估計方法，以減少基于鏈路的行程時間估計模型的時間偏差。然而，該模型需要良好的道路網(wǎng)絡(luò)動態(tài)覆蓋，導(dǎo)致這種方法只能適用于特定的高速公路區(qū)域或一些特定的路線。

（2）基于路徑的行程時間估計

參考文獻(xiàn)[22]研究表明：直接測量道路上路徑的行程時間比分開單獨測量鏈路的行程時間準(zhǔn)確度更高。然而并不是所有的路徑都可以直接測量行程時間，因此基于大規(guī)模路徑的行程時間估計需要將查詢路徑分解為較多的子路徑。為了解決這個問題，Wang Y等人[2]研究了基于路徑的行程時間估計子路徑的長度和最小支持度的最優(yōu)解。他們首先通過最小化子路徑的總行程時間方差來計算最優(yōu)解，并對每個子路徑上的司機(jī)數(shù)量進(jìn)行標(biāo)準(zhǔn)化；然后利用時空特征和驅(qū)動的張量分解，記錄每個子路徑的歷史行程時間；最后構(gòu)造了一個評價函數(shù)，并利用動態(tài)規(guī)劃和后綴樹優(yōu)化來選擇子路徑的最佳組合。該方法取得了很好的實驗效果，相比所有的基線算法和對比算法，其性能都有所提升。Jiang M Y等人[23]在參考文獻(xiàn)[2]的基礎(chǔ)上對算法進(jìn)行改進(jìn)，并用一種隨機(jī)優(yōu)化算法Adam（adaptive moment estimation）[24]替換了原算法中的SGD（stochastic gradient descent）算法[2]，進(jìn)一步提升了算法的效率。

參考文獻(xiàn)[25]提出了一種局部頻繁共享算法，該算法從歷史數(shù)據(jù)中學(xué)習(xí)一組頻繁共享路徑的局部擁堵模式。該算法可以從距離查詢路段最近的軌跡中識別周圍的當(dāng)前擁堵模式，然后結(jié)合歷史數(shù)據(jù)，估計未來的路徑行程時間。該局部頻繁共享算法的準(zhǔn)確率比只使用歷史軌跡的對比算法的準(zhǔn)確率提高了20%～30%。

（3）基于軌跡的行程時間估計

基于軌跡的行程時間估計從歷史數(shù)據(jù)中找到與所要查詢的出發(fā)地、目的地和出發(fā)時間相近的歷史軌跡，從而估計車輛的行程時間[26-27]。軌跡和路徑的區(qū)別是：路 徑是指路網(wǎng)中某一段道路，軌跡是指車輛的行駛軌跡，可能會包含多段道路。通常假設(shè)相同端點之間的車輛軌跡相同或存在少量的替代軌跡。因此，這種方法更適用于預(yù)定路線的估計，如參考文獻(xiàn)[28]的公交車出行。參考文獻(xiàn)[27]根據(jù)匹配的歷史軌跡計算查詢行程的時間分布，并使用統(tǒng)計檢驗方法消除異常值。參考文獻(xiàn)[26]結(jié)合周期性交通模式和與之匹配的歷史軌跡對軌跡的行程時間進(jìn)行調(diào)整估計?；谲壽E的行程時間估計也可以進(jìn)行分層擴(kuò)展，以實現(xiàn)某些路線的多樣性。Yuan H T等人[29]提出了一種新的基于神經(jīng)網(wǎng)絡(luò)的估計模型，根據(jù)軌跡的起迄點（origin-destination，OD）以及軌跡的行程時間，設(shè)計了一種特殊的編碼來與歷史軌跡相關(guān)聯(lián)，當(dāng)輸入OD進(jìn)行查詢時，可以通過編碼直接得到對應(yīng)的歷史軌跡行程時間。

針對歷史軌跡數(shù)據(jù)索引的查詢，Ding Y C等人[30]提出了一種遍歷軌跡聚合查詢（traversal trajectory aggregate query）算法，對歷史軌跡進(jìn)行聚合存儲，并提出了一種新的目標(biāo)索引采樣（targeted index sampling，TIS）框架，對數(shù)據(jù)進(jìn)行采樣查詢，提高了查詢效率和查詢精度。

在參考文獻(xiàn)[31]中，Yuan J等人將行程軌跡表示為一系列在城市熱門地標(biāo)之間的短途軌跡。行程時間為地標(biāo)到地標(biāo)的行程時間總和，再加上從起始點到第一個地標(biāo)以及從最后一個地標(biāo)到結(jié)束點所花費的時間。Yuan J等人[31]指出，盡管基于軌跡的行程時間估計的性能比基于鏈路的算法和基于路徑的算法好，但在獲得有用結(jié)果的同時，由于無法可靠地確定出租車行程的真實起始點和結(jié)束點，它無法被應(yīng)用于沒有位置標(biāo)記的軌跡中。而本文提出的基于監(jiān)控大數(shù)據(jù)的行程時間估計方法也是基于軌跡的行程時間估計方法，所提方法查詢的監(jiān)控大數(shù)據(jù)為真實車輛數(shù)據(jù)，均可以根據(jù)攝像頭記錄來確定車輛的真實起始點位置和結(jié)束點位置（即軌跡經(jīng)過的第一個交通監(jiān)控攝像頭位置和最后一個交通監(jiān)控攝像頭位置）。

3 問題定義

本節(jié)首先給出重要的概念定義，然后對基于交通監(jiān)控大數(shù)據(jù)的行程時間估計問題進(jìn)行定義。

定義1路網(wǎng)。路網(wǎng)表示為其中表示所有路口的集合，E表示路口之間所有路段的集合，ei,j∈E表示從路口ni到路口nj的一條路段。需要注意的是，每個路段都是有方向的，也就是說，ei,j不同于路段ej,i。

定義2攝像頭記錄。攝像頭記錄被定義為一個三元組(vehid,camj,tsj)，表示車輛vehid在tsj時刻經(jīng)過攝像頭camj。

定義3車輛軌跡。車輛vehid的軌跡是一個根據(jù)時間排序的攝像頭記錄序列，表示為其中表示車輛vehid在tsi時刻經(jīng)過攝像頭cami。

由定義3可知，車輛軌跡由車輛經(jīng)過的所有攝像頭的時間序列構(gòu)成，本文將歷史監(jiān)控攝像頭數(shù)據(jù)中所有含有同一車輛vehid的攝像頭記錄序列記為該車輛的車輛軌跡TRid，其部分車輛軌跡記為Trid。所有車輛的軌跡集合記為TRs。

本文將基于城市交通監(jiān)控大數(shù)據(jù)的行程時間估計問題定義如下。

問題定義：給定路網(wǎng)G、路網(wǎng)上所有的攝像頭記錄（即所有的車輛軌跡集合TRs）、起始點位置O (lons,lats)、結(jié)束點位置D( lone,late)以及出發(fā)時間ts，目標(biāo)是得出路線推薦以及行程時間估計Time。

表1給出了本文用到的主要符號及其含義。

4 基于城市交通監(jiān)控大數(shù)據(jù)的行程時間估計方法

4.1 總體框架

圖2給出了本文提出的基于城市交通監(jiān)控大數(shù)據(jù)的行程時間估計方法的總體框架，該框架主要包括三部分：數(shù)據(jù)預(yù)處理、構(gòu)建數(shù)據(jù)索引以及行程時間估計。

（1）數(shù)據(jù)預(yù)處理

數(shù)據(jù)預(yù)處理是指在數(shù)據(jù)查詢和構(gòu)建數(shù)據(jù)索引之前對原始交通監(jiān)控數(shù)據(jù)進(jìn)行轉(zhuǎn)換和篩選處理，主要包括將攝像頭映射到路網(wǎng)上、從監(jiān)控攝像頭數(shù)據(jù)中提取車輛軌跡兩部分。

（2）構(gòu)建數(shù)據(jù)索引

當(dāng)數(shù)據(jù)預(yù)處理完成之后，利用處理好的監(jiān)控數(shù)據(jù)構(gòu)建數(shù)據(jù)索引，提高數(shù)據(jù)查詢效率。數(shù)據(jù)索引包括時空索引和反向索引兩部分。時空索引是利用所有攝像頭記錄來檢索車輛的索引，給定攝像頭編號和時間，找到所有在該時間經(jīng)過此攝像頭的車輛。反向索引是根據(jù)數(shù)據(jù)預(yù)處理得到的車輛軌跡構(gòu)建的，它是通過車輛來查詢攝像頭的索引，主要用于查詢每輛車經(jīng)過的攝像頭組成的車輛軌跡和對應(yīng)的行程時間。給定車輛ID和出發(fā)時間，可以找到該車輛在出發(fā)時間及以后所經(jīng)過的攝像頭。

（3）行程時間估計

給定起始點位置 O(lons,lats)、結(jié)束點位置 D(lone,late)和出發(fā)時間ts，首先將起始點位置和結(jié)束點位置分別匹配到對應(yīng)的攝像頭；然后利用時空索引查詢經(jīng)過起始和結(jié)束攝像頭的所有車輛數(shù)據(jù)，找出它們含有的車輛ID相同的車輛數(shù)據(jù)；接下來采用反向索引，找到這些車輛經(jīng)過起始攝像頭之后的車輛軌跡；最后，從這些車輛軌跡中篩選出符合條件的車輛軌跡，每條車輛軌跡對應(yīng)的行程時間是根據(jù)車輛經(jīng)過起始攝像頭和結(jié)束攝像頭的時間差得到的。

4.2 數(shù)據(jù)預(yù)處理

4.2.1 攝像頭映射

攝像頭映射包括攝像頭到路網(wǎng)位置的映射，以及攝像頭位置到路網(wǎng)中對應(yīng)路口的匹配兩部分。首先，從開源地圖平臺OpenStreetMap[32]上獲取真實路網(wǎng)。根據(jù)定義1，一個路網(wǎng)包括路口集合以及路口之間的路段集合。通常來說，監(jiān)控攝像頭被部署在鄰近路口處的位置，用來獲得所有經(jīng)過此路段的車輛信息。因此，通過攝像頭的位置信息（如經(jīng)度和緯度）將攝像頭映射到路網(wǎng)上，再匹配到相應(yīng)路口上，就能夠獲得車輛在路網(wǎng)上對應(yīng)的行駛記錄。

4.2.2 提取車輛軌跡

根據(jù)定義2，在交通監(jiān)控數(shù)據(jù)中，每個攝像頭監(jiān)控記錄可表示為(vehid,camj,tsj)，表示車輛vehid在tsj時刻經(jīng)過了攝像頭camj。由定義3可知，當(dāng)車輛的ID相同時，根據(jù)時間排序后的攝像頭記錄序列可以表示車輛軌跡。為了保證車輛軌跡的連續(xù)性，本文將歷史監(jiān)控攝像頭數(shù)據(jù)中每輛車經(jīng)過的所有攝像頭作為一條車輛軌跡（即TRid）。

4.3 構(gòu)建數(shù)據(jù)索引

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

構(gòu)建時空索引分為構(gòu)建空間索引和構(gòu)建時間索引兩部分。

如圖3所示，首先構(gòu)建空間索引，生成城市路網(wǎng)后，先利用攝像頭編號和位置信息，將攝像頭映射在路網(wǎng)上，再將每個攝像頭匹配到距離其最近的路口上，并創(chuàng)建攝像頭編號至路口的索引，以便在讀取監(jiān)控數(shù)據(jù)時根據(jù)攝像頭編號將攝像頭記錄存儲到對應(yīng)路口的攝像頭中。

表1 主要符號及其含義

圖2 總體框架

一般情況下人的活動是以天為周期的，很多研究[33-34]驗證了這一點，相應(yīng)的城市交通情況也會以天為周期出現(xiàn)變化。因此，在構(gòu)建時間索引時，本文根據(jù)一天24 h將時間索引平均分為24個時隙層，每個時隙層索引的范圍是1 h。每個時隙層中都包含一個完整的城市路網(wǎng)空間索引。如圖3所示，在存儲攝像頭記錄時，先根據(jù)時間確定攝像頭記錄所在時隙層，再根據(jù)攝像頭編號將攝像頭記錄存儲到對應(yīng)路口的攝像頭中。

圖3 構(gòu)建時空索引

4.3.2 構(gòu)建反向索引

由定義2和定義3可知，對于車輛vehid的車輛軌跡Trid，由車輛vehid和經(jīng)過時間tsj可以唯一確定其經(jīng)過的攝像頭camj。此外，因為車輛軌跡是按時間排序的攝像頭記錄序列，還可以得到車輛vehid在時間tsj之后經(jīng)過的所有攝像頭以及對應(yīng)的經(jīng)過時間。因此，可以根據(jù)車輛軌跡的攝像頭記錄序列，建立根據(jù)車輛ID查找所經(jīng)過攝像頭的反向索引。

如圖4所示，對于車輛vehid的一條車輛軌跡其中cam1、cam2、cam3、cam4分別匹配到路口n1、n2、n3、n4上，給定出發(fā)時間ts1，可以得到車輛vehid在時間ts1經(jīng)過的攝像頭cam1，以及在時間ts1之后，車輛在時間ts2、ts3、ts4分別經(jīng)過的攝像頭cam2、cam3、cam4。

在構(gòu)建反向索引 前，對于車輛的所有攝像頭記錄，各個攝像頭記錄之間是相對獨立的，無法確定單獨的一條攝像頭記錄是否為噪聲數(shù)據(jù)。然而，在構(gòu)建反向索引之后，可以根據(jù)車輛軌跡中相鄰攝像頭記錄之間的關(guān)系來過濾噪聲數(shù)據(jù)，比如由于霧天導(dǎo) 致車牌號碼識別錯誤或者車輛在相鄰攝像頭記錄之間有較長時間的停留等導(dǎo)致的噪聲數(shù)據(jù)，詳細(xì)描述見第4.4節(jié)。

4.4 行程時間估計

在時空索引和反向索引構(gòu)建完成之后，給定起始點位置O(lons,lats)、結(jié)束點位置D(lone,late)以及出發(fā)時間ts，就可以根據(jù)時空索引和反向索引對查詢點進(jìn)行車輛的路線推薦和行程時間估計。

在城市路網(wǎng)中，一個路口一般安裝多個攝像頭，因此在將攝像頭映射到路網(wǎng)上時，可能有多個監(jiān)控攝像頭匹配到同一個路口。這些匹配到同一路口的攝像頭產(chǎn)生的攝像頭記錄都表示車輛經(jīng)過了攝像頭所匹配的路口。因此本文將匹配到同一路口的攝像頭組成一個攝像頭集合，當(dāng)車輛經(jīng)過一個攝像頭時，表示車輛經(jīng)過了該攝像頭所匹配路口的所有攝像頭。設(shè)定表示起始點位置O(lons,lats)匹配到的攝像頭所在路口的攝像頭集合；表示結(jié)束點位置D(lone,late)匹配到的攝像頭所在路口的攝像頭集合。

這樣在查詢OD匹配的攝像頭時，可以查詢到匹配攝像頭所在路口的所有攝像頭記錄，提高了查詢效率和查詢范圍。

算法1展示了路線推薦和行程時間估計的偽代碼。

算法1路線推薦和行程時間估計算法

輸入：起始點位置O(lons,lats)、結(jié)束點位置D(lone,late)、出發(fā)時間ts

輸出：推薦路徑Pathtopn和對應(yīng)的行程時間

如算法1所示，首先，根據(jù)出發(fā)時間ts確定no所在時隙層的路網(wǎng)確定ts對應(yīng)的時隙層之后，會出現(xiàn)一個問題，即要查詢的行程時間超過了一個時隙層的范圍（即行程時間超過1 h），導(dǎo)致車輛實際的結(jié)束時間與出發(fā)時間不在同一個時隙層，而是在下一個時隙層或者后面的時隙層。此時，如果只查找ts所在時隙層路網(wǎng)中的攝像頭記錄，會影響查詢精度或者無法得到車輛在結(jié)束時間所在時隙層的攝像頭記錄。為了解決這個問題，這里新增了一個結(jié)束時間te=ts+tp，用來預(yù)測nd所在時隙層的路網(wǎng) Gd=(Nd,E)。te是由出發(fā)時間ts和通過基于有向圖的Dijkstra最短路徑算法（以下簡稱最短路徑算法）[35]得到的行程時間tp相加后得到的大致預(yù)測時間，并不是真實的行程時間。tp被用來預(yù)先估計OD的行程時間，預(yù)測te所在時隙層，以提高本文所提方法的查詢精度。通過最短路徑算法得到的行程時間tp的計算方式如下：給定起始點位置O(lons,lats)、結(jié)束點位置D(lone,late)和路網(wǎng) G =(N,E)，同時，路網(wǎng)中的每個路段ei,j附帶了距離權(quán)重和時間權(quán)重。距離權(quán)重表示從路口ni到路口nj的行駛距離，時間權(quán)重表示從路口ni到路口nj的行駛時間，這里的行駛時間為從路口ni到路口nj的歷史車輛軌跡的平均行駛時間。在路網(wǎng)G =(N,E)中分別匹配到距離O、D最近的路口為no和nd。根據(jù)每個路段的時間權(quán)重，利用最短路徑算法得到從路口ni到路口nj的行程時間tp。

圖4 反向索引的構(gòu)建示例

例如，當(dāng)出發(fā)時間為10:40時，查詢no的時隙層范圍為10:00—11:00的時隙層。若tp時長為50 min，那么te為11:30，查詢nd的時隙層范圍為10:00—11:00的時隙層以及11:00—12:00的時隙層。

如第3～9行所示，確定了要查詢的時隙層 的范圍之后，根據(jù)所給的起始點位置O(lons,lats)和結(jié)束點位置D(lone,late)，在路網(wǎng)中分別匹配到距離最近的起始點攝像頭camo和結(jié)束點攝像頭camd。然后，找到camo和camd所在路口的攝像頭集合co和cd。這里需要注意，從起始點位置到達(dá)起始點所匹 配的攝像頭位置以及從結(jié)束點所匹配的攝像頭位置到達(dá)結(jié)束點位置的這兩段路程，會分別根據(jù)ts和te所在時隙層，以及該路程在路網(wǎng)中所處的路段中所占的長度比例來計算時間，最后與主路程相加。

如第10～16行所示，在確定了co和cd之后，分別查詢co和cd中各攝像頭包含的攝像頭記錄reco和recd，并得到在該時隙層中經(jīng)過起始點和結(jié)束點攝像頭的車輛集合Veho和Vehd。然后，求出集合Veho和Vehd的交集Vehc，即起始路口和結(jié)束路口的攝像頭記錄中共同含有的車輛ID。

如第17～23行所示，得到共同車輛ID之后，根據(jù)反向索引，可以得到每輛車vehid的部分車輛軌跡Trid。這里Trid的起始攝像頭cam1為co中的攝像頭，出發(fā)時間ts1在ts確定的時隙層；結(jié)束攝像頭camn為cd中的攝像頭，結(jié)束時間tsn在te預(yù)測的時隙層。軌跡Trid的行程時間Timeid為結(jié)束時間tsn與出發(fā)時間ts1的差值。

同時，為了解決前文提到的監(jiān)控攝像頭的噪聲數(shù) 據(jù)問題，本文為每個路段ei,j設(shè)置了一個時間閾值范圍thi,j，閾值范圍根據(jù)該路段歷史車輛軌跡的平均行駛時間來確定，本文取平均行駛時間的一半和3倍分別作為thi,j的最小值和最大值。thi,j用來判斷前文得到的Vehc中每輛車vehid的部分車輛軌跡Trid中是否存在噪聲數(shù)據(jù)（即可能是噪聲數(shù)據(jù)的攝像頭記錄）。具體方法 為，依次計算車輛軌跡Trid中相鄰攝像頭記錄的時間差，并與攝像頭記錄所對應(yīng)的路段上的時間閾值范圍thi,j進(jìn)行比較，如果該時間差處于時間閾值范圍外，就認(rèn)為該相鄰攝像頭記錄存在噪聲數(shù)據(jù)，并過濾該條車輛軌跡。例如，對于軌跡根據(jù)相鄰攝像頭記錄計算ts1和ts2的時間差值，并與cam1和cam2所對應(yīng)路段的時間閾值范圍進(jìn)行比較，然后依次計算直到

過濾噪聲數(shù)據(jù)后，根據(jù)行程時間Timeid的大小，進(jìn)行由小到大的排序，選出時間最短的前Topn條車輛軌跡，放入Pathtopn，然后將車輛軌跡經(jīng)過的攝像頭編號替換為該攝像頭所匹配的路口，就可以得到車輛在路網(wǎng)上的推薦路線和對應(yīng)的行程時間估計。這里由于攝像頭覆蓋率以及噪聲數(shù)據(jù)等原因，得到的推薦路線可能會存在相鄰路口不連續(xù)的情況，導(dǎo)致路線不夠詳細(xì)，如果想要得到更加詳細(xì)的路線，可以在這些不相鄰的路口間采用最短路徑算法，進(jìn)一步細(xì)化路線。

5 實驗與結(jié)果

本節(jié)將在真實數(shù)據(jù)集上進(jìn)行實驗，以驗證本文所提基于城市交通監(jiān)控大數(shù)據(jù)的行程時間估計方法UTSD的有效性。

5.1 實驗數(shù)據(jù)集

本文采用的實驗數(shù)據(jù)集為某省會城市的真實交通監(jiān)控數(shù)據(jù)集。該數(shù)據(jù)集包括2016年8月1—31日共31天的從1 704個監(jiān)控攝像頭抓拍的4億多條數(shù)據(jù)記錄。路網(wǎng)是從開源地圖OpenStreet Map[32]上采集得到的，本次實驗區(qū)域為該城市部分市區(qū)，路網(wǎng)包括78個路口節(jié)點、149條路徑，路網(wǎng)區(qū)域內(nèi)有99個攝像頭覆蓋在39個路網(wǎng)節(jié)點上。對路網(wǎng)數(shù)據(jù)預(yù)處理（如去掉直行路段中多余的路口等）后，路網(wǎng)內(nèi)有56個路網(wǎng)節(jié)點、125條路徑，路網(wǎng)區(qū)域內(nèi)有77個攝像頭覆蓋在33個路網(wǎng)節(jié)點上，攝像頭覆蓋率為59%。

5.2 實驗設(shè)置

所有實驗均在一臺戴爾筆記本計算機(jī)上進(jìn)行，系統(tǒng)為Windows10(64位)，配置為4核Intel(R) Core(TM)i5-5200U CPU@ 2.20 GHz，運行內(nèi)存為8 GB。程序采用Python語言，編譯器版本為Python 3.7.0[MSC v.1912 64 bit (AMD64)]。每個實驗運行1 000次，求出平均運行結(jié)果。

5.2.1 對比算法

由于本文方法為基于攝像頭數(shù)據(jù)的大數(shù)據(jù)查詢方法，目前暫時沒有與該方法相關(guān)的大數(shù)據(jù)查詢算法。因此本文使用基于有向圖的Dijkstra最短路徑算法[35]和百度地圖的API查詢算法（以下簡稱百度算法）作為對比算法。

基于有向圖的Dijkstra最短路徑算法是有向加權(quán)圖中最基本的最短路徑算法?；谟邢驁D的Dijkstra最短路徑算法可以表示為：給定加權(quán)有向圖G和源點A，求A到G中其他頂點的最短路徑，在求最短路徑時，從起始點開始，采用貪心算法的策略，遍歷距起始點最近且未訪問過的頂點的鄰接節(jié)點，直到遍歷到結(jié)束點。那么在路網(wǎng)中求最短路徑可以表示為：給定路網(wǎng)和起始點no，求no到路網(wǎng)中另一個路口nd的最短路徑。

百度地圖的API查詢算法是通過調(diào)用百度地圖開發(fā)的API來查詢起始點和結(jié)束點的算法。該算法運行在百度服務(wù)器上，實驗中只能得到算法結(jié)果的返回值。

5.2.2 參數(shù)設(shè)置

實驗中本文所提算法的默認(rèn)參數(shù)設(shè)置如下：用來查詢的監(jiān)控數(shù)據(jù)為7天的歷史數(shù)據(jù)，查詢時隙層的范圍是出發(fā)時間ts和結(jié)束時間te所在的時隙層，時間估計結(jié)果取前10%的數(shù)據(jù)的均值（即topn為前10%的數(shù)據(jù)）。

5.2.3 評估指標(biāo)

本文采用行程時間估計常用的兩種性能評估標(biāo)準(zhǔn)——行程時間的平均相對誤差（MRE）和平均絕對誤差（MAE）來評估算法的有效性。同時，為了減少數(shù)據(jù)集中存在的與 大多數(shù)行程顯著不同的異常行程對實驗結(jié)果的影響，本文還增加了中值相對誤差（MedRE）和中值絕對誤差（MedAE）來評估算法的有效性。

平均相對誤差的定義如下：

平均絕對誤差的定義如下：

中值相對誤差的定義如下：

中值絕對誤差的定義如下：

5.3 性能評估

本節(jié)首先對3種算法在不同查詢時隙下的相對誤差和絕對誤差進(jìn)行評估，然后對3種算法的平均查詢時間進(jìn)行分析。

為了更好地評估算法的有效性，本文選取3個時隙：上下班的早高峰和晚高峰時隙以及查詢較少的時隙，分別為8:00—9:00和18:00—19:00、0:00—1:00。

各算法的平均相對誤差和中值相對誤差分別如圖5和圖6所示。從實驗結(jié)果可以看出，UTSD的平均相對誤差和中值相對誤差都小于最短路徑算法和百度算法。在3個查詢時隙中，最短路徑算法的最小平均相對誤差為79.66%，百度算法的最小平均相對誤差為55.58%，而UTSD的最小平均相對誤差為14.64%，UTSD的準(zhǔn)確率比最短路徑算法和百度算法分別提高了65.02%和40.94%。而在中值相對誤差的比較中，UTSD的最小中值相對誤差為14.03%，最短路徑算法的最小中值相對誤差為77.16%，百度算法的最小中值相對誤差為51.11%，最短路徑算法和百度算法的中值相對誤差分別為UTSD的5.5倍和3.6倍。此外，UTSD在3個時隙上平均相對誤差的最大值和最小值的差值為4.55%，比最短路徑算法的28.55%和百度算法的7.61%都要低，這說明UTSD的穩(wěn)定性更高。

圖5 各算法的平均相對誤差

圖6 各算法的中值相對誤差

在圖7和圖8中，UTSD、最短路徑算法和百度算法的最小平均絕對誤差分別為45 s、142 s和98 s。UTSD的平均絕對誤差比最短路徑算法和百度算法分別減少了97 s和53 s。因為實驗采用的路網(wǎng)數(shù)據(jù)為城市路網(wǎng)的部分市區(qū)路網(wǎng)，查詢的起始點和結(jié)束點均在該部分市區(qū)路網(wǎng)內(nèi)，因此真實行程時間較短，絕對誤差較小。若將路網(wǎng)區(qū)域擴(kuò)大為監(jiān)控數(shù)據(jù)覆蓋的整個城市區(qū)域，真實行程時間增長，那么各算法的時間差值擴(kuò)大，UTSD將更具優(yōu)勢。

從圖5～圖8可以看出，3種算法在時隙18:00—19:00的相對誤差最小，在時隙8:00—9:00的相對誤差居中，在時隙0:00—1:00的相對誤差最大。最短路徑算法和百度算法的絕對誤差變化趨勢和相對誤差變化趨勢相同，而UTSD的絕對誤差在時隙18:00—19:00比時隙0:00—1:00要大，這可能是因為時隙18:00—19:00為車輛出行高峰期，雖然UTSD在時隙18:00—19:00的相對誤差比在時隙0:00—1:00的相對誤差要小，但是交通擁堵導(dǎo)致車輛行程時間變長所帶來的的影響更大，導(dǎo)致UTSD的絕對誤差變大。

從圖5～圖8還可以看出，相比最短路徑算法和百度算法，UTSD在行程時間估計結(jié)果中的誤差較?。礈?zhǔn)確度較高）。這是因為UTSD進(jìn)行路徑查詢和對應(yīng)的行程時間估計時，采用的都是經(jīng)過篩選的真實歷史車輛行程數(shù)據(jù)，而最短路徑算法進(jìn)行行程時間估計時，采用的只是歷史車輛數(shù)據(jù)的平均時間數(shù)據(jù)，并沒有對歷史數(shù)據(jù)進(jìn)行充分的利用，百度算法由于只采用接口進(jìn)行查詢，無法確定其采用的具體方法，但是可以看出其誤差也比UTSD高。

圖7 各算法的平均絕對誤差

圖8 各算法中值絕對誤差

各算法的平均查詢時間見表2，第一列到第四列分別表示UTSD在1天、3天、5天、7天歷史數(shù)據(jù)上的平均查詢時間。從表2可以看出，最短路徑算法的平均查詢時間最短，為1.56×10-4s，這是因為最短路徑算法的時間復(fù)雜度很低，且路網(wǎng)構(gòu)建的有向圖含有的數(shù)據(jù)也很少，所以平均查詢時間非常短。百度算法的平均查詢時間為1.45×10-2s，由于本文中的百度算法通過調(diào)用百度地圖的API進(jìn)行查詢，算法沒有在本地計算機(jī)上進(jìn)行計算，而是在百度服務(wù)器上進(jìn)行計算，運行算法時的硬件設(shè)備無法確定。UTSD在1天和3天的歷史數(shù)據(jù)上的平均查詢時間分別為3.17×10-2s和9.61×10-2s，與百度算法的平均查詢時間在同一個數(shù)量級上，這表明UTSD在時間效率上與百度算法相近。隨著歷史數(shù)據(jù)天數(shù)增加，UTSD的平均查詢時間也不斷增加，這是由于算法要對大量的監(jiān)控數(shù)據(jù)進(jìn)行查詢和處理必定會花費一定的時間，盡管如此，UTSD在以7天監(jiān)控數(shù)據(jù)作為歷史數(shù)據(jù)的情況下，平均查詢時間低于0.3 s，完全可以滿足城市出行的即時查詢需求。

表2 各算法平均查詢時間/s

5.4 參數(shù)敏感性估計

本節(jié)將評估參數(shù)變化對所提方法的性能影響。本文所提方法是基于大數(shù)據(jù)的查詢方法，因此主要影響因素是歷史數(shù)據(jù)天數(shù)。

圖9展示了本文所提方法在歷史數(shù)據(jù)天數(shù)為3～17天的平均相對誤差和中值相對誤差的變化情況。從圖9可以看出，在歷史數(shù)據(jù)天數(shù)為3天時，所提方法的平均相對誤差和中值相對誤差均最高，這可能是因為3天的歷史數(shù)據(jù)所含有的歷史車輛軌跡樣本不夠充足，形成的車輛軌跡不夠完整，以及存在一些噪聲數(shù)據(jù)，導(dǎo)致行程時間估計誤差較大。隨著歷史數(shù)據(jù)天數(shù)的不斷增加，本文所提方法的這兩種誤差不斷減小，這說明隨著歷史數(shù)據(jù)天數(shù)的增加，該方法能夠從歷史數(shù)據(jù)中查詢到更多符合查詢條件的歷史車輛軌跡，進(jìn)而更好地進(jìn)行路徑推薦和對應(yīng)行程時間的估計。當(dāng)歷史數(shù)據(jù)天數(shù)達(dá)到13天后，所提方法在平均相對誤差和中值相對誤差上的變化趨于穩(wěn)定。隨著歷史數(shù)據(jù)天數(shù)增加到17天，所提方法的兩種誤差并沒有明顯減小，這說明當(dāng)歷史數(shù)據(jù)達(dá)到一定數(shù)量時，能夠覆蓋路網(wǎng)中所有的查詢區(qū)域以及查詢時間，并有足夠的歷史軌跡滿足查詢需求，再次增加新歷史數(shù)據(jù)的同時，也會增加噪聲數(shù)據(jù)，噪聲數(shù)據(jù)增加的誤差量不變，而新歷史數(shù)據(jù)所能減少的誤差量逐漸減小，導(dǎo)致算法誤差的降低程度越來越小，進(jìn)入“瓶頸期”。

圖9 歷史數(shù)據(jù)天數(shù)對相對誤差的影響

圖10 歷史數(shù)據(jù)天數(shù)對UTSD的平均查詢時間的影響

圖10展示了本文所提方法在歷史數(shù)據(jù)天數(shù)為3～17天的平均查詢時間的變化情況。從圖10可以看出，隨著歷史數(shù)據(jù)天數(shù)的增加，算法的平均查詢時間也在增加，而且隨著天數(shù)的增加，平均查詢時間增加的幅度越來越大。這一方面是因為隨著歷史數(shù)據(jù)數(shù)量的增加，讀取、查詢和處理數(shù)據(jù)的時間增大，進(jìn)而導(dǎo)致運行時間增大；另一方面是因為本文所提方法本身的算法復(fù)雜度決定了算法隨歷史數(shù)據(jù)的增加所需要的運行時間會不斷增加。

結(jié)合圖9和圖10可以看出，歷史數(shù)據(jù)天數(shù)低于7天時，本文所提算法的誤差較高，歷史數(shù)據(jù)天數(shù)高于11天時，其誤差與7天的誤差相比降低較少，但平均查詢時間增加較大。若要在較短的查詢時間內(nèi)得到較低的誤差，使用7～11天的歷史數(shù)據(jù)比較合適。

6 結(jié)束語

本文針對城市出行的時間估計問題，提出了一種基于城市交通監(jiān)控大數(shù)據(jù)的行程時間估計方法UTSD。首先將道路網(wǎng)絡(luò)建模為有向加權(quán)圖，然后根據(jù)位置信息將攝像頭映射到路網(wǎng)地圖上，形成路網(wǎng)數(shù)據(jù)庫和攝像頭數(shù)據(jù)庫。然后，結(jié)合R樹構(gòu)建時空索引和反向索引結(jié)構(gòu)，時空索引用于快速檢索所有車輛的攝像頭記錄，反向索引用于快速得到車輛的行程時間和經(jīng)過的攝像頭軌跡，大大提升了數(shù)據(jù)查詢和行程時間估計的效率。通過在某省會城市的真實交通監(jiān)控數(shù)據(jù)上進(jìn)行實驗評估，驗證了本文所提方法的有效性，且相比對比算法其準(zhǔn)確性有顯著的提升。

雖然城市路網(wǎng)中的現(xiàn)有監(jiān)控攝像頭數(shù)量較多，但是攝像頭在路網(wǎng)中的覆蓋率還不夠高，提高攝像頭在路網(wǎng)中的覆蓋率顯然無法做到，那么如何在攝像頭覆蓋率不變的情況下，進(jìn)一步提升算法的精度和效率，是下一步需要進(jìn)行的工作。