跨省高速公路通行費(fèi)快速計(jì)算方案

周 鋼，徐 杰

(中遠(yuǎn)海運(yùn)科技股份有限公司,上海 200135)

0 引 言

近些年，隨著我國國民經(jīng)濟(jì)快速發(fā)展,交通運(yùn)輸業(yè)務(wù)快速增長(zhǎng)，高速公路交通擁堵問題日益嚴(yán)重。為解決該問題，全國29個(gè)省(區(qū)、市)的ETC(Electronic Toll Collection)車道系統(tǒng)于2015年9月開始聯(lián)網(wǎng)收費(fèi)運(yùn)行，全國的ETC車輛在省界主線收費(fèi)站實(shí)現(xiàn)了不停車?yán)U費(fèi)通行，顯著提高了高速公路的通行效率和服務(wù)水平。

2018年，國家提出“推動(dòng)取消高速公路省界收費(fèi)站”，進(jìn)一步提升高速公路的服務(wù)能力和服務(wù)水平，更好地為經(jīng)濟(jì)社會(huì)的發(fā)展和人們的安全便捷出行服務(wù)。為貫徹落實(shí)國家的決策部署，交通運(yùn)輸部將重慶、四川、山東和江蘇等4個(gè)地區(qū)作為試點(diǎn)，開展取消高速公路省界收費(fèi)站的相關(guān)工作。高速公路省界收費(fèi)站拆除之后，將從技術(shù)層面和管理層面帶來新的問題。

1) 從技術(shù)層面看，虛擬省界收費(fèi)站通過自由流ETC門架交易過往車輛，對(duì)車輛通行路徑還原和計(jì)費(fèi)有很高的時(shí)間要求。同時(shí)，對(duì)于自由流收費(fèi)失敗的車輛而言，在出口收費(fèi)車道不僅需計(jì)算其所在省市的通行費(fèi)額，而且需計(jì)算其在其他省市的通行費(fèi)額;各省市的貨車計(jì)費(fèi)規(guī)則、綠色通行車輛執(zhí)行標(biāo)準(zhǔn)、特殊車型認(rèn)定和通行費(fèi)優(yōu)惠政策執(zhí)行標(biāo)準(zhǔn)等都不盡相同，如何實(shí)現(xiàn)外省通行路段的計(jì)費(fèi)是一個(gè)較難解決的問題。此外，對(duì)于省界標(biāo)識(shí)點(diǎn)標(biāo)識(shí)失敗的多省通行車輛而言，如何還原其整體行駛路徑也是一個(gè)急需解決的問題。

2) 從管理層面看，路網(wǎng)邊界范圍擴(kuò)大會(huì)導(dǎo)致車輛單次通行費(fèi)用急劇增加，U轉(zhuǎn)通行車輛逃費(fèi)、通行超時(shí)和節(jié)假日逃費(fèi)等問題都會(huì)被放大，誘發(fā)更多的偷逃通行費(fèi)行為。同時(shí)，車輛單次通行涉及多個(gè)省份，一旦出現(xiàn)爭(zhēng)議，需多個(gè)高速公路通行管理單位聯(lián)合處理，這會(huì)增加協(xié)調(diào)溝通的成本，增大管理難度。

1 總體方案

出于對(duì)目前的聯(lián)網(wǎng)收費(fèi)系統(tǒng)進(jìn)行改造考慮，通過圖論算法、云端計(jì)費(fèi)系統(tǒng)、5.8 GHz標(biāo)識(shí)和高清車牌圖像識(shí)別卡口等技術(shù)手段，以“收費(fèi)站計(jì)算為主、云平臺(tái)計(jì)算為輔”為原則，采用“分省計(jì)費(fèi)、統(tǒng)一收費(fèi)”方式解決上述技術(shù)層面的問題。

物理省界收費(fèi)站拆除之后，在收費(fèi)廣場(chǎng)原址建設(shè)省界虛擬收費(fèi)站。省界虛擬收費(fèi)站ETC門架交易系統(tǒng)采用5.8 GHz專用短程通信(DSRC)技術(shù)對(duì)經(jīng)過的ETC車輛進(jìn)行交易，生成ETC交易記錄上傳給省中心。對(duì)于經(jīng)過的MTC(Manual Ton Collection)車輛，ETC門架交易系統(tǒng)將省界標(biāo)識(shí)信息寫入CPC卡，生成CPC卡通行記錄上傳給省中心。

