转转上门履约的LBS实践
1 什么是LBS
2 名词解释
3 业务简介
4 基于围栏的曝光下单和分配订单
4.1 曝光下单
4.2 分配订单
5 基于定位服务的路线规划、自主订单调度
5.1 路线规划
5.2 自主订单调度
6 总结
7 参考文档
1 什么是LBS
基于位置的服务（Location Based Services，LBS），是利用各类型的定位技术来获取定位设备当前的所在位置，通过移动互联网向定位设备提供信息资源和基础服务。首先用户可利用定位技术确定自身的空间位置，随后用户便可通过移动互联网来获取与位置相关资源和信息。LBS服务中融合了移动通讯、互联网络、空间定位、位置信息、大数据等多种信息技术，利用移动互联网络服务平台进行数据更新和交互，使用户可以通过空间定位来获取相应的服务。
2 名词解释
工程师：上门履约小哥 围栏：由点组成的闭合的多边图形，如图所示(就是由经纬度组成的多边形)
3 业务简介
转转上门履约业务主要依托于转转C2B，针对3C数码产品进行上门回收，为用户提供快速，精确的上门服务。简单流程图如下：
具体步骤:
用户打开转转APP回收页，根据用户的IP信息和GPS（用户授权情况下）获取所在城市(或地址)是否支持上门。 当用户所在城市支持上门，判断用户输入的上门地址是否支持上门。 用户对需要回收的机器进行估价。 用户下单，系统自动将订单分配给上门小哥。 上门工程师上门回收。
4 基于围栏的曝光下单和分配订单
4.1 曝光下单
基于二手3C数码场景，并不能做到全国每个城市，每个角落都支持上门小哥上门回收，所以精准地判断用户地址是否支持上门回收对业务来说至关重要。
简而言之，就是根据用户下单的地址转换成对应的经纬度坐标，根据经纬度判断当前点是否在围栏中，从而判断用户的地址是否支持上门履约。
但是将全国的地图切割成一个个不规则的多边形，在成千上万的不规则图形中，如何快速地判断某一个经纬度在哪一个围栏之中？目前我们采用的是两段匹配的方式。
4.1.1 初筛：最小覆盖区域矩形
如下图所示，任何一个不规则的多边形都能用一个矩形将其框住，只需要获取右上角的坐标，和左下角的坐标就能构建这个矩形，从而快速的判断用户地址经纬度是否在这个矩形里边，快速过滤掉大部分的干扰围栏。
4.1.2 精筛：射线法精确匹配
射线算法：从待判断的点向某一个方向引射线，计算和多边形交点的个数，如果个数是偶数或者0，则点在多边形外，如果是奇数，则在多边形内（当然，一些特殊情况需要单独判断，比如点刚好在顶点或者边上）。如图所示：
根据射线法，就可以精准判断坐标是否在围栏内。
目前常用的判断点在多边形内的方法
射线法：时间复杂度O(n)，适用任意多边形。 转角法：时间复杂度O(n)，适用任意多边形，对精度要求比较高。 角度判断法：时间复杂度O(n)，适用任意多边形，和转角法类似，对精度要求比较高。 叉积判断法：时间复杂度O(n)，适用凸多边形。 面积法：时间复杂度O(n)，适用凸多边形。 二分法：时间复杂度O(logn)，适用凸多边形。 弧长法：时间复杂度O(n)，适用任意多边形。
当然，还有其他的算法，如果感兴趣可以自行搜索相关资料。我们根据业务场景需求以及对算法的熟悉，理解程度，最终选择射线法作为匹配算法。为了计算的速度，所有的计算过程都是基于内存运算。
4.1.3 简单的检索流程
大体上分为两个阶段：
第一阶段：服务拉取DB中的围栏信息，做初始化数据，并在内存中构建查询索引。 第二阶段：用户发起查询，系统通过内存中的数据，根据上述算法规则计算是否在围栏中。
4.1.4 检索索引介绍
随着围栏的数量越来越多，暴力遍历的寻找方式会大大的降低检索的速度，所以这里我们采取的是利用R树索引的方式来加快检索的速度，主要加速的是最小覆盖区域矩形
主要步骤如下：
首先通过R树迅速判断用户所在位置（粗红点）是否被外包矩形覆盖（如下图，红色点代表用户所在位置；R树平均查询复杂度为O(Log(N))，N为多边形个数）。 如果不被任何外包矩形覆盖则返回不在地理围栏多边形内。 如果被外包矩形覆盖则还需要进一步判断是否在此外包矩形的多边形内部，采用上文提到的射线法判断。
4.2 分配订单
不同于外卖和网约车的场景，二手回收场景的订单密度和订单量并不是非常大，那低成本地实现快速订单分配就极其重要。基于现状，还是通过围栏的匹配算法，就能找到在当前服务区域内提供服务的上门小哥。
简单匹配流程
大体步骤：
将工程师根据每个人的服务区域挂载相对应的围栏下边。 用户下单后，根据订单的经纬度匹配到围栏。 找到围栏下边挂载的工程师，再根据相应的业务规则、特殊场景分配工程师。
5 基于定位服务的路线规划、自主订单调度
5.1 路线规划
随着订单的数量越来越多，履约效率成为整个履约过程中极为重要的一环。而提高履约效率，最为关键的是要判断订单和人之间的距离。具体讲一下整个根据距离来履约的演进过程：
根据两点间的坐标点计算直线距离
这是所说的直线距离，实际为球面距离，我们的地球是一个球体，球面上的两个点，可以通过纯数学的几何公式进行计算，感兴趣的可以自行搜索公式和推导过程。
根据两点之间计算和订单的距离是最简单、粗暴的方法，但是这个又会带出另一个问题，针对一些复杂地形，只是计算直线距离会带来极大的误差（如遇到河流，桥梁等等，尤其像重庆这样地形复杂的城市），如图所示：
根据第三方导航服务计算距离
要计算两点间的真实距离，由于涉及到城市的道路规划，复杂路线，自己去实现一套智能导航系统不太现实，所以我们采用的是接入第三方的导航服务来实现人和订单距离之间的智能导航。但是随之也产生了问题，由于业务的特殊性，复杂性(经常需要批量调用、根据复杂业务规则计算等等)，如果用同步请求第三方的导航服务的方式来做智能规划，这样请求服务的耗时会明显的增加，显然这样不能满足我们性能的要求。所以针对这种场景，我们的现在的方案如下（简图）：
具体步骤如下：
用户下单。 根据LBS服务将订单分配到工程师身上。 系统根据工程师身上的所有订单情况（实际业务场景订单的属性）做订单规划。 异步调用第三方服务，根据导航结果做计算。 再根据规则，综合计算真正的路线规划，再将数据放入缓存中。 工程师从缓存中查询相关的信息。
5.2 自主订单调度
随着订单量越来越多，实际情况也越来越复杂，后台系统分配规则，计算再合理也有满足不了实际情况的时候。这个时候，一线的人员自主的对订单进行调度分配，这样可以使得整个业务流程更加的顺畅。
场景1：工程师A有一订单A，但是现在工程师A临时有事过不去，发现工程师B正好在订单A附近，这个时候相联系工程师B将订单转过去。 场景2：工程师A刚履约完订单A，发现这附近刚好有一订单B属于工程师B，为了提高效率，工程师A可以联系工程师B将订单抢过来。
简图如下：
那如何快速地找到在某个工程师附近的订单，或者某个订单附近的工程师呢？显然，暴力遍历是可以实现的，但是明显性能是完全不能满足我们的要求的。基于这个场景，我们使用了ES的GEO来实现，将工程师实时的位置信息，订单的地址信息存入ES，利用ES来快速计算。
简单来说，就是工程师定时上报地址经纬度，存入ES。用户下单后，将订单地址的经纬度也存入ES，查询的时候再直接使用ES提供的GEO查询范围内的数据。
"filter": [{
"geo_distance": {
//查询中心点
"location": {
"lat": 20.12345,
"lon": 100.223344
}
//范围
"distance": "3km",
"distance_type": "arc",
}
}
}]
其实很多的第三方存储引擎都提供了GEO的服务，如MySql，Redis，ES这里就不展开讲了，有兴趣可以自行搜索资料。
6 总结
本文描述了转转上门履约业务基于LBS的几种不同场景的简单使用，当然除了上面描述的场景，还有更多的复杂的使用需要根据不同的业务的场景做特殊，定制化的处理。随着数据量的不断增加，业务的实现方式，检索的方式也是需要不断的优化，服务也需要不断的升级，为业务保驾护航。
7 参考文档
https://www.cnblogs.com/lbser/p/4471742.html https://my.oschina.net/1024bits/blog/782820 https://www.cnblogs.com/yym2013/p/3673616.html https://blog.csdn.net/WilliamSun0122/article/details/77994526 https://toutiao.io/posts/4as8i9/preview
关于作者：
刘山，转转履约业务研发工程师
想了解更多转转公司的业务实践，欢迎点击关注下方公众号：