覃力更 李旭

摘要：隨著高速公路不斷建設(shè)，路網(wǎng)日趨復(fù)雜，多義性路徑精確識(shí)別及通行費(fèi)的計(jì)算拆分逐漸成為目前收費(fèi)管理研究的熱點(diǎn)。文章探討了5.8G多義性路徑識(shí)別在高速公路有向圖中面臨的問(wèn)題，通過(guò)優(yōu)化最短路徑算法，對(duì)逆向標(biāo)識(shí)數(shù)據(jù)進(jìn)行自動(dòng)糾錯(cuò)。該算法基于廣西高速公路通行數(shù)據(jù)進(jìn)行仿真實(shí)驗(yàn)，通行費(fèi)計(jì)算準(zhǔn)確度達(dá)到99.99%，逆向標(biāo)識(shí)數(shù)據(jù)糾正率達(dá)到100%，同時(shí)計(jì)算效率能滿足高速公路出口快速通行的要求。

關(guān)鍵詞：5.8G DSRC;多義性路徑識(shí)別;有向圖

中圖分類號(hào)：U491 文獻(xiàn)標(biāo)識(shí)碼：A DOI：10.13282/j.cnki.wccst.2019.07.045

文章編號(hào)：1673-4874（2019）07-0150-04

0引言

隨著我國(guó)高速公路不斷建設(shè)，公路網(wǎng)結(jié)構(gòu)變得錯(cuò)綜復(fù)雜，路徑多義性問(wèn)題日益嚴(yán)峻。特別是我國(guó)目前實(shí)施高速公路聯(lián)網(wǎng)收費(fèi)，呈現(xiàn)出投資主體多元化以及管理結(jié)構(gòu)形式多樣性的特點(diǎn)，如不考慮車輛實(shí)際行駛路徑，單單依靠記錄車輛通過(guò)高速公路入、出口信息來(lái)實(shí)施收費(fèi)操作，這種方式既不科學(xué)又不準(zhǔn)確，也影響了不同投資主體的收費(fèi)利益。通行費(fèi)的拆分直接關(guān)系到高速公路收費(fèi)運(yùn)營(yíng)工作，關(guān)系到各條高速公路的合法利益。

在基于視頻車牌識(shí)別技術(shù)的基礎(chǔ)上，5.8G DSRC已成為新的多義性路徑標(biāo)識(shí)技術(shù)標(biāo)準(zhǔn)，許多省份已進(jìn)行了相關(guān)的試點(diǎn)研究。隨著高速公路“營(yíng)改增”不斷深化，貨車ETC、取消高速公路省界收費(fèi)站等相關(guān)政策的不斷推進(jìn)，5.8G多義性路徑識(shí)別技術(shù)、基于多義性路徑識(shí)別的通行費(fèi)精確計(jì)算與拆分顯得尤為重要。

1問(wèn)題描述

車輛從入口進(jìn)入高速，經(jīng)過(guò)存在多義性的路段被標(biāo)識(shí)點(diǎn)標(biāo)識(shí)，從出口駛出高速，收費(fèi)車道系統(tǒng)需要根據(jù)該車輛的實(shí)際行駛路徑進(jìn)行收費(fèi)并將相應(yīng)的收費(fèi)額清分給對(duì)應(yīng)的路段業(yè)主。因?yàn)槟壳案咚俟返哪Ｊ绞欠忾]式收費(fèi)模式，若標(biāo)識(shí)點(diǎn)數(shù)據(jù)足夠完備，可以還原車輛的實(shí)際行駛路徑。將高速路網(wǎng)轉(zhuǎn)換成有向圖，則該問(wèn)題轉(zhuǎn)換為求從起點(diǎn)依序經(jīng)過(guò)指定點(diǎn)序列最終到達(dá)終點(diǎn)的最短路徑。與此同時(shí)，在有向圖模型中采用5.8G短程專用通信標(biāo)識(shí)行駛車輛，還會(huì)存在標(biāo)識(shí)點(diǎn)重復(fù)標(biāo)識(shí)和標(biāo)識(shí)點(diǎn)逆向標(biāo)識(shí)這兩個(gè)問(wèn)題。

1.1標(biāo)識(shí)點(diǎn)重復(fù)標(biāo)識(shí)

在標(biāo)識(shí)點(diǎn)所在路段擁堵時(shí)或者OBU、CPC卡多次喚醒的情況下，可能會(huì)發(fā)生同一標(biāo)識(shí)點(diǎn)對(duì)同一個(gè)車輛（OBU、CPC卡）多次標(biāo)識(shí)的情況，在出口讀取標(biāo)識(shí)點(diǎn)數(shù)據(jù)時(shí)會(huì)產(chǎn)生多次行駛經(jīng)過(guò)該標(biāo)識(shí)點(diǎn)的情況，干擾通行費(fèi)的計(jì)算。

1.2標(biāo)識(shí)點(diǎn)逆向標(biāo)識(shí)

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

