隐马尔可夫模型的道路拥堵时间预测

张绪冰，谢雨飞

北京建筑大学 电气与信息工程学院，北京 100044

城市道路交通问题是我国致力解决的社会难题之一，根据相关数据显示，我国一线城市的机动车保有量在近十年来已经突破七位数量级，并每年保持17%左右的增长速度，尤其是小汽车的增长更加明显，给交通系统带来了巨大负担。在拥堵高峰期，北京道路上车辆通行时间剧增，每年有近25 小时损失在道路拥堵当中。道路拥堵问题日益严重，社会面临巨大的挑战。道路拥堵问题不仅增加了发生交通事故的概率，甚至会让自然环境变得越来越糟。因此，道路拥堵问题急需得到改善，人们应算好道路拥堵时间而合理安排出行，减轻交通压力。

目前，针对交通预测的理论已有运用贝叶斯预测模型[1]、卡尔曼滤波模型[2]、小波模型等研究方法。例如，杨文忠等人将时间序列预测模型应用到道路交通的模型中，实验结果与实际的状态非常接近，得到了很好的应用[3]；Patra等人以卡尔曼滤波模型为理论基础提出了卡尔曼滤波预测模型[4-5]，该模型精度较高，能够处理平稳的数据，但仍为线性模型；韦凌翔等人在ARIMA模型上研究了交通流预测方法在短时区间道路中的应用[6-8]，在该模型上针对短时交通的流量问题分别研究了该模型在城市道路中的应用和自适应预测模型中的应用；胡枫利用马尔可夫模型与小波模型的组合对交通流进行预测[9]。然而，这些方法都存在一些不足，均未从数据的角度对交通流进行预测，对其特性研究得不够深入。另外，这些方法预测的模型为线性模型，对于非线性的真实道路交通情况，预测的准确度不够。

本文基于隐马尔可夫模型对道路拥堵时间进行预测，并且分析出当前时间段的最优出行路线。隐马尔可夫链对于预测问题、选择最优路线有着强大的能力。通过训练集获取并分析道路实时拥堵时间来建立对应的隐马尔可夫模型，从而预测下一时间段的道路拥堵时间，分析最优路径。并且对韦尔奇算法进一步改进，增加研究某一时刻的前n时刻数据，改善算法，使得训练集参数与实际更接近，预测精度更高，适用能力更强大。

1 交通拥堵时间的因素分析

一般来说，影响道路交通拥堵的因素主要有气温、能见度、行驶高峰期、交通事故发生情况等。根据“综合交通出行大数据开放云平台”的数据显示，这些因素与车辆通行时间密切相关。

天气温度与车辆行程时间的关系如表1 所示。随气温的不断升高，在10～25 ℃时以及气温在35 ℃以上，道路上车辆的行程时间呈正增长的趋势，行程时间增长明显，进而道路拥堵时间增加。因此，在温度较为适宜出行和不适宜出行的天气温度情况下，道路拥堵时间长。

表1 天气温度与车辆通行时间的关系Table 1 Relationship between weather temperature and vehicle travel time

能见度与车辆行程时间的关系如表2 所示。随着能见度的增长，道路拥堵时间明显降低。可见，能见度对于道路拥堵时间的影响呈负相关，即能见度越低，拥堵时间越长。

表2 能见度与车辆通行时间的关系Table 2 Relationship between visibility and vehicle travel time

交通事故发生情况与车辆行程时间的关系如表3所示。在发生交通事故的情况下，随着交通事故数量增长，道路拥堵时间明显增加。因此，交通事故的发生对于道路拥堵时间的影响呈正相关，即事故发生且次数多，拥堵时间越长。

表3 交通事故数量与车辆通行时间的关系Table 3 Relationship between number of traffic accidents and vehicle travel time

时间段与车辆行程时间的关系如表4 所示。在早7：00—9：00 和晚16：00—20：00 两个早晚高峰时间段内，车辆通行时间明显增加，拥堵时间长。

表4 时间段与车辆通行时间的关系Table 4 Relationship between time period and vehicle travel time

综上所述，通过对影响道路交通拥堵时间的因素分析，本文选择用隐马尔可夫模型来解决道路拥堵时间预测问题，以影响因素作为可观测变量，拥堵时间作为隐状态。

2 基于隐马尔可夫模型的道路拥堵时间预测模型

2.1 隐马尔可夫模型

