基于馬爾可夫過程的路網交通狀態預測方法

郭海鋒，蔡華波，朱 超，查 琪

(浙江工業大學 信息工程學院，浙江 杭州 310023)

基于馬爾可夫過程的路網交通狀態預測方法

郭海鋒，蔡華波，朱 超，查 琪

(浙江工業大學 信息工程學院，浙江 杭州 310023)

針對城市道路交通管控對路網實時交通狀態信息的需求，首先對交叉口的交通狀態進行了界定并劃分為4個狀態等級，然后以15 min為時間間隔，結合歷史數據采用馬爾可夫過程計算每個交叉口的狀態轉移概率，并對各個交叉口下一時刻的交通狀態進行預測，進而對每個交叉口進行分類并采用綜合評價法確定整個路網的交通狀態.試驗以MAPE為評價指標對已有算法進行對比，結果表明：該方法不僅能夠實時地確定每個交叉口的交通狀態，同時能夠基于不同類型交叉口的預測結果確定整個路網的交通狀態，且交叉口平均預測誤差為7.04%.

城市路網；交叉口；馬爾可夫過程；綜合評價法；交通狀態

目前，大城市交通擁堵已由偶發的個別交叉口擁堵發展為隨機的局部區域性擁堵，甚至路網級的交通擁堵也已成為常態.雖然已有文獻對道路交通狀態評價方法的研究較為成熟[1-3]，但相關成果主要集中于對單個交叉口或路段交通狀態的評估，缺乏面向區域路網交通狀態的研究.董宏輝等提出[4]基于主觀評價的方法確定路網交通狀態的分級標準及各評價指標在線性判別模型中的權重，進而定量評判路網的交通狀態等級.張和平等[5]從中觀角度定義交通狀態變量并建立路網交通狀態模型，通過對路口交通狀態分析處理，得到路口可達性、路段連通性及路網整體狀態的判別結果.郭偉等[6]通過對路口檢測器數據分析，利用K均值聚類和EM算法相結合，提出表征路口交通流運行狀態的特征向量，并對路口狀態進行分析.

文獻[7-9]主要以路網可靠性、路網交通流參數均值等方式來評價路網的交通狀態，且該評估方式由于考慮因素較多、限定條件苛刻以及計算相對復雜，其更適用于對路網交通狀態的離線分析，而不適合指導實時的交通管控策略.為進一步滿足動態交通管控的實時性要求，尤其是滿足對區域性交通擁堵的優化管控需求，應采用計算快速、高效穩定的預測算法對路網的交通狀態進行短時預測，并依此制定科學的交通管理和控制決策.為此，首先以每個交叉口為分析對象，然后采用馬爾可夫過程對其狀態進行跟蹤預測，進而利用模糊綜合評價法對路網整體的交通狀態進行判定，最終預測路網的交通狀態.

1 馬爾可夫過程預測交叉口的狀態

飽和狀態下，路網各交叉口交通流的運行狀態在前后時刻彼此影響較大[10]，因此，評估路網的交通狀態不能簡單地累計當前每個交叉口的交通狀態，而應綜合考慮當前及未來各交叉口狀態的變化情況，進而對路網整體交通狀態進行預測.馬爾可夫過程能夠較好地描述系統狀態的轉移情況，適用于對交叉口的狀態變化進行定量描述.

1.1 馬爾可夫過程

若系統t時刻及t之前時刻狀態已知，t+1時刻的狀態只與t時刻的狀態有關，與t之前的狀態無關，那么該隨機過程稱為馬爾可夫過程.

馬爾可夫過程實際上是一個將系統狀態和狀態轉移定量化的數學模型，能夠根據已知系統狀態對下一時刻系統的狀態進行分析和預測.確定狀態轉移概率是關鍵環節，它實際上是一個條件概率，即

pij=p(xn=j|xm=i)

(1)

式中pij表示系統在m時刻狀態為i，在n時刻狀態為j的可能性大小.

1.2 交叉口狀態界定

交叉口是城市路網的節點，其繁忙程度直接反映了所轄范圍內的交通流運行情況.在已有評價交叉口狀態的指標中，服務水平和飽和度最能直觀地反映交叉口的運行狀態.尤其是服務水平，其能夠客觀地評估一個交叉口當前的運行情況，但是服務水平的獲得通常采取線下分析的方式來進行，難以在線獲得.然而，飽和度則可依據檢測器獲得的交通流量數據以及信號控制參數信息實時地獲得.因此，為便于定性定量地界定交叉口的交通狀態，已有相關研究成果對服務水平LOS與飽和度s之間的相關關系[11]進行了研究，描述如下(暫不考慮飽和度溢出)：0≤s<0.3，LOS=A；0.3≤s<0.6，LOS=B；0.6≤s<0.7，LOS=C；0.7≤s<0.8，LOS=D；0.8≤s<0.9，LOS=E；0.9≤s≤1，LOS=F.

