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

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

基于馬爾可夫過程的路網(wǎng)交通狀態(tài)預測方法

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

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

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

城市路網(wǎng)；交叉口；馬爾可夫過程；綜合評價法；交通狀態(tài)

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

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

1 馬爾可夫過程預測交叉口的狀態(tài)

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

1.1 馬爾可夫過程

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

馬爾可夫過程實際上是一個將系統(tǒng)狀態(tài)和狀態(tài)轉移定量化的數(shù)學模型，能夠根據(jù)已知系統(tǒng)狀態(tài)對下一時刻系統(tǒng)的狀態(tài)進行分析和預測.確定狀態(tài)轉移概率是關鍵環(huán)節(jié)，它實際上是一個條件概率，即

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

(1)

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

1.2 交叉口狀態(tài)界定

交叉口是城市路網(wǎng)的節(jié)點，其繁忙程度直接反映了所轄范圍內的交通流運行情況.在已有評價交叉口狀態(tài)的指標中，服務水平和飽和度最能直觀地反映交叉口的運行狀態(tài).尤其是服務水平，其能夠客觀地評估一個交叉口當前的運行情況，但是服務水平的獲得通常采取線下分析的方式來進行，難以在線獲得.然而，飽和度則可依據(jù)檢測器獲得的交通流量數(shù)據(jù)以及信號控制參數(shù)信息實時地獲得.因此，為便于定性定量地界定交叉口的交通狀態(tài)，已有相關研究成果對服務水平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.

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

1.3 交叉口狀態(tài)預測

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

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

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

(2)

式中：p11指當前狀態(tài)為1，下一時刻狀態(tài)為1的概率；n11指歷史數(shù)據(jù)中當前狀態(tài)為1，下一時刻狀態(tài)為1的個數(shù)；n1指歷史數(shù)據(jù)中當前狀態(tài)為1的個數(shù).

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

(3)

(4)

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

2 綜合評價法分析路網(wǎng)的交通狀態(tài)

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

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

(5)

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

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

(6)

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

獲得以上數(shù)據(jù)后，可獲得路網(wǎng)交通狀態(tài)下一時刻的綜合評價矩陣，即

(7)

運行狀態(tài)評價矩陣可以對路網(wǎng)交通狀態(tài)進行評定，設路網(wǎng)運行狀態(tài)矩陣為A，其表達式為

(8)

其中

(9)

比較矩陣A中的各元素，較大值則為路網(wǎng)下一時刻的交通狀態(tài).

3 實驗分析

3.1 數(shù)據(jù)準備

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

圖1 簡單路網(wǎng)圖Fig.1 A simple road network

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

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

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

3.2 預測交叉口狀態(tài)

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

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

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

4所示.

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

3.3 確定模糊狀態(tài)評價矩陣

結合預測數(shù)據(jù)及歷史數(shù)據(jù)，可得出兩組實驗中預測時間段的路網(wǎng)模糊狀態(tài)評價矩陣，分別為

(10)

(11)

3.4 確定路網(wǎng)整體狀態(tài)

根據(jù)各類交叉口的權重系數(shù)，得到組1預測時間段的路網(wǎng)運行狀態(tài)矩陣為

(12)

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

(13)

再次比較，暢通狀態(tài)對應的概率最大為0.94，從而得到此時路網(wǎng)整體狀態(tài)為暢通.

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

(a)預測的路網(wǎng)運行狀態(tài)(7：45—8：00)

(b)預測的路網(wǎng)運行狀態(tài)(11：45—12：00)

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

(14)

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

表2 不同交通狀態(tài)預測方法比較

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

3.5 時間性能分析

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

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

表3 方法各階段耗費時間

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

4 結 論

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

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

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

[2] 姜桂艷.道路交通狀態(tài)判別技術與應用[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] 董宏輝,賈利民,孫曉亮,等.城市道路宏觀路網(wǎng)交通狀態(tài)評價方法的研究[J].物流技術,2010,29(8):38-40.

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

[6] 郭偉,姚丹亞,付毅,等.區(qū)域交通流特征提取與交通狀態(tài)評估方法研究[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] 沈國江,陳文峰.方案選擇式區(qū)域協(xié)調控制方法及應用[J].浙江工業(yè)大學學報,2016,44(3):237-241.

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

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

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

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

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

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

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

[18] 孟利民,徐楊.基于動態(tài)指數(shù)平滑預測的負載均衡算法[J].浙江工業(yè)大學學報,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—)，男，吉林松原人，副教授，博士，研究方向為智能交通系統(tǒng)，E-mail:guohf@zjut.edu.cn.

U491.14

A

1006-4303(2017)04-0421-06