深度强化学习的理论、算法与应用 - Stella2019/study GitHub Wiki

AI 科技评论按：7 月 29 日，YOCSEF TDS《深度强化学习的理论、算法与应用》专题探索报告会于中科院自动化所成功举办，本文为报告会第一场演讲，讲者为滴滴副总裁、AI Labs 负责人叶杰平教授，演讲题为「深度强化学习在滴滴的探索与实践」，AI 科技评论对本次演讲内容进行了重点整理。

据介绍，现在的滴滴平台每日路径规划请求 400 多亿次，每日新增 100+TB 的轨迹原始数据，每日处理数据量为 4875+TB。海量大数据也让滴滴能更积极地进行 AI 研究和布局。

据叶杰平教授介绍，滴滴的 AI 战略和布局主要围绕三个层面展开，最底层是基础的 AI 算法，比如强化学习算法、深度学习算法等；中间一层则是滴滴拥有的非常核心的 AI 技术，如语音、自然语言处理、图像等；而最上一层则是 AI 技术支持的应用—包括用技术创新提高出行平台的用户体验，以人工智能、大数据技术助力城市建设智慧交通网络，布局智能驾驶及新能源汽车等领域。

叶杰平教授还介绍了滴滴的智能决策中心滴滴大脑。首先，地图服务是交易引擎必不可少的一项基础服务，其中有两项重要的服务，一项是路径规划，另一项是 ETA（Estimated Time of Arrival）。比较理想的路径规划需要达到三个目标，一是最小化费用，二是最大化司机工作效率，三是优化交通系统效率。目前，Dijkstra 算法和 A star 算法是最常见的路径规划算法。为了更高效的提供服务，基于 Dijkstra 的改进算法 Contraction Hierarchies 也是目前业界的主流解决方法。ETA 服务可以应用于多项任务，比如估计到达时间，估计未来行驶时间，提供数字地图/导航的基础服务。滴滴自 2015 年自主研发了 ETA 的机器学习解决方案，经过了不断的更新迭代，目前主要使用深度神经网络的方法，并且设计了针对性的深度神经网络－宽深循环学习（Wide-Deep-Recurrent Learning），进一步提升了预估精度。相关算法实践也被写入《Learning to Estimate the Travel Time》论文，被国际数据挖掘领域顶级会议 KDD 2018 收录。

滴滴叶杰平教授还介绍了深度强化学习技术在滴滴智能派单中应用。由于派单的决定会影响未来的司机分布，且派单既要考虑司机收入还要保障用户体验，综合考虑这两个需求，叶杰平教授介绍了两种方法来解决派单问题，一种方法是 MDP（Markov Decision Process），另一种是深度强化学习。

首先是 MDP，MDP 在派单中的应用中分为两个部分，一是线上的计划过程，二是离线的学习过程，这两个过程结合了强化学习和组合优化。考虑到每一次匹配对未来是有影响的，这样可以能基于全天供需、出行行为预测，来考虑一天之内司机整体的效率。

离线学习——策略评估

线上计划——优势函数

最终的结果显示，这种基于强化学习和组合优化的派单算法能在确保乘客出行体验的同时明显提升司机的收入。相关模型实践论文也将在国际数据挖掘顶级会议 KDD 2018 中以 Oral 形式发表。

叶杰平教授介绍的第二种方法是深度强化学习，深度强化学习在应用中具有如下几个优点，一是对于实时供需变换具有良好的适应性，二是可以学习不同城市和时间段的数据，三是由于输入（上车地点，时间，目的地，内容）权重共享，所有泛化能力强。具体使用的深度强化学习模型是带有行动搜索的 DQN（Deep Q-network）模型。训练过程如下所示。

最后叶杰平教授比较了 DQN 和策略评估的方法，得到了两个结论，一是 DQN 对于服务是有优化的，二是城市越小，城市布局越简单，这种优化就愈加不明显。

以上就是雷锋网整理的叶杰平教授演讲的全部内容。

**

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

**

<!-- 文章内容 -->
<div data-note-content="" class="show-content">
  <div class="show-content-free">
    <div class="image-package">

1 2 3 4

写这篇分析的背景是，工作上正在经历一个智能调度平台的搭建和设计，希望通过对于滴滴调度系统进行调研，来得出一些可借鉴的、优秀的设计方案。本质上来讲，一个好的调度系统，就是要解决资源最优利用的问题，这个在之前的文章做过简单的介绍,见《调度系统的数学定义》。

它山之石，可以攻玉。

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

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

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

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

04 滴滴专车派单架构

派单架构图

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

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

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

05 匹配因子

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

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

06 滴滴的业务模型

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

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

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

