李 銳

（安徽省高速公路聯(lián)網(wǎng)運(yùn)營(yíng)有限公司,安徽 合肥 230000）

0 引言

高速公路車(chē)輛行駛路徑預(yù)測(cè)的結(jié)果可用于運(yùn)輸組織優(yōu)化、異常行駛路徑分析、交通狀況預(yù)測(cè)、交通熱點(diǎn)分布分析等，對(duì)高速公路交通管控有著十分重要的意義。[1]在高速公路門(mén)架系統(tǒng)建設(shè)前，對(duì)于環(huán)網(wǎng)造成的多義路徑問(wèn)題，采用在入口和出口中間建設(shè)標(biāo)識(shí)點(diǎn)的方式來(lái)精確識(shí)別和預(yù)測(cè)行駛路徑。2019年啟動(dòng)取消高速公路省界收費(fèi)站工程后，通過(guò)路網(wǎng)增設(shè)的近29 000 套ETC 門(mén)架系統(tǒng)，可以更加精確地實(shí)現(xiàn)路徑識(shí)別，并從ETC 收費(fèi)系統(tǒng)中的入口、出口、門(mén)架、車(chē)道、時(shí)間、車(chē)牌、車(chē)型等數(shù)據(jù)中，挖掘出具有一定特征的車(chē)輛在一定行駛行為和行駛狀態(tài)下的行駛規(guī)律，從而預(yù)測(cè)出車(chē)輛后續(xù)的行經(jīng)門(mén)架，分析異常行駛路徑。[2]該文通過(guò)對(duì)ETC 門(mén)架數(shù)據(jù)的挖掘，構(gòu)建了ETC 門(mén)架序列數(shù)據(jù)庫(kù)，并在此基礎(chǔ)上實(shí)現(xiàn)了單一馬爾可夫鏈，并給出了轉(zhuǎn)移概率的計(jì)算方法。針對(duì)單一馬爾可夫鏈在預(yù)測(cè)上準(zhǔn)確率和覆蓋率不足的缺點(diǎn)，提出了多維融合的馬爾可夫路徑預(yù)測(cè)模型，該模型在單一馬爾可夫鏈的基礎(chǔ)上，將門(mén)架系統(tǒng)數(shù)據(jù)中得到的時(shí)間維、路網(wǎng)維、車(chē)輛維數(shù)據(jù)進(jìn)行多維融合和信息下鉆，預(yù)測(cè)出車(chē)輛的在途后續(xù)行駛路徑。

1 路徑預(yù)測(cè)模型

自1959年車(chē)輛行駛路徑問(wèn)題被提出以來(lái)，很多算法和數(shù)據(jù)模型用于解決行駛路徑計(jì)算和預(yù)測(cè)問(wèn)題。啟發(fā)式算法中的禁忌搜索算法、遺傳算法和模擬退火算法實(shí)現(xiàn)了全局最優(yōu)解的功能，多用于解決最短路徑問(wèn)題；蟻群算法雖然用于解決旅行商問(wèn)題，但是容易陷入局部?jī)?yōu)化的缺陷，不適用路網(wǎng)規(guī)模較大的情況；卡爾曼濾波法基于車(chē)輛運(yùn)動(dòng)模式，對(duì)車(chē)輛未來(lái)行駛路徑進(jìn)行預(yù)測(cè)，也用于道路交通量的預(yù)測(cè)；固定階馬爾可夫模型則可用于短距離路徑預(yù)測(cè)。

根據(jù)《高速公路ETC 門(mén)架系統(tǒng)技術(shù)要求》布設(shè)原則，ETC 門(mén)架與互通立交、入/出口匝道端部、被交道路直線距離1.5～3 km，相鄰兩個(gè)實(shí)體門(mén)架間的平均里程約為15 km。如果能夠通過(guò)車(chē)輛數(shù)據(jù)、路網(wǎng)數(shù)據(jù)、時(shí)間數(shù)據(jù)的融合挖掘，預(yù)測(cè)車(chē)輛即將行駛的下一個(gè)或下幾個(gè)門(mén)架，則實(shí)現(xiàn)了動(dòng)態(tài)預(yù)測(cè)車(chē)輛行駛路徑的目的。因此，在當(dāng)前被ETC 門(mén)架全覆蓋的路網(wǎng)環(huán)境下，更適宜采用馬爾可夫模型進(jìn)行短距離路徑預(yù)測(cè)。

2 基于ETC 門(mén)架序列的單一馬爾可夫鏈

2.1 聯(lián)合概率分布

