諶儀 谷麗莎 楊鳳滿

摘 ? 要：高速公路的廣域聯(lián)網(wǎng)收費(fèi)需要根據(jù)車輛行駛路徑作為通行費(fèi)費(fèi)額計(jì)算和拆分的依據(jù)，這就要求收費(fèi)系統(tǒng)能夠精準(zhǔn)判定車輛行駛路徑。本文在具有通信功能的智能車輛的基礎(chǔ)上提出了一種利用圖論理論解決多義性路徑問題的方法。本文首先對(duì)多路徑識(shí)別問題的邏輯本質(zhì)進(jìn)行了分析和簡(jiǎn)化，隨后通過對(duì)目前所采用的不同的工程解決方法的分析和比較，給出二義性路徑問題的核心內(nèi)容;隨后提出了通信節(jié)點(diǎn)等概念的設(shè)想，并結(jié)合實(shí)際工程情況給出了約束條件;最后利用圖論理論給出了收費(fèi)路網(wǎng)與圖的映射方法與多路徑識(shí)別實(shí)現(xiàn)思路。

關(guān)鍵詞：智能車輛 ?收費(fèi)道路 ?二義性路徑 ?車路通信 ?路徑識(shí)別

中圖分類號(hào)：TP391 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A ? ? ? ? ? ? ? ? ? ? ? ?文章編號(hào)：1674-098X（2019）09（a）-0031-03

隨著電子不停車收費(fèi)技術(shù)的普及和無線通信技術(shù)的發(fā)展，高速公路聯(lián)網(wǎng)收費(fèi)已經(jīng)成為未來的明確發(fā)展方向。2019年4月28日，交通運(yùn)輸部在新聞發(fā)布會(huì)上公開介紹了目前取消全國高速公路省界收費(fèi)站的最新進(jìn)展，并表示后續(xù)會(huì)加快推進(jìn)各項(xiàng)工程建設(shè)，確保按期完成取消全國高速公路省界收費(fèi)站的目標(biāo)任務(wù)?？梢灶A(yù)見，在各省省界收費(fèi)站取消的情況下全國高速公路將形成一張結(jié)構(gòu)復(fù)雜、規(guī)模龐大的路網(wǎng)，這將對(duì)道路收費(fèi)的管理體制、機(jī)制以及收費(fèi)方式產(chǎn)生極大影響，使得目前國內(nèi)使用的最短路徑收費(fèi)處理方式存在的問題進(jìn)一步凸顯。目前國內(nèi)使用的最短路徑收費(fèi)處理方式存在明顯的弊端：首先是在入口和出口跨省或跨公路運(yùn)營主體的情況下，無法準(zhǔn)確、公正的拆分費(fèi)用，查分比例無計(jì)算依據(jù)。其次，一般采用最短路徑收取通行費(fèi)，在復(fù)雜路網(wǎng)情況下，通行費(fèi)流失將明顯加大[1]，熟悉路網(wǎng)的司機(jī)可合法逃費(fèi)。再次，個(gè)別收費(fèi)站存在車輛逃費(fèi)的情況，在全國路網(wǎng)聯(lián)通的情況下將產(chǎn)生更嚴(yán)重的通信費(fèi)流失問題。路徑識(shí)別問題得到了越來越廣泛的關(guān)注。

隨著我國高速公路的快速發(fā)展，復(fù)雜路網(wǎng)逐步形成，導(dǎo)致路網(wǎng)收費(fèi)計(jì)費(fèi)、拆分和逃費(fèi)問題凸顯。這些問題促使以車路無線技術(shù)為代表的各類新技術(shù)被迅速應(yīng)用到交通行業(yè)中，并得到快速的普及。5.8G已成為交通領(lǐng)域的專用頻段，在此基礎(chǔ)上已經(jīng)發(fā)展成熟了ETC電子不停車系統(tǒng)[2];同時(shí)，面向智能車輛的DSRC、LTE-V車路通信技術(shù)也有了迅速的發(fā)展，相應(yīng)的車路通信系統(tǒng)已經(jīng)初具雛形?；谝曨l檢測(cè)的各類算法功能日益強(qiáng)大，形成了大量具有精準(zhǔn)車輛識(shí)別功能的設(shè)備產(chǎn)品和系統(tǒng)[3]。未來應(yīng)充分利用交通信息化發(fā)展的成果解決當(dāng)前的復(fù)雜收費(fèi)路網(wǎng)的現(xiàn)實(shí)問題，已經(jīng)成為行業(yè)領(lǐng)域內(nèi)的共識(shí)。這些技術(shù)應(yīng)用從根本上看，都是以車與路之間的信息傳達(dá)為目的，即車與路的信息通信。路網(wǎng)不再是單一的物理系統(tǒng)，而是信息與物理共同構(gòu)建的系統(tǒng)。

