浅谈派单算法：滴滴出行里车主是如何接到平台派单的？( 二 ) _派单算法

▍如果是1个订单、1个司机

文章插图

看上去似乎就非常简单了，我们直接把这个订单指派给这个司机就好了嘛。
“那么为什么有时候附近有辆空车却不能指派给你呢？”
【浅谈派单算法：滴滴出行里车主是如何接到平台派单的？】实际线上的系统会比这里稍微复杂一点，原因一方面有可能是司机正好网络出现故障，或者正在和客服沟通等等导致司机无法听单，另一方面的原因是并不是所有的车都能够符合服务你订单的要求，最基本的策略其实是人工设定的规则过滤。举几个最基础的例子：

规则A：快车司机不能接专车订单
规则B：保证司机接单后不会通过限行限号区域
规则C：为设定实时目的地的司机过滤不顺路区域
规则D：为只听预约单司机过滤实时订单
规则E：同一个订单只会发给一个司机一次
......

必须澄清的一点是这里的规则并不会造成分单时不公平的效果，而完全是为了业务能正常运行而设立的，这些策略承担着保证业务正确性的重要职责。
▍如果是1个订单和2个司机
假设这两个司机都能够分配给这个订单，那么我们来看系统应该是如何分配的。
首先第一种情况是，同一时刻下，这两个司机和订单的距离都完全一样的情况下，系统应该如何分配？

文章插图

刚才也说到，我们平台订单分配最大的原则是就近分配，当距离完全一样的情况下，当前我们系统上会主要考虑司机的服务分的优劣，服务分较高的司机会获取到这个订单（注：服务分对分单的影响，简单的理解可以换算为多少分可以换成多少米距离的优势，这块不是今天的重点就不展开介绍），再说明一下，系统用到的是地图的导航距离，而非人直观看到的直线距离，有时候差一个路口就会因为需要掉头导致距离差异很大；并且如果司机的定位出现问题，也会出现分单过远的情况。
那么我们来看第二种情况，如果A司机离的近， B司机离的远，系统怎么派？

文章插图

这就简单了，根据就近分配的原则，我们会把A司机分配给这个订单。嘿嘿~~ ，假设我们再把问题设置的更加实际一点，当订单发出时， B司机已经在线并空闲，但是A司机还没有出现（没有上线，或者还在送乘客），但再过1s ，离得更近的A司机突然出现可被分单了，假设我们使用先到先得的贪心策略，那么B司机就会被分给这个订单，那就违背我们希望就近分单的目标了：（。所以看上去简单，但实际情况下，算法还需要变的更好一些，这个问题我们把它叫做派单中的时序问题，我们后面再来看怎么解决。
▍如果有N个乘客、M个司机
最后我们来考虑最复杂的多对多的情况，这也是线上系统每天高峰期都需要面对的挑战，我们一般把这种情况会形式化为一个二部图的匹配问题，在运筹领域也叫做matching的问题，如图所示：

文章插图

我们再把这个问题具象一点，假设这个时候我们有20个乘客，有20个司机，这些乘客都可以被这20个司机中的一个接驾，我们的系统需要把这20个乘客都分配出去，并且让大家的总体接驾的时长最短。听上去是不是有点复杂？我们套用下组合数学的知识，这其中可能的解法存在20的阶乘那么多， 20的阶乘是什么概念呢？20*19*18*…*1= 2432902008176640000 ，这个数巨大无比，想要完全的暴力搜索是绝对不可能的。这里需要更聪明的办法。
▍如果有N个乘客、M个司机，一会再来几个乘客和司机？
这就是派单问题最大的挑战，我们不仅仅需要当前这个时刻的最优，我们要考虑未来一段时间整体的最优，新来的司机和乘客会在整个分配的网络中实时插入新的节点，如何更好的进行分配也就发生了新的变化，所以如何考虑时序对我们非常重要，这个问题在业内也被称为Dynamic VRP问题，这个Dynamic也就是随时间时序变化的意思，这也就是为什么，滴滴的派单问题远复杂于物流行业的相对静态的货物和路线的规划问题。假设我们知道了未来供需的完全真实的变化，仿真告诉我们，我们的系统有可能可以利用同样的运力完成1.2~1.5倍的需求量，这也是派单算法的同学持续为之努力的方向。