一种面向智能车辆的多路径识别方法的初步思考①

设计的，并不一定能够满足新的复杂路网的路径辨识需求。原有设备选点是否有效、是否需要增加设备点位、增加于何处等问题都将成为工程设计实施中的难点。最后是多义性路径识别结果在通行费计费和拆分计算过程中的使用效率问题。无论采用何种多路径识别设备，车辆通行费的计费与拆分都是统一到收费系统的计算中心进行计算处理的。考虑到庞大复杂路网的通行车辆数量巨大、路径组合繁多、通行费拆分方式复杂等因素，这样的集中处理方式必然会导致计算效率的低下。

可见，复杂大规模路网的精准多路径识别问归结在以下三个方面：复杂路网的拆分与组合、多义性路径辨识与定位以及多义性路径路网的改造。

2  问题的简化

高速公路路网是典型的收费路网，其路线在物理空间上是连续的。但从收费系统的角度看，高速公路路网是以布设在高速路出入口、主线省界交汇点和互通枢纽等处的收费站为节点，以道路路段为线段的点线组合体。从收费系统的角度看，理想的路网状态是任何两个相鄰收费站之间仅存在一条确定的通道;在车辆驶离路网后，收费系统根据车辆途经的收费站判断车辆的行驶路径，并根据该路径进行通行费用的相关处理。但新建道路的出现可能会打破这种理想状态，使得某两个相邻收费站之间出现了多条通道，并导致收费系统无法准确判断车辆的行驶路径。这时我们称该路网具有多义性路径。

多义性路径会带来两个方面的现实问题。首先，不同的车辆行驶路径可能会因为里程或里程单价的不同而产生不同的通行费费额。多义性路径的存在使得收费系统无法准确计算通行费费额。其次，当多义性路径中的路段属于不同的省份、地区或运营单位（业主）时，收费系统无法判别通行费的归属，进而无法进行通行费拆分[5]。

图1展示了一组典型的多义性路径。当通行车辆进入收费路网的入口后，可以选择通过线路A、B和C到达出口，从而使得收费系统无法判断车辆的实际行驶路径。假设线路A和B属于同一运营管理机构，而线路A的里程较线路B长，通行费比线路B也高一些;线路C与线路A的里程相同，但路线C与路线A、B分属不同的业主。这种情况下，收费系统无法确定通行费用是按照线路A和C的里程来计算收取，还是按照线路B来计算收取;同时收费系统也不知道收上来的通行费应该划拨到哪一个业主的资金账户中。

工程上一般会在多义性路径的路段上布设两类多路径识别设备。一类是能够识别车辆身份的监测设备，另一类是能够在车载电子标签中顺序标记路段标识码的射频写入设备[6]。如图1所示，分别在路径A、B和C的适当位置布设车辆身份监测设备，并将监测结果及时的告知收费系统，则收费系统可以在任意一辆车驶离路网后精确的判断出它的行驶路径。

从交通工程的角度上看，多路径识别问题就是通过某些技术手段使收费系统获取足够多的车辆行驶路径上的途经点信息，从而反推计算出车辆确切的行驶路径。但如果将收费系统和道路网络视为一个信息系统和物理系统叠加而成的有机整体，从收费系统的角度看，多路径识别问题的本质是通过技术手段将收费路网原有拓扑结构进行改变，使得收费系统获得一个不存在多义性路径的路网拓扑结构。

3  道路网络与图的映射

图论是组合数学的—个分支学科，与其他的数学分支，如群论、矩阵论、概率论、拓扑学、数值分析等有着密切的联系[7]。图论理论最早出现于十七世纪，并用于研究哥尼斯堡城的七桥问题，并由数学家欧拉发表了有关图论的最早论著。图论利用图的概念来对客观世界中的具体实物间的联系进行抽象的数学表述，并对其特性和规律加以研究。由于图的基本结构是由“顶点”和“边”构成，这些构成图的要素与路网中的“起点”、“终点”和“路段”等要素具有极好的吻合性。因此，利用图论理论对路网进行建模、将路网的拓扑结构以图的形式进行表征和研究是一个值得探索的方法[8]。在解决多义性路径的问题上，已经有结合图论理论进行研究案例。

