一種基于改進(jìn)的馬爾可夫鏈的交通狀況預(yù)測(cè)模型

周明升，劉抒揚(yáng)

(1.上海外高橋保稅區(qū)聯(lián)合發(fā)展有限公司，上海 200131；2.上海商學(xué)院 商務(wù)信息學(xué)院，上海 201400)

0 引言

確定了用戶的出發(fā)地和目的地后，準(zhǔn)確預(yù)測(cè)各條可能路線未來(lái)某段時(shí)間(行駛到達(dá)路段時(shí))的交通狀況，可以為用戶推薦最優(yōu)出行線路，減少行駛時(shí)間，也方便用戶私家車與公共交通的選擇。某段線路上的行駛時(shí)間應(yīng)綜合考慮以下幾個(gè)因素：路線本身的情況、行駛到該路線上時(shí)的交通流量和駕駛員的駕駛習(xí)慣等。當(dāng)前對(duì)交通狀況、路線推薦的研究主要有以下幾類：(1)基于交通分析的方法[1-2]：通過(guò)道路上的識(shí)別器及車流量信息，通過(guò)“識(shí)別器-車流量-行駛方向”的范式來(lái)研究交通狀況推薦路線，這種方法準(zhǔn)確性的前提是要有足夠的識(shí)別器和車流量信息，數(shù)據(jù)獲取比較困難[3]。通過(guò)獲取車輛信息，估計(jì)實(shí)時(shí)交通流量，預(yù)測(cè)將來(lái)的交通狀況[4-6]，其基于路段的分析需要借助大量數(shù)據(jù)進(jìn)行分析，當(dāng)采樣率低、數(shù)據(jù)稀疏時(shí)無(wú)法準(zhǔn)確估計(jì)。(2)基于交通模式學(xué)習(xí)的方法：給出了概率為基礎(chǔ)的方法，通過(guò)用戶歷史GPS 軌跡數(shù)據(jù)，預(yù)測(cè)駕駛員的目的地和行車路徑[7-8]。其通過(guò)學(xué)習(xí)GPS 軌跡數(shù)據(jù)來(lái)獲取駕駛和速度模式計(jì)算最快路線[9-10]。(3)智能推薦：試圖挖掘駕駛員道路選擇的傾向，通過(guò)人機(jī)交互或推理模型推薦個(gè)性化路線，其推薦路線沒有隨行駛時(shí)間而優(yōu)化[11]。其通過(guò)GPS 軌跡數(shù)據(jù)，尋找關(guān)鍵節(jié)點(diǎn)和關(guān)鍵路線，結(jié)合用戶行為，推薦最快線路[12-13]。

與之前的研究不同，本文的研究通過(guò)配置了GPS 的出租車作為交通狀況的接收器，獲取歷史交通路況和實(shí)時(shí)交通路況信息，通過(guò)多階馬爾可夫鏈模型預(yù)測(cè)未來(lái)的交通狀況。出租車的GPS 日志信息既反映了不同時(shí)間、不同道路的交通狀況，也體現(xiàn)了出租車駕駛員的智慧，可以體現(xiàn)駕駛員的行為習(xí)慣。本文不是直接從GPS 軌跡數(shù)據(jù)中直接分析道路行駛速度和駕駛員駕駛模式，而是通過(guò)馬爾可夫鏈來(lái)預(yù)測(cè)某些路線將來(lái)某段時(shí)間的交通狀況。預(yù)測(cè)過(guò)程中，將多階馬爾可夫鏈轉(zhuǎn)化為一階馬爾可夫鏈，提高了運(yùn)算效率和用戶響應(yīng)速度。

1 模型建立

1.1 變量定義

假設(shè)交通狀況服從m 階馬爾可夫鏈，模型中相關(guān)概念、變量定義如表1 所示。

表1 變量定義

1.2 問(wèn)題描述

交通狀況預(yù)測(cè)模型框架如圖1 所示。其中，H 表示歷史交通狀況，R 表示實(shí)時(shí)交通路況，F(xiàn) 表示將來(lái)的交通狀況。本文要做的是用歷史交通狀況(H)和實(shí)時(shí)交通路況(R)，預(yù)測(cè)將來(lái)某段時(shí)間的交通路況(F)，即H+R→F。

