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

理查德1986 发布于 2017/01/19 23:30
阅读 2K+
收藏 1

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

加载中
0
中山野鬼
中山野鬼

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

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

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

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

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

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

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

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

中山野鬼
中山野鬼
回复 @理查德1986 : 评分的这个好说,仅仅是个权重。你放在确定子集后进行再排序就足够了。哈。
理查德1986
理查德1986
你给出的思路应该就是解决了距离上面的问题,但是如果结合评分来选择是不是需要对某个范围内的在进行排序筛选?
1
MyronLee
MyronLee
动态规划
乌龟壳
乌龟壳
四个字就回答了题主所有问题了
0
大洋的顶端
大洋的顶端

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

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



理查德1986
理查德1986
上网看了下,确实滴滴后台是用haskell这种来做这个,不过一般小企业搞这种打车软件我想应该还是用回简单的那种排序方法来解决派单问题了。
0
zigzagroad
zigzagroad
在SQL中调用自定义的数据库函数计算距离 来获得指定公里数以内的司机,再用程序对评分进行筛选(或者也可以在SQL中筛选,看逻辑复杂度)。
0
zigzagroad
zigzagroad
初期来说,线上的司机不会太多,所以暂时可以不考虑计算性能问题。
0
大洋的顶端
大洋的顶端

引用来自“zigzagroad”的评论

在SQL中调用自定义的数据库函数计算距离 来获得指定公里数以内的司机,再用程序对评分进行筛选(或者也可以在SQL中筛选,看逻辑复杂度)。

 大哥,你这是天天研究数据库SQL语句吧,全国目前有1800W-2000W滴滴司机,平均10秒写入一次数据,这是需要多大的分布式构架,数据库才能受得了?

而且顾客打车的时候是即时把信息发送到服务器,假如服务器从数据库用SQL语句即时筛选,这样下来数据库还受得了吗?

而且现实中复杂的网络环境,地址位置不停变换,处理订单的复杂性等等,这会严重影响筛选结果。

况且SQL语句的排序、筛选最终的实现还是底层的算法。

假如滴滴搞SQL语句筛选,那滴滴离倒闭不远了。

zigzagroad
zigzagroad
滴滴 刚上线时是没有上千万司机的。况且除了距离这一个筛选条件,还可以加上“城市”条件去筛选司机(听说 北京 只有20多万出租车司机)。商业上是首先验证商业模式;软件部分基本上达到 可用 就可以了(软件不可能一上来就是 大而全 的系统)。
0
江依旺85847
江依旺85847
mongo可以支持最近多少km排序筛选,新版的redis也支持
0
inuxor
inuxor

2分钟想了下,这个事要想快,必须得是打格子啊

思路就是司机端不断发送经纬度信息到服务器,服务器根据这个经纬度不断更新该司机当前所在的格子编号。当用户端发送一个打车请求到服务器,则根据用户经纬度找到所在格子,这时则可以定位用户所在格子(以及可能周边格子)所有的司机,剩下的就是有限数量的线段距离计算了,如果需要综合司机评分,无非设定一个加权算法,比如最简单的每100分可以顶多少米。

0
tunghsing
tunghsing
有两个关键指标,距离和评分,要实现匹配算法,你需要指定这两个参数的权重,写出一个公式根据这两个参数得出一个匹配分数。可以后台实时的计算匹配数,你开始匹配的时候只管排序获取就行了。也可以在分配的时候全部计算一遍,但这样耗时太大,建议距离和评分变化之后立即计算评分。
理查德1986
理查德1986
你的想法和昨晚想到的差不多,当时想到就是做一个加权平均数然后排序就好啦。后来想到距离和评分两者又是相反的,例如权重都是50%,然后距离越大则评分越高。但是早上和同事讨论的时候想到我距离应该是取负值就好啦。突然觉得自己还是有点笨的啦。
0
程序员孟帅
程序员孟帅

MongoDB有2D空间索引

https://docs.mongodb.com/manual/applications/geospatial-indexes/

db.collection.find( { location: { $near: [lng, lat] }
    }
)
也可以设置半径

{
   <location field>: {
      $geoWithin: { $center: [ [ <x>, <y> ] , <radius> ] }
   }
}





程序员孟帅
程序员孟帅
回复 @理查德1986 : 那你研究下这个吧,java 来进行mysql查询,这样也是可行的。 http://janmatuschek.de/LatitudeLongitudeBoundingCoordinates
理查德1986
理查德1986
公司那个用的是Mysql呢,估计只能在java端实现了
OSCHINA
登录后可查看更多优质内容
返回顶部
顶部