收費(fèi)站部署2臺(tái)用于執(zhí)行多省通行車輛通行費(fèi)快速計(jì)算處理程序的服務(wù)器，部署方式應(yīng)滿足高可用性和雙機(jī)互為備用的需求。對(duì)于單省通行的車輛，車道收費(fèi)系統(tǒng)通過車道計(jì)費(fèi)模塊計(jì)算通行費(fèi);對(duì)于多省通行的車輛，車道收費(fèi)系統(tǒng)通過收費(fèi)站服務(wù)器上部署的多省通行車輛通行費(fèi)快速計(jì)算處理程序計(jì)算通行費(fèi)。

交通運(yùn)輸部聯(lián)網(wǎng)中心(以下簡(jiǎn)稱“部聯(lián)網(wǎng)中心”)劃分區(qū)域建設(shè)云端輔助計(jì)費(fèi)系統(tǒng)。實(shí)體收費(fèi)站的入口上道信息、高清車牌識(shí)別卡口的車輛高清車牌識(shí)別記錄、5.8 GHz標(biāo)識(shí)點(diǎn)的標(biāo)識(shí)信息記錄和省界虛擬收費(fèi)站的車輛高清車牌識(shí)別信息及車輛通行記錄等數(shù)據(jù)實(shí)時(shí)上傳給部聯(lián)網(wǎng)中心，作為云端輔助計(jì)費(fèi)系統(tǒng)特殊情況處理和通行費(fèi)計(jì)算的依據(jù)。

2 通行費(fèi)計(jì)算實(shí)施模式

2.1 基于部聯(lián)網(wǎng)中心-省中心-收費(fèi)站的站級(jí)計(jì)費(fèi)服務(wù)模式

各省中心基于通行費(fèi)快速算法，以各省為單元生成各省的路網(wǎng)結(jié)構(gòu)參數(shù)和費(fèi)率計(jì)算參數(shù)，并將其上傳至部聯(lián)網(wǎng)中心。路網(wǎng)結(jié)構(gòu)參數(shù)的格式由部聯(lián)網(wǎng)中心統(tǒng)一定義，各省中心嚴(yán)格按照部聯(lián)網(wǎng)中心的要求對(duì)這些參數(shù)進(jìn)行錄入和上傳。由部聯(lián)網(wǎng)中心對(duì)各省上傳的路網(wǎng)結(jié)構(gòu)參數(shù)的準(zhǔn)確性、合理性和完整性進(jìn)行校驗(yàn)，校驗(yàn)通過之后匯總所有省市的路網(wǎng)結(jié)構(gòu)參數(shù)，形成一張全國高速公路路網(wǎng)結(jié)構(gòu)圖。費(fèi)率計(jì)算參數(shù)不用統(tǒng)一，各省以文件包的方式將省內(nèi)費(fèi)率計(jì)算參數(shù)上傳給部聯(lián)網(wǎng)中心。

部聯(lián)網(wǎng)中心將全國路網(wǎng)結(jié)構(gòu)參數(shù)和各省市的費(fèi)率計(jì)算參數(shù)文件打包生成聯(lián)網(wǎng)省份費(fèi)率參數(shù)文件下發(fā)給省中心，由省中心下發(fā)給收費(fèi)站，供收費(fèi)站服務(wù)器上的車輛通行費(fèi)快速計(jì)算處理程序加載使用。收費(fèi)站向車道提供多省通行計(jì)費(fèi)服務(wù)接口。虛擬省界收費(fèi)站由相鄰的2個(gè)省中心共同建設(shè)，分不同的方向各自建設(shè)出省方向的自由流交易系統(tǒng)。省界虛擬收費(fèi)站自由流交易系統(tǒng)從各自的省中心下載路網(wǎng)結(jié)構(gòu)參數(shù)和費(fèi)率計(jì)算參數(shù)，用于計(jì)算單省通行車輛的通行費(fèi)。圖1為基于收費(fèi)站級(jí)服務(wù)的通行費(fèi)計(jì)算數(shù)據(jù)流。

2.2 基于云平臺(tái)的云端輔助計(jì)費(fèi)系統(tǒng)模式

基于云平臺(tái)的云端輔助計(jì)費(fèi)系統(tǒng)(即通行費(fèi)快速計(jì)算處理程序)部署在云端，由云端系統(tǒng)完成多省通行車輛的路徑還原和通行費(fèi)計(jì)算,同時(shí)降低出現(xiàn)單點(diǎn)故障的風(fēng)險(xiǎn)。