07 滴滴的系统架构

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

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秒钟发起一次请求），描述整体资源的情况，当用户发出用车需求后，第一时间根据资源情况，进行订单推送。 订单热力图：基于对历史数据的统计并结合实时订单数据，给出当前全城范围内订单密集区域的分布，给司机提供有价值的听单位置参考，提高听单概率并减少司机空驶时间。 供需预测：基于海量实时出行数据，以数十亿订单数据和数百万司机位置信息为基础，预测任意时间段各个区域的订单需求和运力分布状况。 运力调度：基于供需预测结果，大规模有序调动全城所有可用运力，实现资源最优化分配。 智能分单：在司机和乘客的历史数据中学习接单概率模型，提高司机和乘客的匹配度，利用运力的规模效应实时地从全局上最优化总体交通运输效率和乘客出行体验。 滴滴派单和Uber派单对比

    <p id="main-toc"><strong>目录</strong></p>

1

一、滴滴

1、滴滴派单主要模式

2、参数选取

3、模型描述

4、评估方案

二、Uber

1、算法概述

2、Uber的算法解读

一、滴滴

1、滴滴派单主要模式

业务场景：一个订单被派给多个司机，司机根据自己的喜好选择接受或拒绝 目标：最大化一次派单成单率 关键问题：estimate the probability of each driver's acceptance of an order 算法方案：步骤1，估计每个司机的接单概率；步骤2，将各个司机接单率作为输入，最大化派单成功率

2、参数选取

订单-司机关联特征：接驾里程、订单推送给多少个司机、订单是否与司机当前驾驶方向一致 订单特征：起点到终点的距离、ETA、终点类型（医院、机场、学校、商务区等）、规划路线的路况、目的地历史上的订单频率 司机特征：历史接单率、司机活跃地点、接驾里程偏好、最近接单率等 补充特征：特征日、特征小时、司机数、附近运单数 3、模型描述

使用LR和GBDT模型

约束表示，一个司机一个时刻最多只能派一单

目标是使这一批订单这一次派单的总体成单率最高。

使用启发式算法解上述问题。

初始解：对每个司机，派给他接单率最大的订单，然后计算每一单的成单率，得到平均成单率

迭代：对运单i，找到没有被派到i的司机集合U，对U的每个司机k，如果把i派给k，平均成单率提高，则改派

4、评估方案

指标：

成单率 平均接驾时长 平均派单时长 取消率 人均单量

二、Uber

1、算法概述

全局优化算法Dispatch Optimization

<1>降低燃料成本

当您了解调度总成本（包括影响真正节省燃料成本的隐藏成本）时，有效的燃料计划会显著提高。

获取实时数据以改变燃料需求，最大化批量折扣并规划最有利可图的路线。 <2>提高资产利用率

提高资产利用率的有效策略是从网络中获取正确的数据，以便在为未来需求做准备时做出实时决策。

通过更好的资源分配，最大化每日负载历程匹配正确的驱动程序以获得最佳负载并控制盈利能力。 <3>最小化空的里程

通过规划路线并匹配驾驶员的预计到达时间来最大化每日行驶里程数，以减少等待时间。

使用完整的产品套件来识别可能导致空里程的网络问题，使用精准数据平衡容量 <4>集成电子测井数据

通过为负载规划人员提供工具以提高网络可见性，使电子日志过渡更顺畅。

使用驱动程序和加载负载仪利用的预测装载计划驾驶室的数据并更改执行计划。 <5>管理服务时间

持续的安全性和合规性对企业有利。在整个规划过程中和在路上有效地使用每个司机的HOS。

使用完整的产品套件，可以获得可能影响盈利能力和负载征求的驱动程序HOS数据的端到端的可见性 <6>保留卡车司机

通过选择驾驶员首选路线（例如特定卡车停靠点）以及在周末关闭时将负载匹配到司机，与您的驾驶员建立牢固的关系。

让驾驶员准时回到家，同时考虑对燃料成本的影响，以保持领先的需求 <7>降低通行费用

当整个车队成倍增加时，通行费成本增加。获取有关路线的实时建议，以避免收费或提前准备通行费。

自动计算通行费用以确定最便宜的路线

2、Uber的算法解读

均可以随着数据量的不断增加进行学习~所以只会越来越准，只会越来越准，只会越来越准。

1.计算车辆预计到达的时间算法 一开始使用的算法是Google这个行业已有巨头开发出来的API算法，后来发现其算法的误差较大。对于出租车较多的城市，这般不准确很有可能会使得用户放弃二次使用。不妨设想下，你站在路边等你叫的Uber，这时一辆空车开过你身边，你看了下手机，Uber提示说“你的专车1分钟后到达”，你想想算了就一分钟，过了这一分钟后你发现车还没来···错过那辆车的后悔之情会让你的每一分钟都不好熬。

