CN105489011A - 基于网格切分的大规模车辆路网实时限速计算方法 - Google Patents

Abstract

本发明涉及一种基于网格切分的大规模车辆路网实时限速计算方法。采用三级网格设计策略，使用欧拉距离算法匹配道路，采用分布式存储及部署方式实现并行计算，包括如下步骤：1、将运输路网按照经纬度划分区域；2、划分一级网格、二级网格；3、网格数据生成；4、数据初始化；5、实时道路限速计算。本算法简洁高效，能够准确匹配道路；系统部署只需几台物理机，成本低廉，将本方法应用于道路运输车辆的监控平台上，能使监控平台同时处理遍布于全国各地的大量运输车辆的分路段限速计算，为运输企业、政府监管部门提供快速有效的手段实现其所辖范围内的所有在途车辆的分路段限速提示，提升了道路运输车辆的行车安全，保障了运输的人、车、货安全，降低了因超速行驶而发生事故所带来的经济损失。

Description

基于网格切分的大规模车辆路网实时限速计算方法

技术领域

本发明涉及车辆运输管理技术领域，特别涉及一种基于网格切分的大规模车辆路网实时限速计算方法。

背景技术

当前，高发的交通安全事故使道路运输车辆的行车安全成为社会关注的焦点，国家也高度重视道路运输安全，运输车辆基本都需要安装车载终端，并接入车辆监控平台，以实现对运输车辆的监控，众所周知，超速行驶是引发道路安全事故的主要原因之一，要真正保障车辆行车安全，理所当然要在车辆行驶速度的把控上采取有效措施，目前最有效的办法就是对车辆进行限速行驶，并对驾驶员进行限速提示，但要做到分路段限速并不容易，因为需要详细区分规定线路的高速公路、国道、省道、城市道路、县级、乡村路段，依据各路段的限速规定，准确合理的计算和界定分路段的车辆限速标准，这在运输车辆少，运输范围小的情况下还是可以实现，但是对于大规模的在全国路网上运输的车辆，要实现实时分路段限速，计算量非常之大，目前还没有一个好的方法来解决这个问题。

要实现大规模运输车辆的实时分路段限速就需要同时对大量运输车辆进行实时限速计算，而且运输范围遍布全国各地，这个需求对分段限速运算量的要求表现为：以30万台车辆为基准，取20%上线率，每30秒上传一个定位点，即平均每秒60000*2/60=2000次分段限速的运算，全国路网大约550万条道路，系统需满足每秒2400（2000*120%）次道路匹配运算，以单机计算，每次运算耗时应在0.4ms内完成。

目前，在道路运输车辆分段限速方面，若采用传统ArcGIS与空间数据库结合方式，完成一条GPS的道路匹配需要94ms，以单机计算，每秒能完成10.6次，因此，传统的计算方案无法满足大规模车辆全国路网实时限速的要求。

发明内容

本发明的目的是针对现有路网上大规模运输车辆要实现实时分路段限速计算量大的问题，提出一种基于网格切分的大规模车辆路网实时限速计算方法，提升车辆监控的有效性，切实保障道路运输的安全。

为解决大规模车辆路网实时限速计算的问题，本发明的技术解决方案是提供一种基于网格切分的大规模车辆路网实时限速计算方法，采用三级网格设计策略，使用欧拉距离算法匹配道路，采用分布式存储及部署方式实现并行计算。

一种基于网格切分的大规模车辆路网实时限速计算方法的具体步骤如下：

步骤1：将运输路网按照经纬度划分区域，形成运输路网的矩形区域网格；

步骤2：划分一级网格、二级网格，所述一级网格是经度和纬度各1°的网格，每个一级网格对应一个数据表，所述二级网格是每个一级网格再细分为一个经度和纬度均为0.0005°的二级网格，每个二级网格对应数据表中的一条记录；

步骤3：网格数据生成，将最小单元网格与其包含的道路信息匹配，存储后以备使用，即以一级网格为单元，采用空间数据库的交集函数和存储过程，逐一计算属于一级网格的二级网格内的道路；

步骤4：数据初始化，将网格数据加载到内存数据库，内存数据库的网格表和空间数据库一一对应，然后从内存数据库加载网格数据到路网计算服务，路网计算服务将各自区域的网格加载到本地缓存中，数据初始化以备路网计算服务的实时道路限速计算所用；

步骤5：实时道路限速计算，所述实时道路限速计算由路网计算服务来完成，路网计算服务采用分布式存储和计算，路网计算服务集群中的每个服务存储某个区域的网格数据，所述路网计算服务根据已初始化的网格数据以及车辆上传的GPS经纬度数据完成道路匹配。

