基于复杂城市道路网络的交通拥堵预测模型

刘 张，李 坚，王 超，蔡世民，唐 明，黄 琦，陈照辉(. 电子科技大学能源科学与工程学院 成都 673；2. 成都师范学院物理与工程技术学院 成都 630；3. 电子科技大学大数据研究中心 成都 673；.华为技术有限公司 成都 673；. 电子科技大学互联网科学中心 成都 673)



基于复杂城市道路网络的交通拥堵预测模型

刘 张1,2,3，李 坚1，王 超4，蔡世民5，唐 明5，黄 琦1，陈照辉1
(1. 电子科技大学能源科学与工程学院 成都 611731；2. 成都师范学院物理与工程技术学院 成都 611130；3. 电子科技大学大数据研究中心 成都 611731；4.华为技术有限公司 成都 611731；5. 电子科技大学互联网科学中心 成都 611731)

【摘要】随着城市交通的发展，道路网络越来越复杂，交通拥堵越来越严重，准确预测交通拥堵是城市缓堵保畅，提高城市交通管理能力关键技术之一。传统马尔可夫预测模型中的单变量模型只能解决单个时间序列上的交通预测问题，一阶模型仅考虑了相邻时间点数据之间的影响，高阶多变量马尔可夫模型的预测精度不足，难以解决复杂城市道路网络交通拥堵预测的问题。对此，文章提出了一种添加调节项的高阶多变量马尔可夫模型(AAT-HO3M)，证明了模型的收敛性，进行了参数估计，并参考城市道路交通运行评价指标体系，对城市拥堵进行预测分析。通过预测试验证明，AAT-HO3M预测精度高于传统高阶多变量马尔可夫模型和改进高阶多变量马尔可夫模型。预测效率优于改进的高阶多变量马尔科夫模型。

关 键 词交通拥堵; 预测精度; 高阶多变量马尔可夫模型; 交通流

A Prediction Model for Traffic Congestion in Complex Urban Road Networks

LIU Zhang1,2,3, LI Jian1, WANG Chao4, CAI Shi-min5, TANG Ming5, HUANG Qi1, and CHEN Zhao-hui1
(1. School of Energy Science and Engineering, University of Electronic Science and Technology of China Chengdu 611731; 2. College of Physics and Engineering, Chengdu Normal University Chengdu 611130; 3. Big Data Research Center, University of Electronic Science and Technology of China Chengdu 611731; 4. Huawei Technologies Co. Ltd. Chengdu 611731; 5. Web Science Center, University of Electronic Science and Technology of China Chengdu 611731)

Abstract Some traditional Markov prediction models such as single variable model can only solve traffic on a single time series prediction problem. The first-order model only considers the influence between adjacent time point data, but the prediction precision of the higher-order multivariable Markov model needs to be improved. These models are difficult to solve traffic congestion prediction problem in complex urban road networks. This paper proposes a add adjustment term to the higher-order multivariable Markov model (AAT-HO3M) with convergence and estimation of the parameters. This model is applied in traffic congestion prediction. The results of the predictions illustrate that the prediction precisions of AAT-HO3M are higher than the traditional higher-order multivariable Markov model and improved multivariable Markov model, and the time overheads of AAT-HO3M are less than the improved multivariable Markov model.

Key words traffic congestion; prediction precision; higher-order multivariate Markov model; traffic flow

随着社会经济的发展，机动车数量增多，城市道路网络日趋复杂，城市交通压力越来越大。为了缓解交通拥堵，需要对道路上的机动车平均行驶速度(交通流速度)进行准确、高效的分析和预测。预测交通流速度的传统方法比较多，如：多元线性回归模型[1]理论成熟，容易实现，但适应性差、容易受实际交通状况的影响；ARIMA模型[2]虽然能够反映交通流的非线性特征，但是当交通流状态不确定性较强时，模型的运算量较大；历史平均法模型[3]的预测速度快，但是无法体现交通流状态的不确定性与非线性特征；人工神经网络模型[4]虽然具有较好的学习能力，但是需要大量的数据对模型进行训练，当数据缺失时，预测效果较差。

