【转】关于滴滴智能调度的分析和思考

比眉伴天荒 2021-09-27 14:50 587阅读 0赞

[![96][]][96 1] [AnthonyD][96 1] 关注

2017.01.15 23:55\* 字数 3809 阅读 10743评论 1喜欢 47赞赏 3写这篇分析的背景是，工作上正在经历一个智能调度平台的搭建和设计，希望通过对于滴滴调度系统进行调研，来得出一些可借鉴的、优秀的设计方案。本质上来讲，一个好的调度系统，就是要解决资源最优利用的问题，这个在之前的文章做过简单的介绍,见[《调度系统的数学定义》][Link 1]。

> 它山之石，可以攻玉。

--------------------

01 滴滴的智能调度是什么

> 智能调度是整个滴滴的智能大脑和决策系统。
> 
> 核心思想是“激活闲置资源、中心调度、高效匹配”。

智能调度结合了大数据与机器学习，搭建滴滴交通和决策大脑，去年成立的滴滴研究院正在从事相关的实验和研究。滴滴交通大脑需要收集每个城市、每一时刻的所有交通出行相关数据，然后做出最优的决策（匹配、导航等），从而提高出行效率。

--------------------

02 体现在哪些地方

智能大脑主要渗透到以下各个环节：预测目的地、价格预估、时间预估、最佳路径匹配、司机和乘客匹配、订单分派、供需预测、预测乘客体验。

其中，司机和乘客匹配、订单分配是**滴滴智能调度的核心。**订单分配：在某个时刻有成千上万的乘客，同时也有成千上万的空闲车辆，要完成司机和乘客的最优匹配，最大限度提升匹配率和成交率。

--------------------

03 滴滴的调度算法

> 滴滴采用的抢单模式+滴米算法来形成自己的调度算法

首先说明一下抢单模式，相对于单独派单模式而言，这里就不得不说一下UBER的派单算法：

> Uber使用Google的S2 Geometry Library，S2能够将球体分为小区cell，每个小区有一个id，地球大致是一个球形。S2有两个重要特性：它能够定义每个cell的分辨率，它能发现需要覆盖区域的cell。Uber使用3,31平方公里的cell来分片其数据。所有这些让Uber降低乘客等待时间，司机的额外驾驶以及到达乘客招车点的时间(ETA)，当一个乘客使用Uber会发生什么？Uber会使用乘客的当时地理位置和S2的面积覆盖函数来寻找其周围适配的司机，Uber然后选择更短的ETA， Uber寻找的不仅是可搭载乘客的司机，而且还包括那些正在行驶到目标地可搭顺路车的司机。
> 
> ETA : 预计达到时间

**Uber主打是强制派单模式**，旅客通过Uber发出订单之后，需求会直接推送给某一位司机，如果司机在20秒内接单，则订单成交。如果20秒后司机仍不接单，那么系统会再把订单派给另外一位司机，继续等20秒，这种调度模式的优势是用户体验比较好，可以快速连接打车需求和司机端，但是这种调度模式依赖的匹配算法上的技术挑战会比较高，需要准确匹配“乘客需求－司机供给”的模型，每个订单通过算法（包括是否可用、以往评价等因素），决定了司机和车辆的推荐顺位，如果不能很好的匹配和推荐，会导致系统转派指标值大幅上升，但是从目前实际运行效果看，这种调度算法运行还算是不错的。

**与UBER派单模式存在不同的是，滴滴采用的是抢单模式**，乘客通过滴滴发出一个订单后，系统会把这个需求推送给多位符合条件的司机，如果所有司机都拒绝后才会进行第二轮派单。

![webp][]

滴滴的订单分派模式

这种模式的优势在于一开始就可以加大范围的推送给司机，由司机端来进行抢单，对于调度算法的准确性要求不算太高。