馬爾可夫模型是基于當(dāng)前狀態(tài)僅僅依賴(lài)于前幾個(gè)狀態(tài)的馬爾可夫假設(shè)來(lái)實(shí)現(xiàn)的。n階馬爾可夫模型的意思表示是：狀態(tài)間的轉(zhuǎn)移僅依賴(lài)于前n個(gè)狀態(tài)的過(guò)程。將車(chē)輛從某個(gè)門(mén)架開(kāi)往下一個(gè)門(mén)架的動(dòng)作表示為該門(mén)架的狀態(tài)轉(zhuǎn)移，該門(mén)架到達(dá)下一個(gè)門(mén)架的概率為轉(zhuǎn)移概率。則根據(jù)一階馬爾可夫鏈，車(chē)輛經(jīng)過(guò)某個(gè)門(mén)架序列的N次觀測(cè)序列的聯(lián)合概率分布為：

式中，p(xi)——車(chē)輛開(kāi)往門(mén)架i的觀測(cè)概率；——車(chē)輛開(kāi)往門(mén)架n的概率觀測(cè)值，該值僅依賴(lài)于車(chē)輛經(jīng)過(guò)門(mén)架n-1 的觀測(cè)概率。由此可知，由前n個(gè)狀態(tài)決定的n階馬爾可夫鏈公式表示如下：

2.2 ETC 門(mén)架序列數(shù)據(jù)庫(kù)

為了能夠基于馬爾可夫模型計(jì)算出車(chē)輛經(jīng)過(guò)某個(gè)門(mén)架序列的概率，需要建立ETC 門(mén)架序列數(shù)據(jù)庫(kù)，實(shí)現(xiàn)對(duì)路網(wǎng)中所有路徑的數(shù)據(jù)化表示，并供路徑預(yù)測(cè)模型調(diào)用。門(mén)架序列可以是單個(gè)門(mén)架，也可以是多個(gè)轉(zhuǎn)移概率為100%所組成的序列。

假設(shè)ETC 車(chē)輛在高速公路上所經(jīng)過(guò)的門(mén)架為一個(gè)門(mén)架序列，則車(chē)輛所經(jīng)過(guò)的門(mén)架序列構(gòu)成ETC 門(mén)架序列數(shù)據(jù)庫(kù)GSDB，表示為：

GSDB={x1,x2, …,xm}，其中xi(i=1…m)表示車(chē)輛行經(jīng)的門(mén)架序列。

2.3 GSDB 單一馬爾可夫鏈

GSDB 馬爾可夫鏈表示為：M=。

X是GSDB 的集合，可表示為{x1,x2, …,xn}，每個(gè)xi對(duì)應(yīng)一個(gè)門(mén)架序列{x1,x2, …,xm}，稱(chēng)為模型的一個(gè)狀態(tài)；

P為轉(zhuǎn)移概率矩陣，P=pij=p(Xt=xi|Xt-1=xi)表示由狀態(tài)xi轉(zhuǎn)移到狀態(tài)xj的概率。

P滿足以下條件：

2.4 基于GSDB 的單一馬爾可夫鏈的路徑預(yù)測(cè)

假設(shè)某輛車(chē)在t時(shí)刻生成的車(chē)輛路徑序列為x，狀態(tài)用xt表示，則t時(shí)刻處于狀態(tài)xi的第i維等于1, 其余各維都為0。則基于GSDB 單一馬爾可夫鏈的未來(lái)路徑預(yù)測(cè)概率為：

可以從矩陣結(jié)果中取概率值最大的前n個(gè)狀態(tài)的集合或者取大于規(guī)定閾值的狀態(tài)集合作為模型的預(yù)測(cè)結(jié)果。

3 多維融合馬爾可夫路徑預(yù)測(cè)模型

在采用單一馬爾可夫鏈預(yù)測(cè)t時(shí)刻車(chē)輛的未來(lái)路徑序列時(shí)，只采用了門(mén)架序列數(shù)據(jù)庫(kù)這一路網(wǎng)維度特征對(duì)所有車(chē)輛的行駛路徑進(jìn)行預(yù)測(cè)。但是車(chē)輛的行駛行為是一個(gè)復(fù)雜的過(guò)程，會(huì)受到多種因素的影響，采用多維數(shù)據(jù)融合技術(shù)，將車(chē)輛類(lèi)別、行駛時(shí)間等維度的數(shù)據(jù)融合至預(yù)測(cè)模型，從細(xì)致的維度來(lái)描述車(chē)輛的通行特征，預(yù)測(cè)結(jié)果將會(huì)更加精準(zhǔn)[3-4]。