在云端輔助計(jì)費(fèi)系統(tǒng)模式下，各省仍需按照收費(fèi)站級(jí)計(jì)費(fèi)服務(wù)模式上傳路網(wǎng)結(jié)構(gòu)參數(shù)和費(fèi)率計(jì)算參數(shù)，匯總的聯(lián)網(wǎng)省份費(fèi)率參數(shù)不再下發(fā)。同時(shí),收費(fèi)站的入口交易記錄和省界虛擬收費(fèi)站的高清卡口標(biāo)識(shí)信息上傳給部聯(lián)網(wǎng)中心云平臺(tái)，用于輔助還原車輛行駛路徑，以便更精確地計(jì)算通行費(fèi)。

車道逐級(jí)上報(bào)多省通行計(jì)費(fèi)請(qǐng)求至云端系統(tǒng)，計(jì)費(fèi)請(qǐng)求包含車牌信息、車型信息、入口信息和路徑信息等。云端輔助計(jì)費(fèi)系統(tǒng)首先會(huì)根據(jù)省界虛擬收費(fèi)站的標(biāo)識(shí)信息,按省份劃分路徑，然后將各省路徑信息交給各省費(fèi)率計(jì)算模塊進(jìn)行路徑還原和計(jì)費(fèi)處理，從而得出各省的通行路徑和車輛通行費(fèi)。此外,對(duì)全部省市的通行金額進(jìn)行疊加得出多省通行車輛通行費(fèi)總金額，并將結(jié)果逐級(jí)返回至出口收費(fèi)車道。圖2為基于云平臺(tái)的通行費(fèi)計(jì)算數(shù)據(jù)流。

圖1 基于收費(fèi)站級(jí)服務(wù)的通行費(fèi)計(jì)算數(shù)據(jù)流

圖2 基于云平臺(tái)的通行費(fèi)計(jì)算數(shù)據(jù)流

2.3 具體實(shí)施方案

高速公路收費(fèi)系統(tǒng)屬于全天24 h不間斷生產(chǎn)系統(tǒng)，其業(yè)務(wù)特點(diǎn)要求系統(tǒng)必須具有很強(qiáng)的耐用性，即使通信系統(tǒng)發(fā)生故障，車道系統(tǒng)仍可正常運(yùn)行，保證收費(fèi)秩序正常。因此，基于部聯(lián)網(wǎng)中心-省中心-收費(fèi)站的站級(jí)計(jì)費(fèi)服務(wù)更適合作為常規(guī)計(jì)費(fèi)模式。各省應(yīng)強(qiáng)化收費(fèi)站的站級(jí)計(jì)費(fèi)系統(tǒng)，使收費(fèi)站具有獨(dú)立的費(fèi)率計(jì)算能力，防止遭受網(wǎng)絡(luò)攻擊之后出現(xiàn)通信問題導(dǎo)致無法計(jì)算跨省費(fèi)率。收費(fèi)站站級(jí)計(jì)費(fèi)服務(wù)系統(tǒng)完成對(duì)入口收費(fèi)站信息和省界標(biāo)識(shí)點(diǎn)信息的多省通行車輛的路徑還原和通行費(fèi)快速計(jì)算。

基于云平臺(tái)的云端輔助計(jì)費(fèi)系統(tǒng)模式能保證路網(wǎng)結(jié)構(gòu)參數(shù)和費(fèi)率計(jì)算參數(shù)的準(zhǔn)確性和及時(shí)性。當(dāng)入口收費(fèi)站信息或省界標(biāo)識(shí)點(diǎn)信息不完整、出口收費(fèi)站費(fèi)率參數(shù)未及時(shí)更新時(shí)，收費(fèi)站站級(jí)收費(fèi)系統(tǒng)無法及時(shí)有效地核查車輛通行情況，無法進(jìn)行路徑還原和通行費(fèi)計(jì)算?；谠破脚_(tái)的云端輔助計(jì)費(fèi)系統(tǒng)擁有這部分流水記錄，通過車牌或卡號(hào)進(jìn)行關(guān)聯(lián)獲取這部分?jǐn)?shù)據(jù)，用于還原缺失的入口收費(fèi)站信息或省界標(biāo)識(shí)點(diǎn)信息，最終完成多省通行車輛的路徑還原和通行費(fèi)計(jì)算。

