張緒冰，謝雨飛

北京建筑大學 電氣與信息工程學院，北京 100044

城市道路交通問題是我國致力解決的社會難題之一，根據(jù)相關數(shù)據(jù)顯示，我國一線城市的機動車保有量在近十年來已經(jīng)突破七位數(shù)量級，并每年保持17%左右的增長速度，尤其是小汽車的增長更加明顯，給交通系統(tǒng)帶來了巨大負擔。在擁堵高峰期，北京道路上車輛通行時間劇增，每年有近25 小時損失在道路擁堵當中。道路擁堵問題日益嚴重，社會面臨巨大的挑戰(zhàn)。道路擁堵問題不僅增加了發(fā)生交通事故的概率，甚至會讓自然環(huán)境變得越來越糟。因此，道路擁堵問題急需得到改善，人們應算好道路擁堵時間而合理安排出行，減輕交通壓力。

目前，針對交通預測的理論已有運用貝葉斯預測模型[1]、卡爾曼濾波模型[2]、小波模型等研究方法。例如，楊文忠等人將時間序列預測模型應用到道路交通的模型中，實驗結果與實際的狀態(tài)非常接近，得到了很好的應用[3]；Patra等人以卡爾曼濾波模型為理論基礎提出了卡爾曼濾波預測模型[4-5]，該模型精度較高，能夠處理平穩(wěn)的數(shù)據(jù)，但仍為線性模型；韋凌翔等人在ARIMA模型上研究了交通流預測方法在短時區(qū)間道路中的應用[6-8]，在該模型上針對短時交通的流量問題分別研究了該模型在城市道路中的應用和自適應預測模型中的應用；胡楓利用馬爾可夫模型與小波模型的組合對交通流進行預測[9]。然而，這些方法都存在一些不足，均未從數(shù)據(jù)的角度對交通流進行預測，對其特性研究得不夠深入。另外，這些方法預測的模型為線性模型，對于非線性的真實道路交通情況，預測的準確度不夠。

本文基于隱馬爾可夫模型對道路擁堵時間進行預測，并且分析出當前時間段的最優(yōu)出行路線。隱馬爾可夫鏈對于預測問題、選擇最優(yōu)路線有著強大的能力。通過訓練集獲取并分析道路實時擁堵時間來建立對應的隱馬爾可夫模型，從而預測下一時間段的道路擁堵時間，分析最優(yōu)路徑。并且對韋爾奇算法進一步改進，增加研究某一時刻的前n時刻數(shù)據(jù)，改善算法，使得訓練集參數(shù)與實際更接近，預測精度更高，適用能力更強大。

1 交通擁堵時間的因素分析

一般來說，影響道路交通擁堵的因素主要有氣溫、能見度、行駛高峰期、交通事故發(fā)生情況等。根據(jù)“綜合交通出行大數(shù)據(jù)開放云平臺”的數(shù)據(jù)顯示，這些因素與車輛通行時間密切相關。

天氣溫度與車輛行程時間的關系如表1 所示。隨氣溫的不斷升高，在10～25 ℃時以及氣溫在35 ℃以上，道路上車輛的行程時間呈正增長的趨勢，行程時間增長明顯，進而道路擁堵時間增加。因此，在溫度較為適宜出行和不適宜出行的天氣溫度情況下，道路擁堵時間長。

表1 天氣溫度與車輛通行時間的關系Table 1 Relationship between weather temperature and vehicle travel time

能見度與車輛行程時間的關系如表2 所示。隨著能見度的增長，道路擁堵時間明顯降低?？梢姡芤姸葘τ诘缆窊矶聲r間的影響呈負相關，即能見度越低，擁堵時間越長。

表2 能見度與車輛通行時間的關系Table 2 Relationship between visibility and vehicle travel time

交通事故發(fā)生情況與車輛行程時間的關系如表3所示。在發(fā)生交通事故的情況下，隨著交通事故數(shù)量增長，道路擁堵時間明顯增加。因此，交通事故的發(fā)生對于道路擁堵時間的影響呈正相關，即事故發(fā)生且次數(shù)多，擁堵時間越長。

