陳瑤 馮興林 魏永俊 王浦安

摘 要：為對(duì)高速公路路段標(biāo)識(shí)站點(diǎn)進(jìn)行合理布置，依據(jù)支撐樹(shù)性質(zhì)，計(jì)算出高速公路路段標(biāo)識(shí)站點(diǎn)數(shù)量，同時(shí)依據(jù)高速公路路段交通量，引入高速公路路段權(quán)值，即路段車流量大的路段權(quán)值小，利用破圈法求得高速公路網(wǎng)連通圖G的最小支撐樹(shù)，得到高速公路路段標(biāo)識(shí)站點(diǎn)合理的布置位置，即高速公路路段標(biāo)識(shí)站位于求解最小支撐樹(shù)過(guò)程中刪去的邊，該布置方法能夠避免高速公路路段標(biāo)識(shí)站的車輛識(shí)別裝置產(chǎn)生車輛識(shí)別錯(cuò)誤和遺漏，同時(shí)提高車輛識(shí)別裝置的可靠性。

關(guān)鍵詞：高速公路 路段標(biāo)識(shí)站點(diǎn) 最小支撐樹(shù) 識(shí)別可靠性

中圖分類號(hào)：U49 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-3791（2016）05（c）-0052-04

隨著全國(guó)各省高速公路聯(lián)網(wǎng)收費(fèi)規(guī)模的不斷擴(kuò)大，使高速公路聯(lián)網(wǎng)收費(fèi)管理出現(xiàn)了兩個(gè)難題：路徑識(shí)別及通行費(fèi)拆分的問(wèn)題，而最根本的就是路徑識(shí)別問(wèn)題[1]。

目前準(zhǔn)確的高速公路路徑識(shí)別方法主要為車牌識(shí)別法和射頻卡識(shí)別法等標(biāo)識(shí)站法，標(biāo)識(shí)站法的核心是在高速公路路段上設(shè)置相應(yīng)的標(biāo)識(shí)站，車輛經(jīng)過(guò)標(biāo)識(shí)站時(shí)，通行卡記錄該標(biāo)識(shí)站對(duì)應(yīng)的信息，結(jié)合高速公路路徑和通行卡所記錄的信息，準(zhǔn)確地識(shí)別出車輛的實(shí)際行駛路徑。叢浩哲等人展開(kāi)了基于支撐樹(shù)法的高速公路多路徑識(shí)別問(wèn)題研究，該文章僅僅實(shí)現(xiàn)了標(biāo)識(shí)站位置的規(guī)劃，忽略了高速公路路段車流量對(duì)標(biāo)識(shí)站法所用車輛識(shí)別裝置可靠性的影響。

該文以高速公路路段車流量為依據(jù)，引入相應(yīng)的高速公路路段權(quán)值，利用破圈法求解最小支撐樹(shù)，對(duì)高速公路路段標(biāo)識(shí)站點(diǎn)位置進(jìn)行最優(yōu)規(guī)劃，以減小高速公路路段車流量對(duì)標(biāo)識(shí)站法所用車輛識(shí)別裝置可靠性的影響，避免高速公路路段標(biāo)識(shí)站的車輛識(shí)別裝置產(chǎn)生車輛識(shí)別錯(cuò)誤和遺漏，最后通過(guò)實(shí)例對(duì)該方法的可行性和實(shí)用性進(jìn)行驗(yàn)證。

1 基本理論

高速公路網(wǎng)實(shí)際可理解為由各路段組成的無(wú)向連通圖，即高速公路網(wǎng)可用圖G=（V，E，W ）表示，V （G ）={v1，v2，…，vm}為節(jié)點(diǎn)的簡(jiǎn)化集合，由高速公路網(wǎng)中的互通立交和收費(fèi)站組成，E （G ）={e1，e2，…，en}為高速公路的路段簡(jiǎn)化集合，由收費(fèi)站之間和收費(fèi)站與互通立交之間的路段組成，W （G ）={w1，w2，…wp}為高速公路的路段權(quán)值簡(jiǎn)化集合，ei的權(quán)值記為w i，該文所提到的圖，如未加特殊說(shuō)明，都是連通圖[2]。

