CN109141445B - 一种分布式在线地图匹配方法 - Google Patents

Abstract

本发明涉及一种分布式在线地图匹配方法，其首先对地图进行网格化预处理，能够将许多实时地图匹配计算工作预先完成，并用文件方式保存下来，在实际的匹配处理阶段只要查询之前预先分析的结果，需要的空间计算任务会得到极大减轻，这一步工作是提高地图匹配性能的关键。

Description

一种分布式在线地图匹配方法

技术领域

本发明涉及智能交通技术领域，更具体地，涉及一种分布式在线地图匹配方法。

背景技术

浮动车GPS数据是智能交通系统一种重要的交通数据，能为相关部门提供实时交通状况信息并为后续路径选择等研究奠定基础。而地图匹配技术是浮动车数据处理中最关键的内容之一。地图匹配是将车辆当前位置与电子地图上的道路相关联，其目标是鉴别车辆正在行驶的路段和确定车辆在该路段上的位置。只有判断出车辆在哪条道路上行驶，才能将GPS数据转化为有效的道路交通状态信息。

而目前基于ArcGIS的GPS数据地图匹配，用的是ArcEngine做空间分析引擎，ArcEngine的空间分析能力大概在每核每秒40条的水平，明显偏低。而针对现在的海量浮动车数据，以广州为例，广州现有6万辆浮动车，GPS数据日均增量超过2亿条，传统的地图匹配技术进行计算时需要耗费大量硬件资源，已经不能够满足日益增长的数据分析需求，且具有软件平台依赖性。

发明内容

本发明的发明目的在于海量数据，设计一种新的分布式地图匹配方法，满足高效地、在线地处理大规模浮动车数据的要求。

为实现以上发明目的，采用的技术方案是：

一种分布式在线地图匹配方法，包括以下步骤：

一、网格化预处理阶段

S1.对地图进行网格化处理，对得到的每个网格按其左下角坐标的经纬度进行编号；

S2.对于每个网格，搜索其临近的道路，具体如下：以网格的中心为中心构建m米*m米的大矩形；然后通过空间分析得到所有和这个大矩形相交的道路或包含在大矩形内的道路；

S3.对于每个网格，搜索其临近的停车场，具体如下：网格的中心为中心构建n米*n米的大矩形；然后通过空间分析得到所有和这个大矩形相交或包含在大矩形内的停车场；

S4.通过空间分析得到网格所在的市、所在的区县；

S5.将道路图层由gis格式转换为geojson格式文件；

S6.步骤S2～S5生成网格临近路段文件、网格临近停车场文件、网格所在市区县文件与道路图层geojson文件四个文件，四个文件主要为网格与路段、停车场、所属地区以及路段id与路段实体的哈希映射表，将四个文件包含的内容加载到内存数据库redis；

二、实时匹配阶段

S7.对实时获取的车辆GPS数据进行初步地图匹配：

1)计算GPS点所在的网格编号；

2)查询1)确定的网格对应的网格临近路段文件、网格临近停车场文件、网格所在市区县文件与道路图层geojson文件四个文件，从而获得网格临近路段信息，网格临近停车场信息、网格所在市区县信息；

S8.结合2)中获得的信息，考虑车辆在之前一定时长内的定位点序列对车辆的所在道路进行匹配，找到置信度最高的道路为匹配道路；或者结合2)中获得的信息，判断定位点序列是否有移动，并根据之前一定时长内的定位点序列对停车场进行匹配。

优选地，所述步骤S1将地图按经纬度小数点后四位为单位切分成一个个网格。

优选地，所述步骤S1将每个网格左下角坐标的经纬度进行组合排列得到网格的编号。

优选地，所述m为70，所述n为150。

与现有技术相比，本发明的有益效果是：

本发明提供的方法首先对地图进行网格化预处理，能够将许多实时地图匹配计算工作预先完成，并用文件方式保存下来，在实际的匹配处理阶段只要查询之前预先分析的结果，需要的空间计算任务会得到极大减轻，这一步工作是提高地图匹配性能的关键。

附图说明

图1为方法的框架示意图。

图2为网格的示例图。