表3 交通事故數(shù)量與車輛通行時間的關系Table 3 Relationship between number of traffic accidents and vehicle travel time

時間段與車輛行程時間的關系如表4 所示。在早7：00—9：00 和晚16：00—20：00 兩個早晚高峰時間段內(nèi)，車輛通行時間明顯增加，擁堵時間長。

表4 時間段與車輛通行時間的關系Table 4 Relationship between time period and vehicle travel time

綜上所述，通過對影響道路交通擁堵時間的因素分析，本文選擇用隱馬爾可夫模型來解決道路擁堵時間預測問題，以影響因素作為可觀測變量，擁堵時間作為隱狀態(tài)。

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

2.1 隱馬爾可夫模型

隱馬爾可夫模型（hidden Markov model，HMM）是統(tǒng)計模型，用來描述一個含有隱含未知參數(shù)的馬爾可夫過程。一個標準的隱馬爾可夫模型存在5 個變量(S,O,π,A,B)。其中，S表示隱含狀態(tài)，表示不能直接觀察到的狀態(tài)；O表示可觀測狀態(tài)，表示可以直接觀察到的狀態(tài)。在模型中，這些狀態(tài)與隱狀態(tài)存在特定的關系，π是初始狀態(tài)概率矩陣，表示隱含狀態(tài)在初始時刻的狀態(tài)轉移概率分布；A是隱含狀態(tài)轉移概率矩陣，用來描述模型中狀態(tài)之間相互轉換的概率；N表示隱含狀態(tài)的個數(shù)，則Aij=P(Sj|Si)表示在某時刻，狀態(tài)為Si的條件下，在t+1 時刻狀態(tài)是Sj的概率；B是觀測狀態(tài)轉移概率矩陣，令M表示可觀測狀態(tài)數(shù)目，則Bij=P(Oi|Sj)表示在t時刻，隱含狀態(tài)是Sj條件下，觀察狀態(tài)為Oi的概率[10]。

2.2 道路擁堵時間模型

2.2.1 隱馬爾可夫模型建立

在許多實際問題下，參數(shù)不能由直接計算得到，而是需要進行估計，這就是隱馬爾可夫模型的學習問題。訓練問題的核心是當獲得觀測序列O={o1,o2,…,oT}之后，調(diào)整模型參數(shù)A、B、π,使得P(O|λ)取得最大值。通過對模型參數(shù)A、B、π的不斷調(diào)整，使得模型建立更加準確。本文分別利用前向-后向算法[11]和改進后的韋爾奇算法對模型進行評價和參數(shù)估計。

前向-后向算法是率先估計隱馬氏模型的參數(shù)，并且通過已有的數(shù)據(jù)來重新評估參數(shù)的值，并減少引起的錯誤，以重新修訂這些模型參數(shù)。前向-后向算法對P(O|λ)求解方法如下：

對于一個狀態(tài)序列X={x1,x2,…,xT},有

則所求概率為：

韋爾奇算法[12-13]是為了解決隱馬爾可夫模型中的參數(shù)估計問題，對于給出的觀測序列，估計模型參數(shù)，使得在該模型下觀測序列概率最大。用韋爾奇算法估計參數(shù)A、B、π的方法如下：

給出模型參數(shù)λ和觀測序列O，定義二元函數(shù)γt(i,j)=P(xt=qi,xt+1=qj|O,λ)表示在t時刻由狀態(tài)qi轉換到t+1 時刻狀態(tài)qj的概率。

本文根據(jù)路段的擁堵時間以及平均車速分布，分別設定不同時間內(nèi)通過路段的范圍表示隱狀態(tài)，并將其劃分等級。收集數(shù)據(jù)在某一時段的時間范圍等級轉換到另外一個時段的時間范圍等級數(shù)量的方法，計算每個狀態(tài)之間轉換的概率，得出來的結果組成狀態(tài)轉移矩陣。利用之前預設的時間等級狀態(tài)所表示的三種隱狀態(tài)，挑選使用已有的道路擁堵時間作為訓練數(shù)據(jù)集，建立預測模型，并挑選未來道路擁堵情況作為測試集，來驗證模型的精確性和預測性。最后提出某時段出行的最優(yōu)路線。