但是这带来了一个问题，如何有效规避司机“挑肥拣瘦”、最大程度让乘客订单呼叫都得到满足，让乘客获得更好的出行体验。”滴米“在司机端的体现是一种虚拟积分。对于司机来说，行驶里程多、道路状况好的‘好单’会扣除滴米，而行驶里程较少、道路状况拥堵的“坏单”的司机则会奖励‘滴米’。如果乘客发出叫车需求，而此时有两辆车与乘客的距离是一样的，那么司机谁的‘滴米’多，就是谁获得这个订单。所以这种方式严格的讲是基于抢单模式的一种补充，形成抢单+派单混合模式来调度。

滴米算法：https://www.zhihu.com/question/29953467

--------------------

04 滴滴专车派单架构

![webp 1][]

派单架构图

1. 乘客打车下单到下单队列，由派单引擎进行消费。

2. 根据匹配因子构建规则匹配相应产品，根据产品下配置的查询规则从db中按照地理位置索引粗粒度选择周边司机，经内存匹配和内存排序匹配司机，进行发单。

3. 司机接单后即可抢单并加入抢单队列，由派单引擎根据撮合规则进行匹配和排序，对乘客绑定的信用卡进行预授权并通知乘客下单成功。

--------------------

05 匹配因子

![webp 2][]

匹配因子

如何权衡订单是否匹配，合不合适，可以有多种办法解决：比如距离和时间上离你最近的司机。当然，权衡订单问题背后也包含个性化搜索，如个别用户可能只喜欢某一类车型、某一种类型的司机。尤其是女性用户在深夜十一二点，可能对车型和司机的要求比较高，这需要进行个性化匹配。

从乘客的角度，他可能希望自己发出打车指令，以他为圆心由近到远的发给司机，但是司机那边收单时不应该是这样的。从司机的角度看，他更希望的是先给他推送离他近的单，再是远一点的单，乘客和司机是两个圆，需要做比较复杂的匹配。

--------------------

06 滴滴的业务模型

![webp 3][]

简化的业务模型图

模型可以做得非常抽象和简单。比如，你想要打快车去机场，你就是一个需求方，你的需求会发到很多服务者那里去，服务者会根据特征进行一些匹配。最基本的特征是服务能力，如果服务者能够开快车并通过了能力验证，这个需求就有可能发给他。如果开出租车的也有能力开快车，但是他还没有在平台上验证这个能力，就只能开出租车。一个人可以验证很多服务，白天可以开快车，晚上可以做代驾，做不同的事。

服务和需求的匹配是通过计价模型和匹配策略来实现的。发送需求的时候需要选择计价模型和车的类型。快车和专车服务过程大同小异，但是价格差别很明显，专车价格会贵很多。通过匹配策略可以实现各种需求的匹配。例如，选择了拼车，这个需求会尽量匹配已经有拼友和顺路的车。如果选择专车，可以要求这辆车在指定时间来接人，这时候匹配策略会优化倾向这种方式。

滴滴所有的业务基本上都是以这种模式运转的，所有功能都是核心主干或者旁路，只要把业务模型抽象出来，基本上就能够满足大部分的业务了。

--------------------

07 滴滴的系统架构

![webp 4][]

系统架构图

滴滴的系统架构分为四层。

1. 最顶层是用户应用，每一个用户应用就是一个端，也就是用户所能看到的入口。

2. 然后是接入层，这是非常传统的结构，使用了Nginx，还专门做了TCP接入层。

3. 在业务层，Web是非常大的集群，有非常大的代码量，只对业务做了分割，有策略引擎、司机调度。

4. 在数据层，有KV集群、MySQL集群、任务队列、特征存储。

--------------------

08 技术上的挑战

从新闻上看到，今年 4 月份滴滴第一次突破 1000 万单一天，从籍籍无名到日订单超过1000万，滴滴花费了三年半的时间，相比之下，淘宝订单从零到千万却用了八年。

随着滴滴的体量越来越大：订单量、用户数、司机数量，每天产生的大数据，这些远远超出了人工规则的范畴。车辆的调度与用户匹配上比想象的更复杂，考虑的维度、复杂性、实时性超越了其他的行业。

比如如何分配订单的问题：

1. 人多人少的时候该如何做；

2. 高峰期、平峰期又如何做；

3. 在有需求时需要考虑附近乘客和司机；

4. 拼车时考虑乘客以及顺路的乘客；

