GPS定位信息和电子地图收费路段匹配的方法

摘要

本发明公开了一种GPS定位信息和电子地图收费路段匹配的方法，其方法如下：初始化确定搜索范围；接收GPS定位信息；根据当前车辆的行驶速度确定搜索范围；以当前接收到的GPS位置点为中心，搜索范围为半径，在收费地图上搜索路段数据，判断收费点和收费路段；搜索地图数据；当车辆当前未在收费路段上时，判断该收费节点属于哪一个收费路段，接着再判断是否该收费路段类型为入口，根据判断结果开始计费过程或返回上一步骤；当路段收费标志值在收费路段时，继续判断在搜索范围内是否存在收费节点，判断该收费节点和上一个收费节点是否存在邻接关系，根据判断结果进行计费或收费结束。本发明能够大大的节省了存储空间和提高了计算效率。

说明书

技术领域

本发明涉及一种GPS定位信息和电子地图收费路段匹配的方法。

背景技术

收费用电子地图在整个GPS卫星收费体系中起到核心的作用，针对不同导航应用往往会采用不同规格的电子地图。通常电子地图由记录实际地物的地理数据和与实际地物相关的标识、属性信息以及各类附加信息组成。电子地图主要由道路形状数据、背景数据、拓扑数据和属性数据构成，它们之间紧密衔接，共同为车辆导航应用提供服务。由于目前收费是针对道路来说，所以涉及道路的形状数据、拓扑数据和属性数据是必不可少的要素。此外电子地图数据必须在保证地图精度和收费信息量不丢失的情况下尽可能的精炼，同时其数据结构也必须更加符合嵌入式设备显示、运算和分析的要求。高速公路上行下行车道间距离很小，通常只有5米左右。就目前通常GPS定位的精度仅仅在20米范围，单纯依靠GPS定位很难区分上下行两个距离很近的点，对两条道路匹配混乱，对收费路径的判断错误。上述问题解决方法：1、提高电子地图精度：制作高精度的专门用于GPS定位收费的电子地图；2、提高GPS定位精度：理论上这是提高匹配准确性的最好办法，但是GPS定位精度受车载设备成本限制，在车载设备中不太可能采用高精度的GPS模块。

发明内容

本发明所述的GPS定位信息和电子地图收费路段匹配的方法，其硬件包括GPS定位接收装置和计算机处理器，步骤如下：

步骤1，初始化；

当前路段收费标志值为没有在收费路段，通性费用为0元，搜索范围为15米；

步骤2，接收GPS定位信息，包括当前坐标值，当前行驶速度，GPS接收频率为1次/秒；

步骤3，根据当前车辆的行驶速度确定搜索范围：

当速度小于36公里/小时，搜索范围为初始值15米；

当速度大于或等于36公里/小时，搜索范围为：速度×1000/3600+搜索范围初始值；

步骤4，以当前接收到的GPS位置点为中心，搜索范围为半径，在收费地图上搜索路段数据，判断收费点和收费路段；搜索地图数据，如果有道路节点在GPS位置点的搜索范围内，判断该节点是否是收费路段上的节点：

如果收费地图上的节点在GPS位置点的搜索范围内，则：继续判断是否是收费路段上的节点，如果是，则：进入步骤5；

步骤5，如果是收费节点，这里分两个情况处理：车辆当前未在收费路段上；车辆已经行驶在收费路段上。

1)当车辆当前未在收费路段上时，判断该收费节点属于哪一个收费路段，接着再判断是否该收费路段的路段类型是入口路段0，如果是，进入收费道路开始计费过程；否则返回上一步骤，继续判断；

具体步骤如下：

如果该收费节点属于一个收费路段

如果路段的收费类型为0

置道路收费标志值为1；记录入口路段ID，

开始计费，通行费＝路段费用值×费率；

返回步骤2；

否则

返回步骤2；

