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

　　希望讲的不要太像数学课，enjoy~
　　派单流程
　　首先整体看一下司乘及背后的派单逻辑：
　　我们把乘客打车分成了 3 类场景：
　　立即叫车（A 流程）：用车时间距当前时间小于等于 N 分钟；
　　非高峰预约用车（B 流程）：用车时间距当前时间大于 N 分钟，但用车时间非高峰时间段；
　　高峰预约用车（C 流程）：用车时间距当前时间大于 N 分钟，且用车时间在高峰时间段。
　　A 流程
　　用车时间距当前时间小于等于 N 分钟的用车，会采取「立即派单」的方式：
　　找到所有符合条件的司机：上班状态、服务状态、距离、司机类型等；
　　司机排序：热区围栏号码、配置距离等；
　　派单：对于自营司机采取派单制，对于非自营司机采取抢单制。
　　B 流程
　　用车时间距当前时间大于 N 分钟，但用车时间处于非高峰时间段，会采取「叫车成功，到时再派司机」的方式：
　　是否超出该时段该围栏的预约上限，若超过会走超预约上限派单流程；
　　司机筛选、排序同 A 流程；
　　非当时分配司机的预约单，会有一个失败后每隔两分钟的轮询机制；
　　经过三轮轮询后仍未成功的订单，会转进人工处理。
　　C 流程
　　用车时间距当前时间大于 N 分钟，且用车时间在高峰时间段，会采取「预约单，立即派司机」的方式：
　　司机筛选：除与 B 流程相同的规则外，司机可以选择是否接听此类订单（风险较高）；
　　高峰订单主要集中在早、晚、凌晨，所以筛选司机是按照距司机家庭住址距离，而不是距当前位置距离；
　　也会采取 3 轮的派单轮询，与 B 流程不同的是，如果无人接单，派单会立即失败，不会进入人工派单。
　　热区排队
　　还有一个不得不提的流程是，针对机场火车站这类单大人多的围栏，这一区域的派单有两个最大的问题：
　　大家距离都差不多，为啥先派给他，不派给我？
　　司机都希望去捞一票大的，排很久接个小单会很不爽。
　　首先需要配置若干热区围栏，以便于后续规则的设计；
　　触发排队规则包含 3 种场景：空驶入队、服务入队、上班入队；
　　针对每个围栏会有围栏上限，超过上限时仅能排队，但不能切换到接单状态（防止司机在围栏等待过长时间）；
　　排队基本按照司机的入队时间，派单时的司机顺序与上述流程大致类似；
　　接单超时时长：司机主动驶处、接单成功等情况下会驶出热区，其中针对接单出队这种情况会设置一个接单超时时长，若司机在此时间范围内归队，则仍能保留原有排号，这样就解决了司机对接小单的抱怨。
　　当然，派单中遇到的问题远不只此，如超出预约上线就不派了么？车型降级怎么兼容？不同城市道路的限行问题 等等就不在此赘述，有时间可以另起一个话题来聊~
　　调度流程
　　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. 抢单失败的提示
　　事情是这样，在抢单列表中，司机可以点击抢单按钮进行抢单，但是，会有多种情况导致抢单失败，其中有两类：
　　点击抢单时，订单已经被别人抢走；
　　点击抢单时，订单已经超时（系统有自动派单机制兜底，订单在 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,v>是由一些代理（Ag={1,2,…,n},n≥2），和每个代理在这个合作项目中所做的贡献量的特征方程 v(C)=k（(∑i∈C) xi）表示。</ag,v>
　　3. 派单 or 抢单，哪种才是对平台司机乘客更好的方式
　　与滴滴相反，我们是经历了一个先是全部走平台派单，后来部分改为抢单的过程。
　　因为早期，全部是自营司机，领取的是基本工资+绩效，他们的每天的工作都是按照拼台的安排来进行，采取派单能将平台的效率最大化。
　　后来，接入了兼职、优驾、出租车等非自营司机，这部分司机习惯于多平台听单，如果还是强制派单，很容造成流失，所以针对这一部分采取的抢单。
　　相较而言，滴滴早期切入市场时，采取的抢单，具有绝对话语权，就改为派单了~