5. 乘客、司机偏好等等。

这其中的变量和因素太多。同时由于滴滴数据量特别大，每一个乘客不只是让一个司机去匹配，而是需要跟周围上百个司机匹配。在任何一个时刻，滴滴的匹配量高达千万次以上，在一两秒钟完成上千万次的路径规划，这是一项非常大的挑战。

--------------------

09 思考

1. 打车平台真正要解决的就是如何提高匹配效率。滴滴初期可能更靠补贴和地推去抢市场，到了后期，匹配效率的提升是最重要的，只有匹配合适的出行资源，才能让客户的需求得到最大限度的满足。

同样的，在蚂蚁金服客户服务的智能调度当中，如何让用户的需求得到最准确的匹配和解决，就能最大限度的达成用户价值。

2. 支撑这套智能调度的能力包括，资源实时管控管控能力——地理信息实时更新（4秒钟发起一次请求）、订单热力图、供需预测（基于海量实时出行数据，以数十亿订单数据和数百万司机位置信息为基础，预测任意时间段各个区域的订单需求和运力分布状况）、运力调度（基于供需预测结果，大规模有序调动全城所有可用运力，实现资源最优化分配）

--------------------

**09 思考**

1. 智能调度的核心思想是“**激活闲置资源、中心调度、高效匹配**”。不管是滴滴的智能调度系统还是蚂蚁金服客户中心的调度平台，都是基于这样的原则进行设计的。

> 中心调度 体现在派单制上，即依据一系列因素算出一个或者一批效率最优解直接派单。

> 高效匹配 其中一个的关键点是按需分配，识别用户的准确需求，并在众多资源当中匹配到最合适的。

> 为了做到高效匹配，滴滴从每日上百万订单中积累了大量来自司机和用户的信息，包括它们的行程路线、行为习惯、特殊需求等等，除此之外，还有对整个城市交通状况的了解，做到提前预测需求，然后确保供应量与将要达到的需求量相匹配，这样可以以一个最佳的方式来激活闲置资源。

2. 打车平台真正要解决的就是如何提高匹配效率。滴滴初期可能更靠补贴和地推去抢市场，到了后期，匹配效率的提升是最重要的，只有匹配合适的出行资源，才能让客户的需求得到最大限度的满足。

> 同样的，在蚂蚁金服客户服务的智能调度当中，如何让用户的需求得到最准确的匹配，并且保证相应资源的可用性，解决了这些问题，才能能最大限度的达成用户价值。

3. 支撑这套智能调度的能力包括：

> 资源实时管控能力：地理信息实时更新（4秒钟发起一次请求），描述整体资源的情况，当用户发出用车需求后，第一时间根据资源情况，进行订单推送。

> 订单热力图：基于对历史数据的统计并结合实时订单数据，给出当前全城范围内订单密集区域的分布，给司机提供有价值的听单位置参考，提高听单概率并减少司机空驶时间。

> 供需预测：基于海量实时出行数据，以数十亿订单数据和数百万司机位置信息为基础，预测任意时间段各个区域的订单需求和运力分布状况。

> 运力调度：基于供需预测结果，大规模有序调动全城所有可用运力，实现资源最优化分配。

> 智能分单：在司机和乘客的历史数据中学习接单概率模型，提高司机和乘客的匹配度，利用运力的规模效应实时地从全局上最优化总体交通运输效率和乘客出行体验。

[96]: /images/20210923/30b09d1a1ef64ac3bfe63df9ac8bcf07.png
[96 1]: https://www.jianshu.com/u/160c1597155c
[Link 1]: https://www.jianshu.com/p/4113a710e40e
[webp]: /images/20210923/4d603227f1a241ff879b65018e05492b.png
[webp 1]: /images/20210923/21450fc11d76419bb639a88e4f6c9485.png
[webp 2]: /images/20210923/889625c23b2641e19280d66feacc828b.png
[webp 3]: /images/20210923/f55ffcf189314db2a60a11a5379803b0.png
[webp 4]: /images/20210923/42768d80d5ae4abca70cd90c96d06d57.png