2)当路段收费标志值在收费路段时，车辆已经进入收费路段，继续判断在搜索范围内是否存在收费节点，判断该收费节点和上一个收费节点是否存在邻接关系，如果存在，车辆当前行驶在这个收费路段上，进行计费，最后判断该收费路段类型是出口1，之后设置路段收费标志值为0，说明车辆离开收费路段，收费结束，返回步骤2；否则返回步骤2；

具体步骤如下：

如果该收费节点和上一个收费节点属于同一收费路段

如果该收费路段类型为1

置路段收费标志值为0；记录路段出口ID号；

计费通行费＝上次计算出的费用+路段费用值×费率；

收费结束，返回步骤2；

否则

计费通行费＝上次计算出的费用+路段费用值×费率；

返回步骤2；

否则

返回步骤2；

程序结束；

上述流程中费用计算是按里程收费的计算方法，对于按路段出入口收费的情况下，只需在收费路段出口处，将记录的入口ID和出口ID，在费率表中匹配，即可得到入口到出口整条路段的通行费用。

如上所述的GPS定位信息和电子地图收费路段匹配的方法，所述电子地图通过精简地图数据进行压缩，去除不必要的形状连接点，保留路段的拓扑结构，对地图匹配来说，路段中包括组成路网拓扑关系和路段走向的关键点-节点即交点，去除对路段的拓扑关系路段走向没有影响的形状点，利用ARCGIS平台编辑地图修改去除形状点。

如上所述的一种GPS定位信息和电子地图收费路段匹配的方法，所述电子地图属性定义根据存放位置的不同分两部分：一部分存储在车载单元，这部分存放精简的属性信息；另一部分存储在管理中心数据库中，这部分涉及GPS定位收费所需的详细的地图信息，包括路段编号，路段名称，长度，路段类型，限速，左节点节点编号，右节点节点编号，收费类型，高速路名称，高速公路公司代码；费率计算分两种情况，瘦客户端和胖客户端，两种形式下属性信息的配置也不一样，瘦客户端是将费率计算放在后台完成，而胖客户端将费率计算放在前端完成；瘦客户端收费地图数据：包括路段编号，路段左节点坐标，路段右节点坐标，路段类型；胖客户端收费地图数据的定义要考虑增加收费类型表和费率表，根据收费类型，查询费率表内相关费率，基本表包括：路段编号，路段名称，路段长度，路段左节点坐标，路段右节点坐标，路段类型即出入口信息，收费类型。

本发明能够大大的节省了存储空间和提高了计算效率；以在京津塘高速公路和交通部公路实验场进行的实验测试为例，京津塘高速公路电子地图实际路段有450多个，数据量有大概2M。经过地图精简后仅剩余80多个路段，5K数据。在京津塘高速公路有300台正常的运输车辆参与了卫星收费实验过程，地图匹配准确，收费准确，效果良好。在交通部公路实验场进行了功能测试，在各种情况下，对匹配算法准确性和可靠性进行了测试，主要的测试条件为车辆在道路上以40公里--180公里/小时的速度范围，单车连续长时间测试，匹配准确率达到了99％。

附图说明

图1是本发明的收费地图匹配方法的程序框图。

图2是精简前的路段节点图。

图3是精简后的路段节点图。

图4是GPS位置点和电子地图对应路段的对比情况图。

图5是高速公路上行下行车道的路段结构图。

图6是高速公路的路段邻接关系的节点表达图。

具体实施方式

本发明的收费电子地图的精简方案：

收费用电子地图在整个GPS卫星收费体系中起到核心的作用，针对不同导航应用往往会采用不同规格的电子地图。通常电子地图由记录实际地物的地理数据和与实际地物相关的标识、属性信息以及各类附加信息组成。电子地图主要由道路形状数据、背景数据、拓扑数据和属性数据构成，它们之间紧密衔接，共同为车辆导航应用提供服务。由于目前收费是针对道路来说，所以涉及道路的形状数据、拓扑数据和属性数据是必不可少的要素。此外电子地图数据必须在保证地图精度和收费信息量不丢失的情况下尽可能的精炼，同时其数据结构也必须更加符合嵌入式设备显示、运算和分析的要求。

1.1电子地图的形状信息精简