将道路网络映射为图，首先要将路网及其相关设施、设备进行完整、统一的抽象提取。根据公路收费计算的基本原则（按里程计费、按分属机构拆分），多路径识别本质上是信息空间和物理空间融合问题的一个特例。从图1中可以直观的看到，在入口、出口和车辆检测设备所在点位都会发生一些信息交互;而道路的其他点位则仅仅是为车辆通行提供条件。因此，我们将一些可以产生信息交互的点作为图的顶点，其他的普通路段作为图的边，这样形成的图抽象的表征了信息空间和物理空间。为了抽象表述的需要，我们将车辆与道路设施进行通信的位置称为通信节点，简称节点。从工程实现的角度看，节点是由一些具备通信功能的实体设备实现的。这些实体设备由于技术、结构等方面的不同，其特性也有所不同。

4  约束条件与映射方法

为了能够使用图提供的数学工具为多义性路径精准识别问题提供普适性解决方法，需要根据实际情况为收费路网设定约束：（1）车辆在经过收费路网的通信节点时以不同规律发生车路通信事件。（2）无论车路通信事件的信息传递方向是车辆到道路还是道路到车辆，在车辆离开收费路网的最后一个节点时，车辆所经过的路径上的全部节点所发生的通信事件信息将汇总至收费管理中心。（3）路網中的道路均为双向道路。

在约束条件下，图可以采用以下两条基本方法构建：（1）收费路网中的出口、入口、互通收费站以及主线收费站等视为节点，映射为图中的顶点;（2）节点间可连续通行的道路（主线）映射为图的边。一个典型的收费路网结构如图2所示，根据上述构建方法形成的图G，如图3所示。

5  基于图的精准多路径识别

在复杂且规模庞大的路网中不仅存在着大量的出入口、互通枢纽，还包括了种类繁多的检测、通信设备，并且随着交通建设的推进，这种情况还会变得更加明显。利用对图的各种特性分析，以及图中链、迹和路等概念的应用，可以获得普适性的分析和计算方法。本文提出以下设想和思路。

思路1：利用复杂图精准计算任意一辆通行车辆的收费标准和通行费拆分比例将是一个计算量庞大的任务。因此我们可以利用图运算理论，通过割边和割点对复杂连通图进行拆分。拆分后的路网由多个简单子路网组成，便于问题的分析与解决。

思路2：通过对路网中二义性路径所对应的链、迹和路等组成部分进行改造，通过增加节点的方式，去除带有二义性的路径组成部分;增加的节点可以反映设到实际道路工程中，并以节点通信设备的方式体现出来。

思路3：收费道路路网所映射的图可以规范的以矩阵形式表述，矩阵的各种特性代表了路网的各种特性的同时，在拆分组合和加权运算等方面还具有便于计算机语言实现的特点，为道路网络建设的工程实现奠定了很好的基础。

参考文献

[1] 王勤.复杂高速路路网联网收费清分方法研究[D].武汉理工大学，2010.

[2] 王义祥.电子不停车收费系统在我国的发展[J].物流科技，2006（2）：72-75.

[3] 薄秀丽.高速收费站高清视频车牌识别系统的研究[J].山西交通科技，2016（5）：99-100.

[4] 郑远，李江，施丽娟，等.车牌识别技术在多义性路径问题中的应用[J].交通信息与安全，2007（6）：121-127.

[5] 宋祖科，赵修建.高速公路车辆通行费精确收取及拆分技术研究[J].公路工程，2009（1）：147-150.

[6] 孙凯.高速公路多路径识别技术研究及实现[D].郑州大学，2013.

[7] 卜月华.图论及其应用[M].福建：东南大学出版社，2002.

[8] 陈雨人，陈少军.包含立交匝道信息的高速公路网络复杂拓扑结构[J].同济大学学报：自然科学版，2010，38（2）：230-237.