站級(jí)計(jì)費(fèi)模式能擺脫收費(fèi)站對(duì)外部網(wǎng)絡(luò)的依賴，提高收費(fèi)站的獨(dú)立計(jì)費(fèi)能力，增強(qiáng)系統(tǒng)的安全性?；谠破脚_(tái)計(jì)費(fèi)系統(tǒng)模式，能提高參數(shù)的安全性，確保費(fèi)率參數(shù)及時(shí)更新和參數(shù)的一致性；同時(shí),能解決站級(jí)計(jì)費(fèi)模式下路徑信息不全等特殊情況下無法解決的問題。綜上，多省通行車輛的通行費(fèi)計(jì)算宜采用“站級(jí)計(jì)費(fèi)服務(wù)為主，云端輔助計(jì)費(fèi)系統(tǒng)為輔”的方式。

3 通行費(fèi)計(jì)算方案

3.1 路徑還原

路徑還原用于還原多省通行車輛的完整行駛路徑，從中確定車輛經(jīng)過的省界虛擬站，得到的省內(nèi)路徑可不作為計(jì)費(fèi)依據(jù)。路徑還原以實(shí)際里程最短為尋優(yōu)原則。圖3為多省通行車輛通行路徑示意。

注:1)A省、B省、C省、D省、E省和F省之間共有S1、S2、S3、S4、S5、S6和S7等7個(gè)省界虛擬收費(fèi)站，以及F1、F2、F3和F4等4個(gè)標(biāo)識(shí)點(diǎn);

2)車輛從D省Sin收費(fèi)站上道，從C省Sout收費(fèi)站下道，卡內(nèi)依次包含標(biāo)識(shí)信息F3和F2;

3)通過尋優(yōu)算法還原車輛完整行駛路徑為Sin→S6→F3→S4→F2→S2→Sout，可從中確定車輛經(jīng)過的省界虛擬收費(fèi)站為S6、S4和S2；

4)路徑還原完成之后，分別按照D省(Sin→S6)、E省(S6→S4)、B省(S4→S2)和C省(S2→Sout)計(jì)費(fèi)，最后匯總計(jì)費(fèi)金額

圖3 多省通行車輛通行路徑示意

3.2 創(chuàng)建路網(wǎng)結(jié)構(gòu)模型

部聯(lián)網(wǎng)中心定義統(tǒng)一格式的路網(wǎng)結(jié)構(gòu)參數(shù)，各省市按定義完成各自的路網(wǎng)結(jié)構(gòu)參數(shù)錄制工作并將其上傳至部聯(lián)網(wǎng)中心，由部聯(lián)網(wǎng)中心構(gòu)建能使系統(tǒng)識(shí)別的由點(diǎn)和邊組成的路網(wǎng)結(jié)構(gòu)模型。該模型應(yīng)保證路網(wǎng)解析方式一致、參數(shù)表結(jié)構(gòu)定義和數(shù)據(jù)定義一致及異常尋優(yōu)規(guī)則一致。

參照重慶市局部路網(wǎng)結(jié)構(gòu)繪制路網(wǎng)元素分布示意,具體見圖4。該路網(wǎng)包含標(biāo)識(shí)點(diǎn)、路由節(jié)點(diǎn)、省界虛擬站和實(shí)體收費(fèi)站(主線站是一種特殊的實(shí)體收費(fèi)站)等內(nèi)容。Li為路段編號(hào)；Nij為路由節(jié)點(diǎn)編號(hào)；Fi為標(biāo)識(shí)點(diǎn)編號(hào)；Si為實(shí)體收費(fèi)站編號(hào)。

圖4 路網(wǎng)元素分布示意

路由節(jié)點(diǎn)用于定義省內(nèi)路段間的連接關(guān)系和路段內(nèi)的分支連接關(guān)系，同時(shí)包括跨省路段間的連接關(guān)系。1個(gè)路由節(jié)點(diǎn)由相交的2條路段上的各自1個(gè)虛擬邏輯站組成，1個(gè)路段分支點(diǎn)由路段內(nèi)相交的2條支路上的的各自1個(gè)虛擬邏輯站組成。路段分支點(diǎn)是一種特殊的路由節(jié)點(diǎn)，本文只針對(duì)省內(nèi)路段間的路由節(jié)點(diǎn)進(jìn)行介紹，路段分支點(diǎn)和跨省路段間的路由節(jié)點(diǎn)原理與之相同。