马尔可夫模型自从被提出以来，就被广泛应用于销售需求预测[5-6]、信用和金融预测[7]等领域。为了提高模型的预测精度，文献[8-19]在对多个相互关联的马尔可夫链构成的马尔可夫模型进行了很多相关研究。同时，还有很多学者也为此做出了大量贡献[20-26]。高阶马尔可夫模型[27]在短期交通流预测中取得了一定的效果，但由于未考虑其他多条道路交通流状态数据对被预测道路的影响，其预测的可靠性值得商榷。

在实际城市交通中，道路网络复杂，各条道路之间错综影响，一条道路某时刻的交通状态，不仅和该条道路前多个时刻的交通状态有关，而且与其他多条道路的交通状态有关。使用高阶多变量马尔可夫模型，既反应了各相关道路交通数据列之间的关联关系，又考虑了一条道路各时间点数据之间的相互影响，这种混合预测的模式，更加接近实际情况，因而做出的预测更加符合现实，预测精度更高。在此基础上，本文提出了一种添加调节项的高阶多变量马尔可夫模型，并将该模型用于城市道路拥堵预测，同时在预测效率、预测精度方面同传统高阶多变量马尔可夫模型和改进马尔可夫模型进行了比较。预测试验证明，AAT-HO3M预测精度高于传统高阶多变量马尔可夫模型和改进高阶多变量马尔可夫模型。预测效率优于改进的高阶多变量马尔科夫模型。

1 预测模型

1.1 一阶马尔可夫模型

则一阶马尔可夫模型可以表示为：

1.2 传统高阶多变量马尔可夫模型

传统高阶多变量马尔可夫模型[29]既考虑了多个数据列之间的相互影响，又反应了一个数据列各时间点之间的相互影响，因而预测效果比一阶马尔可夫模型更好，其模型如下：

同时满足：

1.3 改进高阶多变量马尔可夫模型

改进高阶多变量马尔可夫模型[7]在传统高阶多变量马尔可夫模型的基础上添加了一个负向调节，使得预测精度更高，其模型为：

1.4 添加调节项的高阶多变量马尔可夫模型(AATHO3M)

改进高阶多变量马尔可夫模型所加入的负向调节为固定值，其调节能力有限，为了进一步优化预测效果，本文对改进高阶多变量马尔可夫模型进行改造，通过添加多个调节参数，改变负向调节权重和单位规范因子权重，通过正负双向逼近，使得模型精度更好，预测效率高。AAT-HO3M可表示为：

式中，s( s≥ 2)为分类数据列的列数；模型阶数为n，是第j列t +1时刻的状态概率分布；是第k列t− h+1时刻的状态概率分布；是第k列时刻的状态转移到第j列t +1时刻状态的h步转移概率矩阵；为带有调节因子的负向调节项；e为元素为1的列向量；βe为单位规范因子权重；为了归一化，令m= s× n。为了保障能够双向逼近，应有γ>0，则

并满足：

1.4.1 模型收敛性证明

若有：

则AAT-HO3M表示为：

即：

其中，当j= k时，

当j≠ k时，

且有：

式(9)经过t +1次迭代，有：

因为矩阵Λ、Ζ中的任意元素都大于零，故有：

进而有：

根据引理1有：

则式(14)是收敛的，进而有AAT-HO3M是收敛的。结论得证。

1.4.2 模型参数估计

规范化后，得转移频率矩阵Ph(i , j )，可记为：

满足式(24)。

为方便计算，把这一优化问题转化为线性规划问题，如式(25)所示，满足条件如式(26)。

满足：

2 道路拥堵预测

2.1 道路及数据选取

选取中国西南C城市中一交叉路口的3条主干道2014年3月前3周的周六、周日9—21点每隔1小时的交通流速度数据，来测试AAT-HO3M的有效性。道路交通示意图如图1所示。

图1　道路交通示意图

2.2 道路拥堵状态划分

城市道路交通运行评价指标体系[31]中对城市中快速路、主干路、次干路、支路的状态划分进行了详细规定，如表1所示。

表1　路段交通运行等级划分 km/h