考慮現實中的交通管控需求，可對上述映射關系進一步作調整[12]：LOS=A，暢通狀態；LOS=B，輕微擁擠狀態；LOS=，擁擠狀態；LOS=F，嚴重擁擠狀態.

1.3 交叉口狀態預測

交通狀態預測，是基于檢測器獲得的交通流量數據及歷史狀態數據對其下一時刻的狀態進行預測分析.對于城市路網而言，在同一時間尺度上交通流變化通常呈現出較強的自相似性[13-15].因此，可通過分析歷史數據獲得交叉口在不同工作日各時段的交通狀態信息，進而結合當前時段交叉口以及歷史數據中該時段交叉口的交通狀態信息來評估下一時刻該交叉口的交通狀態變化情況.

為便于量化計算，將前述界定的交叉口暢通、輕微擁擠、擁擠和嚴重擁擠4個狀態分別映射為對應等級1,2,3,4.同時，以15 min為間隔對獲取的歷史交通流量數據進行分析，然后計算每15 min交叉口的狀態等級，進而計算交叉口狀態轉移概率.

交叉口在下一時刻的狀態可由當前狀態轉換為其他幾種狀態中的某一種.假設交叉口當前狀態為1，下一時刻狀態也為1，則其狀態轉移概率為

(2)

式中：p11指當前狀態為1，下一時刻狀態為1的概率；n11指歷史數據中當前狀態為1，下一時刻狀態為1的個數；n1指歷史數據中當前狀態為1的個數.

由式(2)類推，可獲得不同狀態間的轉移概率，進而可得出交叉口下一時刻的狀態轉移概率矩陣為

(3)

(4)

式中pi(i=1，2，3，4)分別為交叉口下一時刻各狀態概率，較大值為下一時刻的預測狀態.

2 綜合評價法分析路網的交通狀態

路網交通狀態是各個交叉口狀態的綜合反映，可通過各交叉口狀態的變化呈現路網總的交通發展態勢.通過馬爾可夫過程預測出每個交叉口下一時刻的狀態之后，如何以此計算整個路網的交通狀態尚需進一步研究.筆者采用綜合評價法并依據馬爾可夫過程計算的各交叉口下一時刻的狀態對路網的交通狀態進行評估.

首先，將路網中的交叉口分為六類.將主干路與主干路相交的交叉口作為第一類交叉口；主干路與次干路相交的交叉口作為第二類交叉口；主干路與支路相交的交叉口作為第三類交叉口；次干路與次干路相交的交叉口作為第四類交叉口；次干路與支路相交的交叉口作為第五類交叉口；支路與支路相交的交叉口作為第六類交叉口.設路網中六類交叉口的數目分別為b1，b2，b3，b4，b5，b6，其對應的權重集合為

(5)

式中Bi=bi/(b1+b2+b3+b4+b5+b6),i=1,2,…,6.

其次，結合馬爾可夫預測的交叉口下一時刻狀態信息以及歷史數據中交叉口下一時刻狀態信息對每類交叉口進行分析.假設馬爾可夫預測的交叉口暢通、輕微擁擠、擁擠和嚴重擁擠的數目分別為x1，x2，x3，x4；歷史數據中下一時刻交叉口暢通、輕微擁擠、擁擠和嚴重擁擠的數目分別為y1，y2，y3，y4.便可進一步求得每類交叉口下一時刻對應狀態的概率為

(6)

式中：mqi為第q(q=1，2，…，6)類交叉口的狀態為i(i=1，2，3，4)的概率；u為調整參數(由經驗獲得，u=0.7).

獲得以上數據后，可獲得路網交通狀態下一時刻的綜合評價矩陣，即

(7)

運行狀態評價矩陣可以對路網交通狀態進行評定，設路網運行狀態矩陣為A，其表達式為

(8)

其中

(9)

比較矩陣A中的各元素，較大值則為路網下一時刻的交通狀態.

3 實驗分析

3.1 數據準備

