回顾KDD2017
A Taxi Order Dispatch Model based On Combinatorial Optimization
最大化全局的匹配概率
基于贝叶斯框架来预测用户目的地
KDD2018
Large-Scale Order Dispatch in On-Demand Ride-Hailing Platforms: A Learning and Planning Approach
MDP+组合优化，value function 与 匹配组合优化的目标函数结合
一、 Learning（离线）：序列决策 (Sequential Decision Making) 问题
-
收集历史数据中的订单信息，表示为强化学习中的四元组形式；
-
使用动态规划求解value function。将价值函数以查找表 (lookup table) 形式保存以供线上使用。
二、 Planning（在线）：
-
收集待分配的司机和订单列表;
-
计算每个司乘匹配对应的State-Action Function Q(s,a) ，优化为advantage function A(s,a) ，并以此为权重建立二分图;
-
将上述匹配权值作为权重嵌入 KM 算法，充分考虑接驾距离、服务分等因素，求解最优匹配，进入最终派单环节。
三、 Combining（迭代）：
步骤 3 迭代重复进行 1 和 2，即根据新积累的数据离线更新价值函数，和使用更新后的价值函数指导派单的过程。
Details
空间分片方式：
一般处理方式都是采用六边形格子 ( google S2 ) 对地图进行划分，单独的格子可能会有稀疏问题，因此可以对相邻的格子依据供需状况做聚类，最终作为统一的空间分片。
advantage function的考虑因素：
- 订单价格，高价格订单会更具有优势，Rγ(j)Rγ(j)；
- 司机位置，司机当前的位置有一个负的影响，−V(si)−V(si)，因此，在相同的条件下，司机在更小价值的位置更容易被选择服务订单；
- 订单目的地，选择高价值地区的目的地的订单更有优势，因为它会有一个更大的V(s′ij)V(sij′)；
- 接乘客的距离，接乘客的距离也会影响advantage function，更长的距离需要更多的时间来接乘客，使得订单的未来价值降低，总体的值降低。
其他解读
[1] 滴滴 KDD 2018 论文详解：基于强化学习技术的智能派单模型
[2] 基于 “ 滴滴 KDD 2018 论文：基于强化学习技术的智能派单模型 ” 再演绎
[3] Dispatching-in-Didichuxing-2
[4] [高效的多维空间点索引算法 — Geohash 和 Google S2](