點(diǎn)擊上方藍(lán)字關(guān)注我們

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

李文明¹,?劉芳¹,?呂鵬¹,?于彥偉²

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

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

?

摘要：隨著智慧交通的發(fā)展，越來越多的監(jiān)控?cái)z像頭被安裝在城市道路路口，這使得利用城市交通監(jiān)控大數(shù)據(jù)進(jìn)行車輛行程時間估計(jì)和路徑查詢成為可能。針對城市出行的行程時間估計(jì)問題，提出一種基于城市交通監(jiān)控大數(shù)據(jù)的行程時間估計(jì)方法UTSD。首先，將交通監(jiān)控?cái)z像頭映射到城市路網(wǎng)，并根據(jù)交通監(jiān)控?cái)?shù)據(jù)記錄構(gòu)建有向加權(quán)的城市路網(wǎng)圖；然后，針對行程時間估計(jì)，構(gòu)建時空索引和反向索引結(jié)構(gòu)，時空索引用于快速檢索所有車輛的攝像頭記錄，反向索引用于快速獲取每輛車輛的行程時間和經(jīng)過的攝像頭軌跡，這兩個索引大大提升了數(shù)據(jù)查詢和行程時間估計(jì)的效率；最后，基于構(gòu)建的索引，給出一種有效的行程時間估計(jì)和路徑查詢方法，根據(jù)出發(fā)時間、出發(fā)地和目的地，在時空索引結(jié)構(gòu)上匹配出發(fā)地與目的地共有的車輛，再利用反向索引，快速獲得行程時間估計(jì)與車輛路線。使用某省會城市的真實(shí)交通監(jiān)控大數(shù)據(jù)進(jìn)行實(shí)驗(yàn)評估，所提方法UTSD的準(zhǔn)確率比基于有向圖的Dijkstra最短路徑算法和百度算法分別提高了65.02%和40.94%，且UTSD在以7天監(jiān)控?cái)?shù)據(jù)作為歷史數(shù)據(jù)的情況下，平均查詢時間低于0.3 s，驗(yàn)證了所提方法的有效性和高效性。

關(guān)鍵詞：?城市交通監(jiān)控大數(shù)據(jù)?;?時空索引結(jié)構(gòu)?;?行程時間估計(jì)?;?路線推薦

論文引用格式：

李文明, 劉芳, 呂鵬,? 等. 基于城市交通監(jiān)控大數(shù)據(jù)的行程時間估計(jì)[J]. 大數(shù)據(jù), 2021, 7(1): 107-123.

LI W M, LIU F, LV P, et al. Travel time estimation based on urban traffic surveillance data[J]. Big Data Research, 2021, 7(1): 107-123.

1 引言

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

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

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

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

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

為了解決上述挑戰(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)控?cái)?shù)據(jù)可以得到出發(fā)地和目的地所含有的共同車輛ID，再根據(jù)車輛ID利用反向索引得到其經(jīng)過的攝像頭編號和時間信息，經(jīng)過時間排序，可以得到車輛的推薦路線和行程時間。

圖1???車輛出行的不同情況

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

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

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

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

2 相關(guān)工作

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

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

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

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

2.2 車輛行程時間估計(jì)

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

（1）基 于鏈路的行程時間估計(jì)

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

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

（2）基于路徑的行程時間估計(jì)

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

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

（3）基于軌跡的行程時間估計(jì)

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

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

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

3 問題定義

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

定義1 路網(wǎng)。路網(wǎng)表示為G=(N,E),其中N={n₁,n₂,……,n_m}表示所有路口的集合，E表示路口之間所有路段的集合，e_i,j∈E表示從路口n_i到路口n_j的一條路段。需要注意的是，每個路段都是有方向的，也就是說，e_i,j不同于路段e_j,i。定義2 攝像頭記錄。攝像頭記錄被定義為一個三元組(veh_id,cam_?j,ts?_j)，表示車輛veh_id在ts_j時刻經(jīng)過攝像頭cam_j。

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

由定義3可知，車輛軌跡由車輛經(jīng)過的所有攝像頭的時間序列構(gòu)成，

本文將歷史監(jiān)控?cái)z像頭數(shù)據(jù)中所有含有同一車輛veh_id的攝像頭記錄序列記為該車輛的車輛軌跡TR_id，其部分車輛軌跡記為Tr_id。所有車輛的軌跡集合記為TRs。

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

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

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

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

4.1 總體框架

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

圖2???總體框架

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

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

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

