新闻资讯门户
互联网、云计算领域最新资讯
首页 > 互联网 > 产品经理

产品经理匹配策略:为什么打车软件不给你最近的车?

好久没有更新,最近大出行领域风起云涌,那么就趁着这个机会简单聊一下打车的匹配策略。

本身服务匹配算法是非常复杂的,要考虑多个因素,但是如果我们只看最基本的逻辑,服务匹配就是将多个服务者和多个用户之间进行匹配。这篇文章会简单介绍如何构建匹配度,同时具体如何对匹配问题求解。

1. 匹配度构建

匹配度的构建其实并不复杂,就是构造一个计算用户需求和服务者之间的相关性的方法。复杂的是确认清楚我们的目标是什么。介绍核心函数的构建我们仍然以打车为例。

比如在打车的时候,我们可以先思考下有哪些因素是乘客叫车的时候乘客比较关心的。首先乘客最关心的就是司机和乘客之间的距离。对于每个乘客而言,距离越近就意味着司机赶过来越快,等待时间越短,在大多数情况下,快速上车出发是乘客的第一需求。乘客关心的第二个问题是司机的服务,具体体现在乘客对于司机的评价和司机的服务单量上,用户评分越高的司机往往更能提供优质的服务,如果可以周围有大量司机可以选择的话,乘客期待评分更好的司机。对于司机而言,司机期待乘客的终点是热点地区,这样可以获得更高的收入,如果周围有大量的乘客,那么单纯从效率的角度看,我们更应该匹配目的地在时空价值更高时间域的订单。如果业务取向真的是上面分析的这样,那么用户和司机的匹配度函数就应该由三个因子构而成。不过当多个参数在同一个函数中的时候,就需要对每个参数进行有效的归一化和变形,才能让结果符合预期。

需要强调的一点是,当我们对每个用户和周围的司机都有相关度计算,可以知道对每个用户最合适的司机,也并不意味着所有用户都可以得到最合适的司机。这就回到了一个用户经常抱怨的问题:为什么打车软件不给我派最近的车?

即使核心函数中只有距离一个因子,也不一定会给每个用户都匹配最近的车。具体case如下图所示:

在左边的图中,距离用户A最近的车是a,在这种情况下可以给用户A派最近的车。但是如果如右边图所示,同时有两个用户呼叫,这种情况下,给用户A分配车辆a,会导致B分配到的车都会比较远。就应该给用户A分配车辆b,给用户B分配车辆a。而实际在设计的服务匹配方法中还需要考虑多种其他因素,比如服务、公平等因素,就更不可能给所有用户都分配最近的车。

从这个例子中看出,系统应该寻求的是整个系统匹配度最大化。下面我们会详细阐述可以用什么样的方法来达到系统的最优化。

2. 二分图匹配

二分图是图论中的一种特殊模型。 通俗解释的话,二分图有两个特点,在二分图图中的点可以分到两个互不相交的子集中,同时每条边都需要连接这两个子集。如果有这个定义去看的话,一段时间内,乘客和司机的匹配问题就是典型的二分图问题,两个集合分别代表司机和乘客,司机和乘客的匹配度则代表司机的边长。

在二分图中,有一个经典问题就是如何求二分图的最大匹配。最大匹配的定义就是任意交点只连接一条边的最优解。具体到打车问题中,就是寻找让整个系统叫做多的人叫到车,所有人和司机之前的匹配度之和最大。这也正是我们希望得到的线下交易系统最好的匹配结果。如果我们能找到二分图的最大匹配算法,就能用这个算法作为线下交易匹配的问题。

值得庆幸的是二分图问题是有典型的求最大匹配的算法的。二分图问题本质上也是线性规划问题,用线性规划的单纯形法也可以作为迭代方法。不过因为这种方法效率低下,工程上不会使用。在工程上使用最大流、匈牙利算法或者KM算法都可以作为最大匹配问题的解法,尤其是KM算法基本就是为了解决二分图这种特殊问题设计的算法。这三种算法在效率和原理上是基本通用的,这里涉及一些基础图论问题,就不对这些算法做数学展开,有兴趣的读者可以从网上查找KM算法相关资料。

当然,即使不了解KM算法的数学原理,但是并不妨碍我们理解使用这种方法。KM算法要求的两个集合中的不同点的匹配度作为边长,权重越大则代表匹配度越高。算法通过迭代会给出匹配度最高的匹配组合,也就是我们需要的全局最优解。在KM算法中,只要将所有我们需要的因素都考虑进入匹配度算法中,那么这个算法就可以每隔一段(比如10s)时间执行一次,每次服务者和用户退出匹配系统,也会有新的服务者和用户加入匹配系统,算法循环执行,不断匹配。

3. 给太长不看的朋友

打车的匹配策略就和男生和女生相亲一样。为什么不给所有男生自己最喜欢的女生,因为资源有限,一个女生也不能分给一堆男生。那么最好的结果就是每个人都找到差不多和自己匹配的人,让整个系统成双入对的情侣满意度总和最高。

那么回到打车的问题,为什么不给你最近的车,因为同时有一堆人想要最近的车,系统不能保证给每个人最近的车。那么最终系统的优化目标就变成了最大化整体的效率和体验指标。不给一个特定最近用户最近的车,是因为对于系统而言,最优化的目标是系统的最优化,不是针对每个人的最优化。

未经允许不得转载,或转载时需注明出处:西部数码新闻资讯门户 » 匹配策略:为什么打车软件不给你最近的车?
分享到:更多 ()

网友评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

中国领先的互联网域名及云服务提供商

为您提供域名,比特币,P2P,大数据,云计算,虚拟主机,域名交易最新资讯报道

域名注册云服务器