参考表1标准，结合C城市路网实际情况，本文将路网拥堵状态分为3个等级，分别为拥堵状态(快速路平均行驶速度低于20 km/h，主干路低于15 km/h，次干路和支路低于10 km/h)、畅通状态(快速路平均行驶速度高于50 km/h，主干路高于35 km/h，次干路和支路高于25 km/h)和缓行状态(车速介于拥堵和畅通状态之间)。在此分级标准之下，对3条道路按照主干路处理，其状态定义如表2所示。

表2　道路状态定义

2.3 拥堵预测

在此利用AAT-HO3M建立道路拥堵预测模型。先由式(20)估计出转移概率矩阵再令β=1，通过AAT-HO3M转化成的线性规划问题如式(26)，求得。取阶数为3阶，得到AAT-HO3M如式(26)所示。

同理，本文将3条道路的状态数据列用于传统的高阶多变量马尔可夫模型和改进高阶多变量马尔可夫模型的行预测。比较3种模型的预测效果，所用时间和均方误差如表3所示。

表3中，Time为运算时间，MSE(mean squared error)[32]为均方误差值。AAT-HO3M与传统高阶多变量马尔可夫模型相比，当阶数n =1，AAT-HO3M的 MSE值为10.267 4，小于传统高阶多变量马尔可夫模型的12.425 1，随着阶数的增高，当n =2,3时，AAT-HO3M的预测误差分别比传统高阶多变量马尔可夫模型小2.190 0和2.991 1。

AAT-HO3M与改进高阶多变量马尔可夫模型相比，其运算效率和预测精度均有提高，在运算效率上，当n =1,2,3时，AAT-HO3M的运算时间分别为0.015 6 s、0.015 6 s、0.031 2 s，比改进高阶多变量马尔可夫模型在各阶所用时间少0.062 4 s，0.015 6 s，0.015 6 s。在预测精度上，AAT-HO3M在n =1,2,3时，其预测误差均比改进的高阶多变量马尔可夫模型要小。

AAT-HO3M随着阶数的增加，如果当n =1,2,3时，其预测误差MSE值分别为10.267 4，10.234 9，9.433 9，依次减少。由此可见通过添加系数项，可以提高模型的预测精度，通过提高阶数可进一步减少预测误差。

表3　模型预测效果对比

下面进一步研究AAT-HO3M在不同参数下的预测精度变化情况。

当阶数n =1时：

AAT-HO3M预测误差MSE随参数γ、β的变化曲线如图2所示。在图2中，取δ=0.2，如图2a所示，当γ=5.1，β=0.5时，预测误差最小，为MES = 10.277 4。取δ=0.7，如图2b所示，当时，预测误差最小，为MES = 10.267 4。取δ=1.2，如图2c所示，当γ=4.1，时，预测误差最小，为MES = 10.465 8。取如图2d所示，当γ=5.1，β=1.5时，预测误差最小，为MES = 11.224 5。由此可见当阶数n =1时，γ=0.7，β=5.1，δ=0.5，AAT-HO3M的预测误差最小，预测效果最好。

图2　AAT-HO3M在n=1时预测误差随参数变化图

当阶数n =2时：

AAT-HO3M预测误差MSE随参数γ、β的变化曲线如图3所示。在图3中，取δ=0.2，如图3a所示，当γ=5.1，β=0.5时，预测误差最小，为MES = 10.244 9。取δ=0.7，如图3b所示，当时，预测误差最小，为MES = 10.234 9。取δ=1.2，如图3c所示，当γ=4.1，时，预测误差最小，为MES = 10.275 1。取如图3d所示，当γ=5.1，β=0.5时，预测误差最小，为MES = 11.464 1。由此可见当阶数的预测误差最小，预测效果最好。

图3　AAT-HO3M在n=2时预测误差随参数变化图

当阶数n =3时：

AAT-HO3M预测误差MSE随参数γ、β的变化曲线如图4所示。取δ=0.2，如图4a所示，当γ=5.1，时，预测误差最小，为MES = 10.244 9。取如图4b所示，当γ=5.1，β=0.5时，预测误差最小，为MES = 9.433 9。取δ=1.2，如图4c所示，当γ=1.1，β=0.5时，预测误差最小，为MES = 11.185 1。取δ=0.2，如图4d所示，当时，预测误差最小，为MES = 10.277 4。由此可见当阶数n =3时，δ=0.7，AAT-HO3M的预测误差最小，预测效果最好。

