结合有趣的实际案例讲解：网约车的派单、调度

希望讲的不要太像数学课，enjoy~

派单流程

首先整体看一下司乘及背后的派单逻辑：

我们把乘客打车分成了 3 类场景：

• 立即叫车（A 流程）： 用车时间距当前时间小于等于 N 分钟；
• 非高峰预约用车（B 流程）： 用车时间距当前时间大于 N 分钟，但用车时间非高峰时间段；
• 高峰预约用车（C 流程）： 用车时间距当前时间大于 N 分钟，且用车时间在高峰时间段。

A 流程

用车时间距当前时间小于等于 N 分钟的用车，会采取「立即派单」的方式：

1. 找到所有符合条件的司机：上班状态、服务状态、距离、司机类型等；
2. 司机排序：热区围栏号码、配置距离等；
3. 派单：对于自营司机采取派单制，对于非自营司机采取抢单制。

B 流程

用车时间距当前时间大于 N 分钟，但用车时间处于非高峰时间段，会采取「叫车成功，到时再派司机」的方式：

1. 是否超出该时段该围栏的预约上限，若超过会走超预约上限派单流程；
2. 司机筛选、排序同 A 流程；
3. 非当时分配司机的预约单，会有一个失败后每隔两分钟的轮询机制；
4. 经过三轮轮询后仍未成功的订单，会转进人工处理。

C 流程

用车时间距当前时间大于 N 分钟，且用车时间在高峰时间段，会采取「预约单，立即派司机」的方式：

1. 司机筛选：除与 B 流程相同的规则外，司机可以选择是否接听此类订单（风险较高）；
2. 高峰订单主要集中在早、晚、凌晨，所以筛选司机是按照距司机家庭住址距离，而不是距当前位置距离；
3. 也会采取 3 轮的派单轮询，与 B 流程不同的是，如果无人接单，派单会立即失败，不会进入人工派单。

热区排队

还有一个不得不提的流程是，针对机场火车站这类单大人多的围栏，这一区域的派单有两个最大的问题：

• 大家距离都差不多，为啥先派给他，不派给我？
• 司机都希望去捞一票大的，排很久接个小单会很不爽。

1. 首先需要配置若干热区围栏，以便于后续规则的设计；
2. 触发排队规则包含 3 种场景：空驶入队、服务入队、上班入队；
3. 针对每个围栏会有围栏上限，超过上限时仅能排队，但不能切换到接单状态（防止司机在围栏等待过长时间）；
4. 排队基本按照司机的入队时间，派单时的司机顺序与上述流程大致类似；
5. 接单超时时长：司机主动驶处、接单成功等情况下会驶出热区，其中针对接单出队这种情况会设置一个接单超时时长，若司机在此时间范围内归队，则仍能保留原有排号，这样就解决了司机对接小单的抱怨。

当然，派单中遇到的问题远不只此，如超出预约上线就不派了么？车型降级怎么兼容？不同城市道路的限行问题 等等就不在此赘述，有时间可以另起一个话题来聊~

调度流程

1. 空车调度系统介绍

系统自动预测当前城市未来半小时之内的车辆与订单的分布情况，以系统六边形格子为单位，将缺车区域与富余车辆区域相匹配，将富裕的车调往缺车区域，使该城市的订单需求能更好地被满足。

同时司机接到系统发起的空车调度单并按要求到达目的地后，可快速地接到订单，更好地完成自己的绩效。另外，系统调度无需人工干预，由系统经过一系列预测和计算之后，智能的、精准的匹配供需。

2. 调度目标

对每个格子，我们可以预测出其30分钟后的成功订单数succOrder，空闲车辆数freeCar。

我们定义：

• 当succOrder大于freeCar时，本格子是 需求格子(S) ，需求数量为succOrder-freeCar。
• 当succOrder小于freeCar时，本格子是 供给格子(D) ，供给数量为freeCar- succOrder。

我们的目标就是从D向S调度车，使得全城的需求格子的需求数尽量变为0，即，我们乘客的需求尽量被满足。在实际问题上，这并不容易，主要是因为以下三个问题。

3. 调度问题

调度主要遇到以下3个问题：

（1）派单距离会大于格子距离，一些调度不需要

六边形格子相对于传统的人工围栏来说，单位面积更小，反映城市的供需情况更加精确，然而带来的一个问题是，专车下单时，派单半径较大，可能会覆盖到周围的六边形格子，如图：

图中红色的a块是缺车区域，邻近的α、β是多车区域，如果直接按照简单的调度算法，就可能将α、β块的车辆调入a块。但a块在下单时向周围辐射的派单半径将α、β块都囊括其中，α、β块中的车辆能够接到a块的订单，所以没有必要发起空车调度。

我们需要界定，哪些供给与需求之间需要调车，而哪些不需要。

（2）真实的需求，真实的供给