當(dāng)數(shù)據(jù)預(yù)處理完成之后，利用處理好的監(jiān)控?cái)?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）行程時間估計(jì)

給定起始點(diǎn)位置O(lon_s,lat_s)、結(jié)束點(diǎn)位置D(lon_e,lat_e)和出發(fā)時間ts，首先將起始點(diǎn)位置和結(jié)束點(diǎn)位置分別匹配到對應(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上獲取真實(shí)路網(wǎng)。根據(jù)定義1，一個路網(wǎng)包括路口集合以及路口之間的路段集合。通常來說，監(jiān)控?cái)z像頭被部署在鄰近路口處的位置，用來獲得所有經(jīng)過此路段的車輛信息。因此，通過攝像頭的位置信息（如經(jīng)度和緯度）將攝像頭映射到路網(wǎng)上，再匹配到相應(yīng)路口上，就能夠獲得車輛在路網(wǎng)上對應(yīng)的行駛記錄。

4.2.2 提取車輛軌跡

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

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)控?cái)?shù)據(jù)時根據(jù)攝像頭編號將攝像頭記錄存儲到對應(yīng)路口的攝像頭中。

一般情況下人的活動是以天為周期的，很多研究驗(yàn)證了這一點(diǎn)，相應(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可知，對于車輛veh_id的車輛軌跡Tr_id，由車輛veh_id和經(jīng)過時間ts_j可以唯一確定其經(jīng)過的攝像頭cam_j。此外，因?yàn)檐囕v軌跡是按時間排序的攝像頭記錄序列，還可以得到車輛veh_id在時間ts_j之后經(jīng)過的所有攝像頭以及對應(yīng)的經(jīng)過時間。因此，可以根據(jù)車輛軌跡的攝像頭記錄序列，建立根據(jù)車輛ID查找所經(jīng)過攝像頭的反向索引。

如圖4所示，對于車輛veh_id的一條車輛軌跡，，其中cam₁、cam₂、cam₃、cam₄分別匹配到路口n₁、n₂、n₃、n₄上，給定出發(fā)時間ts₁，可以得到車輛veh_id在時間ts₁經(jīng)過的攝像頭cam₁，以及在時間ts₁之后，車輛在時間ts₂、ts₃、ts₄分別經(jīng)過的攝像頭cam₂、cam₃、cam₄。

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

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

4.4 行程時間估計(jì)

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

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

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

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

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

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

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

如第10～16行所示，在確定了c_o和c_d之后，分別查詢c_o和c_d中各攝像頭包含的攝像頭記錄rec_o和rec_d，并得到在該時隙層中經(jīng)過起始點(diǎn)和結(jié)束點(diǎn)攝像頭的車輛集合Veh_o和Veh_d。然后，求出集合Veh_o和Veh_d的交集Veh_c，即起始路口和結(jié)束路口的攝像頭記錄中共同含有的車輛ID。

如第17～23行所示，得到共同車輛ID之后，根據(jù)反向索引，可以得到每輛車veh_id的部分車輛軌跡Tr?_id。這里，。Tr_id的起始攝像頭cam₁為c_o中的攝像頭，出發(fā)時間ts₁在ts確定的時隙層；結(jié)束攝像頭cam_n為c_d中的攝像頭，結(jié)束時間ts_n在t e預(yù)測的時隙層。軌跡Tr _id的行程時間Time_id為結(jié)束時間ts_n與出發(fā)時間ts₁的差值。

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

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

5 實(shí)驗(yàn)與結(jié)果

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

5.1 實(shí)驗(yàn)數(shù)據(jù)集

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

5.2 實(shí)驗(yàn)設(shè)置

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

5.2.1 對比算法

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

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

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

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

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

5.2.3 評估指標(biāo)

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

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

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

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

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

其中，表示算法對行程i的估計(jì)時間，

表示行程i的真實(shí)時間。

5.3 性能評估

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

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

各算法的平均相對誤差和中值相對誤差分別如圖5和圖6所示。從實(shí)驗(yàn)結(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。因?yàn)閷?shí)驗(yàn)采用的路網(wǎng)數(shù)據(jù)為城市路網(wǎng)的部分市區(qū)路網(wǎng)，查詢的起始點(diǎn)和結(jié)束點(diǎn)均在該部分市區(qū)路網(wǎng)內(nèi)，因此真實(shí)行程時間較短，絕對誤差較小。若將路網(wǎng)區(qū)域擴(kuò)大為監(jiān)控?cái)?shù)據(jù)覆蓋的整個城市區(qū)域，真實(shí)行程時間增長，那么各算法的時間差值擴(kuò)大，UTSD將更具優(yōu)勢。

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