圖1 交通狀況預(yù)測(cè)模型框架

時(shí)間間隔定義為：

根據(jù)實(shí)際交通狀況，最小時(shí)間間隔τ 通常是固定的(是外部變量，由交通系統(tǒng)自身決定，如10 min、15 min、30 min 等)。預(yù)測(cè)間隔φ 由用戶查詢時(shí)輸入，為最小時(shí)間間隔τ 的整數(shù)倍，即：

根據(jù)上述定義，問(wèn)題轉(zhuǎn)換為已知?dú)v史交通狀況和當(dāng)前交通狀況，如何預(yù)測(cè)第k 段(即將來(lái)kτ 時(shí)間)路況的問(wèn)題。根據(jù)模型假設(shè)，如果已知?dú)v史交通狀況和當(dāng)前交通狀況，求得初始轉(zhuǎn)移概率矩陣和k 步狀態(tài)轉(zhuǎn)移矩陣，便可求得時(shí)間間隔φ 時(shí)的交通狀況。于是，?yi∈S，i=1，2，…，n，本文將問(wèn)題轉(zhuǎn)換為：根據(jù)已知分布集合，預(yù)測(cè)Ym+k的分布，得到轉(zhuǎn)移矩陣：

其中，m 和k 是關(guān)鍵指標(biāo)，m 根據(jù)歷史數(shù)據(jù)測(cè)算得出或事先給出，k 由用戶輸入的時(shí)間間隔決定。

1.3 實(shí)驗(yàn)?zāi)Ｐ?/h3>

建模和計(jì)算過(guò)程如下：

(1)用貝葉斯概率模型計(jì)算S 空間的m 階馬爾可夫鏈的1 步狀態(tài)轉(zhuǎn)移矩陣P(1)。

根據(jù)貝葉斯模型理論，狀態(tài)轉(zhuǎn)移矩陣P(1)可由下面公式求出：

舉例說(shuō)明如下，假設(shè)狀態(tài)空間S={1，2}(其中1 表示暢通，2 表示擁堵)，通過(guò)歷史GPS 數(shù)據(jù)可計(jì)算得出某路線的初始轉(zhuǎn)移概率，得到轉(zhuǎn)移矩陣P(1)，如圖2所示，其中第1，1行第2列的值P1，1→2=0.125表示從狀態(tài){Y1=1，Y2=1}到Y(jié)3=2的概率。P1，1→2及P(1)中其他元素的值由貝葉斯概率公式求出。

圖2 P=P(1)

(2)通過(guò)變量的矢量化處理，將m 階馬爾可夫鏈轉(zhuǎn)換為Sm空間1 階馬爾可夫鏈。

將S 空間上的m 階馬爾可夫鏈轉(zhuǎn)換為Sm空間1 階馬爾可夫鏈[14]，可以簡(jiǎn)化運(yùn)算，轉(zhuǎn)換過(guò)程如圖3 所示。

圖3 將S 空間上的馬爾可夫鏈轉(zhuǎn)換為Sm 空間的馬爾可夫鏈

接下來(lái)，本文計(jì)算Sm空間上Zi的1 步狀態(tài)轉(zhuǎn)移矩陣，計(jì)算公式如下：

圖4 P=P′(1)

(3)計(jì)算Sm空間上數(shù)列Zi的k 步狀態(tài)轉(zhuǎn)移矩陣。