电子地图可通过精简地图数据进行压缩，去除不必要的形状连接点，保留路段的拓扑结构，可以大大缩减电子地图的数据量，节省数据存储空间和减小程序计算量。

对地图匹配来说，图2中路段1234中1，4点是节点(交点)，是路网拓扑关系和路段走向的关键点，不可缺少。而2，3对路段的拓扑关系路段走向没有影响，反而会增大存储空间，增加计算量，这样的形状点过多还会影响GPS数据的准确性，引起处理算法判断上出现问题。所以应该去除2，3点。精简后的地图数据如图3所示。

由于通常电子地图数据中存在大量的类似2，3连接点，去除这些点可以大大缩减电子地图的数据量，大大节省数据存储空间和减小程序计算量。这些地图修改工作可以在ARC GIS平台编辑完成。

1.2电子地图的属性信息精简

地图属性信息的精简就是首先确定收费地图所必需的信息，去除不必要的其它信息，从而将电子地图路段属性进行精简。电子地图属性定义根据存放位置的不同，分两部分：一部分存储在车载单元，这部分要求尽可能精简的属性信息。另一部分存储在管理中心数据库中，这部分涉及GPS定位收费所需的尽可能详细的地图信息，包括路段编号，路段名称，长度，路段类型，限速，左节点节点编号，右节点节点编号，收费类型，高速路名称，高速公路公司代码。除以上属性信息外其他的所有属性信息均可去除，从而节省前后台的空间。

考虑到车载系统受成本限制硬件资源如RAM容量等非常有限，因此需要尽量缩小存储地图的数据量。即车载端只存储必要的用于收费的基础信息，大量的时效性数据的查询和计算量较大的操作都放到服后台服务器上进行。所以需要对电子地图数据进行裁减，仅保留收费路段的必要信息。

费率计算分两种情况，瘦客户端和胖客户端。两种形式下，属性信息的配置也不一样，瘦客户端是将费率计算放在后台完成，而胖客户端将费率计算放在前端完成，从而减轻后台的计算压力。

瘦客户端收费地图数据：包括路段编号，路段左节点坐标，路段右节点坐标，路段类型。

胖客户端收费地图数据的定义要考虑增加收费类型表和费率表，根据收费类型，查询费率表内相关费率，基本表包括：路段编号，路段名称，路段长度，路段左节点坐标，路段右节点坐标，路段类型(出入口信息)，收费类型。

结合我国实际情况，高速公路分属不同的高速公路公司，收费的费率也存在差异，这样定义的优点在于，按公里计费，费率可以随时段(高峰时段与正常时段)变化，也可随地段变化(拥堵路段)。可以较好的解决拥堵问题。

2.地图匹配方法

使用GPS定位信息和电子地图收费路段进行匹配计算。

2.1基于算法的高速公路收费地图匹配技术

路段匹配就是对GPS采集的位置点与收费地图收费路段进行分析匹配，来判断当前车辆是否行驶在收费路段，以决策是否对车辆进行收费。程序从通过RS-232串口接收到GPS数据定位信息(NEMA0183语句)后，作译码处理(格式转换)，提取位置、速度、方向、时间及其他环境数据信息。对接收的GPS信息采用GPRMC指令，包括位置信息，经纬度，时间，速度，可信度，方向等信息，(其中经度、纬度是车辆的地图位置信息，表示为平面直角系的x，y坐标，在路段匹配中是至关重要的参数)对路段进行精确匹配，这样就可以清晰区分收费路段和非收费路段，达到较准确的收费效果。

图4是真实情况下GPS位置点和电子地图对应路段的对比情况，当前车辆行驶在红色的路段上，从地理位置投影可知GPS连续定位的位置点应该和电子地图上的红线重合，可是实际上由于电子地图精度或GPS定位精度的不准确，造成GPS位置点和实际所在的道路相差很远。这样就不能实现GPS定位点和收费路段的正确匹配，使收费不正确。

高速公路上下行路段情况，这类布局情况在实际高速公路中非常普遍。

