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

諶儀 谷麗莎 楊鳳滿

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

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

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

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

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

1 ?多路徑識別問題現狀

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

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

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

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

2 ?問題的簡化

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

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

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

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

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

3 ?道路網絡與圖的映射

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

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

4 ?約束條件與映射方法

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

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

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

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

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

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

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

參考文獻

[1] 王勤.復雜高速路路網聯網收費清分方法研究[D].武漢理工大學，2010.

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

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

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

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

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

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

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