圖8???各算法中值絕對誤差

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

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

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

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

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

圖9展示了本文所提方法在歷史數(shù)據(jù)天數(shù)為3~17天的平均相對誤差和中值相對誤差的變化情況。從圖9可以看出，在歷史數(shù)據(jù)天數(shù)為3天時，所提方法的平均相對誤差和中值相對誤差均最高，這可能是因?yàn)?天的歷史數(shù)據(jù)所含有的歷史車輛軌跡樣本不夠充足，形成的車輛軌跡不夠完整，以及存在一些噪聲數(shù)據(jù)，導(dǎo)致行程時間估計(jì)誤差較大。隨著歷史數(shù)據(jù)天數(shù)的不斷增加，本文所提方法的這兩種誤差不斷減小，這說明隨著歷史數(shù)據(jù)天數(shù)的增加，該方法能夠從歷史數(shù)據(jù)中查詢到更多符合查詢條件的歷史車輛軌跡，進(jìn)而更好地進(jìn)行路徑推薦和對應(yīng)行程時間的估計(jì)。當(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ù)為3~17天的平均查詢時間的變化情況。從圖10可以看出，隨著歷史數(shù)據(jù)天數(shù)的增加，算法的平均查詢時間也在增加，而且隨著天數(shù)的增加，平均查詢時間增加的幅度越來越大。這一方面是因?yàn)殡S著歷史數(shù)據(jù)數(shù)量的增加，讀取、查詢和處理數(shù)據(jù)的時間增大，進(jìn)而導(dǎo)致運(yùn)行時間增大；另一方面是因?yàn)楸疚乃岱椒ū旧淼乃惴◤?fù)雜度決定了算法隨歷史數(shù)據(jù)的增加所需要的運(yùn)行時間會不斷增加。

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

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

6 結(jié)束語

本文針對城市出行的時間估計(jì)問題，提出了一種基于城市交通監(jiān)控大數(shù)據(jù)的行程時間估計(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ù)查詢和行程時間估計(jì)的效率。通過在某省會城市的真實(shí)交通監(jiān)控?cái)?shù)據(jù)上進(jìn)行實(shí)驗(yàn)評估，驗(yàn)證了本文所提方法的有效性，且相比對比算法其準(zhǔn)確性有顯著的提升。

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

作者簡介

李文明（1997-），男，煙臺大學(xué)計(jì)算機(jī)與控制工程學(xué)院碩士生，主要研究方向?yàn)闀r空數(shù)據(jù)挖掘。

劉芳（1994-），女，煙臺大學(xué)計(jì)算機(jī)與控制工程學(xué)院碩士生，主要研究方向?yàn)榫植慨惓z測。

呂鵬（1995-），男，煙臺大學(xué)計(jì)算機(jī)與控制工程學(xué)院碩士生，主要研究方向?yàn)楦呔S數(shù)據(jù)異常檢測。

于彥偉（1986-），男，博士，中國海洋大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系副教授，中國計(jì)算機(jī)學(xué)會會員，主要研究方向?yàn)闀r空數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)、分布式計(jì)算。

聯(lián)系我們:

Tel:010-81055448

? ? ? ?010-81055490

? ? ? ?010-81055534

E-mail:bdr@bjxintong.com.cn?

http://www.infocomm-journal.com/bdr

http://www.j-bigdataresearch.com.cn/

轉(zhuǎn)載、合作：010-81055537

大數(shù)據(jù)期刊

《大數(shù)據(jù)（Big Data Research，BDR）》雙月刊是由中華人民共和國工業(yè)和信息化部主管，人民郵電出版社主辦，中國計(jì)算機(jī)學(xué)會大數(shù)據(jù)專家委員會學(xué)術(shù)指導(dǎo)，北京信通傳媒有限責(zé)任公司出版的期刊，已成功入選中文科技核心期刊、中國計(jì)算機(jī)學(xué)會會刊、中國計(jì)算機(jī)學(xué)會推薦中文科技期刊，并被評為2018年、2019年國家哲學(xué)社會科學(xué)文獻(xiàn)中心學(xué)術(shù)期刊數(shù)據(jù)庫“綜合性人文社會科學(xué)”學(xué)科最受歡迎期刊。

關(guān)注《大數(shù)據(jù)》期刊微信公眾號，獲取更多內(nèi)容

總結(jié)

以上是生活随笔為你收集整理的基于城市交通监控大数据的行程时间估计的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。