高速公路多路徑識別點布設與優化分析

摘 要： 針對聯網高速公路的多路徑識別問題，通過將高速公路網狀路網結構簡化為無向連通圖，引入路段距離作為路徑權值，采用最小支撐樹生成算法推算得出路網的識別點布設最少數量及其初始布設位置，通過枚舉與對比分析在布設冗余識別點后的環路總體識別率，得出識別點的最優冗余布設方式，實現高速公路網狀路網結構中多路徑識別點的合理布設。實踐表明，通過最小支撐樹算法和分布式冗余方式所得的識別點布局能夠較好的解決高速公路多路徑識別問題。

關鍵詞： 智能交通； 高速公路； 多路徑識別點； 最小支撐樹

中圖分類號： TN911?34 文獻標識碼： A 文章編號： 1004?373X（2015）24?0050?03

Layout and optimized analysis of multipath recognition points of expressway

LIN Dong， JIN Tao， ZHANG Tong

（Xi’an Highway Institute， Xi’an 710065， China）

Abstract： Aiming at the problem of multipath recognition of networked expressway， the structure of the expressway network is simplified to the undirected connected graph， the road distance is introduced as route weight value， and the minimal spanning tree is used to generate the algorithm to derive minimum number of the recognition points in the road net and its initial layout position. The overall recognition rate of the loop after the redundancy recognition points are wer laid out is analyzed by enumeration and comparison toobtain the optimal redundancy layout mode of the recognition points， and realize the reasonable layout of the multipath recognition points in the structure of the expressway network. The practice shows that the layout of the recognition points obtained by the minimum spanning tree algorithm and distributed redundancy mode can solve the problem of multipath recognition of expressway

Keywords： ITS； expressway； multipath recognition point； minimum spanning tree

0 引 言

隨著高速公路的不斷建設，路網密度逐漸增大，在路網中兩站點之間可能存在2條或2條以上的行駛路徑，對于司乘人員來說，可選擇多種行駛路徑。而在高速公路聯網收費和高速公路投資主體多元化的環境下，由于車輛行駛路徑的無法確定有可能產生諸多問題[1]。通過在路段中布設的識別點識別車輛或車輛代碼信息，結合由收費數據已知的車輛入口、出口信息，就可以準確地判斷車輛在路網中的行駛路徑，從而為解決高速公路多路徑問題提供基礎[2]。目前識別點布設位置大多采用支撐樹理論來確定[3?5]，而對于同一個簡單連通圖，以不同的節點作為起始節點運算時所得的支撐樹結果并不一致[6]。因此，通過該方法仍無法確定較合理的識別點布設位置。本文針對上述問題，引入路段權值，采用最小支撐樹算法，計算較合理的識別點布設位置，并在相同條件下分析識別點布設優化方式，以實現更好的提高整體識別率。

1 理論基礎

高速路網結構實際可理解為由各路段組成的無向連通圖，因而可通過一定路徑算法在連通圖的關鍵路徑中設置識別點，將交通網絡網狀結構圖轉化為路徑惟一的樹狀結構圖。而對于樹狀路網結構，兩站點之間的路徑是惟一的。連通圖與樹狀圖相差的斷面即為理論應布設識別點的位置。因此，識別點的布設過程實際上是將該簡單連通圖轉換為路徑惟一樹狀圖的過程。本文基于圖論基本理論[6]，確定環路路網需要設置的識別點問題。

對于給定環路圖G，記為：

[G=（V（G），E（G），Φ（G））]

式中：[V（G）={v1，v2，…，vm}]為節點簡化集合，由路網中的互通立交和收費站組成；[E（G）={e1，e2，…，en}]為路段簡化結合，包含收費站之間和收費站與互通立交之間的路段斷面。對于單個斷面et，由兩起止節點[vi]和[vj]連接組成，記[et={vi，vj}]；[Φ（G）]為節點之間的關聯函數，可用鄰接矩陣進行描述。

定理1 一個圖有支撐樹的充分必要條件是該圖是一個連通圖。

定理2 一個圖是樹的充分必要條件是任意兩頂點之間有且僅有一條邊。

2 識別點的數量