為驗證提出方法的有效性，采用一個由7條主干路、3條次干路、5條支路以及32個交叉口組成的路網，其中第1類至第6類交叉口數量分別為10，8，7，2，4，1個，如圖1所示，圖1中數字代表交叉口類型.依據交通流的自相似性[15]等特性，采用數值模擬的方式獲取了各交叉口兩周內的交通流量數據，以15 min為時間間隔，分析的時間段分別為7:30—7:45；7:45—8:00；11:30—11:45；11:45—12:00.實驗中主要的運算工作基于DEV-CPP的C語言開發環境完成.

圖1 簡單路網圖Fig.1 A simple road network

依據獲取的歷史數據能夠獲得每個交叉口各時段的狀態等級，圖2展示其中兩個交叉口的歷史數據.

為評價所提預測方法的適用性和準確性，實驗中分別采用了早上和中午2組數據樣本.采集當前7:30—7:45及11:30—11:45的流量計算交叉口的交通狀態，然后采用馬爾可夫過程對7:45—8:00及11:45—12:00的各交叉口狀態進行預測.時間段分組信息如表1所示.

組別觀察時間段預測時間段17:30—7:457:45—8:00211:30—11:4511:45—12:00

3.2 預測交叉口狀態

圖3記錄了32個交叉口在組1預測時間段的預測狀態及其實際狀態.

圖3 交叉口預測狀態及實際狀態Fig.3 Predicted state and real state of intersections

采用同樣的方法，對32個交叉口在組2的預測時間段狀態進行預測，其預測狀態及實際狀態如圖

4所示.

圖4 交叉口預測狀態及實際狀態Fig.4 Predicted state and real state of intersections

3.3 確定模糊狀態評價矩陣

結合預測數據及歷史數據，可得出兩組實驗中預測時間段的路網模糊狀態評價矩陣，分別為

(10)

(11)

3.4 確定路網整體狀態

根據各類交叉口的權重系數，得到組1預測時間段的路網運行狀態矩陣為

(12)

比較其中的四個元素，輕微擁擠狀態對應的概率最大為0.53，從而得到此時路網整體狀態為輕微擁擠.同理，得到組2預測時間段的路網運行狀態矩陣為

(13)

再次比較，暢通狀態對應的概率最大為0.94，從而得到此時路網整體狀態為暢通.

圖5分別給出了7:45—8:00,11:45—12:00兩個時間段路網中各交叉口的預測狀態，并將路網狀態形象描述，前一個時間段路網呈現出的整體狀態為輕微擁擠，后一個時間段路網呈現出的整體狀態為暢通.

(a)預測的路網運行狀態(7：45—8：00)

(b)預測的路網運行狀態(11：45—12：00)

為說明路網交通狀態預測的準確性，采用MAPE指標來評價預測精度，其采用百分比誤差，表示為誤差的相對量而非絕對值，從而避免了度量值大小對結果的影響.其計算式為

(14)

根據式(14)計算可得：時間段組1和組2的MAPE值分別為9.38 %，4.69 %.為便于比較，計算實驗結果的平均預測誤差為7.04%，如表2所示.通過對多種交通狀態預測方法[16-18]進行比較分析可知：基于模糊馬爾可夫過程的路網交通狀態預測方法具有較好的預測精度.由于實現簡單，本預測方法在多種算法中具有一定競爭力，能夠很好地反映交叉口的實際狀態.

表2 不同交通狀態預測方法比較

表2中：ES代表指數平滑法；AR代表自回歸模型；MA代表移動平均模型；ROC代表能力區域法[17]；CP代表融合預測法[16]；FMP代表模糊馬爾可夫過程法.

3.5 時間性能分析

所述預測方法在實施過程中主要包括兩個階段：1) 歷史數據的載入；2) 數據的處理與計算.在編程實現該預測方法時，分別在兩個階段前后加入時間獲取函數便可以計算得到各階段耗時.將程序

運行多次，得到如表3所示的結果，其中tload為數據載入耗時；tcore為數據處理與計算耗時；ttotal為兩個階段的總耗時.

表3 方法各階段耗費時間

分析表3可知：歷史數據的載入耗時在2～4 ms范圍波動，數據的計算處理在8～10 ms范圍波動.盡管計算處理階段耗時明顯多于數據載入階段(這是由于算法中含有大量矩陣計算)，但是兩個階段總耗時仍然可以穩定在10～12 ms之間.結果表明：所述預測方法對路網交通狀態預測具有簡單、快速的特點，且該方法實施過程耗時小、計算過程穩定，具有一定的實時性，因此適合于交通狀態的預測及實時在線更新.

4 結 論