1 ?多路徑識(shí)別問題現(xiàn)狀

在高速公路出現(xiàn)的早期，多路徑識(shí)別問題并沒有成為關(guān)注焦點(diǎn)。一方面是由于路網(wǎng)規(guī)模較小、結(jié)構(gòu)簡(jiǎn)單，多義性路徑非常少見;另一方面是因?yàn)楦咚俟返耐顿Y運(yùn)行主體單一，以國家或地方政府為主，不存在費(fèi)用歸屬判定的問題。隨著我國高速公路建設(shè)腳步的加快，路網(wǎng)規(guī)模和復(fù)雜程度的不斷提升，投資和運(yùn)營管理模式也變得更加多元化。二義性路徑數(shù)量的快速增長(zhǎng)和通行費(fèi)拆分需求的出現(xiàn)，使得多路徑識(shí)別問題逐步被關(guān)注和研究。

在收費(fèi)全部采用人工收費(fèi)方式的時(shí)期，由于多路徑識(shí)別技術(shù)手段匱乏，難以實(shí)現(xiàn)通行費(fèi)拆分;而費(fèi)額計(jì)算的問題一般是采用簡(jiǎn)化的最短路徑計(jì)算費(fèi)用的方法處理。隨著傳感器技術(shù)、通信技術(shù)和計(jì)算機(jī)技術(shù)的發(fā)展，各種信息化、智能化設(shè)備在收費(fèi)系統(tǒng)中的應(yīng)用，使得通行費(fèi)拆分問題逐步得到解決。目前常見的多路徑識(shí)別工程解決方法有兩大類，即模糊識(shí)別方法與精確識(shí)別方法。模糊識(shí)別是指通過地感線圈、流量雷達(dá)、視頻識(shí)別等技術(shù)，統(tǒng)計(jì)不同路徑的車流量和車型比例。在后續(xù)做通行費(fèi)拆分時(shí)，根據(jù)統(tǒng)計(jì)結(jié)果估算拆分比例，并將路費(fèi)拆分劃撥給不同的業(yè)主。模糊識(shí)別策略不能夠識(shí)別指定輛車的行駛路徑，因此不能夠作為通行收費(fèi)標(biāo)準(zhǔn)的選擇依據(jù)，只能作為通行費(fèi)拆分的依據(jù)，而且作為通行費(fèi)拆分依據(jù)也是粗略的。精確識(shí)別方法可以準(zhǔn)確識(shí)別目標(biāo)車輛的通行路徑，同時(shí)解決費(fèi)額計(jì)算和通行費(fèi)拆分的問題[4]。

雖然精準(zhǔn)識(shí)別方法能夠產(chǎn)生令人滿意識(shí)別結(jié)果，在大規(guī)模復(fù)雜路網(wǎng)的工程應(yīng)用中卻面臨諸多難點(diǎn)。首先是多義性路徑的辨識(shí)問題。在如圖1的簡(jiǎn)單路網(wǎng)中可以直觀的看出其中的多義性路徑。但大規(guī)模的復(fù)雜路網(wǎng)，其通道縱橫交錯(cuò)、互通形式多種多樣，很難直觀判別多義性路徑是否存在以及存在的位置。其次是多路徑識(shí)別設(shè)備的布設(shè)選點(diǎn)問題。在簡(jiǎn)單路網(wǎng)中可以直觀選點(diǎn)部署。但在復(fù)雜路網(wǎng)中存在各種形式的收費(fèi)站和多路徑識(shí)別設(shè)備，它們的位置和數(shù)量是基于舊的路網(wǎng)結(jié)構(gòu)設(shè)計(jì)的，并不一定能夠滿足新的復(fù)雜路網(wǎng)的路徑辨識(shí)需求。原有設(shè)備選點(diǎn)是否有效、是否需要增加設(shè)備點(diǎn)位、增加于何處等問題都將成為工程設(shè)計(jì)實(shí)施中的難點(diǎn)。最后是多義性路徑識(shí)別結(jié)果在通行費(fèi)計(jì)費(fèi)和拆分計(jì)算過程中的使用效率問題。無論采用何種多路徑識(shí)別設(shè)備，車輛通行費(fèi)的計(jì)費(fèi)與拆分都是統(tǒng)一到收費(fèi)系統(tǒng)的計(jì)算中心進(jìn)行計(jì)算處理的?？紤]到龐大復(fù)雜路網(wǎng)的通行車輛數(shù)量巨大、路徑組合繁多、通行費(fèi)拆分方式復(fù)雜等因素，這樣的集中處理方式必然會(huì)導(dǎo)致計(jì)算效率的低下。