虛擬邏輯收費(fèi)站用于具體描述路由節(jié)點(diǎn)處2條路段的連接關(guān)系，是路網(wǎng)結(jié)構(gòu)模型點(diǎn)邊元素中的點(diǎn)，沒有相應(yīng)的收費(fèi)車道，無法進(jìn)行上下道。虛擬邏輯站編號(hào)用Vi表示。

圖4為路網(wǎng)元素分布示意。其中：

1) 路網(wǎng)中總共存在9條路段，分別是L1、L2、L3、L4、L5、L6、L7、L8和L9。

2)L1路段包含S101、S102、S103和S104等實(shí)體收費(fèi)站和V199、V198、V197和V196等虛擬邏輯站,其余路段也包含各自的實(shí)體收費(fèi)站和虛擬邏輯站。

3) 路網(wǎng)中存在環(huán)的每條邊上建設(shè)標(biāo)識(shí)點(diǎn)，分別用F1、F2、F3、F4和F5表示。

4) 2條路相交的路由節(jié)點(diǎn)處需定義1個(gè)路由節(jié)點(diǎn)編號(hào)，比如L1與L2相交處的N12；3條路相交的路由節(jié)點(diǎn)處需定義3個(gè)路由節(jié)點(diǎn)編號(hào)，比如L5、L8和L9相交處的N58、N59和N89；x條路相交的路由節(jié)點(diǎn)處需定義個(gè)路由節(jié)點(diǎn)編號(hào)。

5) 相鄰2個(gè)圓點(diǎn)(包括省界虛擬站、實(shí)體收費(fèi)站及路由節(jié)點(diǎn)處定義的虛擬邏輯站)之間的路徑定義為邊；邊的權(quán)值既可是實(shí)際里程(用于路徑還原)，也可是計(jì)費(fèi)金額(用于計(jì)費(fèi))。

6) 同一個(gè)路由節(jié)點(diǎn)處的虛擬邏輯站之間的邊權(quán)值為0。

若以圓點(diǎn)為頂點(diǎn)，以相互之間的權(quán)值為邊的鄰接矩陣為G，則G按以下規(guī)則定義：

1) 若頂點(diǎn)Pi與Pj相鄰，則G[i,j]=Wij，Wij表示邊上的權(quán)值；

2) 若頂點(diǎn)Pi與Pj不相鄰、不互通，則G[i,j]=無窮大；

3) 若頂點(diǎn)Pi與Pj屬于同一路由節(jié)點(diǎn)，則G[i,j]=0。

根據(jù)路網(wǎng)結(jié)構(gòu)的解析和元素定義結(jié)果生成基礎(chǔ)參數(shù)，結(jié)合基礎(chǔ)支撐算法，采用全國統(tǒng)一的路徑還原尋優(yōu)規(guī)則實(shí)現(xiàn)多省通行車輛的路徑還原，采用各自省內(nèi)的計(jì)費(fèi)尋優(yōu)規(guī)則實(shí)現(xiàn)車輛通行費(fèi)動(dòng)態(tài)計(jì)算。

3.3 基礎(chǔ)參數(shù)

根據(jù)上述路網(wǎng)結(jié)構(gòu)模型對(duì)路網(wǎng)結(jié)構(gòu)中的點(diǎn)和邊進(jìn)行分類歸納，基礎(chǔ)參數(shù)主要包括站點(diǎn)基礎(chǔ)編碼信息表、路由節(jié)點(diǎn)信息表和路段內(nèi)費(fèi)率表。

3.3.1 站點(diǎn)基礎(chǔ)編碼信息表

該表用來描述路段內(nèi)的站點(diǎn)信息(包括實(shí)體收費(fèi)站、省界虛擬站、虛擬邏輯站、標(biāo)識(shí)點(diǎn)和掉頭位等),組成信息包括路段編碼、站點(diǎn)編碼、站點(diǎn)名稱、站點(diǎn)類型、物理序號(hào)、啟用時(shí)間和版本號(hào)等。以圖4中的L2路段為例，站點(diǎn)基礎(chǔ)編碼信息表見表1。

表1 L2路段站點(diǎn)基礎(chǔ)編碼信息表

3.3.2 路由節(jié)點(diǎn)信息表