图4　AAT-HO3M在n=3时预测误差随参数变化图

进一步，给出AAT-HO3M在不同阶数下，取最优参数时，计算时间变化趋势如图5所示，预测精度变化趋势如图6所示。

图5　AAT-HO3M在不同阶数下计算时间变化趋势图

图6　AAT-HO3M在不同阶数下预测精度变化趋势图

从以上两幅图可以看到随着预测模型阶数的增加，预测精度提高，计算成本变高。

综合图2～图6可知，通过调节AAT-HO3M的参数来提升预测精度是有效的。

3 结 束 语

本文提出的基于复杂城市道路网络的AAT-HO3M既反映了一条道路各时间点数据之间的相互影响，又考虑了各相关道路数据列之间的关联关系，这种混合预测的模式，更加接近城市交通网络的复杂情况，因而做出的预测更加符合现实。本文在改进模型的基础上引入多个参数，使得预测精度更高，预测效率更优。模型还可以通过调节参数，进一步提高模型预测精度。由于论文只涉及3周数据，实验数据集较小，但在实际应用中，可以根据不同情况通过收集更多的数据来验证预测模型的预测精度和预测效率，这不影响模型的实用价值。AAT-HO3M即可以用于复杂交通路口各相关道路的拥堵预测，也可以用于在整个交通网络下对各条道路的拥堵预测。这一研究结果为城市道路交通拥堵预测提供了一种新的方法。

本文研究工作得到成都师范学院科研项目(CS14ZB02)的支持，在此表示感谢。

参 考 文 献

[1] RICE J, ZWETE V. A simple and effective method for predicting travel times on freeways[J]. IEEE Transactions on Intelligent Transportation Systems, 2004, 5(3): 200-207.

[2] HORVITZE J, APACIBLE J, SARIN R, et al. Prediction, expectation, and surprise: Methods, designs, and study of a deployed traffic forecasting service[C]//Proceedings of the Twenty-First Conference on Uncertainty in Artificial Intelligence. Edinburgh: [s.n.], 2005: 275-283.

[3] STEPHANEDES Y J, MICHALOPOULOS P G, PLUM R A. Improved estimation of traffic flow for real-time control[C]// Proceedings of The 60th Annual Meeting of the Transportation Research Board. Washington: Transportation Research Board, 1981: 28-39.

[4] DOUGHERTY M S, KIRBYHR, BOYLE R D. The use of neural networks to recognizeand predict trafficcongestion[J]. Trafic Engineering and Control, 1993, 34(6): 311-314.

[5] CHINGWK, FUNG E S, NG MK. A multivariate Markov chain model for categorical data sequences and its applications in demand predictions[J]. IMA Journal of Management Mathematics, 2002,13(3): 187-199.

[6] CHING W K, FUNG E S, NG MK. Higher-order Markovchain models for categorical data sequences[J]. Naval Research Logistics, 2004, 51(4): 557-574.

[7] CHING W K, SIU T, LI L. An improved parsimonious multivariate Markov chain model for credit risk[J]. Journal of Credit Risk, 2009, 5(1): 1-25.

[8] CHING W K. Iterative methods for queuing and manufacturing systems[M]. London: Springer, 2001.

[9] CHING W K. A higher-order Markov model for the newsboy’s problem[J]. Journal of Operational Research Society, 2003, 54: 291-298.

[10] CHING W K, FUNG E S, NG MK. Higher-order hidden Markov models with applications to DNA sequences[C]// Intelligent Data Engineering and Automated Learning. Heidelberg: Springer, 2003: 535-539.

[11] CHING W K, NG MK, WONG K. Hidden Markov models and their applications to customer relationship management[J]. IMA Journal of Management Mathematics, 2004, 15(1): 13-24.

[12] CHING W K, SCHOLTES S, ZHANG S. Numericalalgorithms for dynamic traffic demand estimation between zones in a network[J]. Engineering Optimization, 2004, 36(3): 379-400.

[13] SIU T K, CHING W K, FUNG E S, et al. Extracting information from spot interest rates and credit ratings using double higher-order hidden Markov models[J]. Computational Economics, 2005, 26(3): 69-102.