Uber想，那就自己来组建开发团队。然后招呼来了火箭研究科学家，计算神经学专家和核物理学家。听说一开始很不顺利，因为原始数据太少，不过像这种最终会得到真实数据的算法都能根据自己的预测和真实值之间的差别进行自主学习，so，预测会越来越准他们最后捣鼓出来的算法将预测准确度提高了3分钟，更重要的是，这是个平均值。3可能是这般得出的：（2+2+2+2+2+2+2+2+2+12）/10=3，看到没，Google那个算法中12的大误差被消灭了哦，恭喜Uber，少损失了一个用户

2.浮动溢价算法 设想下，一个演唱会结束的时候，公交车大都停运，而此时这附近的出租车肯定出于一种供不应求的状态。我们都嗨了，也都累了，贵点就贵点早点到家就行。所以，Uber的“特定区域随时浮动定价算法”对于土豪和次土豪而言是很不错的。而且，这个提价的信号一旦启动，对于附近稍远的司机而言是非常有诱惑的，不过，当你们来了之后还是不是这个价就另说了。高收益怎能没有点风险和机会成本。而且啊，Uber瞄准的这个市场，有效供给和有效需求太太容易被获得了，有什么理由不借助价格来推动供需平衡呢？

所以现在的情况是，在用户的等待时间出现相对陡峭的上升趋势时，便会触动提价算法。而这些情况大部分时候都是可以预测的不过在这个算法神乎其神之前，遇到这篇报道中描述的问题的可能性也不低，超可怕

不过真能做到的话就天下无敌啦~看看咱们现在的便利店，同一条街上卖矿泉水的都会定价不一样（没错，我就是在乎这几毛钱，而且当用百分数来考察时，5毛就是2元矿泉水的40%啊！）

anyway，尊重市场的产品最终会得到了来自市场的回报，我就很讨厌说“罗斯福拯救美国经济那个论断”，都已经到了最低谷，谁来都会变好的。只是来的那个人，本身要能给人力量，说白了就是能忽悠。

3.如何在一个城市中部署最少的车，来有效满足全城的需求（travelling-salesman problem）

4.自动匹配算法 Uber采用的是一对一的自动匹配算法，国内滴滴的黑文说：Uber匹配的效率贼低啊！不如我们用户至上把需求发给好几个人让他们抢单。

先把滴滴这种模式的弊端放一放，我们来看看Uber算法到底是怎么样的：只把一个用户的需求发给一个司机，然后给司机15秒钟响应~如果不接的话就算接单失败，然后再发给另外一个司机，直至有司机接单为止。乍一看这个过程耗时很长，不过，当司机拒单的成本很大时，拒单情况基本不存在时，一对一派单的效率就很高了。而Uber是如何让司机拒单率保持在一个很低的水平？

方法如下： 用好补贴这个经济杠杆，人民司机啊，你不是对大额补贴趋之若鹜吗？如果拿到补贴的前提是1)不低于80%的接单率；2)较高的评分；3)几乎不存在的投诉；4)```其余各种各样保证用户体验的要求。那么一对一派单这个系统就有了最大的帮手~

首先看下第1点，80%的接单率需要你在5次系统派单中最多只能拒绝一个单，如果你拒绝了2次，也有办法补救，那就再跑5单呗，这个时候，系统给的任意5单你都不能拒绝。那么在这10次派单中，你一共接单8次（3+5）,唉，总算达到了补贴的门槛之一，且慢还有之二。

第2点评分。没错，和上面的道理差不多，为了达到4.8的综合评分，你需要尽量拿5分哦，万一4分拿多了怎么办？多跑跑，世界上还是好人多啊~

看到没，这个补贴的门槛让司机慎重选择上线等待客户这个状态，一旦上线就是Uber的人啦于Uber而言，不用算法就筛选出了当下最有效的资源（那句老话怎么说的，占着茅坑不拉屎的人几乎没有）。而当在线资源的可调度性很高时，全局资源优化就成了一件分外可行的事，听说最近Uber优化了派单系统，采用了一个能考虑全局指数的算法——Dispatch Optimization，不得不说这是很大一盘棋的起点。中国的孩儿们，光快有啥用呢？这个策略的远大作用还可以慢慢挖掘

滴滴的劣势。1)太不尊重人了，让司机总在神经紧绷；2)明明都是烧钱，看Uber顺便优化了司机素养。

划重点

滴滴的本质是提升接单率，所以把一单派给很多人抢，这样可以保证订单的消化，主要是考虑企业自身的盈利。

反看Uber出了溢价这个问题，其他大部分是以司机(用户)为主，保证推荐的司机没人跟他抢所以只派一个人，其他路线规划考虑的也是司机的利益，当然它的补贴也是变相的对司机进行控制，但是总体上还是比较人性的。