高速公路路段标识站点布置方法

陈瑶 冯兴林 魏永俊 王浦安

摘 要：为对高速公路路段标识站点进行合理布置，依据支撑树性质，计算出高速公路路段标识站点数量，同时依据高速公路路段交通量，引入高速公路路段权值，即路段车流量大的路段权值小，利用破圈法求得高速公路网连通图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.