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

　　希望讲的不要太像数学课，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），需求数量为succOrderfreeCar。
　　当succOrder小于freeCar时，本格子是供给格子（D），供给数量为freeCarsuccOrder。
　　我们的目标就是从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）最后的供给与需求如何做匹配
　　假如我们找到了真实的供给和需求后，如何找到一种匹配方法，使得最后供给与需求之间的调度代价（调度距离总和）最小。
　　例如在下面的例子中，我们的调度应该是（a21、b11）还是（a21、b11）？
　　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是真正的需求和供给。下一步计算时，就会产生两种匹配结果，（a21、b11）和（a21、b11），这两种结果哪种是最优的呢？
　　假设他们之间的距离如下图：
　　a2距1为6km，b1距1为7km，a2距1为3km，b1距1为5km。
　　如果按照（a21、b11）进行匹配，距离总和为6713km。
　　如果按照（a21、b11）进行匹配，距离总和为358km。
　　所以第二种匹配方案距离总和最低，成本最小。利用km算法可快速计算出距离总和最低的匹配方案。
　　实操中解的一些有趣的case
　　1。抢单失败的提示
　　事情是这样，在抢单列表中，司机可以点击抢单按钮进行抢单，但是，会有多种情况导致抢单失败，其中有两类：
　　点击抢单时，订单已经被别人抢走；
　　点击抢单时，订单已经超时（系统有自动派单机制兜底，订单在N分钟内没人抢单判定为超时，系统会自动派单）。
　　对于这样的情况，在一开始都给司机做出了明确的反馈：
　　订单已被抢
　　订单已超时
　　但是，上线后反馈却很不好：明明已经超时了，为什么还要显示在页面上让我们抢，抢又抢不到！确实，这样的做法很不好。抢单是一个对效率要求很高的环节，在这样的反复抢单失败中，严重损害了司机抢单的积极性。
　　不得已，只能在待抢单列表中增加了定时刷新的机制，每隔1分钟刷新列表。这样可以过滤掉部分已经被抢或已经超时的订单，但还是有部分订单因为超时而抢单失败。最后只能做了一个小小的欺骗：将订单已超时和订单已被抢的提示都统一成了手慢了，订单已被抢。上线后客服收到的此类反馈骤降，但其实抢单结果上没有任何差别
　　从心理学来说：人们在归因的时候，更容易得出自己想得到的结论，而不一定是真实的结论。并且出于心理上的自我保护，人们会将导致失败的外界原因放大，而将自己个人的原因淡化。
　　当因为订单超时导致抢单失败时，司机会抱怨产品的设计问题（外部因素），但是同样的结果（问题本质并没有得到改善），“欺骗”司机是因为自己手速慢了，导致订单被抢，却没人再抱怨了（个人因素）。不但没有抱怨了，反而看到订单的时候都及时去抢单了，不再挑三拣四，订单处理的整体效率还得到了提升
　　2。如何在拼车定价时做到大家都满意
　　机场火车站是一个任何时候都需求旺盛的地方，在网约车政策越来越收紧的情况下，供给越来越跟不上需求，因此在非专车品类也推出了拼车这种形式。
　　但是，拼车天然会有一个问题，那就是拼车的人该如何分担拼车费用呢？举个栗子大家就明白啦
　　熊大、熊二和光头强都下了飞机打车回家，按照三者的目的地，计算出拼车总价是18元，如果不拼车，熊大需要6元、熊二需要11元、光头强需要15元。
　　光头强说：咱们各出6块吧！
　　熊大听了怒了：我自己打车回家就6块，跟你俩货拼还是6块，凭啥！
　　熊大琢磨了一会：要不这样吧，第一段的钱咱们3个人平分，第二段的钱你们两个人平分，最后一段就光头强自己掏了吧。
　　熊二和光头强一听笑了：我俩为了你绕道，居然还要帮你平分你那部分的钱，不拼啦！不拼啦！
　　熊二说：用我清华池学的博弈论给一个方案吧，假设熊大打车回家途中先后遇到我和光头强，当然也有可能先遇到光头强，再遇到我，可能出现的情况如下：
　　补充一下，从熊大家到光头强家直线距离的价格为11元。
　　这里的计算思路是：谁先来的谁付钱，后来的补上多出来的钱。
　　那么以Case2来举例：
　　熊大先要回家，所以熊大要付6元；这时光头强加入了，就要补上从熊大家到光头强家的11元；最后熊二只要付18（611）1元。
　　同理可以推导出6种情况下每个人的支付金额：
　　因为每一种情况出现的概率都是相等的，所以平均计算后，熊大需要支付2。83元、熊二需要支付5。33元、光头强需要支付9。83元。
　　熊二讲完，大家都服了
　　这个理论其实是博弈论三位大神之一Shapley的经典理论，称为沙普利值（Shapleyvalue），通过考虑各个代理（agent）做出的贡献，来公平的分配合作收益。代理i的沙普利值是i对于一个合作项目所期望的贡献量的平均值。
　　具体来说，一个合作项目C是由一些代理（Ag｛1，2，，n｝，n2），和每个代理在这个合作项目中所做的贡献量的特征方程v（C）k（（iC）xi）表示。
　　3。派单or抢单，哪种才是对平台司机乘客更好的方式
　　与滴滴相反，我们是经历了一个先是全部走平台派单，后来部分改为抢单的过程。
　　因为早期，全部是自营司机，领取的是基本工资绩效，他们的每天的工作都是按照拼台的安排来进行，采取派单能将平台的效率最大化。
　　后来，接入了兼职、优驾、出租车等非自营司机，这部分司机习惯于多平台听单，如果还是强制派单，很容造成流失，所以针对这一部分采取的抢单。
　　相较而言，滴滴早期切入市场时，采取的抢单，具有绝对话语权，就改为派单了