例如，下图的三个连续的格子，经过预测，我们得知A区域是需求区域，需要3辆车：D（3），B区域是供给区域S（4），C是D（3）。A的派单距离只能看到B，看不到C。

那么，从A看来，自身的需求可以被派单区域内的B满足，整体看来应该是S（1）。但是如果我们多看一步，就会发现，B区域还要去满足C，使得B不能同时满足A和C。而如果我们“再多看一步”，也许C的旁边还有个供给区域S（4），也许没有。

为了计算A区域是否真的“不缺车”，我们“连锁反应的”考察了其相邻的相邻的格子，我们甚至可能要扫描全城的格子。

我们需要找出，如果经过全盘考虑后，那些格子是真实的供给，那些是真实的需求。

（3）最后的供给与需求如何做匹配

假如我们找到了真实的供给和需求后，如何找到一种匹配方法，使得最后供给与需求之间的调度代价（调度距离总和）最小。

例如在下面的例子中，我们的调度应该是（a2-γ1 、b1-δ1）还是（a2-δ1 、b1-γ1）？

4. 调度算法

针对问题1、2，我们使用了抹平算法；针对问题3，我们使用了km匹配算法。

六边形调度算法的流程可概括如下： 预测30分钟之后的供需分布 → 抹平算法抵消不必要的空车调度 → KM算法计算最小调车成本 → 发起调度。

（1）抹平算法

1）概述

抹平算法的目的是将邻近六边形块的供给和需求相互抵消，避免不必要的空车调度。抹平算法利用了二分图最大匹配的思想，将供给和需求单位看作左右子图进行配对，并利用匈牙利算法得到最大匹配。匹配完成后，二分图里所有边两端的顶点视为相互抵消，剩余的顶点即为真正的缺车和多车

2）例子

举例说明：

假设上图中，红色的a、b块是某城市所有的缺车区域，数字-3、-2代表a块缺3辆车，b块缺2辆车。蓝色的α、β、γ、δ为多车区域，分别富余2、1、1、1辆车。

对于a、b两个缺车区域而言，假设派单半径能够覆盖周围一圈六边形，那么α能够直接满足a块的订单需求，β块能直接满足b块的用车需求，所以α块无需发起向a块的空车调度，β块也无需发起对b块的空车调度，需要进行抹平计算。

给该城市所有缺车需求和富余车辆进行编号，如下图：

由六边形块的邻近关系得知，α1、α2可直接满足a块的用车需求，β1可直接满足b块的用车需求，根据这个关系，可以得出一个二分图如下：

图中虚线代表了可能的匹配关系，基于以上前提，可以计算一个最大匹配（即尽可能多地将左右子图两两匹配）。利用匈牙利算法，可以求得一个最大匹配，如：

匹配完成后，我们发现左图剩下了a2、b1，右图剩下了γ1、δ1 。也就是说a块和b块都还有一个需求没有被满足，γ和δ块仍然有多余的车辆：

到此，可以得出a块和b块真正的缺车数量为都为1，接下来可对于a、b和γ、δ进行下一步的匹配，生成空车调度单。

3）总结

抹平算法利用了二分图最大匹配的思想，将全城所有的供给和需求构建二分图，以六边形邻近关系做为二分图可能的匹配，并计算一个最大匹配来抵消邻近的供需。匹配完成后，剩余的顶点可视为真正的需求和供给，下一步再利用KM算法，计算调车成本最小的匹配关系。

（2）KM算法

1）概述

空车调度中，利用KM算法的核心目的是，对于多个需求和供给，寻求一种最优匹配，使调度的总成本（行驶距离）最小。

2）例子

上一步抹平算法的例子中，全城的供需分布经过抹平后，剩余a2、b1和γ1、δ1是真正的需求和供给。下一步计算时，就会产生两种匹配结果，（a2-γ1 、b1-δ1） 和（a2-δ1 、b1-γ1），这两种结果哪种是最优的呢？

假设他们之间的距离如下图：

a2距γ1为6km，b1距δ1为7km，a2距δ1为3km，b1距γ1为5km。

如果按照（a2-γ1 、b1-δ1）进行匹配，距离总和为6+7=13km。

如果按照（a2-δ1 、b1-γ1）进行匹配，距离总和为3+5=8km。

所以第二种匹配方案距离总和最低，成本最小。利用km算法可快速计算出距离总和最低的匹配方案。

实操中解的一些有趣的 case

1. 抢单失败的提示

事情是这样，在抢单列表中，司机可以点击抢单按钮进行抢单，但是，会有多种情况导致抢单失败，其中有两类：

1. 点击抢单时，订单已经被别人抢走；
2. 点击抢单时，订单已经超时（系统有自动派单机制兜底，订单在 N 分钟内没人抢单判定为超时，系统会自动派单）。