图3为搜索临近道路的示意图。

具体实施方式

附图仅用于示例性说明，不能理解为对本专利的限制；

以下结合附图和实施例对本发明做进一步的阐述。

实施例1

图1为本发明提供的方法的框架图。本发明提供的方法主要包括有两个步骤，具体如下所述：

一、网格化预处理阶段

1)将整个城市按经纬度小数点后四位即0.0001(相当15米)为单位切分成一个个网格，网格矩形的左下角坐标可以唯一确定网格的位置，如图2所示，图中网格的经纬度为(113.2203，23.1851)，可以代表经度113.2203到113.2204，纬度23.1851到23.1852这块矩形区域。

每个网格统一用左下角经纬度作为其编号，去掉小数点符号一共13位(7+6)，例如，图2中网格编号1132203231851。进行地图网格化的优点是，对于任何一个GPS点都可以直接算出所在网格的编号，例如(113.876694,23.641236)所在网格编号为1138766236412。

2)进行完地图网格化之后，就需要搜索网格附近道路，为之后根据浮动车GPS数据地图匹配奠定基础。在此以目标网格的重心为中心构建70米*70米的矩形，搜索临近道路。主要计算方法如下：

1.计算出网格的中心；

2.以这个中心构建一个70米*70米(可配置)的大矩形；

3.通过空间分析得到所有和这个大矩形相交或包含在大矩形内的道路。

对于图3中的网格，通过计算得到的临近道路包括A、B、C三条。

这个步骤输出的文件所包含的信息包括：网格编号、临近道路ID(1或n条)，网格如果没有临近道路则不保存。

3)地图上的信息，除了道路之外，还包括静态交通组织，例如停车场，也是重要交通组成，因此还需要对地图上的停车场信息与网格进行匹配。计算方法与搜索网格临近道路类似，具体计算步骤如下：

1.计算出矩形的中心；

2.以这个中心构建一个150米*150米(可配置)的大矩形；

3.通过空间分析得到所有和这个大矩形相交或包含在大矩形内的停车场。

这个步骤输出的文件所包含的信息包括：网格编号、临近停车场ID(1或n个)，网格如果没有临近停车场则不保存。

4)搜索完网格附近道路与停车场之后，还需要获取网格所属区域的基本信息，包括所在市区县，为后续分析各种尺度下的交通信息奠定基础。因此通过空间分析直接得到矩形网格所在的市、所在的区县。这个步骤输出的文件所包含的信息包括：网格编号、经纬度、所在市、所在区县。

5)最后，为了在地图匹配数据计算时获取图层信息，需要将道路图层由gis格式转换为geojson格式文件，以方便大数据环境下的使用，摆脱ArcGIS平台限制。

二、Storm环境中的道路匹配算法

1)网格化预处理步骤将生成的4个文件：网格临近路段文件、网格临近停车场文件、网格所在市区县文件与道路图层geojson文件。4个文件主要为网格与路段、停车场、所属地区以及路段id与路段实体的哈希映射表(Hashmap)。为了进行将预处理数据加载到大数据云平台计算，需要将4个文件包含的预处理信息直接加载到内存数据库redis，而需要加载到redis的4个Hashmap如下所示。

2)在加载好地图网格化数据之后，就需要对实时获取的车辆GPS数据进行初步地图匹配，主要是负责对GPS点进行初步的匹配，查出所在市、区县、临近的路、临近的停车场。在此先通过Kafkaspout不断的从kafaka中读出GPS数据。该步骤输入为GPS数据实体，输出为GPS数据、所在市、区县、临近的路、临近的停车场。其具体的计算步骤如下所示：

1.计算GPS点所在网格编号；

2.查网格临近路段hashmap，得到临近路段ID(可多个)。此时该进行该步骤操作的时间复杂度为O(1)；

3.网格临近停车场hashmap，得到临近停车场ID(可多个)。此时该进行该步骤操作的时间复杂度为时间复杂度O(1)；

4.网格所在市区县hashmap，得到临近所在市与区县。此时该进行该步骤操作的时间复杂度为时间复杂度O(1)。