隐马尔可夫模型（hidden Markov model，HMM）是统计模型，用来描述一个含有隐含未知参数的马尔可夫过程。一个标准的隐马尔可夫模型存在5 个变量(S,O,π,A,B)。其中，S表示隐含状态，表示不能直接观察到的状态；O表示可观测状态，表示可以直接观察到的状态。在模型中，这些状态与隐状态存在特定的关系，π是初始状态概率矩阵，表示隐含状态在初始时刻的状态转移概率分布；A是隐含状态转移概率矩阵，用来描述模型中状态之间相互转换的概率；N表示隐含状态的个数，则Aij=P(Sj|Si)表示在某时刻，状态为Si的条件下，在t+1 时刻状态是Sj的概率；B是观测状态转移概率矩阵，令M表示可观测状态数目，则Bij=P(Oi|Sj)表示在t时刻，隐含状态是Sj条件下，观察状态为Oi的概率[10]。

2.2 道路拥堵时间模型

2.2.1 隐马尔可夫模型建立

在许多实际问题下，参数不能由直接计算得到，而是需要进行估计，这就是隐马尔可夫模型的学习问题。训练问题的核心是当获得观测序列O={o1,o2,…,oT}之后，调整模型参数A、B、π,使得P(O|λ)取得最大值。通过对模型参数A、B、π的不断调整，使得模型建立更加准确。本文分别利用前向-后向算法[11]和改进后的韦尔奇算法对模型进行评价和参数估计。

前向-后向算法是率先估计隐马氏模型的参数，并且通过已有的数据来重新评估参数的值，并减少引起的错误，以重新修订这些模型参数。前向-后向算法对P(O|λ)求解方法如下：

对于一个状态序列X={x1,x2,…,xT},有

则所求概率为：

韦尔奇算法[12-13]是为了解决隐马尔可夫模型中的参数估计问题，对于给出的观测序列，估计模型参数，使得在该模型下观测序列概率最大。用韦尔奇算法估计参数A、B、π的方法如下：

给出模型参数λ和观测序列O，定义二元函数γt(i,j)=P(xt=qi,xt+1=qj|O,λ)表示在t时刻由状态qi转换到t+1 时刻状态qj的概率。

本文根据路段的拥堵时间以及平均车速分布，分别设定不同时间内通过路段的范围表示隐状态，并将其划分等级。收集数据在某一时段的时间范围等级转换到另外一个时段的时间范围等级数量的方法，计算每个状态之间转换的概率，得出来的结果组成状态转移矩阵。利用之前预设的时间等级状态所表示的三种隐状态，挑选使用已有的道路拥堵时间作为训练数据集，建立预测模型，并挑选未来道路拥堵情况作为测试集，来验证模型的精确性和预测性。最后提出某时段出行的最优路线。

计算训练数据从前一时刻的状态转移到下一个时刻与之不同的数量，运用公式计算状态转移矩阵A以及观测变量转移概率矩阵B。对于初始概率值，假设已知t-1 时刻隐状态来预测t时刻的状态，设{Sa,Sb,Sc},将初始概率向量π表示为{1，0，0}，即假设初始t-1 时刻真实拥堵时间范围为π的值，代入到预测模型，不断计算出最新的π值。通过公式计算得到t时刻概率最大的隐状态，即t时刻的隐状态预测值。最后预测出某时段的最优路线。

2.2.2 改进型韦尔奇算法

传统韦尔奇算法只结合该时刻的前一时刻的状态进行分析。对于预测未来事件来说，这种传统算法预测的数据往往具有忽高忽低、不稳定的特点，从而导致预测结果与实际结果差距过大。为了提高预测结果的准确性，本文提出改进型韦尔奇算法，即在传统算法的原理基础之上，增加考虑前n个时刻的状态情况，对此进行分析、研究和运算，使得模型能够产生更加精确的数据。改进过程如下：

设t-n时刻状态为Sx，定义PI′、aij′、bj(k)′。

