基于城市交通监控大数据的行程时间估计

doi:10.11959/j.issn.2096-0271.2021008

摘要/Abstract

摘要：

随着智慧交通的发展，越来越多的监控摄像头被安装在城市道路路口，这使得利用城市交通监控大数据进行车辆行程时间估计和路径查询成为可能。针对城市出行的行程时间估计问题，提出一种基于城市交通监控大数据的行程时间估计方法UTSD。首先，将交通监控摄像头映射到城市路网，并根据交通监控数据记录构建有向加权的城市路网图；然后，针对行程时间估计，构建时空索引和反向索引结构，时空索引用于快速检索所有车辆的摄像头记录，反向索引用于快速获取每辆车辆的行程时间和经过的摄像头轨迹，这两个索引大大提升了数据查询和行程时间估计的效率；最后，基于构建的索引，给出一种有效的行程时间估计和路径查询方法，根据出发时间、出发地和目的地，在时空索引结构上匹配出发地与目的地共有的车辆，再利用反向索引，快速获得行程时间估计与车辆路线。使用某省会城市的真实交通监控大数据进行实验评估，所提方法UTSD的准确率比基于有向图的Dijkstra最短路径算法和百度算法分别提高了65.02%和40.94%，且UTSD在以7天监控数据作为历史数据的情况下，平均查询时间低于0.3 s，验证了所提方法的有效性和高效性。

关键词: 城市交通监控大数据, 时空索引结构, 行程时间估计, 路线推荐

Abstract:

With the development of intelligent transportation, more and more surveillance cameras are deployed at the intersections of urban roads, which makes it possible to use the urban traffic surveillance data to estimate the vehicle travel time and query the route. Aiming at the problem of urban travel time estimation, a travel time estimation method based on the urban traffic surveillance data was proposed, which is called UTSD. Firstly, the traffic surveillance cameras were mapped into the urban road network, and a directed weighted urban road network graph was constructed based on traffic monitoring data recording. Secondly, a spatio-temporal index and a reverse index structure were built for travel time estimation, the former was used to quick search the camera records of all vehicles, and the latter was used to fast obtain the travel time and the passing camera trajectory of each vehicle. These two indexes significantly improved the efficiency of data query and travel time estimation. Finally, based on the constructed indexing structures, an effective travel time estimation and path query method was given. According to the departure time, origin and destination, the vehicles with the same origin and destination were matched on the spatio-temporal index structure, and then the reverse index was used to quickly obtain the travel time estimate and vehicle route. Using the real traffic monitoring big data of a provincial capital city for experimental evaluation, compared with Dijkstra shortest path algorithm based on directed graph and Baidu algorithm, the accuracy rate of the proposed method UTSD is improved by 65.02% and 40.94%, respectively. In addition, the average query time of UTSD is less than 0.3 s when the 7-day monitoring data is used as historical data, which verifies the effectiveness and efficiency of the proposed method.

Key words: urban traffic surveillance data, spatio-temporal index structure, travel time estimation, route recommendation

中图分类号:

TP391

李文明, 刘芳, 吕鹏, 于彦伟. 基于城市交通监控大数据的行程时间估计[J]. 大数据, 2021, 7(1): 107-123.

Wenming LI, Fang LIU, Peng LYU, Yanwei YU. Travel time estimation based on urban traffic surveillance data[J]. Big Data Research, 2021, 7(1): 107-123.

图/表 12

图1

表1

图2

图3

图4

图5

图6

图7

图8

表2

图9

图10

参考文献 35

[1]	刘晓波, 蒋阳升, 唐优华 ,等. 综合交通大数据应用技术的发展展望[J]. 大数据, 2019,5(3): 55-68.
	L IU X B , JIANG Y S , TANG Y H ,et al. Development prospect of integrated transportation big data application technology[J]. Big Data Research, 2019,5(3): 55-68.