根據(jù)Chapman-Kolmogorov 方程[13]，Sm空間的Zi的k步狀態(tài)轉(zhuǎn)移矩可以由矩陣P′自乘k 次得到(P′(k)=P′k），即：

如果k=4，則步驟(1)中在Sm空間的k 步狀態(tài)轉(zhuǎn)移矩陣轉(zhuǎn)換如圖5 所示。

圖5 P′(4)=P′4

(4)將步驟(3)的結(jié)果，轉(zhuǎn)換為S 空間中m 階馬爾可夫鏈的k 步狀態(tài)轉(zhuǎn)移矩陣P(k)。

這一步可以看作是步驟(2)的逆運(yùn)算，狀態(tài)轉(zhuǎn)移矩陣計(jì)算方法為：

①當(dāng)1＜k＜m 時(shí)，

根據(jù)上述公式，步驟(1)例子的k 步狀態(tài)轉(zhuǎn)移矩陣(k=4)如圖6 所示。

圖6 P=P(4)

1.4 模型分析

根據(jù)上述模型過(guò)程，本文先根據(jù)歷史記錄計(jì)算S 空間中馬爾可夫鏈{Yi}的1 步狀態(tài)轉(zhuǎn)移矩陣P(1)，當(dāng)k ＞1 時(shí)候，狀態(tài)轉(zhuǎn)移矩陣P′(k)和P(k)可由上述步驟求得[15-16]。計(jì)算P(k)的時(shí)間復(fù)雜度為O(k·|S|∈m)(其中∈＜2.376)，這樣要比全部用貝葉斯概率模型計(jì)算效率高。實(shí)際應(yīng)用中，馬爾可夫鏈的階數(shù)m 和狀態(tài)空間S 的階數(shù)通常是比較小的(如m≤3，|S|≤5)，所以，步驟(2)～步驟(4)的計(jì)算采用在線計(jì)算方式，以提高用戶相應(yīng)速度。

計(jì)算得出狀態(tài)轉(zhuǎn)移矩陣后，本文將得到未來(lái)某段時(shí)間(φ=kτ)的路況，結(jié)合用戶的行為分析，可以計(jì)算通過(guò)某段線路的時(shí)間，進(jìn)而進(jìn)行最優(yōu)路線推薦。

2 實(shí)驗(yàn)分析

2.1 數(shù)據(jù)來(lái)源及參數(shù)配置

(1)數(shù)據(jù)來(lái)源

本文使用的數(shù)據(jù)來(lái)自微軟GeoLife 項(xiàng)目的公開數(shù)據(jù)集。它記錄了北京市超過(guò)33 000 輛出租車連續(xù)3 個(gè)月的GPS 日志數(shù)據(jù)，行駛里程超過(guò)4 億公里，GPS 日志點(diǎn)超過(guò)7.9 億個(gè)，平均間隔為3.1 min，相鄰點(diǎn)平均距離約600 m[12]。本文用前兩個(gè)月的數(shù)據(jù)作為訓(xùn)練集，抽取第3個(gè)月的數(shù)據(jù)作為測(cè)試集。本文抽取了10 個(gè)工作日、天氣狀況良好、5 條道路的所有GPS 數(shù)據(jù)作為測(cè)試數(shù)據(jù)集，樣本平均時(shí)間間隔3.2 min，相鄰點(diǎn)平均距離627 m。

(2)參數(shù)配置

實(shí)驗(yàn)中，本文定義最小時(shí)間間隔τ 為15 min，預(yù)測(cè)時(shí)間間隔φ 為τ 的整數(shù)倍(如15 min、30 min 等)(即k 取1，2等)，馬爾可夫鏈的階數(shù)m 取1、2、3、4，分別進(jìn)行測(cè)試。

2.2 模型評(píng)價(jià)

2.2.1 比較對(duì)象

本文的預(yù)測(cè)方法分別與T-Drive 方法[12]、ARIMA 方法[13]進(jìn)行比較。ARIMA 方法是著名的交通狀況基礎(chǔ)預(yù)測(cè)方法，它依靠當(dāng)前交通狀況信息(通過(guò)GPS、高速公路探測(cè)器等獲得)，預(yù)測(cè)將來(lái)某段時(shí)間的交通狀況；T-Drive方法通過(guò)對(duì)歷史GPS 日志信息的分析，挖掘交通模式，然后根據(jù)其分布預(yù)測(cè)某時(shí)段、某路線的交通狀況。

2.2.2 評(píng)價(jià)方法

本文用均方根誤差(Root Mean Square Error，RMSE)來(lái)評(píng)價(jià)預(yù)測(cè)結(jié)果的準(zhǔn)確性，定義：

(1)預(yù)測(cè)時(shí)間：分別用本文的預(yù)測(cè)模型和其他預(yù)測(cè)模型來(lái)預(yù)測(cè)將來(lái)某時(shí)間段、某段路線(可以是道路的組合)的通過(guò)時(shí)間。

(2)基準(zhǔn)行駛時(shí)間：考慮到工作日與非工作日、時(shí)間段、天氣狀況、駕駛員經(jīng)驗(yàn)等因素對(duì)行駛時(shí)間的影響，本文選擇同一時(shí)間段、同一線路上所有出租車(配置了GPS)的平均通過(guò)時(shí)間作為基準(zhǔn)通過(guò)時(shí)間(xi)。

2.2.3 評(píng)價(jià)結(jié)果

本文分別用時(shí)間段、不同時(shí)間間隔φ(因?yàn)棣?kτ，τ由外部因素決定，k 變化引起φ 的變化)下3 種方法的RMSE 進(jìn)行比較(根據(jù)RMSE 的定義，RMSE 越低，預(yù)測(cè)的準(zhǔn)確率越高)，然后分析m(馬爾可夫鏈的階數(shù))取值不同，對(duì)本文的模型預(yù)測(cè)結(jié)果準(zhǔn)確率的影響。

