路 珊， 徐 剛， 趙卓峰， 丁維龍

1(北方工業(yè)大學(xué) 大規(guī)模流數(shù)據(jù)集成與分析技術(shù)北京市重點(diǎn)實(shí)驗(yàn)室，北京 100043)

2(兗州煤業(yè)股份有限公司，鄒城 273500)

1 引言

隨著高速公路的迅速建設(shè)，路網(wǎng)結(jié)構(gòu)越來越復(fù)雜，在車輛進(jìn)出兩個(gè)收費(fèi)站點(diǎn)之間具有多條可能行駛的路徑，從而產(chǎn)生了多義路徑問題. 當(dāng)前，高速路網(wǎng)中關(guān)鍵位置設(shè)置了大量配備車牌拍照系統(tǒng)或RFID裝備的識(shí)別點(diǎn)，用來幫助準(zhǔn)確判定車輛駛經(jīng)路徑，但這些識(shí)別設(shè)備受環(huán)境亮度或透明度不夠、硬件設(shè)備故障的影響造成車輛識(shí)別不清，使得車輛在進(jìn)出收費(fèi)站點(diǎn)間的監(jiān)測數(shù)據(jù)缺失，車輛實(shí)際行駛路徑難以準(zhǔn)確識(shí)別. 因此，高速公路運(yùn)營中亟待解決的一個(gè)重要問題是如何在多義路徑中確定一條車輛的駛經(jīng)路徑，進(jìn)而實(shí)現(xiàn)通行費(fèi)用的正確收取和合理拆分，維護(hù)道路使用者和業(yè)主的合法利益.

目前，在高速路中多義路徑識(shí)別采用基于識(shí)別點(diǎn)的路徑識(shí)別方法，該方法通過車牌拍照系統(tǒng)或RFID裝備實(shí)現(xiàn)路徑識(shí)別，但是這種方法在有不利因素存在的時(shí)候，準(zhǔn)確度低. 近幾年，為了更好的監(jiān)測車輛的行駛路徑，在高速路的重要路段上設(shè)置了大量的識(shí)別點(diǎn)，識(shí)別點(diǎn)的前端設(shè)備會(huì)實(shí)時(shí)上傳車輛的監(jiān)測數(shù)據(jù)，同時(shí)，高速路收費(fèi)站會(huì)上傳收費(fèi)數(shù)據(jù)，這兩類數(shù)據(jù)上傳至數(shù)據(jù)中心進(jìn)行存儲(chǔ)，積累了大量的車輛歷史通行數(shù)據(jù). 能否充分利用這些歷史數(shù)據(jù)在數(shù)據(jù)缺失時(shí)輔助進(jìn)行多義路徑識(shí)別成為提高路徑識(shí)別精度的一個(gè)新解決思路.

車輛的歷史通行數(shù)據(jù)主要有收費(fèi)數(shù)據(jù)和識(shí)別點(diǎn)監(jiān)測數(shù)據(jù)兩類. 其中，監(jiān)測數(shù)據(jù)是由高速路上的識(shí)別點(diǎn)上傳，某省高速路上收費(fèi)站有數(shù)百個(gè)，識(shí)別點(diǎn)有近千個(gè)，高峰時(shí)平均每分鐘就會(huì)上傳上萬條收費(fèi)監(jiān)測數(shù)據(jù)，隨著時(shí)間的變化，積累了大量的車輛歷史通行數(shù)據(jù)，歷史通行數(shù)據(jù)數(shù)據(jù)量龐大. 為此，需要設(shè)計(jì)實(shí)現(xiàn)一個(gè)可以快速處理大批量歷史數(shù)據(jù)的計(jì)算模型，通過該模型實(shí)現(xiàn)車輛行駛路徑的準(zhǔn)確高效識(shí)別.

本文設(shè)計(jì)了一種基于歷史數(shù)據(jù)的高速多義路徑概率識(shí)別方法，對(duì)車輛的歷史收費(fèi)數(shù)據(jù)和監(jiān)測數(shù)據(jù)使用基于路段聚類的方法進(jìn)行路段概率計(jì)算并與貪心算法相結(jié)合進(jìn)行路徑識(shí)別. 文章的具體組織如下：首先，提出本文需要解決的問題并從研究方法和所用技術(shù)兩個(gè)方面介紹路徑識(shí)別的相關(guān)工作，然后介紹基于路段聚類的路段概率值計(jì)算流程和貪心算法與概率矩陣相結(jié)合實(shí)現(xiàn)路徑識(shí)別的方法; 最后給出總結(jié).

