一種面向智能車輛的多路徑識別方法的初步思考①

諶儀 谷麗莎 楊鳳滿

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

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

中圖分類號：TP391 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文獻標識碼：A ? ? ? ? ? ? ? ? ? ? ? ?文章編號：1674-098X（2019）09（a）-0031-03

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

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

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

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

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

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

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

2 ?問題的簡化

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

多義性路徑會帶來兩個方面的現(xiàn)實問題。首先，不同的車輛行駛路徑可能會因為里程或里程單價的不同而產(chǎn)生不同的通行費費額。多義性路徑的存在使得收費系統(tǒng)無法準確計算通行費費額。其次，當多義性路徑中的路段屬于不同的省份、地區(qū)或運營單位（業(yè)主）時，收費系統(tǒng)無法判別通行費的歸屬，進而無法進行通行費拆分[5]。

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

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

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

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

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

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

4 ?約束條件與映射方法

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

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

5 ?基于圖的精準多路徑識別

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

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

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

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

參考文獻

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

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

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

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

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

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

[7] 卜月華.圖論及其應用[M].福建：東南大學出版社，2002.

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