关于一个派单的算法问题请教

Question

现在公司要做一个打车软件，在用户打车的时候，以用户的所在地点为圆心，以10公里为半径找出在10公里内距离和评分最优的司机来接单。请问大家有何想法呢？

Answer 1

你这个问题，本质上是个两集合求距离关系的问题。因为评分数据相对是比较固定的。首先要解决的是任意两个不同集合中元素之间距离的问题。 哈。 

一种简单的方法是查表法。例如20km * 20km的区域，按照50m x 50m为网格，则有400x400的网格点（物理空间），不同网格点之间的路径距离做表待查询。实际上有些网格点可以优先剔除。

以上说的是，当明确A集合的一个元素位置和B集合的一个元素位置，求两者之间距离的问题。

余下是确实谁与谁的关系。哈。说人话就是，究竟基于用户计算出最优司机的列表还是基于司机计算出最可服务的用户列表。

这个原则上哪个集合元素少，就用哪个集合作为主对象，例如用户远比司机上，则基于用户，计算出针对每个用户的最优司机列表。但实际设计需要根据数据和其他方面的问题综合考虑。

不失一般性的给出一个算法思路。

以更大区域相对（50x50），构成一个司机子集。这些子集之间原则上是可以存在重复元素的（子集覆盖的物理空间存在重叠）。然后以新用户为主对象，在其落于子集中再做分析计算，确定基于用户的最优司机列表。

上述设计，主要考虑，司机的信息相对已知，容易实现基于空间做预分类。哈。

Answer 2

这个问题好像听说过，比如滴滴打车，用的是haskell？好像是这门语言。

它的后台算法是把全国的地图分成无数个六边形，里面包含了精度、纬度等等很多信息，然后根据算法即时提取范围内的司机。。。。。。然后。。。。。

Answer 3

有两个关键指标，距离和评分，要实现匹配算法，你需要指定这两个参数的权重，写出一个公式根据这两个参数得出一个匹配分数。可以后台实时的计算匹配数，你开始匹配的时候只管排序获取就行了。也可以在分配的时候全部计算一遍，但这样耗时太大，建议距离和评分变化之后立即计算评分。