进一步地，步骤5中所述的道路匹配的具体步骤是：将车辆上传的GPS经纬度信息投影到数据网格，获取网格所经过的道路列表，计算车辆行驶位置点和网格内道路的垂直距离，寻找最短距离的道路，完成道路匹配。

进一步地，采用欧拉算法计算车辆行驶位置点和网格内道路的垂直距离，寻找最短距离的道路，完成道路匹配。

进一步地，所述欧拉算法是：当计算车辆行驶位置点与网格内道路的距离时，采用几何算法，计算点与线间的垂直距离，依据位置点到道路垂足的经度，计算位置点到网格内道路的垂直距离，比较垂直距离的大小，完成道路匹配；当计算两个位置点的距离时，依据两个位置点的经纬度，引入可接受的误差，将地球视作标准球体，计算两位置点间的距离。

进一步地，采用欧拉算法进行道路匹配的过程，当车辆行驶位置点出现下述三种情况时，九宫格算法进行道路匹配，所述三种情况包括：

a、车辆行驶在交叉点上；

b、多线路和道路单点情况；

c、规避GPS偏差。

进一步地，当车辆行驶在交叉点上时，点到两条道路的距离相同，所述道路匹配暂时不处理，留待下一个GPS点再上报分段限速信息。

进一步地，当车辆行驶位置点处于多线路和道路单点情况时，被网格切分的道路在网格中存在多段情况，处理方式为增加虚拟节点（0,0）。

进一步地，当规避GPS偏差时，针对GPS漂移误差，采用九宫格算法，计算车辆行驶位置点网格以及周边的8个网格的道路垂直距离，寻找最短距离的道路，完成道路匹配。

一种基于网格切分的大规模车辆路网实时限速计算方法的硬件系统，包括三台物理机：第一台物理机用于空间数据库，所述空间数据库存储运输路网数据、一级网格数据；第二台物理机用于路网计算内存数据库，所述路网计算内存数据库加载空间数据库网格数据；第三台物理机用于路网计算服务器，所述路网计算服务器加载网格数据到本地缓存。

本发明的有益效果是：提出了一种解决针对大规模车辆全国路网的实时限速的大规模计算问题，设计以高性能计算为主线，以满足大规模道路运输车辆安全监管业务需求为目的。

本方法有以下特点：三级网格策略，能够快速索引位置和道路信息；算法简洁高效，能够准确匹配道路；系统部署只需几台物理机，成本低廉。基于以上特点，将本发明应用于道路运输车辆的监控平台上，能使监控平台同时处理遍布于全国各地的大量运输车辆的分路段限速计算，从而为运输企业、政府监管部门等提供快速有效的手段实现其所辖范围内的所有在途车辆的分路段限速提示，切实大大提升了道路运输车辆的行车安全，保障了运输的人、车、货安全，降低了因超速行驶而发生事故所带来的巨大经济损失。

附图说明

图1是本发明基于网格切分的全国路网实时限速计算流程图。

图2是本发明道路限速应用流程图。

图3是全国运输路网划分区域图。

图4是网格数据生成图。

图5是欧拉算法示意图，垂直距离的计算。

图6是欧拉算法示意图，点与线距离的计算。

图7是欧拉算法示意图，两经纬度间距离的计算。

图8是车辆行驶在交叉点上位置示意图。

图9是多线路和道路单点情况位置示意图。

图10是GPS偏差位置示意图。

图11是硬件系统结构图。

具体实施方式

下面结合附图对本发明做进一步地说明。

基于网格切分的大规模车辆全国路网实时限速计算方法，采用三级网格设计策略，将运输范围划分成若干个区域，逐级细分成网格，将道路信息与单元网格数据绑定，预先存储并加载，在应用的过程中，根据车辆上传的GPS经纬度快速索引当前位置数据所在的服务器、数据表和表记录，性能极高，可以迅速匹配GPS点所在的道路，并获取道路的限速值进行限速提示。在匹配道路的时候采用欧拉距离得出，这种方法只有基本的四则运算和平方根运算，算法复杂度低，性能高，并且结合网格定位和九宫格算法具有很高的准确性。

一种基于网格切分的大规模车辆路网实时限速计算方法，具体包括如下步骤。

（1）将全国路网划分区域

如图3所示，查询全国路网数据，获取最小经度（73.927475）、最小纬度（18.197495）以及最大经度（134.687061）、最大纬度（53.558456），形成全国路网的矩形范围【（73.927018.1970）（134.927054.1970）】。

区域网格：区域网格是把中国路网所覆盖的区域等分为1~N个区域（目前N取值为9），将全国路网覆盖的区域按照1°×1°网格大小划分成一级网格，共2196各一级网格，每个区域包含244个一级网格。