計算訓練數(shù)據(jù)從前一時刻的狀態(tài)轉移到下一個時刻與之不同的數(shù)量，運用公式計算狀態(tài)轉移矩陣A以及觀測變量轉移概率矩陣B。對于初始概率值，假設已知t-1 時刻隱狀態(tài)來預測t時刻的狀態(tài)，設{Sa,Sb,Sc},將初始概率向量π表示為{1，0，0}，即假設初始t-1 時刻真實擁堵時間范圍為π的值，代入到預測模型，不斷計算出最新的π值。通過公式計算得到t時刻概率最大的隱狀態(tài)，即t時刻的隱狀態(tài)預測值。最后預測出某時段的最優(yōu)路線。

2.2.2 改進型韋爾奇算法

傳統(tǒng)韋爾奇算法只結合該時刻的前一時刻的狀態(tài)進行分析。對于預測未來事件來說，這種傳統(tǒng)算法預測的數(shù)據(jù)往往具有忽高忽低、不穩(wěn)定的特點，從而導致預測結果與實際結果差距過大。為了提高預測結果的準確性，本文提出改進型韋爾奇算法，即在傳統(tǒng)算法的原理基礎之上，增加考慮前n個時刻的狀態(tài)情況，對此進行分析、研究和運算，使得模型能夠產(chǎn)生更加精確的數(shù)據(jù)。改進過程如下：

設t-n時刻狀態(tài)為Sx，定義PI′、aij′、bj(k)′。

