滴滴 - dispatching

1 2017 - 《A Taxi Order Dispatch Model based On Combinatorial Optimization》

资料：
论文详解:滴滴大数据预测用户目的地，准确率超90% | KDD 2017 | 雷峰网

论文总结：
Dispathing system 派发系统： 就是多对多司机和乘客匹配，使得司机赚钱更多，乘客满意度更高。

1. 传统的方法是：对每个订单，最大化司机的接单率. 缺点：整体成功率可能不高。
2. 新方法：使用的基于组合优化的分单模型，最大化整体的接单成功率，最大化整体的效率，从而提升用户体验。

算法细节如下：

1. 分单时优化整体成交率
   模型的数学形式即：
   

其中，max(E) 为整个模型的优化目标，即成交率；g(a)≤0 为模型必须要满足的约束条件，在这里可能是一些业务规则，比如一个司机同一时刻只能分配一个订单等；a 为模型的解，即如何对整体的订单和整体的司机进行分配。

1. Logistics Regression模型计算司机接受概率
   根据订单的价值、接驾距离、方向夹角、行驶方向等特征，使用logistics regression模型来进行计算司机接受订单的概率。
   
   因为一个订单会同事派发给m个司机，所以第i个订单的成交概率即为：
   

这样整个组合优化模型即为：
其中N是当前的订单总数，M是一单通知的司机个数。优化的是当前时刻所有订单的成功率之和。

2 2018 - 《Large‑Scale Order Dispatch in On‑Demand Ride‑Hailing Platforms: A Learning and Planning Approach》

资料：
滴滴 KDD 2018 论文详解:基于强化学习技术的智能派单模型 | 雷峰网

1. 传统方法：关注的是即时的乘客满意度。
2. 新方法：更关注全局和长远角度下的资源利用率和用户体验。

整体架构：

1. 离线训练价值函数，这里使用的是强化学习，MAP状态空间转移的方法
2. 在线推理的时候根据当前收益，和未来状态下的收益综合判断
   

3 2019 - 《A Deep Value-networkBased Approach for Multi-Driver Order Dispatching》

滴滴KDD 2019 论文详解：基于深度价值网络的多司机智能派单模型

1. 本文是在上篇文章的基础上，使用了深度强化学习+半马尔可夫决策过程（带有时间延展性）。
2. 状态空间中增加情景式特征，上一篇论文中，状态空间只跟时间地点有关。当前修改为：状态 (时间、地点、情景式特征 - 热区，冷区等)。
3. 价值函数更新中增加时延递减信息
   
4. 且不同城市间使用迁移学习，对数据比较少的城市就比较友好，不用从0开始。

4 2019 - 《Efficient Collaborative Multi-Agent Deep Reinforcement Learning for Large-Scale Fleet Management》

多智能体，强化学习
是滴滴的新的玩法，增加了车队的概念，就是这个车队是一个团队，车队和车队之间，是竞争关系。这样一方面司机不会无聊，车队成员之间，会有一个归属感。另一方面，车队之间的竞争关系，会激发司机的工作热情。使用的也是强化学习的方法。没有细看，相关性不大。