浅谈电子围栏的算法思想及技术实现

1 前言
提起电子围栏，物流运输领域的同学们可能多少有所“耳闻”，运输条线会以车辆是否进出某网点电子围栏作为参考，来进行物流运输时效的考核。同时，通过判断车辆进出围栏的动作触发任务自动发车、到车，以减少人工操作，为一线工作人员“减负”。
因而电子围栏对于实际物流运输来说，其重要性不言而喻。本文将带大家了解电子围栏是什么、目前运输是如何进行车辆进出电子围栏计算的，一起探讨有关电子围栏的那些事儿。

2 什么是电子围栏
简单来说，电子围栏就是给以某个网点为中心画个“圈儿”。

为了让大家更直观的了解运输电子围栏是什么，我们可以用类似京me打卡来给大家做一个形象的解说：以京东4号楼为中心，画一个半径500m，当你处于这个圈子的范围之内，就认为你已经到达上班地点了，那么你就可以“叮”的一声打卡成功。

同样，运输的电子围栏就是以某个网点为中心，画一个半径长度合适的圈儿，当司机开车进入了这个圈子，就认为司机来到了这个网点，离开这个圈子就认为司机离开了这个网点。而且，运输的电子围栏要更“智能”一些，当司机开着车触碰网点电子围栏的那一刻，我们就可以马上监测到并进行一系列的业务逻辑计算。

我们把车辆进入电子围栏时触碰电子围栏的这一动作叫做“围栏到车事件”，把车辆离开电子围栏时触碰电子围栏的动作叫做“围栏发车事件”。

那么，我们是如何监测到车辆“触碰电子围栏”这个事件呢？如何判断它是进围栏、还是出围栏呢？

3 电子围栏发/到车事件
3.1 背景介绍
在正式阐述监测电子围栏事件之前，先带大家了解一下目前京东物流电子围栏相关的一些“知识点”：

【自营车辆】目前京东物流所有的自营车辆约3w
【三方车辆】目前京东物流所有的三方车辆（包括个体）约6w
【网点】目前京东物流所有的网点约15w
【车辆GPS数据】车辆坐标上传1.5亿/天，每分钟峰值达12w，车辆GPS上传的主要信息包括：车牌号、当前车辆所处经纬度、上传时间
之所以罗列以上信息的数据量，主要是为了让大家更直观的了解到：监测电子围栏事件，需要处理相当庞大的数据，并且对处理能力、性能等有着非常高的要求。

上图只是北京某一区域的车辆和围栏示意图，可以看到车辆数量非常可观，围栏密度也相当大，所以每当接收到一个车辆的GPS坐标时，如何进行快速计算是一件比较有难度的事情。

接下来，就和大家聊一聊目前运输是如何计算电子围栏事件的。

3.2 车辆进出电子围栏计算过程
其实车辆进出电子围栏计算的关键步骤就是两点：

第一步，对于车辆每次上传的GPS数据，我们要判断它是处于哪个网点围栏内的；
第二步，该次上传的坐标是和“进围栏”相关，还是“出围栏”相关；
说到这里，大家会不会想：计算经纬度坐标在哪个围栏里还不简单，获取到所有的网点围栏信息，循环一下，判断这个点在哪个围栏内不就ok了？

然而实际情况并非如此简单。上节我们说到“数量”问题，如果网点和车辆只是很小的量级，上述计算方式无可厚非。但是我们面对的是全国15W的网点围栏、9W多车辆，并且每分钟的坐标上传高达12W次，这样的计算思路是万万不可取的。

如何“聪明”的计算，降低计算复杂度，提升计算速度？让我们来看看目前运输是怎么做的。

3.2.1 根据上传的GPS经纬度坐标判断该坐标处于哪个围栏范围内
想要让计算的速度非常快，基本思路就是减少不必要的冗余计算，“能少算一次就少算一次”，我们基于“大事化小”和“预加载”的想法：

不需要每次都在所有网点围栏里“大海捞针”，就像是去仓库找货，并不需要去一件一件的找，而是知道货物存放在哪个货架，然后迅速定位到目的位置。把全国网点围栏按某种规则划分为固定数量的区域，对于每一次上传的车辆GPS坐标，只要定位到它是在哪个区域内，就能快速知道该坐标在哪些围栏里；
对于上述提到的的网点围栏数据、以及划分好的固定数量的区域，其本质上都属于基础数据，预加载一次即可，不需要每次都重复计算。
详细步骤如下：