高速公路網(wǎng)的抽象圖G 的一個(gè)連通無(wú)回路圖稱為圖G 的一個(gè)支撐樹(shù)，由于支撐樹(shù)內(nèi)無(wú)回路，故對(duì)于支撐樹(shù)結(jié)構(gòu)，兩點(diǎn)之間的路徑是唯一的。最小支撐樹(shù)是指連通圖所有的支撐樹(shù)中所具有的權(quán)值最小的支撐樹(shù)，由于權(quán)值最小，所以最小支撐樹(shù)是所有支撐樹(shù)中較為合理的支撐樹(shù)。

2 識(shí)別站點(diǎn)的數(shù)量及位置

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

支撐樹(shù)的性質(zhì)決定了支撐樹(shù)中兩點(diǎn)之間的路徑唯一確定，給定一個(gè)圖G =（V，E ），在該圖中刪除m=E （G ）-V （G ）+l 條邊后，剩余的圖是圖G 的一個(gè)支撐樹(shù)，即多一條邊是浪費(fèi)，少一條邊不能得到圖G 的支撐樹(shù)。

2.2 破圈法及識(shí)別站點(diǎn)的位置

最小支撐樹(shù)所具有的權(quán)值最小，使得高速公路路段標(biāo)識(shí)站的布置更為合理，在求最小支撐樹(shù)的時(shí)候，為了保證求得的支撐樹(shù)的權(quán)值W（T）最小，那么在刪去回路上的邊的時(shí)候，總是刪去路段權(quán)值較大的邊，盡量保留路段權(quán)值較小的邊，這就是所謂的破圈法[5]。

破圈法具體步驟如下。

（1）從高速公路網(wǎng)抽象出的連通圖G中任找一個(gè)回路。

（2）在所找的回路中去掉一條路段權(quán)值最大的邊，如果存在兩條或兩條以上路段權(quán)值最大的邊，則任意去掉其中一條。

（3）如果余下的連通圖已不存在任何回路，則該余下的連通圖即為所求的最小支撐樹(shù)，否則在該余下的連通圖中繼續(xù)任找一個(gè)回路，并返回（2）。

運(yùn)用破圈法求解高速公路網(wǎng)連通圖G的最小支撐樹(shù)的過(guò)程中所去掉的權(quán)值較大的邊，即為高速公路路段標(biāo)識(shí)站的規(guī)劃布置位置。

3 高速公路路段的權(quán)值

高速公路路段標(biāo)識(shí)站的車輛識(shí)別裝置識(shí)別車輛的負(fù)荷隨著高速公路路段車流量的變化而相應(yīng)地改變，即路段車流量大時(shí)，標(biāo)識(shí)站車輛識(shí)別裝置的工作頻率高，當(dāng)路段車流量大于標(biāo)識(shí)站車輛識(shí)別裝置的極限工作頻率時(shí)，則會(huì)產(chǎn)生車輛識(shí)別錯(cuò)誤和遺漏，致使標(biāo)識(shí)站車輛識(shí)別裝置可靠性降低，因此，將高速公路路段標(biāo)識(shí)站布置在高速公路車流量較少的路段較為合適，并符合實(shí)際情況。

依據(jù)高速公路路段車流量，對(duì)高速公路的路段賦予相應(yīng)的權(quán)值，即車流量多的路段權(quán)值高，車流量少的路段權(quán)值小，將標(biāo)識(shí)站車輛識(shí)別裝置布置在高速公路車流量較少的路段，也就是將標(biāo)識(shí)站車輛識(shí)別裝置布置在路段權(quán)值高的路段，以減小高速公路路段車流量對(duì)標(biāo)識(shí)站法所用車輛識(shí)別裝置可靠性的影響，避免高速公路路段標(biāo)識(shí)站的車輛識(shí)別裝置產(chǎn)生車輛識(shí)別錯(cuò)誤和遺漏，也為利用最小支撐樹(shù)獲取高速公路網(wǎng)內(nèi)高速公路路段標(biāo)識(shí)站的位置奠定基礎(chǔ)。

賦予高速公路路段權(quán)值的基本方法為計(jì)算高速公路路段的車流量在整個(gè)高速公路網(wǎng)內(nèi)總的車流量中所占的比重，通過(guò)相應(yīng)的計(jì)算公式，得到高速公路各路段相應(yīng)的路段權(quán)值，即車流量小的路段所具有的路段權(quán)值高，具體步驟如下。

（1）統(tǒng)計(jì)出高速公路各路段相應(yīng)的車流量ci。