可見，復(fù)雜大規(guī)模路網(wǎng)的精準(zhǔn)多路徑識(shí)別問歸結(jié)在以下三個(gè)方面：復(fù)雜路網(wǎng)的拆分與組合、多義性路徑辨識(shí)與定位以及多義性路徑路網(wǎng)的改造。

2 ?問題的簡(jiǎn)化

高速公路路網(wǎng)是典型的收費(fèi)路網(wǎng)，其路線在物理空間上是連續(xù)的。但從收費(fèi)系統(tǒng)的角度看，高速公路路網(wǎng)是以布設(shè)在高速路出入口、主線省界交匯點(diǎn)和互通樞紐等處的收費(fèi)站為節(jié)點(diǎn)，以道路路段為線段的點(diǎn)線組合體。從收費(fèi)系統(tǒng)的角度看，理想的路網(wǎng)狀態(tài)是任何兩個(gè)相鄰收費(fèi)站之間僅存在一條確定的通道;在車輛駛離路網(wǎng)后，收費(fèi)系統(tǒng)根據(jù)車輛途經(jīng)的收費(fèi)站判斷車輛的行駛路徑，并根據(jù)該路徑進(jìn)行通行費(fèi)用的相關(guān)處理。但新建道路的出現(xiàn)可能會(huì)打破這種理想狀態(tài)，使得某兩個(gè)相鄰收費(fèi)站之間出現(xiàn)了多條通道，并導(dǎo)致收費(fèi)系統(tǒng)無法準(zhǔn)確判斷車輛的行駛路徑。這時(shí)我們稱該路網(wǎng)具有多義性路徑。

多義性路徑會(huì)帶來兩個(gè)方面的現(xiàn)實(shí)問題。首先，不同的車輛行駛路徑可能會(huì)因?yàn)槔锍袒蚶锍虇蝺r(jià)的不同而產(chǎn)生不同的通行費(fèi)費(fèi)額。多義性路徑的存在使得收費(fèi)系統(tǒng)無法準(zhǔn)確計(jì)算通行費(fèi)費(fèi)額。其次，當(dāng)多義性路徑中的路段屬于不同的省份、地區(qū)或運(yùn)營單位（業(yè)主）時(shí)，收費(fèi)系統(tǒng)無法判別通行費(fèi)的歸屬，進(jìn)而無法進(jìn)行通行費(fèi)拆分[5]。

圖1展示了一組典型的多義性路徑。當(dāng)通行車輛進(jìn)入收費(fèi)路網(wǎng)的入口后，可以選擇通過線路A、B和C到達(dá)出口，從而使得收費(fèi)系統(tǒng)無法判斷車輛的實(shí)際行駛路徑。假設(shè)線路A和B屬于同一運(yùn)營管理機(jī)構(gòu)，而線路A的里程較線路B長(zhǎng)，通行費(fèi)比線路B也高一些;線路C與線路A的里程相同，但路線C與路線A、B分屬不同的業(yè)主。這種情況下，收費(fèi)系統(tǒng)無法確定通行費(fèi)用是按照線路A和C的里程來計(jì)算收取，還是按照線路B來計(jì)算收取;同時(shí)收費(fèi)系統(tǒng)也不知道收上來的通行費(fèi)應(yīng)該劃撥到哪一個(gè)業(yè)主的資金賬戶中。

工程上一般會(huì)在多義性路徑的路段上布設(shè)兩類多路徑識(shí)別設(shè)備。一類是能夠識(shí)別車輛身份的監(jiān)測(cè)設(shè)備，另一類是能夠在車載電子標(biāo)簽中順序標(biāo)記路段標(biāo)識(shí)碼的射頻寫入設(shè)備[6]。如圖1所示，分別在路徑A、B和C的適當(dāng)位置布設(shè)車輛身份監(jiān)測(cè)設(shè)備，并將監(jiān)測(cè)結(jié)果及時(shí)的告知收費(fèi)系統(tǒng)，則收費(fèi)系統(tǒng)可以在任意一輛車駛離路網(wǎng)后精確的判斷出它的行駛路徑。

