覃力更 李旭
摘要:隨著高速公路不斷建設(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)槟壳案咚俟返哪J绞欠忾]式收費(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ù)支持。