圖7 描述了時(shí)間間隔φ 固定時(shí)(實(shí)驗(yàn)中φ=60 min)，3種方法在工作日不同時(shí)間段的RMSE 值。結(jié)果顯示，本文方法比ARIMA 方法和T-Drive 方法要優(yōu)異，特別是高峰時(shí)段(AM7:30-AM9：30)。

圖7 φ=60 min 時(shí)，3 種方法的RMSE 比較

圖8 描述了時(shí)間間隔φ 對(duì)預(yù)測(cè)誤差的影響。隨著時(shí)間增加，3 種方法的誤差都在增大，但本文的方法誤差更小。換句話說(shuō)，在相同的誤差要求下，本文可以預(yù)測(cè)更長(zhǎng)時(shí)間的交通狀況。

圖8 φ 取不同值下3 種方法的RMSE 比較(τ=15 min)

圖9 描述了馬爾可夫鏈的階數(shù)選擇對(duì)準(zhǔn)確性的影響。結(jié)果顯示，其他環(huán)境不變時(shí)，m 取值越大，結(jié)果越準(zhǔn)確。這與時(shí)間情況是一致的，一段時(shí)間以后的交通狀況不僅受到當(dāng)前交通狀況的影響，也受到之前若干時(shí)間交通狀況的影響。但m 取值越大，意味著計(jì)算的難度越大。

圖9 m 的不同取值對(duì)RMSE 的影響

3 結(jié)論

準(zhǔn)確預(yù)測(cè)未來(lái)某段時(shí)間的交通路況是進(jìn)行路線推薦的前提和關(guān)鍵，本文提供了一種基于多階馬爾可夫鏈的交通狀態(tài)預(yù)測(cè)方法。作為一個(gè)對(duì)實(shí)用效果要求很高的課題，為提高模型運(yùn)算速度，提高對(duì)用戶的響應(yīng)速度，對(duì)歷史數(shù)據(jù)進(jìn)行預(yù)處理、預(yù)計(jì)算(初始狀態(tài)轉(zhuǎn)移矩陣等結(jié)果存放在服務(wù)器中)，確定好用戶的始發(fā)地和目的地后，本文對(duì)其各條可能路線、未來(lái)某段時(shí)間的交通路況進(jìn)行在線運(yùn)算。運(yùn)算過(guò)程中，本文將多階馬爾可夫鏈轉(zhuǎn)換為一階馬爾可夫鏈，進(jìn)一步提高了運(yùn)算效率。實(shí)驗(yàn)表明，即使采用較小的階數(shù)，也可以得出比較準(zhǔn)確的結(jié)果，因此本文的方法是行之有效的。