（2）划分一级网格和二级网格

一级网格：宽度（经度）和高度（纬度）各1°的网格（约100公里*100公里），在全国路网矩形范围内【（73.927018.1970）（134.927054.1970）】，一共有（134-73）*（54-18）=61*36=2196个一级网格；在存储设计上，一级网格对应一个数据表。

二级网格：每个一级网格再细分为一个宽（经度）高（纬度）均为0.0005°的二级网格（约50米*50米），每个一级网格由400万个二级网格组成，一共有87.84亿个二级网格。在存储设计上，二级网格对应数据表中的一条记录。

根据测试结果，在道路密集度较高的江浙地区，一个二级网格的平均道路数为1.25条，80%有道路的二级网格只有1条路，根据GPS信息匹配道路速度很快。

（3）网格数据生成

如图4所示，网格数据生成就是将最小单元网格与其包含的道路信息匹配，存储后以备使用。以一级网格为单元，采用空间数据库的交集函数和存储过程，逐一计算属于一级网格的400万二级网格内的道路。一个一级网格对应一个数据表，一共2196个数据表。

网格包含道路的具体数据如下表所示：

主键	网格道路数目	网格道路列表
			二级网格经度+纬度	N	道路列表

道路ID	道路类型	道路限速值	道路点集合
				ID	高速、国道等	Ｎ公里／时	经度、纬度

（4）数据初始化

首先将网格数据加载到内存数据库，内存数据库的网格表和空间数据库一一对应，经过测试一个一级网格数据加载到内存数据库中需要100s。然后从内存数据库加载网格数据到路网计算服务，路网计算服务将各自区域的网格加载到本地缓存中,加载全部需1小时。数据初始化以备路网计算服务的实时道路限速计算所用。

（5）实时道路限速计算

实时道路限速计算由路网计算服务来完成，路网计算服务采用分布式存储和计算，路网计算服务集群中的每个服务存储某个区域的网格数据。路网计算服务主要根据已初始化的网格数据以及车辆上传的GPS经纬度数据完成道路匹配。具体过程是，将经纬度信息投影到数据网格，获取网格所经过的道路列表，计算点和道路的垂直距离（欧拉距离），寻找最短距离的道路，并结合九宫格算法完成道路匹配。

欧拉算法说明：

使用数学计算求出位置点与网格内线路的垂直距离（欧拉距离），如图5所示，以P点位中心的圆的半径为GPS/北斗位置的漂移阈值，一般设置为20米。P点在L1上的垂足为P1点，在L3上的垂足为P3点，P点与L2的垂直相交于L2的延长线上。依据L1、L2、L3的线路宽度，且比较PP1、PP2、PP3的大小，寻找最短距离的道路，完成线路匹配。

点与线间的距离可使用简单的几何计算，如图6所示。

计算过程如下：

K为线段P1P2的斜率，交点P3的坐标可求：

。

两经纬度间的距离计算，引入可接受的误差，将地球视作标准球体，计算两点间的距离，如图7所示。

设第一点A的经纬度为(LonA,LatA)，第二点B的经纬度为(LonB,LatB)，按照0度经线的基准，东经取经度的正值(Longitude)，西经取经度负值(-Longitude)，北纬取90减去纬度值(90-Latitude)，南纬取90加纬度值(90+Latitude)，则经过上述处理过后的两点为(XA,YA)和(XB,YB)。

那么根据三角推导，可以得到计算两点距离的如下公式：

S：所求两点间距离，单位千米

R：地球半径，6378.137千米。

九宫格算法说明，本发明所述的九宫格算法是为了解决在道路匹配的过程中的三种特殊情况，具体如下。

a、交叉点处理：如果车辆正好行驶在交叉点上，如图8所示，点到两条道路的距离相同，在这种情况下，暂时不处理，留待下一个GPS点再上报分段限速信息，。

b、多线路和道路单点情况处理：被网格切分的道路在网格中存在多段情况，如图9所示，处理方式为增加虚拟节点（0,0），保持数据结构的完整性并方便计算。一条道路可能在一个网格只有一个点，这条道路必定落于其他网格中，所以对这种情况不处理。

c、规避GPS偏差的九宫格算法：GPS/北斗位置的漂移阈值，一般为20米，如图10所示，GPS点所在网格有2条道路，相邻网格有1条，实际GPS点匹配的应是相邻网格的道路，针对漂移误差，算法采用九宫格计算，计算本网格以及周边的8个网格，寻找最短距离的道路。

将上述方法应用于实际中需要依靠硬件方案的支持，在此，进行了应用测试。

（1）测试环境部署，如图9和下表所示。

。

