基于网格分块索引的车辆高频活动区域算法

黎飞　程登　黄祖朋　张亮　张送　赵小羽　李淑英

摘 要：車辆的高频活动区域对于车辆的服务应用有较大的参考意义，而汽车高频活动区域的计算中会基于其采集模块提供的经纬度数据进行运算，而该采集模块的经纬度数据误差通常为10米左右，较大误差的引入会影响高频区域计算的复杂度，准确性，及时性。若要降低该误差通常可借助提高采集模块的采集精度，或第三方差分定位服务，但同时导致成本上升。本文将基于当前车辆采集模块的经纬度数据精度，采用地图网格化分块索引的方式改进了车辆高频活动区域的算法，提高了车辆高频活动区域的计算的速度和准确性。

关键词：网格 索引 高频 区域算法

Algorithm of Vehicle High Frequency Activity Region Based on Grid Block Index

Li Fei Cheng Deng Huang Zupeng Zhang Liang Zhang Song Zhao Xiaoyu Li Shuying

Abstract：The high-frequency activity area of the vehicle has a great reference significance for the service application of the vehicle， and the calculation of the high-frequency activity area of the vehicle will be based on the longitude and latitude data provided by the collection module， and the longitude and latitude data error of the collection module is usually about 10 meters， and the introduction of large errors will affect the complexity， accuracy and timeliness of calculation in the high-frequency region. To reduce this error， it is usually possible to improve the acquisition accuracy of the acquisition module or a third-party differential positioning service， but at the same time it leads to an increase in cost. Based on the accuracy of the latitude and longitude data of the current vehicle acquisition module， this paper uses map gridding and block indexing to improve the algorithm of the vehicle high-frequency activity area， and improve the speed and accuracy of the calculation of the vehicle high-frequency activity area.

Key words：grid， index， high frequency， area algorithm

1 引言

随着社会的发展和科技的进步，大数据，机器学习，人工智能等高新尖技术的飞速发展促使汽车向着智能化方向发展，基于车辆位置或活动区域的智能化服务作为其中重要的一环成为当下研究热点。智能化服务的开展更多依赖车辆定位的精准度，运算速度，便于优化用户画像，给车辆的营销，服务推荐等提供决策和改善方向。

当前大部分车辆位置所采集的经纬度误差较大（通常为10～15米），要降低该误差提高计算的准确度有两种方案，一则提高采集设备的精度或引入第三方的差分定位服务，但此方案会导致车辆成本上升;二则通过引入其他特征数据，设计更复杂的运算模型，但此方案导致设计复杂性较高，运算实效和计算的硬件成本上升。综上两种方案均存在一些弊端。本文将介绍一种基于当前车辆经纬度误差条件下，不增加硬件成本，降低运算的复杂性，提高运算时效性和定位精准度的优化算法方案。

2 算法思路

整体算法分为划分区域网格，建立空间索引，处理车辆位置信息，车辆位置地图映射，计算车辆所属网格，确定高频停车区域共6个步骤，如图1。

2.1 划分区域网格

将待分析区域的地图按照经纬度坐标根据一定的间隔在纵横方向上分成M 行和N列，即MxN个网格，如图2。将网格上每个节点的经纬度作为该点的坐标Pi（xi，yi），其中x表示经度，y表示纬度，i表示网格节点编号索引，从0开始计。同时将每个网格建立编号索引。

2.2 建立空间索引

这是一种分割空间对象的索引方法。即为每个网格分配一个动态存储区，并将该网格所框选的空间对象，如道路，建筑物等信息存入该网格对应的存储空间中。

2.3 处理车辆位置数据

依据需求提取某个群体范围里车辆经纬度数据并针对无效数据进行清洗，如空值，异常漂移值等。

2.4 车辆位置在地图映射

将清洗好的车辆经纬度数据映射到地图上，此时车辆每个位置将以点状分布在地图上，如图3。

2.5 计算车辆位置所属网格

假设每个网格的长度和宽度分别为dl，dw。dw为横向两相邻节点横坐标之差即经度之差，dl为纵向相邻两节点纵坐标之差即纬度之差（图4）。

用車辆某个位置坐标xi和yi分别除以dw，dl，即可获得改位置点所在的行和列编号，进而获得网格编号。如公式1

行k=[yi/dl]+1

列j=[xi/dw]+1                公式1

通过以上公式遍历所有车辆位置数据，即可获得每个位置点所属的网格编号。

2.6 确定车辆高频停车区域

计算各网格所包含的位置点的总数并按降序排列，选取数量最多的几个（通常不超过3个）网格所在的区域即为该车辆的高频活动区域。结合区域内存储的空间对象，即可很好的判断车辆的活动喜好。如图5

3 算法总结

该算法的有两个关键点。其一在于合理的定义网格的大小。网格划分越小，确认的高频活动区域越精准，但同时会增消耗较多计算资源和存储资源，增加了计算时长。其二在于计算车辆位置所属的网格编号。通常的算法会用车辆经纬度位置数据分别与每个网格的4个节点的经纬度数据进行比较运算来判断所属网格，但该算法需要遍历每个网格的节点，运算效率不高，消耗的计算资源较多。本文算法采用车辆经纬度位置数据除以网格的长度和宽度的方法，仅计算一次变可以得到结果，效率较高。

4 结语

本文提出的算法无需引入高精采集设备或第三方差分定位服务或复杂计算模型，是一种低成本，高效率，高准确率的计算车辆高频活动区域的算法，尤其面对在海量大数据及实时性要求较高的条件下，计算效能十分明显。

基金项目：广西创新驱动发展专项资金资助项目（桂科AA18242039）;柳州市科学研究与技术开发计划资助项目（2019AG10202）

参考文献：

[1]陶晓丽，张志华， 张丽等. 基于格网索引的点目标捕捉算法[J]. 测绘与空间地理信息，2015，38（10）：200.

[2]徐松杰，陈紫强.基于网格分块的快速地图匹配算法[J]. 桂林电子科技大学学报，2014，34（01）：33-36.

[3]张丽芬，王晓华，胡景松，宋维佳，龙斌. 基于网格划分的几种空间索引[J]. 北京理工大学学报，2004，24（02）：140-144.

[4]张顺，尹洪权，吉敏. 基于网格索引的地图匹配算法[J].齐鲁工业大学学报[J]，2015，29（04）：77-80.