從交通工程的角度上看，多路徑識(shí)別問題就是通過某些技術(shù)手段使收費(fèi)系統(tǒng)獲取足夠多的車輛行駛路徑上的途經(jīng)點(diǎn)信息，從而反推計(jì)算出車輛確切的行駛路徑。但如果將收費(fèi)系統(tǒng)和道路網(wǎng)絡(luò)視為一個(gè)信息系統(tǒng)和物理系統(tǒng)疊加而成的有機(jī)整體，從收費(fèi)系統(tǒng)的角度看，多路徑識(shí)別問題的本質(zhì)是通過技術(shù)手段將收費(fèi)路網(wǎng)原有拓?fù)浣Y(jié)構(gòu)進(jìn)行改變，使得收費(fèi)系統(tǒng)獲得一個(gè)不存在多義性路徑的路網(wǎng)拓?fù)浣Y(jié)構(gòu)。

3 ?道路網(wǎng)絡(luò)與圖的映射

圖論是組合數(shù)學(xué)的—個(gè)分支學(xué)科，與其他的數(shù)學(xué)分支，如群論、矩陣論、概率論、拓?fù)鋵W(xué)、數(shù)值分析等有著密切的聯(lián)系[7]。圖論理論最早出現(xiàn)于十七世紀(jì)，并用于研究哥尼斯堡城的七橋問題，并由數(shù)學(xué)家歐拉發(fā)表了有關(guān)圖論的最早論著。圖論利用圖的概念來對(duì)客觀世界中的具體實(shí)物間的聯(lián)系進(jìn)行抽象的數(shù)學(xué)表述，并對(duì)其特性和規(guī)律加以研究。由于圖的基本結(jié)構(gòu)是由“頂點(diǎn)”和“邊”構(gòu)成，這些構(gòu)成圖的要素與路網(wǎng)中的“起點(diǎn)”、“終點(diǎn)”和“路段”等要素具有極好的吻合性。因此，利用圖論理論對(duì)路網(wǎng)進(jìn)行建模、將路網(wǎng)的拓?fù)浣Y(jié)構(gòu)以圖的形式進(jìn)行表征和研究是一個(gè)值得探索的方法[8]。在解決多義性路徑的問題上，已經(jīng)有結(jié)合圖論理論進(jìn)行研究案例。

將道路網(wǎng)絡(luò)映射為圖，首先要將路網(wǎng)及其相關(guān)設(shè)施、設(shè)備進(jìn)行完整、統(tǒng)一的抽象提取。根據(jù)公路收費(fèi)計(jì)算的基本原則（按里程計(jì)費(fèi)、按分屬機(jī)構(gòu)拆分），多路徑識(shí)別本質(zhì)上是信息空間和物理空間融合問題的一個(gè)特例。從圖1中可以直觀的看到，在入口、出口和車輛檢測(cè)設(shè)備所在點(diǎn)位都會(huì)發(fā)生一些信息交互;而道路的其他點(diǎn)位則僅僅是為車輛通行提供條件。因此，我們將一些可以產(chǎn)生信息交互的點(diǎn)作為圖的頂點(diǎn)，其他的普通路段作為圖的邊，這樣形成的圖抽象的表征了信息空間和物理空間。為了抽象表述的需要，我們將車輛與道路設(shè)施進(jìn)行通信的位置稱為通信節(jié)點(diǎn)，簡(jiǎn)稱節(jié)點(diǎn)。從工程實(shí)現(xiàn)的角度看，節(jié)點(diǎn)是由一些具備通信功能的實(shí)體設(shè)備實(shí)現(xiàn)的。這些實(shí)體設(shè)備由于技術(shù)、結(jié)構(gòu)等方面的不同，其特性也有所不同。

4 ?約束條件與映射方法

為了能夠使用圖提供的數(shù)學(xué)工具為多義性路徑精準(zhǔn)識(shí)別問題提供普適性解決方法，需要根據(jù)實(shí)際情況為收費(fèi)路網(wǎng)設(shè)定約束：（1）車輛在經(jīng)過收費(fèi)路網(wǎng)的通信節(jié)點(diǎn)時(shí)以不同規(guī)律發(fā)生車路通信事件。（2）無論車路通信事件的信息傳遞方向是車輛到道路還是道路到車輛，在車輛離開收費(fèi)路網(wǎng)的最后一個(gè)節(jié)點(diǎn)時(shí)，車輛所經(jīng)過的路徑上的全部節(jié)點(diǎn)所發(fā)生的通信事件信息將匯總至收費(fèi)管理中心。（3）路網(wǎng)中的道路均為雙向道路。