由于使用的是有向圖，收費(fèi)系統(tǒng)在出口計(jì)費(fèi)的時(shí)候采用逆向標(biāo)識(shí)數(shù)據(jù)會(huì)導(dǎo)致計(jì)算出來(lái)的路徑繞圈通行逆向的標(biāo)識(shí)點(diǎn)，造成通行費(fèi)額與實(shí)際不符。因此，一方面通過(guò)限制天線信號(hào)范圍、采用信號(hào)范圍控制較好的CPC卡和OBU減少逆向標(biāo)識(shí)的發(fā)生;另一方面，在計(jì)費(fèi)的算法中也要考慮如何處理逆向標(biāo)識(shí)的情況。

2有向圖多路徑糾錯(cuò)識(shí)別算法

2.1基于有向圖的高速公路路網(wǎng)建模

高速公路路網(wǎng)拓?fù)渲邪闹饕貫榛ネ⒔?、收費(fèi)站出入口等。通過(guò)將互通立交、出入口等元素轉(zhuǎn)換為方向確定的基本路段與道路節(jié)點(diǎn)的組合，可建立高速公路路網(wǎng)拓?fù)涞挠邢驁D模型。

其中，表示W(wǎng)（X，y）道路節(jié)點(diǎn)X到道路節(jié)點(diǎn)y的最短路徑收費(fèi)額，可使用dijkstro最短路徑算法求得0。本算法采用基于堆優(yōu)化的dijkstro最短路徑算法，并處理標(biāo)識(shí)點(diǎn)重復(fù)標(biāo)識(shí)與逆向標(biāo)識(shí)的問(wèn)題。

2.2標(biāo)識(shí)數(shù)據(jù)預(yù)處理

為了避免標(biāo)識(shí)點(diǎn)重復(fù)標(biāo)識(shí)干擾費(fèi)率計(jì)算，同時(shí)初步減少逆向標(biāo)識(shí)的影響，本算法對(duì)于從OBU和卡內(nèi)讀取的標(biāo)識(shí)點(diǎn)數(shù)據(jù)根據(jù)標(biāo)識(shí)時(shí)間進(jìn)行預(yù)處理。預(yù)處理規(guī)則為：

若在設(shè)定的時(shí)間間隔閾值內(nèi)出現(xiàn)重復(fù)的標(biāo)識(shí)點(diǎn)數(shù)據(jù)，則認(rèn)為該車輛為單次通行多次標(biāo)識(shí)，只保留該標(biāo)識(shí)點(diǎn)第一次標(biāo)識(shí)的數(shù)據(jù);若標(biāo)識(shí)時(shí)間間隔大于設(shè)定的閾值，則認(rèn)為是不同的標(biāo)識(shí)動(dòng)作，不改變標(biāo)識(shí)點(diǎn)序列。

2.3逆向標(biāo)識(shí)數(shù)據(jù)糾正

由于高速公路限速且車輛的行駛速度有上限，我們可以通過(guò)行駛速度來(lái)判斷行駛路徑的合理性，從而篩選出逆向標(biāo)識(shí)的情況并實(shí)現(xiàn)自動(dòng)糾正。例如，一輛車經(jīng)過(guò)標(biāo)識(shí)點(diǎn)的原始通行方向速度為100 km/h，若逆向經(jīng)過(guò)該標(biāo)識(shí)點(diǎn)的速度為90 km/h，我們認(rèn)為該車輛實(shí)際在通行標(biāo)識(shí)點(diǎn)時(shí)被逆向標(biāo)識(shí)了。在計(jì)算通行費(fèi)時(shí)糾正標(biāo)識(shí)點(diǎn)的方向，不僅影響當(dāng)前子路徑（以該標(biāo)識(shí)點(diǎn)為終點(diǎn)）的通行費(fèi)計(jì)算，還會(huì)影響下一條子路徑（以該標(biāo)識(shí)點(diǎn)為起點(diǎn)）的通行費(fèi)計(jì)算。因此，在判斷逆向標(biāo)識(shí)數(shù)據(jù)時(shí)不僅要考慮當(dāng)前路徑的行駛速度，還需要考慮下一條子路徑的行駛速度。

如果正向與逆向的行駛速度都超過(guò)速度閾值或者都在速度閾值內(nèi)，即無(wú)法判斷該標(biāo)識(shí)點(diǎn)是否為逆向標(biāo)識(shí)的情況，我們認(rèn)為司機(jī)更傾向于走里程更短的路徑，因此選擇里程更短的標(biāo)識(shí)方向。

3試驗(yàn)分析

3.1試驗(yàn)準(zhǔn)備

為了驗(yàn)證本算法的有效性，我們采集一段時(shí)間內(nèi)廣西全區(qū)高速公路的收費(fèi)數(shù)據(jù)進(jìn)行計(jì)算驗(yàn)證。試驗(yàn)數(shù)據(jù)的要求指標(biāo)見(jiàn)表1，試驗(yàn)考查的指標(biāo)見(jiàn)下頁(yè)表2。

在試驗(yàn)中，我們采用多個(gè)評(píng)價(jià)標(biāo)準(zhǔn)來(lái)評(píng)估本算法的有效性，如表2所示。

3.2結(jié)果分析

3.2.1收費(fèi)一致性