[14] CHING W K, ZHANG S, NG MK. An approximation method for solving the steadys-tate probability distribution of probabilistic Boolean networks[J]. Bioinformatics, 2007, 23(12): 1511-1518.

[15] CHING WK, FUNG ES, NG MK, et al. Interactive hidden Markov models and their applications[J]. IMA Journal of Management Mathematics, 2007, 18(1): 85-97.

[16] CHING W K, SIU T, LI L. Modeling default data via an interactive hidden Markov model[J]. Computational Economics, 2009, 34(1): 1-19.

[17] GU J, CHING WK, SIU T. On infectious models for dependent default risk[C]//The 4th In-ternational Joint Conference on Computational Sciences and Optimization. Yunnan: [s.n.], 2011: 1196-1200.

[18] CHENX, CHING W K, CHEN X S, et al. Construction of probabilistic Boolean networks from a prescribed transition probability matrix: a maximum entropy rate approach[J]. East Asian Journal of Applied Mathematics, 2011, 1: 132-154.

[19] CHING W K, CHEN X, CONG Y, et al. A maximum entropy rate approach for the construction of probabilistic Boolean networks from a prescribed transition probability matrix[J]. East Asian Journal of Applied Mathematics, 2011(1): 132-154.

[20] KIJIMA M, MUROMACHI Y. Evaluation of credit risk of a portfolio with stochastic interest rate and default processes[J]. Journal of Risk, 2000(3): 5-36.

[21] LI D. On default correlation: a copula function approach[J]. Journal of Fixed Income, 2000, 9(4): 43-54.

[22] FREY R, MCNEIL A J. Dependent defaults in models of portfolio credit risk[J]. Journal of Risk, 2003(6): 59-92.

[23] DUFFIE D, ECKNER A, HOREL G, et al. Frailty correlated default[J]. The Journal of Finance, 2009, 64(5): 2089-2123.

[24] XI X J, MAMON R, DAVISON M. A higher-order hidden Markov chain-modulated model for asset allocation[J]. Journal of Mathematical Modelling and Algorithms in Operations Research, 2014, 13(1): 59-85.

[25] GIORDANO J O, KALANTARI A S, FRICHE P M, et al. A daily herd Markov-chain model to study the reproductive and economic impact of reproductive programs combining timed artificial insemination and estrus detection[J]. Journal of Dairy Science, 2012, 95(9): 5442-5460.

[26] HUANG X, XU N, BIGAARD S. A class of Markov chain models for average run length computations for autocorrelatedprocesses[J]. Communications in Statistics-Simulation and Computation, 2013, 42(7): 1495-1513.

[27] QIANG Y G, MING H J, SHUI Z C, et al. Short-term traffic flow forecasting based on Markov chain model[C]// Intelligent Vehicles Symposium. Columbus: [s.n.], 2003: 208-212.

[28] WANG C, HUANG T Z. A new improved parsimonious multivariate Markov chain model[J]. Journal of Applied Mathematics, 2013(4): 924-970.

[29] CHING W K, NG MK, FUNG E S. Higher-order multivariate Markov chains and their applications[J]. Linear Algebra and its Applications, 2008, 428: 492-507.

[30] YONG Z Y, WANG C L. A concept of nonlinear block diagonal dominance[J]. Journal of Computational and Applied Mathematics, 1997, 83: 1-10.

[31] 北京市质量技术监督局. DB11/T 785-2011. 城市道路交通运行评价指标体系[S]. 北京: 中国标准出版社, 2011. Beijing Bureau of Quality and Technical Supervision. DB11/T 785-2011. Urban road traffic performance index[S]. Beijing: Standards Press China, 2011.

[32] NIELSEN T S, JOENSEN A. A new referencefor wind powerforecasting[J]. Wind Energy, 1998(1): 29-34.

编 辑 蒋 晓

·通信与信息工程·

作者简介：刘张(1979 − )，男，博士生，主要从事交通大数据挖掘方向的研究.

基金项目：国家自然科学基金(61304177)；四川省教育厅科研项目(15ZB0345)

收稿日期：2015 − 06 − 24；修回日期： 2015 − 08 − 25

中图分类号U1

文献标志码A

doi:10.3969/j.issn.1001-0548.2016.01.002