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

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

中圖分類號： TN911?34 文獻(xiàn)標(biāo)識碼： 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 引 言

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

1 理論基礎(chǔ)

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

對于給定環(huán)路圖G，記為：

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

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

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

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

2 識別點的數(shù)量

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

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

在確定了路網(wǎng)中需要加識別點的數(shù)量后，就是要確定識別點的布設(shè)位置，即識別點要設(shè)置在哪些邊上。而確定簡單連通圖的識別點的位置問題等價于計算圖的支撐樹問題，即打斷所需布設(shè)識別點的斷面，將圖狀結(jié)構(gòu)轉(zhuǎn)換成樹狀結(jié)構(gòu)。

3 識別點的位置分析

在進(jìn)行支撐樹展開時，從不同起點開始進(jìn)行運(yùn)算所得的結(jié)果不一致。因此，在所得的支撐樹結(jié)果集中仍需選擇一個樹狀結(jié)構(gòu)作為最適合的識別點布設(shè)結(jié)果。

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

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

KRUSKAL算法的基本思路如下：

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

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

（1） 按路段權(quán)值的不減順序?qū)⑦呏嘏懦蒣a1，a2，…，an]，并按這個順序逐個選取候選斷面；

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

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

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

4 識別點布設(shè)實例

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

圖1 陜西西咸北環(huán)線路線簡化圖

根據(jù)支撐樹定理可知，陜西西咸北環(huán)線路徑識別點數(shù)量應(yīng)布設(shè)[E1]-[V1]+1=11個。

通過KRUSKAL算法，將陜西西咸北環(huán)線路網(wǎng)結(jié)構(gòu)簡化圖所得的生成樹記為圖[G2=（V2，E2）]。識別點所需布設(shè)的位置斷面為圖G3=G1-G2，識別點布設(shè)位置見圖2。

圖2 規(guī)劃路線簡化圖最小生成樹

5 識別點布設(shè)優(yōu)化方式

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

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

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

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

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

6 識別點優(yōu)化實例分析

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

圖3 西藍(lán)商環(huán)路與最小支撐樹示意圖

將完全重復(fù)式和分布式冗余布局分別應(yīng)用于在該路網(wǎng)結(jié)構(gòu)中，其布設(shè)位置如圖4所示。

圖4 重復(fù)式布設(shè)與分布式布設(shè)示意圖

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

表1 識別車輛數(shù)比例 %

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

表2 冗余布設(shè)方式平均識別率 %

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

7 結(jié) 語

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

參考文獻(xiàn)

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

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

[3] 張健.高速公路聯(lián)網(wǎng)收費多路徑判斷技術(shù)方法研究[D].西安：長安大學(xué)，2008.

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

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

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

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

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