3)在得到了GPS所属区域与临近道路的初步信息之后，就需要对得到的GPS点临近的几条道路进行分析判断，分析车辆最有可能是行驶在哪条道路上或者判断其在哪个停车场。

在高密度路网下，只考虑单一定位点信息难以对道路进行正确匹配，因此需要考虑车辆轨迹信息(由定位点序列构成)以获得更好的匹配效果。因此在计算单个点到路段的距离，进行点到线匹配之后，还需要进行点序列匹配，找到置信度最高的匹配路段。而针对停车场的匹配，主要是观察点序列是否有移动，以及根据之前的轨迹数据，匹配其最可能停在哪个停车场。该过程主要输入的数据为GPS数据、所在市、区县、临近的路、临近的停车场，而输出结果为GPS数据、所在市、区县、所在道路或者所在停车场，对应的数据表如下所示。

表1地图匹配结果数据表

本发明提供的方法现部署于天河二号超级计算中心，总共包含11个物理节点。实时接入了广州市6万辆浮动车，数据日增量超过2亿条，平均每秒接入超过2000条数据。针对这些浮动车GPS数据，已经能够实现在线实时的地图匹配，为后续对路段速度与状态估计奠定基础。

通过对大规模的浮动车数据进行在线地图匹配，发现采用传统的集中式的地图匹配计算效率低于300条记录/s，一天最多可计算3000万数据，而本发明所提出的在线分布式的地图匹配方法，计算效率达11000条记录/s，超过9亿/天。现已实时接入广州市6万辆浮动车数据，可完全实现大规模浮动车数据的在线地图匹配。

显然，本发明的上述实施例仅仅是为清楚地说明本发明所作的举例，而并非是对本发明的实施方式的限定。对于所属领域的普通技术人员来说，在上述说明的基础上还可以做出其它不同形式的变化或变动。这里无需也无法对所有的实施方式予以穷举。凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等，均应包含在本发明权利要求的保护范围之内。

Claims (4)

1.一种分布式在线地图匹配方法，其特征在于：包括以下步骤：

一、网格化预处理阶段

S1.对地图进行网格化处理，对得到的每个网格按其左下角坐标的经纬度进行编号；

S2.对于每个网格，搜索其临近的道路，具体如下：以网格的中心为中心构建m米*m米的大矩形；然后通过空间分析得到所有和这个大矩形相交的道路或包含在大矩形内的道路；

S3.对于每个网格，搜索其临近的停车场，具体如下：网格的中心为中心构建n米*n米的大矩形；然后通过空间分析得到所有和这个大矩形相交或包含在大矩形内的停车场；

S4.通过空间分析得到网格所在的市、所在的区县；

S5.将道路图层由gis格式转换为geojson格式文件；

S6.步骤S2～S5生成网格临近路段文件、网格临近停车场文件、网格所在市区县文件与道路图层geojson文件四个文件，四个文件分别为网格与路段、网格与停车场、网格与所属地区、路段id与路段实体的哈希映射表，将四个文件包含的内容加载到内存数据库redis；

二、实时匹配阶段

S7.对实时获取的车辆GPS数据进行初步地图匹配：

1)计算GPS点所在的网格编号；

2)查询1)确定的网格对应的网格临近路段文件、网格临近停车场文件、网格所在市区县文件与道路图层geojson文件四个文件，从而获得网格临近路段信息，网格临近停车场信息、网格所在市区县信息；

S8.结合2)中获得的信息，考虑车辆在之前一定时长内的定位点序列对车辆的所在道路进行匹配，找到置信度最高的道路为匹配道路；或者结合2)中获得的信息，判断定位点序列是否有移动，并根据之前一定时长内的定位点序列对停车场进行匹配。

2.根据权利要求1所述的分布式在线地图匹配方法，其特征在于：所述步骤S1将地图按经纬度小数点后四位为单位切分成一个个网格。

3.根据权利要求2所述的分布式在线地图匹配方法，其特征在于：所述步骤S1将每个网格左下角坐标的经纬度进行组合排列得到网格的编号。

4.根据权利要求2所述的分布式在线地图匹配方法，其特征在于：所述m为70，所述n为150。

Images