在高速公路路網(wǎng)內(nèi)各路段斷面ei設(shè)置車輛統(tǒng)計(jì)裝置，該裝置在車輛以一定速度通過(guò)路段斷面時(shí)，車輛統(tǒng)計(jì)裝置能夠識(shí)別出通過(guò)的車輛，其內(nèi)置的計(jì)數(shù)器自動(dòng)加一，最終獲得高速公路各路段相應(yīng)的車流量，記為ci。

（2）統(tǒng)計(jì)出整個(gè)高速公路路網(wǎng)內(nèi)總的車流量T。

該計(jì)算路段權(quán)值的方法能夠滿足高速公路各路段在路段車流量小時(shí)具有高的路段權(quán)值，路段車流量大時(shí)路段權(quán)值低。

4 實(shí)例驗(yàn)證

以叢浩哲等基于支撐樹(shù)法的高速公路多路徑識(shí)別問(wèn)題研究[1]中的實(shí)例為例，進(jìn)一步說(shuō)明依據(jù)高速公路路段車流量而賦予路段權(quán)值，通過(guò)破圈法求得高速公路網(wǎng)的連通圖G的最小支撐樹(shù)，將高速公路路段標(biāo)識(shí)站位于求解最小支撐樹(shù)過(guò)程中刪去的邊所具有的合理性與實(shí)用性。

山東省高速公路網(wǎng)分布如圖1所示。對(duì)高速公路網(wǎng)分布圖進(jìn)行等價(jià)簡(jiǎn)化，從圖1[1]中選取18個(gè)頂點(diǎn)，25條邊，得到山東省高速公路網(wǎng)分布無(wú)向圖，如圖2[1]所示。

根據(jù)支撐樹(shù)的性質(zhì)，山東省高速公路網(wǎng)分布無(wú)向圖轉(zhuǎn)化為一個(gè)支撐樹(shù)需要添加的高速公路路段標(biāo)識(shí)站的數(shù)目為：

m=E（G）-V（G）+l=25-18+l=8

假設(shè)高速公路路網(wǎng)內(nèi)各路段的車流量及各路段的權(quán)值如表1所示。

在圖2中的高速公路網(wǎng)抽象出的連通圖G 中找到一個(gè)回路（e1，e19，e20）為起始回路，運(yùn)用破圈法，計(jì)算得出需要布置高速公路路段標(biāo)識(shí)站的邊為：e1，e24，e11，e9，e15，e2，e25，e16共計(jì)8條邊，在這8條邊上布置高速公路路段標(biāo)識(shí)站并去掉相應(yīng)的邊后，如圖3所示，所得的最小支撐樹(shù)的權(quán)值為W （T ）=398，而叢浩哲等人展開(kāi)了基于支撐樹(shù)法的高速公路多路徑識(shí)別問(wèn)題研究[1]中給出的邊為：e4，e6，e7，e13，e14，e20，e21，e22共計(jì)8條邊，所得的支撐樹(shù)的權(quán)值W （T ）=625，明顯差于由最小支撐樹(shù)獲得的高速公路路段標(biāo)識(shí)站的布置。

5 結(jié)論

依據(jù)支撐樹(shù)的性質(zhì)，計(jì)算出高速公路路段標(biāo)識(shí)站點(diǎn)的數(shù)量，同時(shí)依據(jù)高速公路路段交通量，引入路段權(quán)值，即高速公路路段車流量大的路段權(quán)值小，利用破圈法求得連通圖G 的最小支撐樹(shù)，得到高速公路路段標(biāo)識(shí)站合理的布置位置，即位于求解最小支撐樹(shù)過(guò)程中刪去的邊，通過(guò)實(shí)例驗(yàn)證，在求解最小支撐樹(shù)過(guò)程中刪去的邊上布置高速公路路段標(biāo)識(shí)站，能夠避免高速公路路段標(biāo)識(shí)站的車輛識(shí)別裝置產(chǎn)生車輛識(shí)別錯(cuò)誤和遺漏，同時(shí)提高車輛識(shí)別裝置的可靠性。

參考文獻(xiàn)

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

[2] 林東，金濤，張桐.高速公路多路徑識(shí)別點(diǎn)布設(shè)與優(yōu)化分析[J].現(xiàn)代電子技術(shù)，2015（24）：50-52，55.

[3] 卜月華，吳建專，顧國(guó)華，等.圖論及其應(yīng)用[M].南京：東南大學(xué)出版社，2000.

[4] 王海英，黃強(qiáng)，李傳濤，等.圖論算法及其MATLAB實(shí)現(xiàn)[M].北京：北京航空航天大學(xué)出版社，2010.

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