在約束條件下，圖可以采用以下兩條基本方法構(gòu)建：（1）收費(fèi)路網(wǎng)中的出口、入口、互通收費(fèi)站以及主線收費(fèi)站等視為節(jié)點(diǎn)，映射為圖中的頂點(diǎn);（2）節(jié)點(diǎn)間可連續(xù)通行的道路（主線）映射為圖的邊。一個(gè)典型的收費(fèi)路網(wǎng)結(jié)構(gòu)如圖2所示，根據(jù)上述構(gòu)建方法形成的圖G，如圖3所示。

5 ?基于圖的精準(zhǔn)多路徑識(shí)別

在復(fù)雜且規(guī)模龐大的路網(wǎng)中不僅存在著大量的出入口、互通樞紐，還包括了種類繁多的檢測(cè)、通信設(shè)備，并且隨著交通建設(shè)的推進(jìn)，這種情況還會(huì)變得更加明顯。利用對(duì)圖的各種特性分析，以及圖中鏈、跡和路等概念的應(yīng)用，可以獲得普適性的分析和計(jì)算方法。本文提出以下設(shè)想和思路。

思路1：利用復(fù)雜圖精準(zhǔn)計(jì)算任意一輛通行車輛的收費(fèi)標(biāo)準(zhǔn)和通行費(fèi)拆分比例將是一個(gè)計(jì)算量龐大的任務(wù)。因此我們可以利用圖運(yùn)算理論，通過割邊和割點(diǎn)對(duì)復(fù)雜連通圖進(jìn)行拆分。拆分后的路網(wǎng)由多個(gè)簡(jiǎn)單子路網(wǎng)組成，便于問題的分析與解決。

思路2：通過對(duì)路網(wǎng)中二義性路徑所對(duì)應(yīng)的鏈、跡和路等組成部分進(jìn)行改造，通過增加節(jié)點(diǎn)的方式，去除帶有二義性的路徑組成部分;增加的節(jié)點(diǎn)可以反映設(shè)到實(shí)際道路工程中，并以節(jié)點(diǎn)通信設(shè)備的方式體現(xiàn)出來。

思路3：收費(fèi)道路路網(wǎng)所映射的圖可以規(guī)范的以矩陣形式表述，矩陣的各種特性代表了路網(wǎng)的各種特性的同時(shí)，在拆分組合和加權(quán)運(yùn)算等方面還具有便于計(jì)算機(jī)語言實(shí)現(xiàn)的特點(diǎn)，為道路網(wǎng)絡(luò)建設(shè)的工程實(shí)現(xiàn)奠定了很好的基礎(chǔ)。

參考文獻(xiàn)

[1] 王勤.復(fù)雜高速路路網(wǎng)聯(lián)網(wǎng)收費(fèi)清分方法研究[D].武漢理工大學(xué)，2010.

[2] 王義祥.電子不停車收費(fèi)系統(tǒng)在我國的發(fā)展[J].物流科技，2006（2）：72-75.

[3] 薄秀麗.高速收費(fèi)站高清視頻車牌識(shí)別系統(tǒng)的研究[J].山西交通科技，2016（5）：99-100.

[4] 鄭遠(yuǎn)，李江，施麗娟，等.車牌識(shí)別技術(shù)在多義性路徑問題中的應(yīng)用[J].交通信息與安全，2007（6）：121-127.

[5] 宋祖科，趙修建.高速公路車輛通行費(fèi)精確收取及拆分技術(shù)研究[J].公路工程，2009（1）：147-150.

[6] 孫凱.高速公路多路徑識(shí)別技術(shù)研究及實(shí)現(xiàn)[D].鄭州大學(xué)，2013.

[7] 卜月華.圖論及其應(yīng)用[M].福建：東南大學(xué)出版社，2002.

[8] 陳雨人，陳少軍.包含立交匝道信息的高速公路網(wǎng)絡(luò)復(fù)雜拓?fù)浣Y(jié)構(gòu)[J].同濟(jì)大學(xué)學(xué)報(bào)：自然科學(xué)版，2010，38（2）：230-237.