一種基于有向圖的高速公路5.8G多義性路徑糾錯識別算法

覃力更 李旭

摘要：隨著高速公路不斷建設，路網日趨復雜，多義性路徑精確識別及通行費的計算拆分逐漸成為目前收費管理研究的熱點。文章探討了5.8G多義性路徑識別在高速公路有向圖中面臨的問題，通過優化最短路徑算法，對逆向標識數據進行自動糾錯。該算法基于廣西高速公路通行數據進行仿真實驗，通行費計算準確度達到99.99%，逆向標識數據糾正率達到100%，同時計算效率能滿足高速公路出口快速通行的要求。

關鍵詞：5.8G DSRC;多義性路徑識別;有向圖

中圖分類號：U491 文獻標識碼：A DOI：10.13282/j.cnki.wccst.2019.07.045

文章編號：1673-4874（2019）07-0150-04

0引言

隨著我國高速公路不斷建設，公路網結構變得錯綜復雜，路徑多義性問題日益嚴峻。特別是我國目前實施高速公路聯網收費，呈現出投資主體多元化以及管理結構形式多樣性的特點，如不考慮車輛實際行駛路徑，單單依靠記錄車輛通過高速公路入、出口信息來實施收費操作，這種方式既不科學又不準確，也影響了不同投資主體的收費利益。通行費的拆分直接關系到高速公路收費運營工作，關系到各條高速公路的合法利益。

在基于視頻車牌識別技術的基礎上，5.8G DSRC已成為新的多義性路徑標識技術標準，許多省份已進行了相關的試點研究。隨著高速公路“營改增”不斷深化，貨車ETC、取消高速公路省界收費站等相關政策的不斷推進，5.8G多義性路徑識別技術、基于多義性路徑識別的通行費精確計算與拆分顯得尤為重要。

1問題描述

車輛從入口進入高速，經過存在多義性的路段被標識點標識，從出口駛出高速，收費車道系統需要根據該車輛的實際行駛路徑進行收費并將相應的收費額清分給對應的路段業主。因為目前高速公路的模式是封閉式收費模式，若標識點數據足夠完備，可以還原車輛的實際行駛路徑。將高速路網轉換成有向圖，則該問題轉換為求從起點依序經過指定點序列最終到達終點的最短路徑。與此同時，在有向圖模型中采用5.8G短程專用通信標識行駛車輛，還會存在標識點重復標識和標識點逆向標識這兩個問題。

1.1標識點重復標識

在標識點所在路段擁堵時或者OBU、CPC卡多次喚醒的情況下，可能會發生同一標識點對同一個車輛（OBU、CPC卡）多次標識的情況，在出口讀取標識點數據時會產生多次行駛經過該標識點的情況，干擾通行費的計算。

1.2標識點逆向標識

目前使用的5.8G標識點天線通信范圍為扇形區域，容易誤將對向車輛標識。CPC卡信號角度較廣，有較大幾率發生逆向標識的情況，而OBU安裝位置固定且信號角度較窄，發生逆向標的幾率很小。此外，若半幅路面封路維修，封路方向的車輛會改道至另外半幅路面，在原本單向的車道內雙向通行，必然會發生逆向標識的情況。

由于使用的是有向圖，收費系統在出口計費的時候采用逆向標識數據會導致計算出來的路徑繞圈通行逆向的標識點，造成通行費額與實際不符。因此，一方面通過限制天線信號范圍、采用信號范圍控制較好的CPC卡和OBU減少逆向標識的發生;另一方面，在計費的算法中也要考慮如何處理逆向標識的情況。

2有向圖多路徑糾錯識別算法

2.1基于有向圖的高速公路路網建模

高速公路路網拓撲中包含的主要元素為互通立交、收費站出入口等。通過將互通立交、出入口等元素轉換為方向確定的基本路段與道路節點的組合，可建立高速公路路網拓撲的有向圖模型。

其中，表示W（X，y）道路節點X到道路節點y的最短路徑收費額，可使用dijkstro最短路徑算法求得0。本算法采用基于堆優化的dijkstro最短路徑算法，并處理標識點重復標識與逆向標識的問題。

2.2標識數據預處理

為了避免標識點重復標識干擾費率計算，同時初步減少逆向標識的影響，本算法對于從OBU和卡內讀取的標識點數據根據標識時間進行預處理。預處理規則為：