2 相關(guān)工作

目前，針對(duì)高速路上多義路徑識(shí)別方法以及所用技術(shù)，在國內(nèi)外已經(jīng)有了許多研究成果[1，2]. 其中多義路徑識(shí)別方法主要分為兩類，分別是概率識(shí)別和精確識(shí)別方法，技術(shù)方面又分為傳統(tǒng)技術(shù)和大數(shù)據(jù)技術(shù).

研究方法方面，路徑識(shí)別方法主要分為概率識(shí)別方法和精確識(shí)別方法. 概率識(shí)別方法是指依據(jù)交通均衡與非均衡理論通過數(shù)理統(tǒng)計(jì)方法去計(jì)算路徑，精確識(shí)別方法是指依靠高速路中前端設(shè)備采集信息的功能去記錄路徑. 關(guān)于概率識(shí)別，文獻(xiàn)[3]在分析了影響路徑識(shí)別方法選擇的各種相關(guān)因素基礎(chǔ)上對(duì)布瑞爾交通分配模型進(jìn)行了改進(jìn)，重新定義和標(biāo)定其參數(shù). 該方法依賴于公式中的大量參數(shù)，而參數(shù)的標(biāo)定受很多因素的影響，降低了方法的精確度. 文獻(xiàn)[4]利用每個(gè)車輛在公路網(wǎng)上的行駛時(shí)間來估計(jì)每個(gè)OD對(duì)間的車輛行駛時(shí)間，然后對(duì)比實(shí)際和估計(jì)的OD間行駛時(shí)間，提出修正遺傳算法以獲得車輛的路徑流，該方法需要統(tǒng)計(jì)大量的數(shù)據(jù)，消耗了大量的人力物力. 關(guān)于精確識(shí)別，文獻(xiàn)[5]研究了車牌拍照的路徑識(shí)別方法，詳細(xì)分析了其中的關(guān)鍵原理與技術(shù)，其中車牌識(shí)別過程受環(huán)境影響較大，不能滿足路徑識(shí)別的高精確度要求. 文獻(xiàn)[6]對(duì)RFID射頻識(shí)別技術(shù)的工作原理、特點(diǎn)進(jìn)行分析，并結(jié)合高速公路運(yùn)輸特點(diǎn)，設(shè)計(jì)了基于RFID射頻技術(shù)的高速路收費(fèi)系統(tǒng). 該方法中使用的無源射頻卡的發(fā)射距離有限，有時(shí)會(huì)導(dǎo)致車輛難以被識(shí)別到.

處理技術(shù)方面，處理交通數(shù)據(jù)使用的技術(shù)主要有傳統(tǒng)技術(shù)和大數(shù)據(jù)技術(shù). 傳統(tǒng)技術(shù)是指用關(guān)系型數(shù)據(jù)庫處理數(shù)據(jù)，大數(shù)據(jù)技術(shù)是指用Hadoop等大數(shù)據(jù)框架處理數(shù)據(jù). 關(guān)于傳統(tǒng)技術(shù)，文獻(xiàn)[7]研究了動(dòng)態(tài)交通信息處理技術(shù)，其中使用關(guān)系型數(shù)據(jù)庫存儲(chǔ)交通信息，但由于關(guān)系型數(shù)據(jù)庫存儲(chǔ)量有限，而涉及到的交通數(shù)據(jù)量超過了該數(shù)據(jù)庫的存儲(chǔ)范圍，所以采用定期刪除數(shù)據(jù)的方法來接收新的數(shù)據(jù). 這種方法使得歷史數(shù)據(jù)不完整，影響后續(xù)數(shù)據(jù)的使用. 關(guān)于大數(shù)據(jù)技術(shù)，文獻(xiàn)[8]提出了一個(gè)適合于城市交通網(wǎng)兩節(jié)點(diǎn)間計(jì)算最短路徑的算法，并將任意兩節(jié)點(diǎn)間最短路徑計(jì)算過程移植至MapReduce框架上，得出最短路徑的路徑矩陣和權(quán)值矩陣. MapReduce是大數(shù)據(jù)平臺(tái)Hadoop上的分布式計(jì)算框架，可快速處理大批量的歷史數(shù)據(jù). 為此，本文利用車輛歷史的收費(fèi)數(shù)據(jù)和監(jiān)測數(shù)據(jù)，通過基于路段的聚類方法進(jìn)行概率數(shù)據(jù)計(jì)算，并結(jié)合貪心算法進(jìn)行路徑識(shí)別. 其中針對(duì)數(shù)據(jù)量龐大的歷史數(shù)據(jù)，使用Map Reduce分布式計(jì)算框架進(jìn)行處理，提高了數(shù)據(jù)處理的效率.

