Spatio-temporal Association Rule Mining of Traffic Congestion in a Large-scale Road Network Based on Trajectory Data

doi:10.16182/j.issn1004731x.joss.22-0898

Abstract

Abstract:

A K neighbor-RElim (KNR) algorithm and a sequential KNbr-RElim (SKNR) algorithm are proposed to mine traffic congestion association rules and congestion propagation spatio-temporal association rules by vehicle trajectory data in a large-scale road network. The KNR algorithm extends the spatial topology constraint based on the RElim algorithm. The KNR can be used to mine the road links prone to congestion from the large-scale trajectory dataset in a large-scale road network and quantify the strength of association for congested road links. The SKNR algorithm expands the time dimension in the form of sliding window and can be applied for mining the congestion propagation phenomenon which is difficult to observe directly in a large-scale road network and tracing the path of congestion propagation. The algorithms are illustrated and verified by the empirical results of the Chengdu road network with vehicle trajectory data. The results show the effectiveness and robustness of the proposed algorithms.

Key words: data mining, association rules, congestion propagation, trajectory data, RElim algorithm

CLC Number:

TP301.6

Zhou Qifan, Liu Haixu, Dong Zhipeng, Xu Yin. Spatio-temporal Association Rule Mining of Traffic Congestion in a Large-scale Road Network Based on Trajectory Data[J]. Journal of System Simulation, 2024, 36(1): 260-271.

Figures/Tables 11

Fig. 1

Fig. 2

Fig. 3

Fig. 4

Fig. 5

Table 1

Fig. 6

Fig. 7

Fig. 8

Table 2

Fig. 9

References 20

1	Chandler R E, Herman R, Montroll E W. Traffic Dynamics: Studies in Car Following[J]. Operations Research, 1958, 6(2): 165-184.
2	Daganzo C F. The Cell Transmission Model: a Dynamic Representation of Highway Traffic Consistent with the Hydrodynamic Theory[J]. Transportation Research Part B: Methodological, 1994, 28(4): 269-287.
3	Richards P I. Shock Waves on the Highway[J]. Operations Research, 1956, 4(1): 42-51.
4	Long Jiancheng, Gao Ziyou, Ren Hualing, et al. Urban Traffic Congestion Propagation and Bottleneck Identification[J]. Science in China Series F: Information Sciences, 2008, 51(7): 948-964.
5	杨泳. 城市快速路交通拥堵形成、传播规律及消散控制策略研究[D]. 成都: 西南交通大学, 2014.
	Yang Yong. Study on Congestion Forming、Propagation Properties and Dissipation Control Strategies of Urban Expressway[D]. Chengdu: Southwest Jiaotong University, 2014.
6	Saberi M, Hamedmoghadam H, Ashfaq M, et al. A Simple Contagion Process Describes Spreading of Traffic jams in Urban Networks[J]. Nature Communications, 2020, 11(1): 1616.
7	Befekadu G K. Rare Event Simulation in a Dynamical Model Describing the Spread of Traffic Congestions in Urban Network Systems[M]//Bracken P, Uzunov D I. A Collection of Papers on Chaos Theory and Its Applications. Rijeka: IntechOpen, 2021.
8	韦伟. 基于实测数据的道路交通状态特征及拥堵传播规律分析方法[D]. 北京: 北京交通大学, 2017.
	Wei Wei. Analytical Method of Traffic Condition Characteristics and Congestion Propagation Rules Based on Practical Measured Data[D]. Beijing: Beijing Jiaotong University, 2017.
9	韦伟, 毛保华, 陈绍宽, 等. 基于当期事件识别的拥堵传播特征研究[J]. 交通运输系统工程与信息, 2016, 16(4): 165-170.
	Wei Wei, Mao Baohua, Chen Shaokuan, et al. Spatial Propagating Study of Urban Traffic Congestion Based on Current Event Recognition[J]. Journal of Transportation Systems Engineering and Information Technology, 2016, 16(4): 165-170.
10	欧吉顺. 异质性城市路网交通拥堵传播模式发现与可视化研究[D]. 南京: 东南大学, 2019.
	Jishun Ou. Traffic Congestion Propagation Pattern Recognition and Visualization for Heterogeneous Urban Networks[D]. Nanjing: Southeast University, 2019.
11	王启燕. 基于时间序列关联规则挖掘的交通拥堵预测研究[D]. 北京: 北京交通大学, 2020.
	Wang Qiyan. Traffic Congestion Prediction Model Based On Time Series Association Mining Rules[D]. Beijing: Beijing Jiaotong university, 2020.
12	谭星. 城市主干路交通状态评价与关联规则挖掘研究[D]. 哈尔滨: 哈尔滨工业大学, 2018.
	Tan Xing. Study on Traffic State Evaluation and Association Rules Mining on Arterial Roads[D]. Harbin: Harbin Institute of Technology, 2018.