图5高速公路上行下行车道间距离很小，通常只有5米左右，就目前通常GPS定位的精度仅仅在20米范围，单纯依靠GPS定位很难区分上下行两个距离很近的点，对两条道路匹配混乱，对收费路径的判断错误。

解决方法：

a.提高电子地图精度：制作高精度的专门用于GPS定位收费的电子地图。

b.提高GPS定位精度：理论上这是提高匹配准确性的最好办法，但是GPS定位精度受车载设备成本限制，在车载设备中不太可能采用高精度的GPS模块。

b.匹配算法的优化：目前GPS和电子地图的精度很难满足卫星定位收费的要求。单纯提高这两种精度都不太现实。只能通过对路段进行一些处理、路段间邻接关系得匹配算法来弥补定位精度的不足。考虑前后节点相邻关系，避免对面无相邻关系车道节点干扰。

2.2匹配中节点判断范围的选取

以GPS定位点G(x，y)为中心点，一个值为半径的区域内，在收费电子地图上搜索是否有收费路段存在即收费路段在此范围内，如果有收费路段存在，进行判断。搜索范围的选取非常重要，范围过大，容易造成误判，且加重计算量，如近距离平行的主辅路，使辅路行驶的车辆误收费。

如果搜索范围过小，收费路段点丢失。GPS数据接收频率1次/秒，如果车速过快，搜索范围会跳过路段上的一些节点，造成漏点。影响匹配准确性。搜索范围的选取应考虑以下两个原则

a.和GPS定位精度及地图精度有关，搜寻范围应大于GPS定位精度和地图精度的最大值。这样才能保证所有节点都不会遗漏。

b.实际操作可根据车速在一定范围内自动调节。车辆在高速公路行驶的特点，快速120公里/小时，34米/秒，而GPS定位数据一秒频率接收。所以为不遗漏对任何路段的节点进行判断，在这种情况下，算法判断节点范围至少50米。高速公路双方向路段的横向距离通常大大小于50米。由此可见车速和判断范围的选取对地图匹配的准确性影响很大。随车速增加，判断范围增大，车速减小，判断范围减小。这样既保证在速度慢时匹配的精确，又使速度快时不遗漏节点。

下面是搜索范围算法的详细描述：

符号意义：

search_scope：表示GPS位置点，初始搜索范围值

Bound：表示实际变化的搜索范围

V：表示当前行驶车速

算法：

步骤1：初始化；

令初始搜索范围值：search_scope＝15米，此值由GPS精度决定。

步骤2：由速度确定搜索范围；

当V＜36公里/小时，bound＝search_scope；

当V＞≥36公里/小时，bound＝V*1000/3600+search_scope；

近距离平行收费路段和非收费路段的判别。

c.漏点的处理：如果同一节点单独处理前后两段，或智能化整体考虑路径，根据整体路径的邻接关系判断是否漏点，加以修正。

2.3点与收费路段的匹配

本算法的核心是通过修改收费路段属性，结合收费路段之间的邻接关系，加以合理的算法处理，从而提高地图匹配的准确性，以弥补GPS定位精度的不足。

假设条件：收费路段入口和出口点为单点(非交叉点)，目前高速公路收费点设置基本符合这一设定。另外我们也可以通过对收费路段出入口的设置来满足我们的要求。

收费路段入口：0；收费路段出口：1；

路段邻接关系的表达：如图6所示：节点1-＞节点2-＞节点3-＞节点4，其中：节点1和节点2组成路段(1)，存在邻接关系，路段(1)的左节点为节点1，右节点为2。

设定标志值fee_status区分当前车辆是否在收费路段上：fee_status＝0：不在收费道路上；标志值fee_status＝1：在收费道路上。

下面是匹配算法的详细描述：

算法：

步骤1：初始化；

fee_status＝0，i＝0，j＝0，F(all)＝0，search_scope＝15米；

步骤2：接收GPS定位信息，坐标值Gi(x，y)，速度V，接收频率为1次/秒；

步骤3：根据当前车辆的行驶速度V确定搜索范围bound：