車型收費(fèi)的總體收費(fèi)一致性為99.9983%，通行費(fèi)誤差比例平均值為17%，標(biāo)準(zhǔn)差為14%;計(jì)重收費(fèi)的總體收費(fèi)一致性概率為99.9953%，通行費(fèi)誤差比例平均值為10%，標(biāo)準(zhǔn)差為8%。收費(fèi)一致性均高于99.99%。在不同標(biāo)識(shí)點(diǎn)數(shù)量下的收費(fèi)一致性如圖1所示，個(gè)別計(jì)算結(jié)果與MTC實(shí)際收費(fèi)不符，主要原因?yàn)檐囕v在收費(fèi)站廣場(chǎng)調(diào)頭、個(gè)別標(biāo)識(shí)點(diǎn)系統(tǒng)時(shí)間校準(zhǔn)異常。

3.2.2逆向標(biāo)識(shí)糾正率

首先對(duì)每個(gè)標(biāo)識(shí)點(diǎn)數(shù)據(jù)做逆向處理后再進(jìn)行通行費(fèi)計(jì)算，然后與原始標(biāo)識(shí)點(diǎn)數(shù)據(jù)的計(jì)算結(jié)果進(jìn)行比較。所有標(biāo)識(shí)點(diǎn)數(shù)據(jù)逆向之后計(jì)算得到的結(jié)果與原始計(jì)算結(jié)果一致，在試驗(yàn)中對(duì)逆向標(biāo)識(shí)的糾正率為100%，表明本算法對(duì)于逆向標(biāo)識(shí)具有很好的處理能力。

3.2.3無(wú)標(biāo)識(shí)點(diǎn)收費(fèi)一致性

試驗(yàn)通過(guò)遍歷所有入出口及車型組合，計(jì)算通行費(fèi)并與實(shí)際收費(fèi)進(jìn)行比較。試驗(yàn)結(jié)果與本算法的無(wú)標(biāo)識(shí)點(diǎn)收費(fèi)一致性為100%，表明在未啟用5.8G多義性路徑識(shí)別的條件下，本算法也能正確計(jì)算通行費(fèi)，保證與現(xiàn)有收費(fèi)系統(tǒng)的計(jì)費(fèi)一致性。

3.2.4算法效率

試驗(yàn)使用CPU為Core i34330TE 2.4GHz，系統(tǒng)環(huán)境為32位Linux。本算法在不同標(biāo)識(shí)點(diǎn)數(shù)量下的計(jì)算效率如圖2所示，隨著標(biāo)識(shí)點(diǎn)數(shù)量增加，求最短路徑的計(jì)算次數(shù)也會(huì)增加，導(dǎo)致計(jì)算耗時(shí)變大。

從總體計(jì)算效率角度進(jìn)行評(píng)價(jià)，按車型收費(fèi)的平均計(jì)算耗時(shí)為9 ms，在車輛經(jīng)過(guò)所有標(biāo)識(shí)點(diǎn)都是逆向標(biāo)識(shí)的極端情況下，平均耗時(shí)為26ms;計(jì)重收費(fèi)的平均計(jì)算耗時(shí)為8ms，在車輛經(jīng)過(guò)所有標(biāo)識(shí)點(diǎn)都是逆向標(biāo)識(shí)的極端情況下，平均耗時(shí)為27ms。由此，我們可以看到算法的計(jì)算效率較高，能滿足MTC及ETC的收費(fèi)計(jì)算要求。

4結(jié)語(yǔ)

在高速公路路網(wǎng)有向圖模型的基礎(chǔ)上，本研究指出了有向圖中5.8G多義性路徑標(biāo)識(shí)帶來(lái)的問(wèn)題，通過(guò)標(biāo)識(shí)數(shù)據(jù)預(yù)處理過(guò)濾重復(fù)標(biāo)識(shí)的數(shù)據(jù)，根據(jù)車輛行駛速度對(duì)逆向標(biāo)識(shí)進(jìn)行糾正，然后采用基于堆優(yōu)化的dijkstra最短路徑算法分析車輛通行路徑并計(jì)算通行費(fèi)用。本算法基于廣西高速公路路網(wǎng)數(shù)據(jù)與MTC實(shí)際通行數(shù)據(jù)進(jìn)行仿真實(shí)驗(yàn)，計(jì)算準(zhǔn)確度達(dá)到99.99%，并且能有效地處理逆向標(biāo)識(shí)數(shù)據(jù)。此外，本算法具有較高的計(jì)算效率，能滿足高速公路出口快速通行的需求。同時(shí)需要注意，本計(jì)費(fèi)方案自動(dòng)糾正逆向標(biāo)識(shí)依賴于標(biāo)識(shí)記錄的時(shí)間，因此對(duì)標(biāo)識(shí)點(diǎn)系統(tǒng)的時(shí)間同步精度要求較高。

基于現(xiàn)有研究，下一步針對(duì)差異化收費(fèi)、貨車ETC、取消省界收費(fèi)站等新的應(yīng)用場(chǎng)景優(yōu)化擴(kuò)充算法。通過(guò)二義性路徑大數(shù)據(jù)分析，為高速公路管理方提供稽查數(shù)據(jù)支持。