3 基于路段聚類的歷史數(shù)據(jù)處理

高速路路網(wǎng)結(jié)構(gòu)復(fù)雜，路網(wǎng)中的路徑可以看成是由多個(gè)相互連接的路段所組成，可將收費(fèi)站和識(shí)別點(diǎn)看做是路網(wǎng)中的點(diǎn)，它們之間由路段相連接，因此車輛行駛某一路徑的概率其實(shí)是該路徑所包含的各路段通行概率的一個(gè)組合[9]. 針對(duì)這種情況，在路徑識(shí)別前，應(yīng)預(yù)先計(jì)算出每個(gè)路段的通行概率作為基礎(chǔ)數(shù)據(jù)，以便路徑識(shí)別時(shí)，根據(jù)路徑中各路段的概率去辨別車輛究竟走哪一條路徑. 現(xiàn)實(shí)中，影響一個(gè)司機(jī)路徑選擇的因素很多，例如道路路況、路長、擁擠程度等因素. 而歷史通行記錄是綜合各種因素后道路使用者的最終道路選擇情況，所以基于車輛歷史通行數(shù)據(jù)進(jìn)行路段概率計(jì)算是更為精確的方法. 高速路歷史通行數(shù)據(jù)包括收費(fèi)數(shù)據(jù)和監(jiān)測數(shù)據(jù)，數(shù)據(jù)量龐大，采用傳統(tǒng)的數(shù)據(jù)處理方式效率低、時(shí)效性差. 所以這里采用Hadoop中的MapReduce計(jì)算框架來進(jìn)行數(shù)據(jù)處理，MapReduce框架是分布式計(jì)算框架，適合處理海量數(shù)據(jù)，處理數(shù)據(jù)速度快.

步驟1. 車輛的歷史通行數(shù)據(jù)，包括高速路收費(fèi)數(shù)據(jù)和識(shí)別點(diǎn)監(jiān)測數(shù)據(jù)，這兩類數(shù)據(jù)都屬于單點(diǎn)數(shù)據(jù)，不利于計(jì)算路段車流量. 所以首先，需要根據(jù)收費(fèi)數(shù)據(jù)和監(jiān)測數(shù)據(jù)構(gòu)建車輛歷史路徑，再在路徑數(shù)據(jù)中去判斷每個(gè)路段的通行概率，這樣結(jié)果會(huì)更為精確. 構(gòu)建車輛路徑的MapReduce處理流程如圖1所示.

圖1 構(gòu)建路徑流程

該MapReduce作業(yè)中，輸入是歷史收費(fèi)數(shù)據(jù)、監(jiān)測數(shù)據(jù)，輸出是拼接的車輛歷史路徑數(shù)據(jù). 在map階段，掃描每條車輛收費(fèi)記錄，提取其中的車牌號(hào)、進(jìn)出站點(diǎn)時(shí)間，然后遍歷歷史監(jiān)測數(shù)據(jù)，查詢該車在進(jìn)出收費(fèi)站點(diǎn)時(shí)間范圍內(nèi)的監(jiān)測數(shù)據(jù)，并按照時(shí)間先后順序?qū)④囕v經(jīng)過的站點(diǎn)數(shù)據(jù)拼接. 中間鍵值對(duì)被發(fā)送到reduce階段進(jìn)行存儲(chǔ)，其中key為車牌號(hào)，value為拼接的車輛路徑數(shù)據(jù).

步驟2. 上述步驟構(gòu)建出了車輛的歷史路徑，接下來要將路徑拆分為不同的路段，并統(tǒng)計(jì)每個(gè)路段的通行次數(shù)，這里使用基于路段的聚類方法去統(tǒng)計(jì)路段通行次數(shù)，可以把每條車輛歷史路徑都看成是多個(gè)彼此相連接的路段的組合，遍歷車輛歷史路徑，遍歷每一條路徑數(shù)據(jù)時(shí)，判斷該條路徑中包含哪幾個(gè)路段，然后將對(duì)應(yīng)的路段的通行次數(shù)各加1，MapReduce處理流程如圖2所示.

圖2 統(tǒng)計(jì)通行次數(shù)流程

該MapReduce作業(yè)中，輸入是歷史路徑數(shù)據(jù)，輸出是各路段的通行次數(shù). 在map階段，掃描每條車輛路徑數(shù)據(jù)，將其拆分為多個(gè)路段. 中間鍵值對(duì)被發(fā)送到reduce階段進(jìn)行處理，其中key為路段的兩個(gè)端點(diǎn)(形式為‘路段端點(diǎn)1+路段端點(diǎn)2')，value為1，在reduce階段，中間鍵值對(duì)將根據(jù)key值被聚集和計(jì)數(shù)，最終統(tǒng)計(jì)出各路段的歷史通行次數(shù).

步驟3. 經(jīng)過上述步驟，已經(jīng)計(jì)算出了各個(gè)路段的通行次數(shù)，接下來需要求出路段的通行概率，應(yīng)先計(jì)算出總的路段通行次數(shù)，然后用各個(gè)路段的通行次數(shù)值與其相除求得各個(gè)路段的概率值.

將統(tǒng)計(jì)出的各個(gè)路段通行次數(shù)求和，記為sum，概率值計(jì)算的MapReduce處理流程如圖3所示.

該MapReduce作業(yè)中，輸入是路段通行次數(shù)數(shù)據(jù)，輸出是各路段的通行概率. 在map階段，掃描每條路段通行次數(shù)數(shù)據(jù)，將其值與sum相除得到概率值. 中間鍵值對(duì)被發(fā)送到reduce階段進(jìn)行數(shù)據(jù)存儲(chǔ)，其中key仍為路段的兩個(gè)端點(diǎn)(形式為‘路段端點(diǎn)1+路段端點(diǎn)2')，value為路段的通行概率值.

圖3 計(jì)算概率值流程

最終結(jié)果路段概率值存儲(chǔ)的邏輯結(jié)構(gòu)是鄰接矩陣，鄰接矩陣的上下標(biāo)是路段的兩個(gè)端點(diǎn)，值是該路段的通行概率值. 由于路網(wǎng)中路段眾多，路段概率數(shù)據(jù)量龐大，所以物理存儲(chǔ)采用適合存儲(chǔ)海量數(shù)據(jù)的Hbase數(shù)據(jù)庫，存儲(chǔ)路段概率數(shù)據(jù)的Hbase表結(jié)構(gòu)設(shè)計(jì)如表1所示，其中行鍵設(shè)置為路段的兩個(gè)端點(diǎn)，用橫線相連接，如‘路段端點(diǎn)1-路段端點(diǎn)2'的形式，這種形式可以清晰的表示出路段的結(jié)構(gòu)，然后將列中存儲(chǔ)的值設(shè)置為路段的通行概率. 這種存儲(chǔ)結(jié)構(gòu)有助于后續(xù)使用貪心算法進(jìn)行路段的選擇，以構(gòu)成相應(yīng)的路徑.

表1 表結(jié)構(gòu)設(shè)計(jì)

4 貪心算法和概率矩陣的結(jié)合

高速路路網(wǎng)結(jié)構(gòu)復(fù)雜，在進(jìn)出收費(fèi)站點(diǎn)間可能經(jīng)過一個(gè)或多個(gè)識(shí)別點(diǎn). 因此在數(shù)據(jù)缺失的條件下判斷車輛的通行路徑時(shí)，應(yīng)以路段為單位，不僅需要考慮單個(gè)識(shí)別點(diǎn)數(shù)據(jù)缺失，還需要考慮多個(gè)識(shí)別點(diǎn)數(shù)據(jù)缺失的情況.

在前一節(jié)中基于歷史通行數(shù)據(jù)計(jì)算出的路段概率值是道路路況，時(shí)長、擁擠程度等因素的綜合體現(xiàn)，路網(wǎng)中并行的路段相比較，道路使用者會(huì)偏向于選擇概率更大的路段去行駛. 貪心算法的原則是每次選取最有利的選擇作為當(dāng)前的選擇，這與道路使用者的路徑選擇規(guī)律相符. 所以本文采用貪心算法和概率矩陣相結(jié)合的路徑識(shí)別方法，利用貪心算法搜索出從收費(fèi)站入口到出口的路徑，從入口點(diǎn)開始，尋找路網(wǎng)中可通行的下一點(diǎn)，若有一個(gè)，則直接選取這個(gè)路段作為路徑一部分. 若有多個(gè)，則選取并行的路段中概率值最大的那條路段作為路徑一部分，然后繼續(xù)尋找下一個(gè)點(diǎn)，做相同的判斷和處理，直到到達(dá)出口點(diǎn)為止. 這樣一直選取概率最大的路段去構(gòu)建路徑，最終會(huì)得到一條從收費(fèi)站入口到出口的車輛通行路徑. 利用貪心算法尋找車輛行駛路徑的流程如圖4所示.

圖4 貪心算法流程

首先判斷下一個(gè)點(diǎn)是否是路徑終點(diǎn)，即收費(fèi)站出口點(diǎn)，如果是終點(diǎn)就輸出結(jié)果數(shù)據(jù)，否則繼續(xù)獲取路徑的下一個(gè)點(diǎn)，比較當(dāng)前點(diǎn)與下一個(gè)點(diǎn)相連的并行路段的概率值，選取概率最大的那個(gè)路段加入路徑中. 這里貪心算法的規(guī)則是一直選擇與當(dāng)前點(diǎn)相連接的路段中概率值最大的路段，直到收費(fèi)站出口為止.

5 結(jié)語

當(dāng)前高速公路路網(wǎng)形態(tài)復(fù)雜，車輛在進(jìn)出收費(fèi)站點(diǎn)之間形成了多條可選擇的行駛路徑. 同時(shí)高速路上設(shè)置了大量的識(shí)別點(diǎn)，識(shí)別點(diǎn)上配備的車牌拍照系統(tǒng)或RFID裝備受環(huán)境亮度或透明度不夠、硬件設(shè)備故障的影響，使車輛監(jiān)測數(shù)據(jù)缺失，車輛實(shí)際行駛路徑無法準(zhǔn)確識(shí)別. 針對(duì)以上情況，本文設(shè)計(jì)了基于歷史數(shù)據(jù)的多義路徑概率識(shí)別方法，首先利用車輛歷史通行數(shù)據(jù)，使用基于路段的聚類方法計(jì)算各路段概率值，然后將貪心算法與概率矩陣相結(jié)合進(jìn)行多義路徑識(shí)別. 該方法可以在監(jiān)測數(shù)據(jù)缺失情況下有效輔助多義路徑識(shí)別，給車主通行費(fèi)收取、路公司通行費(fèi)拆分提供了合理的依據(jù).

在下一步的研究工作中，將對(duì)車輛通行數(shù)據(jù)出現(xiàn)錯(cuò)誤的情況下進(jìn)行多義路徑識(shí)別計(jì)算. 本文僅考慮了數(shù)據(jù)缺失的情況，而實(shí)際中車輛通行數(shù)據(jù)不僅僅會(huì)出現(xiàn)數(shù)據(jù)缺失的問題，還可能會(huì)出現(xiàn)數(shù)據(jù)錯(cuò)誤的情況，日后可研究方法進(jìn)行通行數(shù)據(jù)的修正，以保證數(shù)據(jù)的完整性，進(jìn)而實(shí)現(xiàn)數(shù)據(jù)錯(cuò)誤情況下的高速路多義路徑識(shí)別.