转转上门履约的LBS实践

基于位置的服务（Location Based Services，LBS），是利用各类型的定位技术来获取定位设备当前的所在位置，通过移动互联网向定位设备提供信息资源和基础服务。首先用户可利用定位技术确定自身的空间位置，随后用户便可通过移动互联网来获取与位置相关资源和信息。LBS服务中融合了移动通讯、互联网络、空间定位、位置信息、大数据等多种信息技术，利用移动互联网络服务平台进行数据更新和交互，使用户可以通过空间定位来获取相应的服务。,转转上门履约业务主要依托于转转C2B，针对3C数码产品进行上门回收，为用户提供快速，精确的上门服务。简单流程图如下：,,,具体步骤:,,基于二手3C数码场景，并不能做到全国每个城市，每个角落都支持上门小哥上门回收，所以精准地判断用户地址是否支持上门回收对业务来说至关重要。,,,简而言之，就是根据用户下单的地址转换成对应的经纬度坐标，根据经纬度判断当前点是否在围栏中，从而判断用户的地址是否支持上门履约。,但是将全国的地图切割成一个个不规则的多边形，在成千上万的不规则图形中，如何快速地判断某一个经纬度在哪一个围栏之中？目前我们采用的是两段匹配的方式。,如下图所示，任何一个不规则的多边形都能用一个矩形将其框住，只需要获取右上角的坐标，和左下角的坐标就能构建这个矩形，从而快速的判断用户地址经纬度是否在这个矩形里边，快速过滤掉大部分的干扰围栏。,,射线算法：从待判断的点向某一个方向引射线，计算和多边形交点的个数，如果个数是偶数或者0，则点在多边形外，如果是奇数，则在多边形内（当然，一些特殊情况需要单独判断，比如点刚好在顶点或者边上）。如图所示：,,根据射线法，就可以精准判断坐标是否在围栏内。,目前常用的判断点在多边形内的方法,当然，还有其他的算法，如果感兴趣可以自行搜索相关资料。我们根据业务场景需求以及对算法的熟悉，理解程度，最终选择射线法作为匹配算法。为了计算的速度，所有的计算过程都是基于内存运算。,,大体上分为两个阶段：,随着围栏的数量越来越多，暴力遍历的寻找方式会大大的降低检索的速度，所以这里我们采取的是利用R树索引的方式来加快检索的速度，主要加速的是最小覆盖区域矩形,,最小覆盖区域矩形进行R树索引,主要步骤如下：,,R树查询示例,不同于外卖和网约车的场景，二手回收场景的订单密度和订单量并不是非常大，那低成本地实现快速订单分配就极其重要。基于现状，还是通过围栏的匹配算法，就能找到在当前服务区域内提供服务的上门小哥。,简单匹配流程,,大体步骤：,随着订单的数量越来越多，履约效率成为整个履约过程中极为重要的一环。而提高履约效率，最为关键的是要判断订单和人之间的距离。具体讲一下整个根据距离来履约的演进过程：,,这是所说的直线距离，实际为球面距离，我们的地球是一个球体，球面上的两个点，可以通过纯数学的几何公式进行计算，感兴趣的可以自行搜索公式和推导过程。,根据两点之间计算和订单的距离是最简单、粗暴的方法，但是这个又会带出另一个问题，针对一些复杂地形，只是计算直线距离会带来极大的误差（如遇到河流，桥梁等等，尤其像重庆这样地形复杂的城市），如图所示：,,要计算两点间的真实距离，由于涉及到城市的道路规划，复杂路线，自己去实现一套智能导航系统不太现实，所以我们采用的是接入第三方的导航服务来实现人和订单距离之间的智能导航。但是随之也产生了问题，由于业务的特殊性，复杂性(经常需要批量调用、根据复杂业务规则计算等等)，如果用同步请求第三方的导航服务的方式来做智能规划，这样请求服务的耗时会明显的增加，显然这样不能满足我们性能的要求。所以针对这种场景，我们的现在的方案如下（简图）：,,具体步骤如下：,随着订单量越来越多，实际情况也越来越复杂，后台系统分配规则，计算再合理也有满足不了实际情况的时候。这个时候，一线的人员自主的对订单进行调度分配，这样可以使得整个业务流程更加的顺畅。,简图如下：,,那如何快速地找到在某个工程师附近的订单，或者某个订单附近的工程师呢？显然，暴力遍历是可以实现的，但是明显性能是完全不能满足我们的要求的。基于这个场景，我们使用了ES的GEO来实现，将工程师实时的位置信息，订单的地址信息存入ES，利用ES来快速计算。,,简单来说，就是工程师定时上报地址经纬度，存入ES。用户下单后，将订单地址的经纬度也存入ES，查询的时候再直接使用ES提供的GEO查询范围内的数据。,其实很多的第三方存储引擎都提供了GEO的服务，如MySql，Redis，ES这里就不展开讲了，有兴趣可以自行搜索资料。,本文描述了转转上门履约业务基于LBS的几种不同场景的简单使用，当然除了上面描述的场景，还有更多的复杂的使用需要根据不同的业务的场景做特殊，定制化的处理。随着数据量的不断增加，业务的实现方式，检索的方式也是需要不断的优化，服务也需要不断的升级，为业务保驾护航。,关于作者：刘山，转转履约业务研发工程师