由支撐樹的基本定理可知，將簡單圖G轉換為支撐樹所需打斷的斷面數量M的計算過程為：

[M=E（G）-V（G）+1]

在確定了路網中需要加識別點的數量后，就是要確定識別點的布設位置，即識別點要設置在哪些邊上。而確定簡單連通圖的識別點的位置問題等價于計算圖的支撐樹問題，即打斷所需布設識別點的斷面，將圖狀結構轉換成樹狀結構。

3 識別點的位置分析

在進行支撐樹展開時，從不同起點開始進行運算所得的結果不一致。因此，在所得的支撐樹結果集中仍需選擇一個樹狀結構作為最適合的識別點布設結果。

對于識別點識別率達不到100%的情況下，通過的車輛數和識別的錯誤率共同決定金額拆分的誤差。由于司乘人員較大可能的選擇最短路徑，以節省更多的道路出行時間，對于路徑較長的斷面車流相對較小。在一定的識別率情況下，若將識別點布設于環路中路徑最長的斷面，由于車流量可能較其他斷面較少，所產生的誤差數較少。因此，在環路路徑最長的斷面布設識別點較為適合。在路網圖G中，[et={vi，vj}]給[et]賦的值稱為路段的權值，[et]的值可由多種形式來描述，文中將[et]的權值定義為斷面間的距離。

在環路路徑中最長斷面上布點相當于所計算得的支撐樹權值總和應為最小，即在路網圖中選擇合適的位置進行展開樹，可以等效為求連通圖的最小支撐樹問題。該問題可用最小支撐樹算法計算得出，本文采用的是KRUSKAL算法計算簡單連通圖的最小支撐樹[7]。

KRUSKAL算法的基本思路如下：

假設一個有n個頂點的連通圖[G=（V（G），E（G），Φ（G））]，最初構造一個只有n個頂點，但是沒有邊的非連通圖[T={V，Φ}]，圖中每個頂點自成一個連通分量。在E中選擇一條權值最小的邊，若該邊兩個頂點落在不通的連通分量上，則將此邊加入到T中；否則此邊舍去，重新選擇一條邊，并重復上述過程，直到所有的連通分量重新組合成一個連通圖。

綜合上述基本思想，計算高速路網圖的最小支撐樹的KRUSKAL算法的實現過程步驟如下：

（1） 按路段權值的不減順序將邊重排成[a1，a2，…，an]，并按這個順序逐個選取候選斷面；

（2） 將所選取的候選路段加入已選擇的路段集合中，同時，判斷在已選擇路段集合中是否存在環路，若存在環路則拋棄該選擇的斷面，重新選擇下一個斷面；

（3） 重復步驟（2），直到所有邊選擇完畢。

在計算過程中，判斷一線則路段集合中是否存在環路的判定方法：已選擇的路段集合為斷面集合[e（G）]的子集，該子集記為[S={e1，e2，…，ei}]，當該子集已確定時，對候選路段[aj]有圖[GS?{aj}]無圈等價于[aj]的兩端點在[GS]的不同分支中，其中[GS]表示以S為邊集的圖G的生成子圖。由于在算法的第（1）步已經對路段權值進行了不減排序，因此按該順序依次選擇所組成的樹狀圖權值總和應為最小。

4 識別點布設實例

以陜西省西咸北環線在建路網為例，路網如圖1所示。記為[G1=（V1，E1）]，[V1]為節點簡化集合，包含路網中的互通立交和收費站，共27個節點；[E1]為路段斷面簡化結合，包含收費站之間和收費站與互通立交之間的路段斷面，共37條邊。

圖1 陜西西咸北環線路線簡化圖

根據支撐樹定理可知，陜西西咸北環線路徑識別點數量應布設[E1]-[V1]+1=11個。

通過KRUSKAL算法，將陜西西咸北環線路網結構簡化圖所得的生成樹記為圖[G2=（V2，E2）]。識別點所需布設的位置斷面為圖G3=G1-G2，識別點布設位置見圖2。

圖2 規劃路線簡化圖最小生成樹

5 識別點布設優化方式

