隱馬爾可夫模型的道路擁堵時間預測

張緒冰，謝雨飛

北京建筑大學 電氣與信息工程學院，北京 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 結束語

本文利用隱馬爾可夫的改進型韋爾奇算法對參數訓練、閾值確定、模型建立以及數據預測后，完成對三條道路擁堵時間的預測，并且完成對最優路徑的選擇。從本文模型對于道路擁堵時間預測結果來看，準確性較以往算法有提高，可以進行有效預測，并能夠提出不同時間段的最優出行路線方案。

本文對道路擁堵時間預測進行研究，也存在能夠進一步深入研究的地方。比如本次實驗樣本量較少，模型擬合狀態不夠；所選的最優路徑較少，不能靈活地選擇多條道路來避開擁堵，進而節約出行時間；改進型韋爾奇算法計算量龐大，在進行數據計算與整合過程中需要花費大量時間。綜上所述，如何在確保預測準確性的前提下增加數據量、選擇最優路徑以及提高計算效率的問題均為以后工作需要研究的內容。