城市交通擁堵正逐步從單一路段或交叉口擁擠演化為區域性的網絡擁堵，因此分析并預測路網的交通狀態對未來交通管控而言越來越重要.采用馬爾可夫過程對每個交叉口的交通狀態進行預測，然后利用模糊綜合評價法分析路網的交通狀態，從而既能給出每個節點的交通狀態變化情況，又能夠給出整個路網的交通變化趨勢.尤其是，給出的路網交通狀態預測方法計算簡單，適合于在線實時地預測交通狀態.

本文得到浙江工業大學社科基金項目(Z20140176)的資助.

[1] 姚智勝,邵春福.基于狀態空間模型的道路交通狀態多點時間序列預測[J].中國公路學報,2007,20(4):113-117.

[2] 姜桂艷.道路交通狀態判別技術與應用[M].北京:人民交通出版社,2004.

[3] SUN C, WANG B, ZHANG Y, et al. Urban network traffic state evaluation based on a traffic state coefficient[J]. Journal of highway & transportation research & development,2012,6(2):77-85.

[4] 董宏輝,賈利民,孫曉亮,等.城市道路宏觀路網交通狀態評價方法的研究[J].物流技術,2010,29(8):38-40.

[5] 張和生,張毅,胡東成,等.區域交通狀態分析的時空分層模型[J].清華大學學報(自然科學版),2007,47(1):157-160.

[6] 郭偉,姚丹亞,付毅,等.區域交通流特征提取與交通狀態評估方法研究[J].公路交通科技,2005,22(7):101-104.

[7] 魯華偉,紀相財,黃利昆,等.基于馬爾科夫鏈的道路交通狀況的分析預測[J].科教導刊,2011(21):134-135.

[8] SOWUNMI F A. A markov chain approach to the dynamics of vehicular traffic characteristics in abeokuta metropolis[J]. Research journal of applied sciences engineering & technology,2009,1(3):160-166.

[9] JOHNSON E L, SIVALINGAM K M, MISHRA M. Scheduling in optical wdm networks using hidden markov chain based traffic prediction[J]. Photonic network communication,2001,3(3):269-283.

[10] 沈國江,陳文峰.方案選擇式區域協調控制方法及應用[J].浙江工業大學學報,2016,44(3):237-241.

[11] 丁柏群,宋小艷.平面交叉口交通擁擠技術評價指標體系探討[J].交通標準化,2009(2):10-13.

[12] 孫超,王波,張云龍,等.基于一種交通狀態系數的城市路網交通狀態評價研究[J].公路交通科技,2011,28(5):113-120.

[13] 李瑞敏,唐瑾.城市道路交通流離散模型優化分析[J].公路工程,2015,40(4):19-23.

[14] 郭海鋒,方良君,俞立.基于模糊卡爾曼濾波的短時交通流量預測方法[J].浙江工業大學學報,2013,41(2):218-221.

[15] 譚滿春,李英俊,關占榮,等.周相似特性下交通流組合預測方法研究[J].計算機工程與應用,2007,43(33):193-195.

[16] 聶佩林,龔峻峰.一種路網交通流參數的融合預測方法[J].交通運輸系統工程與信息,2015,15(6):39-45.

[17] 劉擎超,陸建,陳淑燕.基于能力區域的交通狀態預測方法[J].物理學報,2014,63(14):94-101.

[18] 孟利民,徐楊.基于動態指數平滑預測的負載均衡算法[J].浙江工業大學學報,2016,44(4):379-382.

(責任編輯：陳石平)

Prediction method of road network traffic state based on Markov process

GUO Haifeng, CAI Huabo, ZHU Chao, ZHA Qi

(College of Information and Engineering, Zhejiang University of Technology, Hangzhou 310023, China)

Aiming at demands of urban traffic control and management for real-time traffic status of road network, this paper firstly gives the definition of traffic state of an intersection and divides the states into 4 levels. Then the state transition probability of each intersection is computed by using Markov process combined with historic data at time intervals of 15 mins, and the next state of each intersection is predicted. Finally, each intersection is classified and a comprehensive evaluation method is used to predict the whole traffic states of a road network. Experimental results show that this method can not only compute the real-time traffic states of each intersection, but also can give the traffic states of the whole road network based on prediction results of different types of intersections, and the average forecast error at the intersection is 7.04%.

urban road network; intersection; Markov process; comprehensive evaluation method; traffic states

2016-12-12

浙江省自然科學基金資助項目(LY14F030012)；中國博士后基金資助項目(2012M511387)

郭海鋒(1977—)，男，吉林松原人，副教授，博士，研究方向為智能交通系統，E-mail:guohf@zjut.edu.cn.

U491.14

A

1006-4303(2017)04-0421-06