若在設定的時間間隔閾值內出現重復的標識點數據，則認為該車輛為單次通行多次標識，只保留該標識點第一次標識的數據;若標識時間間隔大于設定的閾值，則認為是不同的標識動作，不改變標識點序列。

2.3逆向標識數據糾正

由于高速公路限速且車輛的行駛速度有上限，我們可以通過行駛速度來判斷行駛路徑的合理性，從而篩選出逆向標識的情況并實現自動糾正。例如，一輛車經過標識點的原始通行方向速度為100 km/h，若逆向經過該標識點的速度為90 km/h，我們認為該車輛實際在通行標識點時被逆向標識了。在計算通行費時糾正標識點的方向，不僅影響當前子路徑（以該標識點為終點）的通行費計算，還會影響下一條子路徑（以該標識點為起點）的通行費計算。因此，在判斷逆向標識數據時不僅要考慮當前路徑的行駛速度，還需要考慮下一條子路徑的行駛速度。

如果正向與逆向的行駛速度都超過速度閾值或者都在速度閾值內，即無法判斷該標識點是否為逆向標識的情況，我們認為司機更傾向于走里程更短的路徑，因此選擇里程更短的標識方向。

3試驗分析

3.1試驗準備

為了驗證本算法的有效性，我們采集一段時間內廣西全區高速公路的收費數據進行計算驗證。試驗數據的要求指標見表1，試驗考查的指標見下頁表2。

在試驗中，我們采用多個評價標準來評估本算法的有效性，如表2所示。

3.2結果分析

3.2.1收費一致性

車型收費的總體收費一致性為99.9983%，通行費誤差比例平均值為17%，標準差為14%;計重收費的總體收費一致性概率為99.9953%，通行費誤差比例平均值為10%，標準差為8%。收費一致性均高于99.99%。在不同標識點數量下的收費一致性如圖1所示，個別計算結果與MTC實際收費不符，主要原因為車輛在收費站廣場調頭、個別標識點系統時間校準異常。

3.2.2逆向標識糾正率

首先對每個標識點數據做逆向處理后再進行通行費計算，然后與原始標識點數據的計算結果進行比較。所有標識點數據逆向之后計算得到的結果與原始計算結果一致，在試驗中對逆向標識的糾正率為100%，表明本算法對于逆向標識具有很好的處理能力。

3.2.3無標識點收費一致性

試驗通過遍歷所有入出口及車型組合，計算通行費并與實際收費進行比較。試驗結果與本算法的無標識點收費一致性為100%，表明在未啟用5.8G多義性路徑識別的條件下，本算法也能正確計算通行費，保證與現有收費系統的計費一致性。

3.2.4算法效率

試驗使用CPU為Core i34330TE 2.4GHz，系統環境為32位Linux。本算法在不同標識點數量下的計算效率如圖2所示，隨著標識點數量增加，求最短路徑的計算次數也會增加，導致計算耗時變大。

從總體計算效率角度進行評價，按車型收費的平均計算耗時為9 ms，在車輛經過所有標識點都是逆向標識的極端情況下，平均耗時為26ms;計重收費的平均計算耗時為8ms，在車輛經過所有標識點都是逆向標識的極端情況下，平均耗時為27ms。由此，我們可以看到算法的計算效率較高，能滿足MTC及ETC的收費計算要求。

4結語

在高速公路路網有向圖模型的基礎上，本研究指出了有向圖中5.8G多義性路徑標識帶來的問題，通過標識數據預處理過濾重復標識的數據，根據車輛行駛速度對逆向標識進行糾正，然后采用基于堆優化的dijkstra最短路徑算法分析車輛通行路徑并計算通行費用。本算法基于廣西高速公路路網數據與MTC實際通行數據進行仿真實驗，計算準確度達到99.99%，并且能有效地處理逆向標識數據。此外，本算法具有較高的計算效率，能滿足高速公路出口快速通行的需求。同時需要注意，本計費方案自動糾正逆向標識依賴于標識記錄的時間，因此對標識點系統的時間同步精度要求較高。

基于現有研究，下一步針對差異化收費、貨車ETC、取消省界收費站等新的應用場景優化擴充算法。通過二義性路徑大數據分析，為高速公路管理方提供稽查數據支持。