該表用來描述省內(nèi)路段與路段之間的關(guān)系和跨省路段與路段之間的關(guān)系。路由節(jié)點(diǎn)由2條不同路段的各自1個(gè)虛擬邏輯站點(diǎn)組成，組成信息包括節(jié)點(diǎn)編號(hào)、節(jié)點(diǎn)名稱、路段編碼1、站點(diǎn)編碼1、路段編碼2、站點(diǎn)編碼2、啟用狀態(tài)、啟用時(shí)間和版本號(hào)等。以圖4中的L5、L8和L9路段相交的路由節(jié)點(diǎn)為例，路由節(jié)點(diǎn)信息表見表2。

表2 路由節(jié)點(diǎn)信息表

3.3.3 路段內(nèi)費(fèi)率表

該表用來描述路段內(nèi)相鄰2個(gè)站點(diǎn)之間的里程、單價(jià)和標(biāo)識(shí)點(diǎn)信息，組成信息包括路段編碼、站點(diǎn)編碼1、站點(diǎn)編碼2、實(shí)際里程、計(jì)費(fèi)金額、標(biāo)識(shí)點(diǎn)編碼、啟用時(shí)間和版本號(hào)等。以圖4中的L2路段為例，共有4個(gè)站點(diǎn)，應(yīng)包含12條路段內(nèi)費(fèi)率記錄，部分記錄見表3。

表3 路段內(nèi)費(fèi)率表

3.4 基礎(chǔ)支撐算法

當(dāng)前大部分省市都采用“笛卡爾表”將路網(wǎng)的全部路徑和對(duì)應(yīng)的通行費(fèi)羅列出來，通過將實(shí)際路徑與之匹配得出通行費(fèi)。省界實(shí)體收費(fèi)站拆除之后路網(wǎng)結(jié)構(gòu)的疊加導(dǎo)致計(jì)算復(fù)雜度呈幾何級(jí)增長(zhǎng)，全國高速公路仍在不斷建設(shè)聯(lián)網(wǎng)接入系統(tǒng)，費(fèi)率表更新頻繁，采用“笛卡爾表”法羅列的全部路徑會(huì)有十分龐大的數(shù)據(jù)量，參數(shù)的生成、存儲(chǔ)、傳輸、運(yùn)算和特殊情況處理都將成為問題。

全國路段形成一張大網(wǎng)之后，站點(diǎn)基數(shù)激增會(huì)導(dǎo)致運(yùn)算效率下降。因此，本文先將路網(wǎng)的虛擬邏輯站作為點(diǎn)，將路段內(nèi)虛擬邏輯站與虛擬邏輯站之間的實(shí)際里程作為邊，計(jì)算出不同路段內(nèi)虛擬邏輯站之間的最短路徑，再加上入口收費(fèi)站到入口路段虛擬邏輯站的路徑和出口路段虛擬邏輯站到出口收費(fèi)站的路徑，構(gòu)成一條完整的路徑,最后根據(jù)規(guī)則從眾多完整路徑中選取一條最優(yōu)路徑作為最終結(jié)果。

因此，基于圖論原理，將高速公路路網(wǎng)結(jié)構(gòu)解析成點(diǎn)、邊，根據(jù)車輛路徑信息在“圖”中還原車輛行駛路徑，最終達(dá)到動(dòng)態(tài)計(jì)算通行費(fèi)的目的。

本文采用Dijkstra算法計(jì)算不同路段內(nèi)虛擬邏輯站之間的最短路徑，該算法時(shí)間復(fù)雜度為O(n^2)。

以圖4為例，虛擬邏輯站組成的帶權(quán)有向圖見圖5，共包含16個(gè)點(diǎn)和18條邊(7條邊權(quán)值大于0，用實(shí)線表示；11條邊權(quán)值等于0，用虛線表示)。

圖5 虛擬邏輯站帶權(quán)有向圖

現(xiàn)模擬計(jì)算L4路段S404收費(fèi)站與L5路段S504收費(fèi)站之間的最短距離，步驟如下：

1) 獲取L4路段內(nèi)的所有虛擬邏輯站V499和V498，以及L5路段內(nèi)的所有虛擬邏輯站V599和V598;

2) 通過Dijkstra算法計(jì)算V499到其他虛擬邏輯站的最短距離；

3) 將V499到V599的最短距離和V499到V598的最短距離保留；

