派单流程   仅供参考

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

我们把乘客打车分成了 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）总结