step1：把整个中国地图分为若干个小格子
目前物流运输业务大多都是国内的，所以我们也只考虑国内范围，我国南北宽约5500公里，东西长约5200公里，将整个中国地图分为若干面积相等的小格子。具体划分可以进行配置：N*M。

运输目前使用的配置是50*50，该数据是经过实际情况分析取定的，N和M的取值既不能太大也不能太小，太大的话，相当于划分的格子太密集，格子数量和网点数量并没有很大区分度，那么就起不到“大事化小”简化计算的作用。反之，如果取值太小，相当于格子划分很稀疏，那么对于每一个格子来说，它所覆盖的网点围栏数量就会很多，这样对计算也不是很有利。

我国经纬度范围介于经度73°E至136°E，纬度3°N至54°N之间，可据此计算出每个小格子的经纬度范围。

step 2：计算得到每个格子覆盖哪些网点围栏
上节通过计算我们可以知道每个小格子大小约为104公里110公里，实际场景下，网点的电子围栏是一个小范围的标记，直径约几百米到几千米不等（目前我们只支持圆形电子围栏），也就是说一个网点的电子围栏面积比一个小格子要小的多。那么，把圆形电子围栏铺在5050的格子坐标系当中，大概有以下几种情况，当然还有相切的情况，在此不多赘述。

注：由于网点电子围栏信息几乎不会频繁发生变化，所以我们将step2得到的结果放入memory缓存，也就是说系统只需计算一次此结果，并将结果加载到缓存中去，然后再定时更新缓存以加载新增或修改的网点围栏数据。这样每次车辆GPS坐标上传后进行计算的时候直接从缓存里读取，效率和性能会得到很大保障。

我们用格子在整个网格中的二维坐标位置来标记格子的唯一。根据网点围栏经纬度的范围以及格子的经纬度范围就可以知道每个格子覆盖了哪些网点围栏。

格子的数据结构类似于一个二维数据，我们先存一行，然后每行里存一个list，list的每一列，就是一个格子。

grid {
  minCoord ;
  maxCoord;
  seq;
  List grid;
 }

获取所有格子覆盖的网点围栏伪代码：

arealist = getAllNodeArea() ;  //获取所有网点的电子围栏信息集合
rowlist = getAllRowList( ) ;// 获取所有行
Map<格子唯一标识，网点围栏集合> areaMap ;// 定义一个存放格子相关围栏的map
for（i =0; i<=arealist.size();i++）{
       gridSet; // 标记唯一格子的set 
       area = arealist.get( i ); // 每个电子围栏 
           for ( j =0 ; j<= rowlist .size(); j++){
              row = rowlist.get(j); // 每行格
              if( (area.maxLat >= row.minCoord && area.maxLat <=row.maxCoord) ||
                  (area.minLat >= row.minCoord && area.minLat <=row.maxCoord) ){
                    gridlist = row.getGridList();
                   for ( grid : gridlist ){
                     if( (area.maxLng >= grid.minCoord && area.maxLng <=grid.maxCoord) ||
                       (area.minLng >= grid.minCoord && area.minLng <=row.maxCoord) )
                              gridSet.add( row.seq +grid.seq ); // 行+列，标识每一个格子
                   }
              }
             ..... // areaMap里存入 <seq—arealist >
           }
    }

step 3：判断当前上传的车辆GPS坐标是位于哪个格子里，进而得到该坐标位于哪些网点围栏里
当接收到车辆上传的GPS坐标后，根据坐标经纬度在50*50的格子网中首先进行”格子定位”，step2中我们已得到每个格子覆盖哪些网点，进而可以计算出该GPS坐标位于哪些网点围栏内。这就比从15W网点围栏中找效率要高的多。

3.2.2 判断是进围栏还是出围栏事件
判断进/出围栏事件涉及到车辆接连上传的GPS位置相对于网点的电子围栏位置的变化，对于该判断有两个问题需要考虑：