13	Xu Lin, Yue Yang, Li Qingquan. Identifying Urban Traffic Congestion Pattern from Historical Floating Car Data[J]. Procedia - Social and Behavioral Sciences, 2013, 96: 2084-2095.
14	Li Qiang, Ge Qian, Miao Lixin, et al. Measuring Variability of Arterial Road Traffic Condition Using Archived Probe Data[J]. Journal of Transportation Systems Engineering and Information Technology, 2012, 12(2): 41-46.
15	Altintasi Oruc, Tuydes-Yaman Hediye, Tuncay Kagan. Detection of Urban Traffic Patterns From Floating Car Data (FCD)[J]. Transportation Research Procedia, 2017, 22: 382-391.
16	Xie Dongfan, Wang Meihong, Zhao Xiaomei. A Spatiotemporal Apriori Approach to Capture Dynamic Associations of Regional Traffic Congestion[J]. IEEE Access, 2020, 8: 3695-3709.
17	Han Jiawei, Kamber M, Pei Jian, 等. 数据挖掘: 概念与技术[M]. 范明, 孟小峰, 译. 3版. 北京: 机械工业出版社, 2012.
	Han Jiawei, Kamber M, Pei Jian, et al. Data Mining: Concepts and Techniques[M]. Translated by Fan Ming, Meng Xiaofeng. 3rd ed. Beijing: China Machine Press, 2012.
18	Borgelt Christian. Keeping Things Simple: Finding Frequent Item Sets by Recursive Elimination[C]//Proceedings of the 1st International Workshop on Open Source Data Mining: Frequent Pattern Mining Implementations. New York, NY, USA: Association for Computing Machinery, 2005: 66-70.
19	刘喜苹, 刘彩苹, 谭义红. 一个新的不需要候选集的挖掘关联规则算法—Relim算法的研究[J]. 计算技术与自动化, 2006, 25(2): 81-84.
	Liu Xiping, Liu Caiping, Tan Yihong. Study on a New Mining Association Rule Without Candidate Generation Relim Algorithm[J]. Computing Technology and Automation, 2006, 25(2): 81-84.
20	Kong Xiangfu, Yang Jiawen, Yang Zhongyu. Measuring Traffic Congestion with Taxi GPS Data and Travel Time Index[C]//Measuring Traffic Congestion with Taxi GPS Data and Travel Time Index. Reston, VA, USA: ASCE, 2015: 3751-3762.

ID	AB	conf_A	KULC	IR
1	(4548211352, 5530491877, 0), (7366295632, 4548211352, 0)	0.94	0.76	1.66
2	(671600440, 6224263690, 0), (6224263690, 6224263706, 0)	0.76	0.70	1.19
3	(5530491877, 4548211421, 0), (4548211352, 5530491877, 0), (7366295632, 4548211352, 0)	0.99	0.70	2.47
4	(963638438, 5535297029, 0), (5535297029, 1159223970, 0)	0.74	0.62	1.48
5	(963638438, 5535318948, 0), (5535318948, 5218240010, 0)	0.76	0.68	1.27
6	(1339701401,963638438,0), (4549993385,1339701401, 0)	0.73	0.71	1.07

ID	AB	conf_A	KULC	IR
1	(7366295632, 4548211352, 0, 1),(4548211352, 5530491877, 0, 2)	0.74	0.59	1.66
2	(7366295632, 4548211352, 0, 1), (5530491877, 4548211421, 0, 1), (4548211352, 5530491877, 0, 2)	0.76	0.53	2.47
3	(5530491877, 4548211421, 0, 1), (4548211352, 5530491877, 0, 2), (4548211352, 5530491877, 0, 3)	0.71	0.56	1.76
4	(7366295632, 4548211352, 0, 1), (4548211352, 5530491877, 0, 2), (4548211352, 5530491877, 0, 3)	0.73	0.53	2.26
5	(314622918, 672287905, 0, 1), (1159945489, 4548211258, 0， 1), (314622918, 672287905, 0, 2)	0.71	0.57	1.61
6	(1159945489, 4548211258, 0, 1), (314622918, 672287905, 0, 2), (314622918, 672287905, 0, 3)	0.72	0.59	1.61

[1]	Yanjiao Song, Jiayue Zhou, Longhao Wang, Jing Wu, Rui Li, Xiaoping Rui. Efficient HMM Map Matching Method Using R-tree and Trajectory Segmentation [J]. Journal of System Simulation, 2023, 35(2): 339-349.
[2]	Han Chi, Xiong Wei. Research on Assocoation Information Mining of Space Reconnaissance Equipment System Index [J]. Journal of System Simulation, 2021, 33(10): 2372-2380.
[3]	Ma Ning, Lin Shenglin. Simulation-based Effectiveness Evaluation for System-of-system under Multi-equipment Collaboration [J]. Journal of System Simulation, 2020, 32(6): 1155-1163.
[4]	Wu Jingbing, Tang Hanqing, Xu Jun. Analysis and Optimization of Combustion Characteristics of Cement Kiln Cooperatively Disposing Domestic Refuse [J]. Journal of System Simulation, 2020, 32(1): 35-43.
[5]	Lin Yugu, Wang Yan. Energy Efficiency Data Mining and Scheduling Optimization of Discrete Workshop [J]. Journal of System Simulation, 2019, 31(12): 2702-2711.
[6]	Lü Shengping, Yue Qiangsheng, Liu Tao. Optimization of Material Release for Printed Circuit Board Template Based on Data Mining [J]. Journal of System Simulation, 2018, 30(7): 2656-2665.
[7]	Cheng Yanyun, Bian Huisong, Bian Changsheng. Clustering Method Based on Graph Data Model and Reliability Detection [J]. Journal of System Simulation, 2018, 30(6): 2102-2109.
[8]	Zhang Mingzhi, Li Yi. Association Rules Analysis Method of Spatial Data Under MapReduce Framework [J]. Journal of System Simulation, 2018, 30(3): 840-845.
[9]	Chen Bing, Zhang Heng, Cheng Zekai, Dong Peng, Lin Chao. Mining and Validation of Attacking Behavior in the Robocup 2D Simulation [J]. Journal of System Simulation, 2018, 30(12): 4718-4726.