网格化位置的最近距离匹配

Scroll Down

时间过的有点久了,大约半年前有个校友问了我一个问题,今天刚好想起来就随手记录下来。

问题的简单描述是这样的:

在外卖订单派单中,如何派发给距离店家2公里的所有的外卖配送员?

这个问题在我们日常使用共享单车或者打车应用中经常看到,在地图上显示了最近距离用户一定距离范围内的所有共享单车或司机的位置。

我们这里就用GeoHash来讨论下最简单的应用情况

GeoHash算法

Geohash是一种地理编码,由Gustavo Niemeyer发明的。它是一种分级的数据结构,把空间划分为网格。Geohash属于空间填充曲线中的 Z 阶曲线(Z-order curve)的实际应用。

通过GeoHash,我们可以在地图上划分出需要一个个的矩形区域,GeoHash字符串的长度决定了划分区域的大小,同时对应的也决定了矩形区域的长宽。 同时根据Z曲线的性质,一个点附近的点位置,他们的hash字符串总有一个公共前缀,并且公共前缀的长度越长,这两个点距离越近。这一特性通常我们可以用来进行比较快速的邻近点搜索

那实际上这个问题就转变为一个基于GeoHash在给定地点的附近位置的搜索问题

在给定分辨率的情况下是能够快速的输出临近的骑手位置的,只是在其中要考虑下GeoHash的缺陷,就是明明是两个很近的点 但是Hash字符串差异很大的情况,需要把店铺位置周围的几个分块的Hash值都拿到再做相应计算。

那如果只考虑再一个2KM范围内的长方形区域块中快速加载出在这个区域中的骑手,其实在给定分辨率的情况下,在以前的思考中,有想尝试下Hash值二进制的异或运算,异或运算后的数值它总是小于一个给定分辨率对应的数值,并根据此可快速排序并把2KM内返回离店铺最近的骑手数据。

美团有可能是采用的Google S2的正方形网格划分方案或者是用其他网格划分方案来做的(因为曾经看到过美团有相关并行计算思路优化的方案,当然在外卖这种对poi数据要求比较高的场景,还会涉及到对数据的清洗和配送相关场景的调整监控,在最小运力最快派送上去做平衡)。

Uber是采用的自开发的六边形网格划分。

滴滴未知,有可能是自开发方案。

去哪儿是用的四叉树索引来对地理位置进行四分并建多边形索引(酒店类的poi在通过城市维度hash之后,poi数据集不会很大。在内存中建立一颗四叉树,最后通过四叉树索引来进行poi的召回)。