对于这样的情况，在一开始都给司机做出了明确的反馈：

• 订单已被抢
• 订单已超时

但是，上线后反馈却很不好：「明明已经超时了，为什么还要显示在页面上让我们抢，抢又抢不到！」确实，这样的做法很不好。抢单是一个对效率要求很高的环节，在这样的反复抢单失败中，严重损害了司机抢单的积极性。

不得已，只能在待抢单列表中增加了定时刷新的机制，每隔1分钟刷新列表。这样可以过滤掉部分已经被抢或已经超时的订单，但还是有部分订单因为超时而抢单失败。最后只能做了一个小小的欺骗：将订单已超时和订单已被抢的提示都统一成了「手慢了，订单已被抢」。上线后客服收到的此类反馈骤降，但其实抢单结果上没有任何差别~

从心理学来说：人们在归因的时候，更容易得出自己想得到的结论，而不一定是真实的结论。并且出于心理上的自我保护，人们会将导致失败的外界原因放大，而将自己个人的原因淡化。

当因为订单超时导致抢单失败时，司机会抱怨产品的设计问题（外部因素），但是同样的结果（问题本质并没有得到改善），“欺骗”司机是因为自己手速慢了，导致订单被抢，却没人再抱怨了（个人因素）。不但没有抱怨了，反而看到订单的时候都及时去抢单了，不再挑三拣四，订单处理的整体效率还得到了提升……

2. 如何在拼车定价时做到大家都满意

机场火车站是一个任何时候都需求旺盛的地方，在网约车政策越来越收紧的情况下，供给越来越跟不上需求，因此在非专车品类也推出了拼车这种形式。

但是，拼车天然会有一个问题，那就是拼车的人该如何分担拼车费用呢？举个栗子大家就明白啦~

熊大、熊二和光头强都下了飞机打车回家，按照三者的目的地，计算出拼车总价是 18 元，如果不拼车，熊大需要 6 元、熊二需要 11 元、光头强需要 15 元。

光头强说：咱们各出 6 块吧！

熊大听了怒了：我自己打车回家就 6 块，跟你俩货拼还是 6 块，凭啥！

熊大琢磨了一会：要不这样吧，第一段的钱咱们 3 个人平分，第二段的钱你们两个人平分，最后一段就光头强自己掏了吧。

熊二和光头强一听笑了：我俩为了你绕道，居然还要帮你平分你那部分的钱，不拼啦！不拼啦！

熊二说：用我清华池学的博弈论给一个方案吧，假设熊大打车回家途中先后遇到我和光头强，当然也有可能先遇到光头强，再遇到我，可能出现的情况如下：

补充一下，从熊大家到光头强家直线距离的价格为 11 元。

这里的计算思路是：谁先来的谁付钱，后来的补上多出来的钱。

那么以 Case 2 来举例：

熊大先要回家，所以熊大要付 6 元；这时光头强加入了，就要补上从熊大家到光头强家的 11 元；最后熊二只要付 18 -（6+11）= 1 元。

同理可以推导出 6 种情况下每个人的支付金额：

因为每一种情况出现的概率都是相等的，所以平均计算后，熊大需要支付 2.83 元、熊二需要支付5.33 元、光头强需要支付 9.83 元。

熊二讲完，大家都服了~

这个理论其实是博弈论三位大神之一 Shapley 的经典理论，称为沙普利值（ Shapley value） ，通过考虑各个代理（agent） 做出的贡献，来公平的分配合作收益。代理 i 的沙普利值是 i 对于一个合作项目所期望的贡献量的平均值。

具体来说，一个合作项目 C= 是由一些代理（Ag={1,2,…,n},n≥2），和每个代理在这个合作项目中所做的贡献量的特征方程 v(C)=k（(∑i∈C) xi）表示。

3. 派单 or 抢单，哪种才是对平台司机乘客更好的方式

与滴滴相反，我们是经历了一个先是全部走平台派单，后来部分改为抢单的过程。

因为早期，全部是自营司机，领取的是基本工资+绩效，他们的每天的工作都是按照拼台的安排来进行，采取派单能将平台的效率最大化。

后来，接入了兼职、优驾、出租车等非自营司机，这部分司机习惯于多平台听单，如果还是强制派单，很容造成流失，所以针对这一部分采取的抢单。

相较而言，滴滴早期切入市场时，采取的抢单，具有绝对话语权，就改为派单了~

作者：小明，不入流产品汪。写文章是为了督促自己独立思考，也想看看自己能坚持多久。

本文由 @小明 原创发布于人人都是产品经理。未经许可，禁止转载。

题图来自unsplash，基于CC0协议

作者暂无likerid, 赞赏暂由本网站代持，当作者有likerid后会全部转账给作者（我们会尽力而为）。


Support author:
Author's Filecoin address:
Or you can use Likecoin to support author: