基于歷史數據的高速多義路徑概率識別方法①

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

1(北方工業大學 大規模流數據集成與分析技術北京市重點實驗室，北京 100043)

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

1 引言

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

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

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

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

2 相關工作

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

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

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

3 基于路段聚類的歷史數據處理

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

步驟1. 車輛的歷史通行數據，包括高速路收費數據和識別點監測數據，這兩類數據都屬于單點數據，不利于計算路段車流量. 所以首先，需要根據收費數據和監測數據構建車輛歷史路徑，再在路徑數據中去判斷每個路段的通行概率，這樣結果會更為精確. 構建車輛路徑的MapReduce處理流程如圖1所示.

圖1 構建路徑流程

該MapReduce作業中，輸入是歷史收費數據、監測數據，輸出是拼接的車輛歷史路徑數據. 在map階段，掃描每條車輛收費記錄，提取其中的車牌號、進出站點時間，然后遍歷歷史監測數據，查詢該車在進出收費站點時間范圍內的監測數據，并按照時間先后順序將車輛經過的站點數據拼接. 中間鍵值對被發送到reduce階段進行存儲，其中key為車牌號，value為拼接的車輛路徑數據.

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

圖2 統計通行次數流程

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

步驟3. 經過上述步驟，已經計算出了各個路段的通行次數，接下來需要求出路段的通行概率，應先計算出總的路段通行次數，然后用各個路段的通行次數值與其相除求得各個路段的概率值.

將統計出的各個路段通行次數求和，記為sum，概率值計算的MapReduce處理流程如圖3所示.

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

圖3 計算概率值流程

最終結果路段概率值存儲的邏輯結構是鄰接矩陣，鄰接矩陣的上下標是路段的兩個端點，值是該路段的通行概率值. 由于路網中路段眾多，路段概率數據量龐大，所以物理存儲采用適合存儲海量數據的Hbase數據庫，存儲路段概率數據的Hbase表結構設計如表1所示，其中行鍵設置為路段的兩個端點，用橫線相連接，如‘路段端點1-路段端點2'的形式，這種形式可以清晰的表示出路段的結構，然后將列中存儲的值設置為路段的通行概率. 這種存儲結構有助于后續使用貪心算法進行路段的選擇，以構成相應的路徑.

表1 表結構設計

4 貪心算法和概率矩陣的結合

高速路路網結構復雜，在進出收費站點間可能經過一個或多個識別點. 因此在數據缺失的條件下判斷車輛的通行路徑時，應以路段為單位，不僅需要考慮單個識別點數據缺失，還需要考慮多個識別點數據缺失的情況.

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

圖4 貪心算法流程

首先判斷下一個點是否是路徑終點，即收費站出口點，如果是終點就輸出結果數據，否則繼續獲取路徑的下一個點，比較當前點與下一個點相連的并行路段的概率值，選取概率最大的那個路段加入路徑中. 這里貪心算法的規則是一直選擇與當前點相連接的路段中概率值最大的路段，直到收費站出口為止.

5 結語

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

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