3.1 ETC 門(mén)架多維數(shù)據(jù)融合過(guò)程

ETC 門(mén)架數(shù)據(jù)融合經(jīng)歷了數(shù)據(jù)獲取、數(shù)據(jù)預(yù)處理、特征提取、維度分類(lèi)、融合決策的過(guò)程。如圖1 所示，從ETC 門(mén)架系統(tǒng)中獲取ETC 門(mén)架數(shù)據(jù)后，根據(jù)應(yīng)用方向選取樣本數(shù)據(jù)，從樣本數(shù)據(jù)中提取應(yīng)用特征，如車(chē)輛特征、門(mén)架特征、時(shí)間特征、路網(wǎng)特征等，將特征進(jìn)行維度分類(lèi)，將分類(lèi)后的各個(gè)維度及下鉆維度輸入融合決策模型，最終得到?jīng)Q策結(jié)果。

圖1 數(shù)據(jù)融合過(guò)程

（1）門(mén)架數(shù)據(jù)及相關(guān)樣本數(shù)據(jù)。ETC 門(mén)架系統(tǒng)產(chǎn)生的數(shù)據(jù)包括：ETC 門(mén)架交易流水、ETC 通行記錄、牌識(shí)流水記錄、CPC 卡通行記錄、原始收費(fèi)數(shù)據(jù)、異常交易數(shù)據(jù)、抓拍圖片、視頻、日志數(shù)據(jù)和主要設(shè)備設(shè)施狀態(tài)數(shù)據(jù)等。需要采用這些原始數(shù)據(jù)的數(shù)據(jù)庫(kù)表生成新的用于構(gòu)建GSDB 和實(shí)現(xiàn)路徑預(yù)測(cè)的表，并采集樣本數(shù)據(jù)進(jìn)行概率計(jì)算。部分核心信息如表1 所列。

表1 ETC 門(mén)架部分核心信息

（2）門(mén)架數(shù)據(jù)維度處理?！熬S”讓觀察者能夠從某個(gè)特定的角度觀察到事物比較顯而易見(jiàn)的屬性，不同的角度所觀察到的屬性是割裂的，但是利用“維”之間的交匯點(diǎn)實(shí)現(xiàn)多個(gè)“維”的融合后，能夠從全局的角度生成新的事物屬性。

將用于行駛路徑預(yù)測(cè)的門(mén)架樣本數(shù)據(jù)特征值分成時(shí)間維、路網(wǎng)維、車(chē)輛維。通過(guò)時(shí)間維能夠觀測(cè)到車(chē)輛行駛?cè)肟?、出口、各個(gè)門(mén)架以及門(mén)架區(qū)間的具體時(shí)間和通行耗時(shí)；通過(guò)路網(wǎng)維能夠觀測(cè)到高速公路的門(mén)架分布、路網(wǎng)分布，生成門(mén)架序列數(shù)據(jù)庫(kù)GSDB；通過(guò)車(chē)輛維能夠觀測(cè)到車(chē)輛車(chē)牌、車(chē)型、類(lèi)別、顏色、速度等車(chē)輛的動(dòng)態(tài)和靜態(tài)特征。在進(jìn)行維度融合并采用預(yù)測(cè)模型實(shí)現(xiàn)決策處理后，就能夠推算出新的行駛特征結(jié)論，如圖2所示。

圖2 ETC 門(mén)架三維數(shù)據(jù)立方圖

3.2 多維融合馬爾可夫路徑預(yù)測(cè)模型

如果僅采用該文2.3 節(jié)描述的基于ETC 門(mén)架序列的單一馬爾可夫鏈進(jìn)行決策處理，得到的行駛特征結(jié)論只能是：從A 入口駛?cè)敫咚俟?，行?jīng)某門(mén)架序列的車(chē)輛，從B 出口駛出的概率為pj。這一結(jié)論過(guò)于粗糙，存在較大誤差。因此，該文進(jìn)一步提出了多維數(shù)據(jù)融合的馬爾可夫路徑預(yù)測(cè)模型，目的是將車(chē)輛特征、行駛時(shí)間等維度的數(shù)據(jù)融合至預(yù)測(cè)模型，從更加細(xì)致的維度來(lái)描述車(chē)輛的通行特征，得到更加精準(zhǔn)的預(yù)測(cè)結(jié)果。[5]如：某種車(chē)型的車(chē)輛在某個(gè)時(shí)間段內(nèi)通過(guò)A 入口進(jìn)入高速公路，以平均時(shí)速80 km/h 行經(jīng)某門(mén)架序列的概率為pj，滿足以上條件的車(chē)輛，從B 出口駛出的概率為pj。

