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

2022-05-02 20:32发布

希望讲的不要太像数学课,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算法可快速计算出距离总和最低的匹配方案。



实操中解的一些有趣的 case1. 抢单失败的提示

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


  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协议