4) 重復(fù)步驟2)和步驟3)，計(jì)算V498到V599的最短距離和V498到V598的最短距離；

5) 將V499到V599的最短距離路徑與S404到V499的路段內(nèi)路徑和V599到S504的路段內(nèi)路徑相加，構(gòu)成一條完整的路徑S404—V499—V599—S504；

6) 獲取另外3條完整路徑為S404—V499—V598—S504、S404—V498—V599—S504和S404—V498—V598—S504，從4條完整路徑中選取里程最短的路徑作為最終的計(jì)算結(jié)果。

3.5 費(fèi)率計(jì)算模型

全國各高速公路聯(lián)網(wǎng)收費(fèi)省份的貨車計(jì)費(fèi)規(guī)則、綠通車輛執(zhí)行標(biāo)準(zhǔn)、特殊車輛車型認(rèn)定和通行費(fèi)優(yōu)惠政策執(zhí)行標(biāo)準(zhǔn)都不盡相同，為降低取消高速公路省界收費(fèi)站項(xiàng)目的難度和成本，促進(jìn)各省計(jì)費(fèi)規(guī)則的個(gè)性化發(fā)展，對(duì)于費(fèi)率計(jì)算模型，采用圖6所示的模型。

圖6 費(fèi)率計(jì)算模型

在該模型中，路徑還原和疊加計(jì)費(fèi)結(jié)果作為共性模塊由部聯(lián)網(wǎng)中心統(tǒng)一處理，針對(duì)具有差異性的各省費(fèi)率計(jì)算模塊，部聯(lián)網(wǎng)中心定義統(tǒng)一的輸入輸出參數(shù)接口，各省按自己的計(jì)費(fèi)規(guī)則對(duì)路徑還原結(jié)果進(jìn)行通行費(fèi)計(jì)算，并將統(tǒng)一格式的計(jì)費(fèi)結(jié)果反饋給疊加計(jì)費(fèi)結(jié)果模塊，形成一個(gè)完整的多省通行總通行費(fèi)結(jié)果進(jìn)行輸出。

4 應(yīng)用實(shí)例

2018年12月28日，隨著川渝省界10座收費(fèi)站全部停用，車輛從省界虛擬收費(fèi)站高速通過，從跨省交易到跨省清分結(jié)算,通過了完整的數(shù)據(jù)周轉(zhuǎn)流程，標(biāo)志著川渝取消省界收費(fèi)站取得圓滿成功。迄今為止，系統(tǒng)運(yùn)行平穩(wěn)、高效，該方案的可行性得到充分驗(yàn)證。

5 結(jié) 語

本文所述方案解決了省界收費(fèi)站拆除之后由于路網(wǎng)結(jié)構(gòu)疊加導(dǎo)致的通行費(fèi)計(jì)算量級(jí)呈幾何級(jí)增長(zhǎng)帶來的計(jì)算效率問題，避免了采用“笛卡爾表” 方式引起的參數(shù)生成、存儲(chǔ)、傳輸和運(yùn)算方面的問題,實(shí)現(xiàn)了收費(fèi)系統(tǒng)計(jì)費(fèi)模塊的動(dòng)態(tài)化、實(shí)時(shí)化和快速化，計(jì)費(fèi)規(guī)則更靈活，參數(shù)更易維護(hù)。同時(shí)，計(jì)費(fèi)方案有效保留了聯(lián)網(wǎng)收費(fèi)省份各自的特殊收費(fèi)規(guī)則，降低了改造成本。實(shí)施模式不僅滿足了收費(fèi)站獨(dú)立的收費(fèi)業(yè)務(wù)處理能力，而且提供了車輛異常通行情況下路徑還原和通行費(fèi)計(jì)算的處理通道。

由于當(dāng)前技術(shù)的局限性，省界收費(fèi)站拆除之后帶來的U轉(zhuǎn)車輛逃費(fèi)、通行超時(shí)和節(jié)假日逃費(fèi)等問題無法完全通過技術(shù)手段得到解決，可結(jié)合個(gè)人信用系統(tǒng)和稽查系統(tǒng)進(jìn)行有效的管理，避免規(guī)則漏洞被無限放大利用。此外，關(guān)于路網(wǎng)結(jié)構(gòu)中的路段交匯處非互通問題和掉頭位問題，由于該方案的應(yīng)用場(chǎng)景不涉及，因此未作描述，有待進(jìn)一步研究。