基于車(chē)輛通行行為特征實(shí)現(xiàn)車(chē)輛維度分類(lèi)，通行行為包括入/出口組合、GSDB 中的門(mén)架序列組合、平均時(shí)速、通行車(chē)道等。車(chē)輛類(lèi)別的統(tǒng)計(jì)歸類(lèi)采用聚類(lèi)算法實(shí)現(xiàn)，使得同一類(lèi)車(chē)輛之間的通行行為特征相似度最高。設(shè)C={c1,c2, …,ck}表示車(chē)輛的類(lèi)別，任意車(chē)輛屬于類(lèi)別的概率為PC，則：

基于車(chē)輛通行時(shí)間實(shí)現(xiàn)車(chē)輛時(shí)間維度分類(lèi)，通行時(shí)間包括行經(jīng)入/出口時(shí)間、行經(jīng)門(mén)架時(shí)間。設(shè)T={t1,t2, …,tm}表示時(shí)間類(lèi)別，假設(shè)某輛車(chē)t時(shí)刻的時(shí)間類(lèi)別為t1，表達(dá)的意思是某輛車(chē)在t時(shí)刻經(jīng)過(guò)了某入口/出口/門(mén)架，或在t時(shí)間段經(jīng)過(guò)了某門(mén)架序列，該車(chē)輛時(shí)間類(lèi)別為ti的概率為Pti，則：

多維數(shù)據(jù)融合的馬爾可夫鏈表示為：M=。其中，X是GSDB 的集合，可表示為{x1,x2, …,xn}，每個(gè)xi對(duì)應(yīng)一個(gè)門(mén)架序列{x1,x2, …,xn}，稱(chēng)為模型的一個(gè)狀態(tài)；K表示車(chē)輛維度的類(lèi)別數(shù)，C={c1,c2,…,ck}表示車(chē)輛的類(lèi)別，P(C)表示不同類(lèi)別車(chē)輛的概率分布；T表示時(shí)間維度的類(lèi)別數(shù)，P(T)表示不同時(shí)間類(lèi)別的概率分布；MCT={mct11, mct12, …, mct1n}{mctk1, mctk2,…, mctkn}，表示融合時(shí)間維和車(chē)輛維的馬爾可夫鏈集合，每一個(gè)元素mctkn描述了車(chē)輛類(lèi)別為ck、時(shí)間類(lèi)別為tn的馬爾可夫鏈，它的轉(zhuǎn)移概率矩陣表示為：

假設(shè)某輛車(chē)在t時(shí)刻生成的車(chē)輛路徑序列為x，狀態(tài)用xt表示，則t時(shí)刻處于狀態(tài)xi的第i維等于1, 其余各維都為0。則多維數(shù)據(jù)融合的馬爾可夫鏈的未來(lái)路徑預(yù)測(cè)概率為：

可以從矩陣結(jié)果中取概率值最大的前n個(gè)狀態(tài)的集合或者取大于規(guī)定閾值的狀態(tài)集合作為模型的預(yù)測(cè)結(jié)果。

4 結(jié)束語(yǔ)

該文在對(duì)目前成熟的路徑預(yù)測(cè)模型進(jìn)行比較后，針對(duì)當(dāng)前已經(jīng)被門(mén)架覆蓋全網(wǎng)的高速公路路網(wǎng)環(huán)境，采用馬爾可夫鏈實(shí)現(xiàn)未來(lái)行駛路徑預(yù)測(cè)。通過(guò)建立ETC 門(mén)架序列數(shù)據(jù)庫(kù)（GSDB），實(shí)現(xiàn)了對(duì)路網(wǎng)維的數(shù)據(jù)表示，基于GSDB 的單一馬爾可夫鏈的路徑預(yù)測(cè)結(jié)果可以是經(jīng)過(guò)下一個(gè)門(mén)架的概率、經(jīng)過(guò)下一個(gè)出口的概率、經(jīng)過(guò)下一個(gè)門(mén)架序列的概率等。但是單一馬爾可夫鏈的預(yù)測(cè)準(zhǔn)確率不高，因此我們提出了多維融合的馬爾可夫路徑預(yù)測(cè)模型，該模型引入了車(chē)輛維度和時(shí)間維度進(jìn)行更加細(xì)致的特征分類(lèi)，能夠更加明確地對(duì)車(chē)輛行為特征進(jìn)行描述和劃分，預(yù)測(cè)結(jié)果更具有參考性。