经测试预估，内存数据库的路网数据容量在200G左右，计算服务在400G左右，考虑数据冗余，内存数据库集群和计算服务集群各需要1台物理机，配置：4CPU10核512G内存。

（2）性能测试：测试数据为5万组GPS点信息，采用批量提交和计算方式，经过多次测试，计算耗时如下表：

其中，路网计算服务计算耗时组成如下：

5万组数据计算总耗时小于2S，每组40μS；减去IO时间纯计算只有547毫秒，每组11μS。

结论：采用内存计算性能极高，完全能满足业务需求。

Claims (9)

1.一种基于网格切分的大规模车辆路网实时限速计算方法，其特征在于采用三级网格设计策略，使用欧拉距离算法匹配道路，采用分布式存储及部署方式实现并行计算，包括如下步骤：

步骤1：将运输路网按照经纬度划分区域，形成运输路网的矩形区域网格；

步骤2：划分一级网格、二级网格，所述一级网格是经度和纬度各1°的网格，每个一级网格对应一个数据表，所述二级网格是每个一级网格再细分为一个经度和纬度均为0.0005°的二级网格，每个二级网格对应数据表中的一条记录；

步骤3：网格数据生成，将最小单元网格与其包含的道路信息匹配，存储后以备使用，即以一级网格为单元，采用空间数据库的交集函数和存储过程，逐一计算属于一级网格的二级网格内的道路；

步骤4：数据初始化，将网格数据加载到内存数据库，内存数据库的网格表和空间数据库一一对应，然后从内存数据库加载网格数据到路网计算服务，路网计算服务将各自区域的网格加载到本地缓存中，数据初始化以备路网计算服务的实时道路限速计算所用；

步骤5：实时道路限速计算，所述实时道路限速计算由路网计算服务来完成，路网计算服务采用分布式存储和计算，路网计算服务集群中的每个服务存储某个区域的网格数据，所述路网计算服务根据已初始化的网格数据以及车辆上传的GPS经纬度数据完成道路匹配。

2.根据权利要求1所述的一种基于网格切分的大规模车辆路网实时限速计算方法，其特征在于步骤5中所述的道路匹配的具体步骤是：将车辆上传的GPS经纬度信息投影到数据网格，获取网格所经过的道路列表，计算车辆行驶位置点和网格内道路的垂直距离，寻找最短距离的道路，完成道路匹配。

3.根据权利要求2所述的一种基于网格切分的大规模车辆路网实时限速计算方法，其特征在于采用欧拉算法计算车辆行驶位置点和网格内道路的垂直距离，寻找最短距离的道路，完成道路匹配。

4.根据权利要求3所述的一种基于网格切分的大规模车辆路网实时限速计算方法，其特征在于所述欧拉算法是：当计算车辆行驶位置点与网格内道路的距离时，采用几何算法，计算点与线间的垂直距离，依据位置点到道路垂足的经度，计算位置点到网格内道路的垂直距离，比较垂直距离的大小，完成道路匹配；当计算两个位置点的距离时，依据两个位置点的经纬度，引入可接受的误差，将地球视作标准球体，计算两位置点间的距离。

5.根据权利要求4所述的一种基于网格切分的大规模车辆路网实时限速计算方法，其特征在于采用欧拉算法进行道路匹配的过程，当车辆行驶位置点出现下述三种情况时，九宫格算法进行道路匹配，所述三种情况包括：

a、车辆行驶在交叉点上；

b、多线路和道路单点情况；

c、规避GPS偏差。

6.根据权利要求5所述的一种基于网格切分的大规模车辆路网实时限速计算方法，其特征在于当车辆行驶在交叉点上时，点到两条道路的距离相同，所述道路匹配暂时不处理，留待下一个GPS点再上报分段限速信息。

7.根据权利要求5所述的一种基于网格切分的大规模车辆路网实时限速计算方法，其特征在于当车辆行驶位置点处于多线路和道路单点情况时，被网格切分的道路在网格中存在多段情况，处理方式为增加虚拟节点（0,0）。

8.根据权利要求5所述的一种基于网格切分的大规模车辆路网实时限速计算方法，其特征在于当规避GPS偏差时，针对GPS漂移误差，采用九宫格算法，计算车辆行驶位置点网格以及周边的8个网格的道路垂直距离，寻找最短距离的道路，完成道路匹配。

9.采用权利要求1-8所述的一种基于网格切分的大规模车辆路网实时限速计算方法的硬件系统，其特征在于包括三台物理机：第一台物理机用于空间数据库，所述空间数据库存储运输路网数据、一级网格数据；第二台物理机用于路网计算内存数据库，所述路网计算内存数据库加载空间数据库网格数据；第三台物理机用于路网计算服务器，所述路网计算服务器加载网格数据到本地缓存。