γij(t)為給定模型和觀測序列條件下的t狀態(tài)時刻為St,t+1 時刻狀態(tài)為Sj的概率，記為γij(t)=P(it+1=計算得到；

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

αij(t)為給定模型λ，t-n時刻狀態(tài)為Sx,t時刻狀態(tài)為Si,t+1 時刻狀態(tài)為Sj的概率，可由αij(t)=bj(Ot+1)·計算得到；

同理可得：

axij是在t-n時刻處于Sx,t時刻處于狀態(tài)Si，在t+1 時刻轉移到狀態(tài)Sj的概率，可由axij=PIiaxiaij,1 ≤x,i,j≤N計算得到。

使用改進型韋爾奇算法進行大量實驗，分別增加總數(shù)據(jù)量m以及增加考慮的時刻值n，并計算實驗預測數(shù)據(jù)，得出此方法的準確性以及運算出數(shù)據(jù)的平均時間。使用改進型韋爾奇算法得出的統(tǒng)計數(shù)據(jù)如表5所示。

表5 使用改進型韋爾奇算法得出的統(tǒng)計數(shù)據(jù)Table 5 Statistical data obtained by using improved Welch algorithm

如表5 統(tǒng)計的數(shù)據(jù)可知，隨著實驗樣本數(shù)據(jù)的增加，實驗預測結果正確率有一定的提高；而運用改進型韋爾奇算法計算數(shù)據(jù)，隨著增加考慮的時刻越多，預測結果數(shù)據(jù)越貼近真實的實際情況，平均誤差比率小于5%。但是總數(shù)據(jù)量以及考慮的時刻越多，模型復雜性增強，計算機處理數(shù)據(jù)的速度變慢，從而導致實時性有所降低。

因此，在解決實際問題時，合理考慮、選取并使用狀態(tài)值n以及總數(shù)據(jù)量c，在保證數(shù)據(jù)合理性、準確性的基礎之上，提高計算數(shù)據(jù)的實時性。

實驗流程圖如圖1所示。

圖1 擁堵時間預測流程圖Fig.1 Flow chart of road congestion time prediction

3 實驗過程

本文選用某市的路段1 為核心路段，全長15.8 km，其北臨的路段2全長14.8 km，南臨的路段3全長16.3 km。該核心路段經(jīng)過交通樞紐以及中小學校等，屬于該市區(qū)內(nèi)的中心路段，因此道路堵塞情況時有發(fā)生。對于此次道路擁堵時間的預測研究，該路段都有較為典型的特點。針對該路段的擁堵情況，可分析選擇某時段以上三條道路為最優(yōu)通行路徑，以實現(xiàn)避免交通堵塞，減少擁堵時間的目的。

本文的數(shù)據(jù)采集使用交通微波雷達檢測器RTMS（remote transportation microwave sensor）[14]，其是用于觀測道路實時狀況的在線式裝置。RTMS 在微波束的發(fā)射方向上以2 m為一層面分層面探測物體，采用側向安裝方式，設備安裝在路旁的路桿上，以保持微波的投影與道路垂直，分層面的波束能夠提供多個探測區(qū)域，可適用于各種情況的道路。其測量微波投影區(qū)域內(nèi)車輛的位置，通過距離來實現(xiàn)對多車道的車流量、車輛行程時間等交通數(shù)據(jù)進行檢測。RTMS 工作原理流程圖如圖2所示。

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

針對所選核心路段，以及其南北共三個路段，每個路段中采用一個RTMS對交通情況檢測。RTMS以30 s為一個計數(shù)周期，即每隔30 s計數(shù)一次。根據(jù)路段的擁堵時間以及平均車速分布，分別設定不同時間內(nèi)通過路段的范圍表示隱狀態(tài)，并將其劃分為三個等級，如表6所示。

表6 道路擁堵時間段等級劃分Table 6 Classification of time periods of road congestion

在實際的道路交通工程中，交通流量、密度以及車輛速度是道路流的主要三個基本參數(shù)[15]。在實際的采集數(shù)據(jù)中，平均車速是判斷通過某路段時間的重要指標，在道路交通研究當中占據(jù)重要地位。設交通量為Q（輛/h），該時刻道路路段車輛數(shù)為N（輛），平均速度為V（km/h），路段長度為L（km），車輛駛入路段時間為T1,駛離路段時間為T2,通過該路段平均時間周期為T3（h）。

本文使用2020年8月的數(shù)據(jù)樣本共30天的道路擁堵情況作為訓練數(shù)據(jù)集，建立預測模型，并使用該年份9月的數(shù)據(jù)樣本共30天的道路擁堵情況作為測試集，來驗證模型的精確性和預測性，以及提出行程的最優(yōu)路線。將RTMS在24小時內(nèi)采集到的數(shù)據(jù)分為4個時段，分別是07：00—10：00，10：00—16：00，16：00—20：00，20：00—07：00，記錄車道內(nèi)某一集中區(qū)域內(nèi)車輛數(shù)量以及駛入、駛離道路的時間。訓練集平均數(shù)據(jù)如表7 所示，N(i)表示第i條路段車輛數(shù)，T2(i)表示第i條路段車輛駛離道路時間，T3(i)表示通過第i條路段的平均時間，Vi表示第i條道路車輛的平均速度。三條路段在訓練集時段的道路擁堵時間變化如表7所示。

表7 三條路段訓練集平均數(shù)據(jù)Table 7 Average data of three training sets

4 實驗結果及討論

在2020年8月的測試數(shù)據(jù)樣本的模型基礎上，預測同年9月共30天的道路擁堵情況，并適當增加和減少樣本的取樣周期，計算預測準確率。本文使用其他兩種經(jīng)典預測算法與隱馬爾可夫模型韋爾奇算法、改進型韋爾奇算法相比較，通過對比得出更為精確的實驗結果。

利用隱馬爾可夫模型的韋爾奇算法預測的30天內(nèi)三條道路擁堵時間的預測值與真實值對比結果的部分數(shù)據(jù)如圖3 所示。圖中橫坐標表示實驗樣本30 天的時間段，格式為“年份-月份-日期 小時：分鐘：秒”；縱坐標表示車輛平均擁堵時間。三條折線分別表示三條道路的實際擁堵時間，藍色、紅色以及黃色圓點分別表示計算得出的三條道路的時間數(shù)據(jù)預測值，圓點越靠近折線的拐點說明預測結果越準確，圓點偏離折線說明預測結果與實際存在誤差。通過計算預測準確的數(shù)據(jù)與所有數(shù)據(jù)之比，計算出韋爾奇算法的預測準確率為89.6%。使用改進型韋爾奇算法，選取考慮當前時刻之前n=5，并參與計算預測數(shù)據(jù)，改進型韋爾奇算法的預測結果的部分數(shù)據(jù)如圖4所示。通過計算預測數(shù)據(jù)準確率，得出改進型算法的預測準確率分別為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

其他兩種經(jīng)典算法，即馬爾可夫模型和小波模型的組合算法、ARIMA 模型算法預測結果如表8 所示。通過計算預測準確的數(shù)據(jù)與所有數(shù)據(jù)之比，得出兩種傳統(tǒng)算法的預測準確率分別為81.8%、82.9%。馬爾可夫模型和小波模型的組合算法預測隱狀態(tài)Sb的準確率最高，而ARIMA模型算法預測隱狀態(tài)Sa的準確率最高。

表8 經(jīng)典算法計算的路段擁堵時間結果Table 8 Result of road congestion time calculated by classical algorithms

在上述實驗算法的基礎上，更改實驗時間周期，分別選取3 天、7 天、90 天以及120 天作為樣本的取樣周期，進行對比實驗，不同實驗取樣周期的實驗結果如圖5所示。圖中橫坐標為實驗取樣周期，縱坐標為預測數(shù)據(jù)的準確率，四條柱形從左至右分別為韋爾奇算法、改進型韋爾奇算法、馬爾可夫與小波模型算法、ARIMA算法。

圖5 不同實驗周期各種算法的時間數(shù)據(jù)預測準確率Fig.5 Prediction accuracy of time data of various algorithms in different experimental periods

在實驗時間周期為30 天的基礎上，增加和減少實驗的樣本取樣周期，用不同算法計算道路擁堵時間數(shù)據(jù)值。結果表明，隨著實驗周期的不斷增加，氣候、人為等因素的不斷變化，導致道路出現(xiàn)某些情況的隨機性增大，因此各算法預測準確率略有降低，但是改進型韋爾奇算法相比于其他算法準確率最高，實驗周期內(nèi)預測準確率分別為98.0%、97.8%、97.5%、97.1%、96.3%，準確率逐漸趨于平穩(wěn)。而韋爾奇算法以及其他兩種經(jīng)典算法在實驗周期內(nèi)最高與最低預測準確率相差分別為5.5個百分點、6.3個百分點、6.1個百分點，預測準確性存在一定波動。總體來說，經(jīng)典算法總體準確率較改進型韋爾奇算法有明顯的誤差，原因在于，兩種經(jīng)典算法的預測數(shù)值在某一時間段較為集中，間隔時間段之間的預測數(shù)據(jù)數(shù)值起伏較大，從而導致誤差率提高。而改進型韋爾奇算法的預測方式增加考慮前一時刻狀態(tài)，因此預測數(shù)據(jù)較為分散并且準確。由于交通擁堵時間數(shù)據(jù)具有不均衡分布性的特點，從而限制了以往經(jīng)典算法的應用。

因此，本文建立隱馬爾可夫模型對道路擁堵時間進行預測。從實驗結果來看，此方法能夠預測大部分測試集中的道路擁堵時間，但少部分預測結果與實際不相符。通過檢查測試集真實數(shù)據(jù)，發(fā)現(xiàn)偏差數(shù)據(jù)處于等級交界處以及高峰時段。由于各影響因素的不確定性以及高峰期樣本量較其他等級少，模型參數(shù)并不能得到最充分的訓練，導致預測結果有略微偏差，但是并不影響人們對出行時間以及路段的選擇。通過計算與比較，可得出某時段擁堵時間最少的最優(yōu)路段。07：00—10：00與16：00—20：00，即早、晚出行高峰時段，路段2平均擁堵時間最短；10：00—16：00，路段1平均擁堵時間最短；20：00—07：00，路段3 平均擁堵時間最短。因此，利用隱馬爾可夫模型的改進型韋爾奇算法能夠更精確地預測道路交通擁堵時間，并能為市民提供最優(yōu)的出行路徑。

5 結束語

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

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