高速公路路段標識站點布置方法

陳瑤 馮興林 魏永俊 王浦安

摘 要：為對高速公路路段標識站點進行合理布置，依據支撐樹性質，計算出高速公路路段標識站點數量，同時依據高速公路路段交通量，引入高速公路路段權值，即路段車流量大的路段權值小，利用破圈法求得高速公路網連通圖G的最小支撐樹，得到高速公路路段標識站點合理的布置位置，即高速公路路段標識站位于求解最小支撐樹過程中刪去的邊，該布置方法能夠避免高速公路路段標識站的車輛識別裝置產生車輛識別錯誤和遺漏，同時提高車輛識別裝置的可靠性。

關鍵詞：高速公路 路段標識站點 最小支撐樹 識別可靠性

中圖分類號：U49 文獻標識碼：A 文章編號：1672-3791（2016）05（c）-0052-04

隨著全國各省高速公路聯網收費規模的不斷擴大，使高速公路聯網收費管理出現了兩個難題：路徑識別及通行費拆分的問題，而最根本的就是路徑識別問題[1]。

目前準確的高速公路路徑識別方法主要為車牌識別法和射頻卡識別法等標識站法，標識站法的核心是在高速公路路段上設置相應的標識站，車輛經過標識站時，通行卡記錄該標識站對應的信息，結合高速公路路徑和通行卡所記錄的信息，準確地識別出車輛的實際行駛路徑。叢浩哲等人展開了基于支撐樹法的高速公路多路徑識別問題研究，該文章僅僅實現了標識站位置的規劃，忽略了高速公路路段車流量對標識站法所用車輛識別裝置可靠性的影響。

該文以高速公路路段車流量為依據，引入相應的高速公路路段權值，利用破圈法求解最小支撐樹，對高速公路路段標識站點位置進行最優規劃，以減小高速公路路段車流量對標識站法所用車輛識別裝置可靠性的影響，避免高速公路路段標識站的車輛識別裝置產生車輛識別錯誤和遺漏，最后通過實例對該方法的可行性和實用性進行驗證。

1 基本理論

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

高速公路網的抽象圖G 的一個連通無回路圖稱為圖G 的一個支撐樹，由于支撐樹內無回路，故對于支撐樹結構，兩點之間的路徑是唯一的。最小支撐樹是指連通圖所有的支撐樹中所具有的權值最小的支撐樹，由于權值最小，所以最小支撐樹是所有支撐樹中較為合理的支撐樹。

2 識別站點的數量及位置

2.1 識別站點的數量

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

2.2 破圈法及識別站點的位置

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

破圈法具體步驟如下。

（1）從高速公路網抽象出的連通圖G中任找一個回路。

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

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

運用破圈法求解高速公路網連通圖G的最小支撐樹的過程中所去掉的權值較大的邊，即為高速公路路段標識站的規劃布置位置。

3 高速公路路段的權值

高速公路路段標識站的車輛識別裝置識別車輛的負荷隨著高速公路路段車流量的變化而相應地改變，即路段車流量大時，標識站車輛識別裝置的工作頻率高，當路段車流量大于標識站車輛識別裝置的極限工作頻率時，則會產生車輛識別錯誤和遺漏，致使標識站車輛識別裝置可靠性降低，因此，將高速公路路段標識站布置在高速公路車流量較少的路段較為合適，并符合實際情況。

依據高速公路路段車流量，對高速公路的路段賦予相應的權值，即車流量多的路段權值高，車流量少的路段權值小，將標識站車輛識別裝置布置在高速公路車流量較少的路段，也就是將標識站車輛識別裝置布置在路段權值高的路段，以減小高速公路路段車流量對標識站法所用車輛識別裝置可靠性的影響，避免高速公路路段標識站的車輛識別裝置產生車輛識別錯誤和遺漏，也為利用最小支撐樹獲取高速公路網內高速公路路段標識站的位置奠定基礎。

賦予高速公路路段權值的基本方法為計算高速公路路段的車流量在整個高速公路網內總的車流量中所占的比重，通過相應的計算公式，得到高速公路各路段相應的路段權值，即車流量小的路段所具有的路段權值高，具體步驟如下。

（1）統計出高速公路各路段相應的車流量ci。

在高速公路路網內各路段斷面ei設置車輛統計裝置，該裝置在車輛以一定速度通過路段斷面時，車輛統計裝置能夠識別出通過的車輛，其內置的計數器自動加一，最終獲得高速公路各路段相應的車流量，記為ci。

（2）統計出整個高速公路路網內總的車流量T。

該計算路段權值的方法能夠滿足高速公路各路段在路段車流量小時具有高的路段權值，路段車流量大時路段權值低。

4 實例驗證

以叢浩哲等基于支撐樹法的高速公路多路徑識別問題研究[1]中的實例為例，進一步說明依據高速公路路段車流量而賦予路段權值，通過破圈法求得高速公路網的連通圖G的最小支撐樹，將高速公路路段標識站位于求解最小支撐樹過程中刪去的邊所具有的合理性與實用性。

山東省高速公路網分布如圖1所示。對高速公路網分布圖進行等價簡化，從圖1[1]中選取18個頂點，25條邊，得到山東省高速公路網分布無向圖，如圖2[1]所示。

根據支撐樹的性質，山東省高速公路網分布無向圖轉化為一個支撐樹需要添加的高速公路路段標識站的數目為：

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

假設高速公路路網內各路段的車流量及各路段的權值如表1所示。

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

5 結論

依據支撐樹的性質，計算出高速公路路段標識站點的數量，同時依據高速公路路段交通量，引入路段權值，即高速公路路段車流量大的路段權值小，利用破圈法求得連通圖G 的最小支撐樹，得到高速公路路段標識站合理的布置位置，即位于求解最小支撐樹過程中刪去的邊，通過實例驗證，在求解最小支撐樹過程中刪去的邊上布置高速公路路段標識站，能夠避免高速公路路段標識站的車輛識別裝置產生車輛識別錯誤和遺漏，同時提高車輛識別裝置的可靠性。

參考文獻

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

[2] 林東，金濤，張桐.高速公路多路徑識別點布設與優化分析[J].現代電子技術，2015（24）：50-52，55.

[3] 卜月華，吳建專，顧國華，等.圖論及其應用[M].南京：東南大學出版社，2000.

[4] 王海英，黃強，李傳濤，等.圖論算法及其MATLAB實現[M].北京：北京航空航天大學出版社，2010.

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