[2]	WANG Y , ZHENG Y , XUE Y . Travel time estimation of a path using sparse trajectories[C]// The 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:ACM Press, 2014: 25-34.
[3]	BECKMANN N , KRIEGEL H P , SCHNEIDER R ,et al. The R*-tree: an efficient and robust access method for points and rectangles[C]// The 1990 ACM SIGMOD International Conference on Management of Data. New York: ACM Press, 1990: 322-331.
[4]	ZHONG R C , LI G L , TAN K L ,et al. G-tree: an efficient index for KNN search on road networks[C]// The 22nd ACM International Conference on Information ＆amp;Knowledge Management. New York: ACM Press, 2013: 39-48.
[5]	KAMEL I , FALOUTSOS C . Hilbert R-tree:an improved R-tree using fractals[R]. 1993.
[6]	PFOSER D , JENSEN C S , THEODORIDIS Y . Novel approaches to the indexing of moving object trajectories[C]// The 26th International Conference on Very Large Data Bases. [S.l.:s.n.], 2000: 395-406.
[7]	TAO Y F , PAPADIAS D . Efficient historical R-trees[C]// The 13th International Conference on Scientific and Statistical Database Management. Piscataway: IEEE Press, 2001: 223-232.
[8]	WANG L H , ZHENG Y , XIE X ,et al. A flexible spatio-temporal indexing scheme for large-scale GPS track retrieval[C]// The 9th International Conference on Mobile Data Management. Piscataway:IEEE Press, 2018: 1-8.
[9]	CHAKKA V P , EVERSPAUGH A C , PATEL J M . Indexing large trajectory data sets with SETI[C]// The 2003 CIDR Conference. [S.l.:s.n.], 2003: 75-86.
[10]	FINKEL R A , BENTLEY J L . Quad trees a data structure for retrieval on composite keys[J]. Acta Informatica, 1974,4(1: 1-9.
[11]	BENTLEY J L . Multidimensional binary search trees used for associative searching[J]. Communications of the ACM, 1975,189: 509-517.
[12]	JENSEN C S , LIN D , OOI B C . Query and update efficient B+-tree based indexing of moving objects[C]// The 30th International Conference on Very Large Data Bases. [S.l.:s.n.], 2004: 768-779.
[13]	COMER D . Ubiquitous B-tree[J]. ACM Computing Surveys, 1979,11(2): 121-137.
[14]	ZOBEL J , MOFFAT A , RAMAMOHANARAO K . Inverted files versus signature files for text indexing[J]. ACM Transactions on Database Systems, 1998,23(4): 453-490.
[15]	WU C H , HO J M , LEE D T . Traveltime prediction with support vector regression[J]. IEEE Transactions on Intelligent Transportation Systems, 2004,5(4): 276-281.
[16]	CHEN H , RAKHA H A , MCGHEE C C . Dynamic travel time prediction using pattern recognition[C]// The 20th World Congress on Intelligent Transportation Systems. [S.l.:s.n.], 2013.
[17]	HOFLEITNER A , HERRING R , ABBEEL P ,et al. Learning the dynamics of arterial traffic from probe data using a dynamic Bayesian network[J]. IEEE Transactions on Intelligent Transportation Systems, 2012,13(4): 1679-1693.
[18]	ZHAN X Y , HASAN S , UKKUSURI S V ,et al. Urban link travel time estimation using largescale taxi data with partial information[J]. Transportation Research Part C: Emerging Technologies, 2013,33: 37-49.
[19]	ZHANG F M , ZHU X Y , HU T ,et al. Urban link travel time prediction based on a gradient boosting method considering spatiotemporal correlations[J]. ISPRS International Journal of Geo-Information, 2016,5(11): 201.
[20]	NIU X G , ZHU Y , ZHANG X N . DeepSense:a novel learning mechanism for traffic prediction with taxi GPS traces[C]// 2014 IEEE Global Communications Conference. Piscataway: IEEE Press, 2014: 2745-2750.
[21]	RAHMANI M , JENELIUS E , KOUTSOPOULOS H N . Route travel time estimation using low-frequency floating car data[C]// The 16th International IEEE Conference on Intelligent Transportation Systems (ITSC 2013). Piscataway: IEEE Press, 2013: 2292-2297.
[22]	CHEN M , CHIEN S I J . Dynamic freeway travel-time prediction with probe vehicle data: link based versus path based[J]. Transportation Research Record, 2001,1768(1): 157-161.
[23]	JIANG M Y , ZHAO T Q . Vehicle travel time estimation by sparse trajectories[C]// 2019 IEEE 43rd Annual Computer Software and Applications Conference (COMPSAC). Piscataway: IEEE Press, 2019: 433-442.
[24]	KINGMA D P , BA J . Adam: a method for stochastic optimization[J]. arXiv preprint, 2014, arXiv:1412.6980..
[25]	LI Y , GUNOPULOS D , LU C W ,et al. Urban travel time prediction using a small number of GPS floating cars[C]// The 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. New York: ACM Press, 2017: 1-10.
[26]	WANG H J , TANG X F , KUO Y H ,et al. A simple baseline for travel time estimation using large-scale trip data[J]. ACM Transactions on Intelligent Systems and Technology, 2019,10(2): 1-22.
[27]	JIANG Y J , LI X ,et al. Travel time prediction based on historical trajectory data[J]. Annals of GIS, 2013,19(1): 27-35.
[28]	赖永炫, 杨旭, 曹琦 ,等. 一种基于Gradient Boosting的公交车运行时长预测方法[J]. 大数据, 2019,5(5): 58-78.
	LAI Y X , YANG X , CAO Q ,et al. A bus running length prediction method based on Gradient Boosting[J]. Big Data Research, 2019,5(5): 58-78.
[29]	YUAN H T , LI G L , BAO Z F ,et al. Effective travel time estimation: when historical trajectories over road networks matter[C]// The 2020 ACM SIGMOD International Conference on Management of Data. New York: ACM Press, 2020: 2135-2149.
[30]	DING Y C , LI Y H , ZHOU X ,et al. Sampl ing big trajectory data for traversal trajectory aggregate query[J]. IEEE Transactions on Big Data, 2018,5(4): 550-563.
[31]	YUAN J , ZHENG Y , ZHANG C Y ,et al. T-drive: driving directions based on taxi trajectories[C]// The 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems. New York: ACM Press, 2010: 99-108.
[32]	HAKLAY M , WEBER P . OpenStreetMap:user-generated street maps[J]. IEEE Pervasive Computing, 2008,7(4): 12-18.
[33]	LI Z H , WANG J J , HAN J W . Mining event periodicity from incomplete observations[C]// The 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:ACM Press, 2012: 444-452.
[34]	LI Z H , WANG J J , HAN J W . ePeriodicity:mining event periodicity from incomplete observations[J]. IEEE Transactions on Knowledge and Data Engineering, 2015,27(5): 1219-1232.
[35]	NOTO M , SATO H . A method for the shortest path search by extended Dijkstra algorithm[C]// The 2000 IEEE International Conference on Systems, Man and Cybernetics. Piscataway: IEEE Press, 2000: 2316-2320.

符号	含义
lon_s、lat_s	起始点位置经度、纬度
lon_e、lat_e	结束点位置经度、纬度
veh_id	车辆ID
n_i	路网中的路口节点
n_o	起始点位置匹配到的路口节点
n_d	结束点位置匹配到的路口节点
ts	车辆的出发时间
te	车辆的结束时间
Time	路径对应的行程时间
Path_topn	最短路径对应的车辆轨迹集合

UTSD				最短路径算法	百度算法
1天	3天	5天	7天	最短路径算法	百度算法
3.17×10^-2	9.61×10^-2	1.83×10^-1	2.98×10^-1	1.56×10^-4	1.45×10^-2