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

28 评论 28973 浏览 215 收藏 8 分钟

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

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

1. 匹配度构建

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

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

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

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

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

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

2. 二分图匹配

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

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

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

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

3. 给太长不看的朋友

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

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

#专栏作家#

潘一鸣,公众号:产品逻辑之美,人人都是产品经理专栏作家。毕业于清华大学,畅销书《产品逻辑之美》作者;先后在多家互联网公司从事产品经理工作,有很多复杂系统的构建实践经验。

本文原创发布于人人都是产品经理。未经许可,禁止转载。

题图来自 Unsplash,基于 CC0 协议

更多精彩内容,请关注人人都是产品经理微信公众号或下载App
评论
评论请登录
  1. 从这第三点可以看出作者很懂用户了

    来自上海 回复
  2. 有道理

    回复
  3. 非常有道理,详细解释了“假、大、空”的原则

    来自上海 回复
  4. 赞太长不看。

    来自浙江 回复
  5. 抱歉,我是小白,我只想说借口。呵呵,一大堆闲置车辆在路口等着单,一大群人在等单,但是就是等单子的车依然在等,等车的用户依然在等。田忌赛马不行么?对等马,最后浪费了太多时间。一开始的计算公式也是这样的?刚开始为什么能够做到最近派车?滴滴美团一起火拼时候为什么派车都是几百米的?

    回复
  6. 我点赞,是因为这个文章有一个“给太长不看的朋友”

    回复
  7. 写的不错!

    来自广东 回复
  8. 像这样的策略是产品经理来弄还是技术自己去弄的

    回复
    1. 运营和产品制定思路,和技术讨论实现方案的边界

      来自北京 回复
  9. 你们想多了,其实最迟这是为了防止刷单,防止下单人和接单人都相互在一起的(引申告诉你,是同一个人,不要问我为什么知道,因为我在..

    回复
    1. 没错,确实是这样

      来自北京 回复
    2. 大神好

      回复
  10. 个人利益与集体利益

    回复
  11. 其实滴滴没有做附近的车本质并不是“因为同时有一堆人想要最近的车,系统不能保证给每个人最近的车。“其实从用户需求与场景出发思考
    1.因为用户出行的场景更多的关心是我需要在这里上车,而不是跑去附近找车上车,如果要做附近的车就意为要我去找附近的这辆车,滴滴是车找人,不是人找车
    2.一般滴滴司机都是开着车兜来兜去,并不是固定一个点停车在等待,车子位置变动就会导致技术上做的位置匹配的难度
    3.为什么共享单车、共享汽车都做附近的车,因为它们停车的位置是固定的,固定的位置就很容易找到车

    回复
    1. 说得好

      回复
    2. 回复
  12. 确实,打车软件确实要考虑这些方面的事情。

    回复
  13. 同時打車是個什麼情況?同一秒hais同一分鐘?

    回复
  14. 第2点没看明白,其中引用了几个算法的专业名词,可能平时没怎么接触过算法这一块,无法理解吃透;第1点说的通俗易懂;整体上这是一篇很不错的维度的分享,感觉作者为我们解惑、扫盲;

    回复
    1. 为什么你有会员头衔?

      来自广东 回复
  15. 全局最优的情况下可能会导致个别用户等车时间很长,但是总体来说会使得用户平均等待时间最低

    回复
  16. 了解到uber给用户派车永远是第二近的车,这是为什么呢?

    回复
  17. 抱歉,我是新手,不知道你在说什么,所以我表示支持一下

    回复
  18. 嗯。系统最优化,而不是个人最优化。受教了。也对打车算法有了一个初步了解。以后在设计系统的时候也要多考虑,争取做到系统最优

    来自江苏 回复
  19. 竟然涉及到了核心的算法,了解一下

    来自湖南 回复
  20. 算法要根据人性的变化而变化,推导的算法本身就不是很看好。

    来自北京 回复
    1. 你这个骗子,差点就相信你是小盆友了

      回复