高速公路多路徑識(shí)別點(diǎn)布設(shè)與優(yōu)化分析

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

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

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

1 理論基礎(chǔ)

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

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

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

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

定理1 一個(gè)圖有支撐樹(shù)的充分必要條件是該圖是一個(gè)連通圖。

定理2 一個(gè)圖是樹(shù)的充分必要條件是任意兩頂點(diǎn)之間有且僅有一條邊。

2 識(shí)別點(diǎn)的數(shù)量

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

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

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

3 識(shí)別點(diǎn)的位置分析

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

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

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

KRUSKAL算法的基本思路如下：

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

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

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

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

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

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

4 識(shí)別點(diǎn)布設(shè)實(shí)例

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

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

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

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

圖2 規(guī)劃路線簡(jiǎn)化圖最小生成樹(shù)

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

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

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

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

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

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

6 識(shí)別點(diǎn)優(yōu)化實(shí)例分析

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

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

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

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

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

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

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

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

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

7 結(jié) 語(yǔ)

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

參考文獻(xiàn)

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

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

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

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

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

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

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

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