γij(t)为给定模型和观测序列条件下的t状态时刻为St,t+1 时刻状态为Sj的概率，记为γij(t)=P(it+1=计算得到；

εxij(t)=P(it+1=Sj|it=Si,it-n=Sx)可由以下公式计算得到：

αij(t)为给定模型λ，t-n时刻状态为Sx,t时刻状态为Si,t+1 时刻状态为Sj的概率，可由αij(t)=bj(Ot+1)·计算得到；

同理可得：

axij是在t-n时刻处于Sx,t时刻处于状态Si，在t+1 时刻转移到状态Sj的概率，可由axij=PIiaxiaij,1 ≤x,i,j≤N计算得到。

使用改进型韦尔奇算法进行大量实验，分别增加总数据量m以及增加考虑的时刻值n，并计算实验预测数据，得出此方法的准确性以及运算出数据的平均时间。使用改进型韦尔奇算法得出的统计数据如表5所示。

表5 使用改进型韦尔奇算法得出的统计数据Table 5 Statistical data obtained by using improved Welch algorithm

如表5 统计的数据可知，随着实验样本数据的增加，实验预测结果正确率有一定的提高；而运用改进型韦尔奇算法计算数据，随着增加考虑的时刻越多，预测结果数据越贴近真实的实际情况，平均误差比率小于5%。但是总数据量以及考虑的时刻越多，模型复杂性增强，计算机处理数据的速度变慢，从而导致实时性有所降低。

因此，在解决实际问题时，合理考虑、选取并使用状态值n以及总数据量c，在保证数据合理性、准确性的基础之上，提高计算数据的实时性。

实验流程图如图1所示。

图1 拥堵时间预测流程图Fig.1 Flow chart of road congestion time prediction

3 实验过程

本文选用某市的路段1 为核心路段，全长15.8 km，其北临的路段2全长14.8 km，南临的路段3全长16.3 km。该核心路段经过交通枢纽以及中小学校等，属于该市区内的中心路段，因此道路堵塞情况时有发生。对于此次道路拥堵时间的预测研究，该路段都有较为典型的特点。针对该路段的拥堵情况，可分析选择某时段以上三条道路为最优通行路径，以实现避免交通堵塞，减少拥堵时间的目的。

本文的数据采集使用交通微波雷达检测器RTMS（remote transportation microwave sensor）[14]，其是用于观测道路实时状况的在线式装置。RTMS 在微波束的发射方向上以2 m为一层面分层面探测物体，采用侧向安装方式，设备安装在路旁的路杆上，以保持微波的投影与道路垂直，分层面的波束能够提供多个探测区域，可适用于各种情况的道路。其测量微波投影区域内车辆的位置，通过距离来实现对多车道的车流量、车辆行程时间等交通数据进行检测。RTMS 工作原理流程图如图2所示。

图2 RTMS工作原理流程图Fig.2 Flow chart of working principle of RTMS

针对所选核心路段，以及其南北共三个路段，每个路段中采用一个RTMS对交通情况检测。RTMS以30 s为一个计数周期，即每隔30 s计数一次。根据路段的拥堵时间以及平均车速分布，分别设定不同时间内通过路段的范围表示隐状态，并将其划分为三个等级，如表6所示。

表6 道路拥堵时间段等级划分Table 6 Classification of time periods of road congestion

在实际的道路交通工程中，交通流量、密度以及车辆速度是道路流的主要三个基本参数[15]。在实际的采集数据中，平均车速是判断通过某路段时间的重要指标，在道路交通研究当中占据重要地位。设交通量为Q（辆/h），该时刻道路路段车辆数为N（辆），平均速度为V（km/h），路段长度为L（km），车辆驶入路段时间为T1,驶离路段时间为T2,通过该路段平均时间周期为T3（h）。

本文使用2020年8月的数据样本共30天的道路拥堵情况作为训练数据集，建立预测模型，并使用该年份9月的数据样本共30天的道路拥堵情况作为测试集，来验证模型的精确性和预测性，以及提出行程的最优路线。将RTMS在24小时内采集到的数据分为4个时段，分别是07：00—10：00，10：00—16：00，16：00—20：00，20：00—07：00，记录车道内某一集中区域内车辆数量以及驶入、驶离道路的时间。训练集平均数据如表7 所示，N(i)表示第i条路段车辆数，T2(i)表示第i条路段车辆驶离道路时间，T3(i)表示通过第i条路段的平均时间，Vi表示第i条道路车辆的平均速度。三条路段在训练集时段的道路拥堵时间变化如表7所示。

表7 三条路段训练集平均数据Table 7 Average data of three training sets

4 实验结果及讨论

在2020年8月的测试数据样本的模型基础上，预测同年9月共30天的道路拥堵情况，并适当增加和减少样本的取样周期，计算预测准确率。本文使用其他两种经典预测算法与隐马尔可夫模型韦尔奇算法、改进型韦尔奇算法相比较，通过对比得出更为精确的实验结果。

利用隐马尔可夫模型的韦尔奇算法预测的30天内三条道路拥堵时间的预测值与真实值对比结果的部分数据如图3 所示。图中横坐标表示实验样本30 天的时间段，格式为“年份-月份-日期 小时：分钟：秒”；纵坐标表示车辆平均拥堵时间。三条折线分别表示三条道路的实际拥堵时间，蓝色、红色以及黄色圆点分别表示计算得出的三条道路的时间数据预测值，圆点越靠近折线的拐点说明预测结果越准确，圆点偏离折线说明预测结果与实际存在误差。通过计算预测准确的数据与所有数据之比，计算出韦尔奇算法的预测准确率为89.6%。使用改进型韦尔奇算法，选取考虑当前时刻之前n=5，并参与计算预测数据，改进型韦尔奇算法的预测结果的部分数据如图4所示。通过计算预测数据准确率，得出改进型算法的预测准确率分别为97.5%，相比于韦尔奇算法，改进型韦尔奇算法计算结果的准确率提高7.9 个百分点，预测结果更加精确，更适合运用到预测道路拥堵时间的问题当中。

图3 韦尔奇算法计算的路段拥堵时间结果Fig.3 Result of road congestion time calculated by Welch algorithm

图4 改进韦尔奇算法计算的路段拥堵时间结果Fig.4 Result of road congestion time calculated by improved Welch algorithm

其他两种经典算法，即马尔可夫模型和小波模型的组合算法、ARIMA 模型算法预测结果如表8 所示。通过计算预测准确的数据与所有数据之比，得出两种传统算法的预测准确率分别为81.8%、82.9%。马尔可夫模型和小波模型的组合算法预测隐状态Sb的准确率最高，而ARIMA模型算法预测隐状态Sa的准确率最高。

表8 经典算法计算的路段拥堵时间结果Table 8 Result of road congestion time calculated by classical algorithms

在上述实验算法的基础上，更改实验时间周期，分别选取3 天、7 天、90 天以及120 天作为样本的取样周期，进行对比实验，不同实验取样周期的实验结果如图5所示。图中横坐标为实验取样周期，纵坐标为预测数据的准确率，四条柱形从左至右分别为韦尔奇算法、改进型韦尔奇算法、马尔可夫与小波模型算法、ARIMA算法。

图5 不同实验周期各种算法的时间数据预测准确率Fig.5 Prediction accuracy of time data of various algorithms in different experimental periods

在实验时间周期为30 天的基础上，增加和减少实验的样本取样周期，用不同算法计算道路拥堵时间数据值。结果表明，随着实验周期的不断增加，气候、人为等因素的不断变化，导致道路出现某些情况的随机性增大，因此各算法预测准确率略有降低，但是改进型韦尔奇算法相比于其他算法准确率最高，实验周期内预测准确率分别为98.0%、97.8%、97.5%、97.1%、96.3%，准确率逐渐趋于平稳。而韦尔奇算法以及其他两种经典算法在实验周期内最高与最低预测准确率相差分别为5.5个百分点、6.3个百分点、6.1个百分点，预测准确性存在一定波动。总体来说，经典算法总体准确率较改进型韦尔奇算法有明显的误差，原因在于，两种经典算法的预测数值在某一时间段较为集中，间隔时间段之间的预测数据数值起伏较大，从而导致误差率提高。而改进型韦尔奇算法的预测方式增加考虑前一时刻状态，因此预测数据较为分散并且准确。由于交通拥堵时间数据具有不均衡分布性的特点，从而限制了以往经典算法的应用。

因此，本文建立隐马尔可夫模型对道路拥堵时间进行预测。从实验结果来看，此方法能够预测大部分测试集中的道路拥堵时间，但少部分预测结果与实际不相符。通过检查测试集真实数据，发现偏差数据处于等级交界处以及高峰时段。由于各影响因素的不确定性以及高峰期样本量较其他等级少，模型参数并不能得到最充分的训练，导致预测结果有略微偏差，但是并不影响人们对出行时间以及路段的选择。通过计算与比较，可得出某时段拥堵时间最少的最优路段。07：00—10：00与16：00—20：00，即早、晚出行高峰时段，路段2平均拥堵时间最短；10：00—16：00，路段1平均拥堵时间最短；20：00—07：00，路段3 平均拥堵时间最短。因此，利用隐马尔可夫模型的改进型韦尔奇算法能够更精确地预测道路交通拥堵时间，并能为市民提供最优的出行路径。

5 结束语

本文利用隐马尔可夫的改进型韦尔奇算法对参数训练、阈值确定、模型建立以及数据预测后，完成对三条道路拥堵时间的预测，并且完成对最优路径的选择。从本文模型对于道路拥堵时间预测结果来看，准确性较以往算法有提高，可以进行有效预测，并能够提出不同时间段的最优出行路线方案。

本文对道路拥堵时间预测进行研究，也存在能够进一步深入研究的地方。比如本次实验样本量较少，模型拟合状态不够；所选的最优路径较少，不能灵活地选择多条道路来避开拥堵，进而节约出行时间；改进型韦尔奇算法计算量庞大，在进行数据计算与整合过程中需要花费大量时间。综上所述，如何在确保预测准确性的前提下增加数据量、选择最优路径以及提高计算效率的问题均为以后工作需要研究的内容。