当V＜36公里/小时，bound＝search_scope；

当V＞≥36公里/小时，bound＝V*1000/3600+search_scope；

步骤4：以GPS位置点Gi(x，y)为中心，搜索范围bound为半径，在收费地图上搜索路段数据，判断收费点和收费路段；如果有节点Node(i)在点G(x，y)搜索范围bound内，首先，判断Node_i(x，y)是否是收费路段上的节点Node_fee_i(x，y)，再判断是否是收费路段上的节点：

如果Node_i(x，y)∈G(x，y)+bound

如果Node_i(x，y)＝Node_fee_i(x，y)

进入步骤5；

步骤5：如果是收费节点Node_fee_i(x，y)，这里分两个情况处理，车辆当前未在收费路段上；fee status＝0和车辆已经行驶在收费路段上fee status＝1的情况。

1)当fee status＝0时，判断该点Node_fee_i(x，y)属于哪一个收费路段，接着再判断是否该收费路段的路段类型是入口路段0，如果是，进入收费道路开始计费过程。否则返回前面，继续判断。

如果Node_fee_i(x，y)∈Segment_i(u，v)

如果Segment_i(type)＝0

置fee status＝1；记录入口路段ID，

计费Fee(all)＝Fee(all)+Segment_i(L)×Fee(i)；

返回步骤2；

否则

返回步骤2；

2)当fee status为1时，进入收费路段后

接着判断是否通过节点号，判断该节点Node_Fee(j)和上个收费节点Node_Fee(j-1)是否存在邻接关系，如果存在，车辆当前行驶在这个收费路段上，进行计费，最后判断该收费路段是出口＝1，之后设置fee status＝0，车辆离开收费路段，收费结束，返回步骤2；否则返回步骤2。

如果(Node_Fee(j)和Node_Fee(j-1))∈Segment_i(u，v)

如果Segment_i(type)＝1

置fee status＝0；记录路段出口ID号；

计费Fee(all)＝Fee(all)+Segment_i(L)×Fee(i)；

收费结束，返回步骤2；

否则

计费Fee(all)＝Fee(all)+Segment_i(L)×Fee(i)；

返回步骤2；

否则

返回步骤2；

程序结束；

上述流程中费用计算是按里程收费的计算方法，对于按路段出入口收费的情况下，只需在收费路段出口处，将记录的入口ID和出口ID，在费率表中匹配，即可得到入口到出口整条路段的通行费用Fee(all)。上述符号意义见附表1。

电子地图收费运行的实施例：

电子地图可以运行在卫星定位+无线接入模块上，车载设备携带简单的可以表征点线关系的道路信息，根据卫星定位信息将车辆投影到当前路段，并记忆车辆行驶路段。实现嵌入专用电子收费地图，具备道路匹配算法，根据当前位置信息和历史数据准确地确定车辆行驶路段，并记忆车辆行驶路段，根据路段信息和费率信息自动计算道路使用费；具有简单的液晶显示功能，告知司机收费金额、帐户余额及简单的收费道路提示功能并扩展地图显示和服务信息提示功能；按照文本或PDU格式的短信息编码协议实现GSM短信收发功能，并实现GPRS上网功能，并在此功能上实现收费信息上传和信息服务扩展。

附表1：

i，j                i为任一路段号，j为任一节点号

Fee_status          当前路段收费标志值，1：行驶在收费

                    路段；0：没有在收费路段。

Search_scope        GPS位置点，初始搜索范围值

Bound               实际变化的搜索范围

V_i                  当前i位置的行驶车速

G_i(x，y)            GPS位置i的坐标

Node_i(x，y)         任意搜索到的节点i

Node_fee_i(x，y)     收费路段i上的节点

Segment_i(u，v)      收费路段i，左节点号为u，右节点号

                    为v

Segment_i(type)      收费路段类型值，入口为0，出口为1

Segment_i            收费路段长度(公里)

(length)

Fee(all)            总通行费用(元)

Node_Fee(j)         收费路段上的节点号；

Fee(i)              收费路段费率(元/公里)