通過最小支撐樹理論，確定識別點應該布設的路網的路段，能夠解決多路徑的識別問題，該布設方式可稱之為最小布設。實際上，識別點設備也可能會由于各種因素導致設備失效，無法識別出車輛代碼信息，這就需要通過增加冗余識別點與原有的識別點構成識別數據的冗余互補，來提高整個系統的識別可靠性。識別點的冗余布設方式可簡單分為重復布設和分布式布設兩種方式[8]。

（1） 重復式布設。對于路網G=（V，E），其中路網的支撐樹為G1 =（V，E1），E2 =E-E1為標識站所要布設的路段。在路段E2中選擇部分或者全部路段增設識別點，稱之為簡單重復布設。當選擇E2的所有路段增設識別點時，稱之為完全重復式布設。在入出口之間經過識別點數量越多，識別的概率越高。假設識別點的識別率均為p，經過n個識別點的識別概率R的計算公式為：

[R=1-（1-p）n]

（2） 分布式布設。分布式布設是將冗余節點布設于已布設斷面以往外的其他斷面。同上，由于已經確定識別點布設的路段E2=E-E1。在E1中選擇一部分或者全部，記為E3，作為冗余識別點的布設位置，它所對應的圖為G3=（V3，E3），E2和E3共同組成識別點的分布式布設模式。

通過冗余布設后，在相同入出口的多條路徑之間有可能經過的識別點數量不一致，其識別率提高程度也不一致。重復式方式提高了途徑E2識別點的路徑識別率，未經過E2識別率則為零；分布式方式未提高E2的識別率，提高了的E3識別率。兩種方式都提高了車輛識別率，對于環路總體而言，在相同條件下所識別的車輛越多，總體識別率越高，冗余布設點的位置則相對越合理。

6 識別點優化實例分析

以陜西西藍商高速環路為例，環路中有兩個最小環，采用KRUSKAL最小支撐樹算法計算得出的最小支撐樹，其簡單環路和最小布設位置如圖3所示。

圖3 西藍商環路與最小支撐樹示意圖

將完全重復式和分布式冗余布局分別應用于在該路網結構中，其布設位置如圖4所示。

圖4 重復式布設與分布式布設示意圖

假定識別率[p=85%]，斷面流量均為M，通過窮舉法，圖3所示的各節點之間將產生15種路徑，其識別車輛比例如表1所示。

表1 識別車輛數比例 %

對上述各起止節點的路徑識別車輛概率數據求平均概率，結果如表2所示。

表2 冗余布設方式平均識別率 %

由表2可知，以分布式冗余方式增設識別點，在新增較少識別點數量的同時更容易提高系統整體識別率。

7 結 語

通過引入路段權值，利用KRUSKAL最小支撐樹算法，計算出多路徑為題所需的識別點數量及合理的最小布設位置。并通過對比分析冗余布設方式的識別率，提出采用分布式冗余模式，較容易提高系統整體識別率。通過實踐證明，在合理選擇識別點位置，并通過分布冗余方式增設識別點，能夠較好地提高識別率，解決多路徑車輛識別問題。

參考文獻

[1] 金濤，張海峰，張姣姣，等.陜西省高速公路多義性路徑通行費的拆分方法[J].中國交通信息化，2012（8）：76?77.

[2] 賴樹坤，邱淮，劉智麗.基于車牌識別的高速公路通行費拆分技術研究及應用[J].交通運輸系統工程與信息，2011（4）：186?191.

[3] 張健.高速公路聯網收費多路徑判斷技術方法研究[D].西安：長安大學，2008.

[4] 叢浩哲，姜杰.基于支撐樹法的高速公路多路徑識別問題研究[J].交通與運輸：學術版，2007（1）：80?83.

[5] 高潔，施其洲.高速公路標識站選址模型與算法研究[J].公路交通科技，2008（1）：139?141.

[6] 李明哲.圖論及其算法[M].北京：機械工業出版社，2010.

[7] 王海英.圖論算法及其Matlab實現[M].北京：北京航空航天大學出版社，2010.

[8] 蔣貴川，易術，林莉.路徑二義性判別問題中的標識站設置研究[J].公路，2011（5）：104?107.