一是车辆GPS坐标“漂移”问题（上一个坐标点在围栏内，下一个坐标点在围栏外）；
二是车辆与电子围栏“擦边而过”，并不是真正进入围栏；
我们为了排除这种坐标上传位置的偶然性，规定当有两次GPS坐标在围栏内（外）才认定车辆是真正进（出）了围栏。

坐标上传大致情形有以下几类：

1）当只有一个车辆GPS坐标点第一次进入围栏内，那么只对该次围栏事件进行标记（operateSign :not，由于上述“漂移”问题）；

2）当有第二个GPS坐标进入该围栏，且上次围栏事件标识为operateSign :not，那么该次确认为围栏到车事件，并发出围栏到车消息：{nodeCode，eventType:进围栏，GPS设备号，车牌号，经纬度，上传时间….}

3）当前车辆坐标不在任何围栏内，若是GPS坐标是第一次出现在围栏外，那么只对该围栏事件进行标记；若GPS坐标是第二次出现在围栏外，且上次标记为operateSign :not，那么该次确认为围栏发车事件，并发送围栏发车消息。

3.2.3 将本次进出围栏事件放入缓存
以上（3.2.2）会得到一个该车辆进出网点围栏的集合，将该集合放入redis缓存当中去，当接收到该车牌号的下一个GPS坐标后，用于进行进出围栏事件类型的判断。

3.3 计算性能
综上，车辆进出电子围栏计算基于”大事化小””预加载”的思想，通过将全国范围的网点划分区域，利用memory缓存和redis缓存，达到简化计算、提升计算效率的效果。目前，该车辆进出电子围栏计算方法的性能较佳，平均TP99只有约20ms。

自电子围栏应用以来，该计算方法”经久不衰”，计算准确率、计算效率都”无可挑剔”，历受住了多年实践的考验及多次大促压力。

4 电子围栏事件的应用
4.1 围栏发到车时间
目前电子围栏事件主要应用：一是运输时效考核，根据车辆触碰围栏的时间是否在运力计划时效范围之内来判断物流运输是否在时效内；二是围栏发车、到车时自动触发司机任务的发车、到车，以此简化一线人员操作步骤。普遍的应用逻辑就是当计算出车辆进出围栏事件之后发出消息，各应用系统接收消息，根据车牌号、网点等信息进行处理。

比如封车管理中车辆进出围栏时间的计算，以及派车任务明细中车辆进出围栏时间的计算，将封车的围栏发到车时间、任务明细的发到车时间发给路由系统，路由系统会以此为参考时间进行路由时效判断。

4.2 多设备绑定问题
电子围栏事件在实际应用场景当中，会有很多小细节需要考虑和处理，比如一个车辆的多设备绑定问题，我们是通过车辆绑定的GPS设备上传的坐标信息来进行一系列逻辑判断和业务处理的，但是实际情况中，一辆车可能会被多方使用因而需要绑定不同的设备号，那么必然会出现GPS坐标上传设备号混乱的问题，进而产生“业务逻辑”漏洞。

比如，一个车辆绑定了两个不同厂家的GPS设备装置，出围栏的时候A设备发出了围栏事件，而进围栏时确是B设备发出的围栏事件，由于一个车不同的设备号代表不同使用方在使用该车辆，那么”A出B进”这种情况其实是无法判断是不是属于一趟运输任务的。

另外，我们再来考虑一种违规场景：车辆出始发网点围栏的时候上传A设备的信息，在车辆还未到达目的网点时，有人将B设备和车辆进行绑定，但是B设备并没有实际放置于车上，而是在目的网点的某方手中，为了满足时效考核，在车辆没有实际到达目的网点时，B设备”手动触碰围栏”就上传了进入目的网点的坐标信息，很明显这是一种“作弊”行为。

为了避免以上问题，我们在判断车辆是否按时进出围栏就必须校验该一对“进出”围栏事件的上传设备号是否一致，以此来规避各种不正常的现象。在车辆出围栏的时候，记录多个设备号上传的时间以及设备号，车辆进围栏的时候，同样记录多个设备上传的时间及设备号，取进出围栏”配对”的一组记录作为正常实操结果。

自猿其说Tech-京东物流技术发展部
作者：白芳