【论文解读】滴滴智能派单-KDD2018 Large-Scale Order Dispatch in On-Demand Ride-Hailing

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

一、简介

基于大量历史数据，构建一个大Q表,用于订单的评估，满足乘客的需求的同时，兼顾平台的长期价值，最终提升平台的收入。

二、背景

从司机抢单到平台派单，使得平台的收入提升了10%。

对于派单，需要对司机和订单进行高效的组合。之前大家都是基于一些在线策略(会在一定时间将司机和订单放到一个bucket里，然后进行分配)，虽然有效但是并不高效。

本文的目的是期望将配对的过程更加高效，更加注意平台的长期价值，并最终提升平台的收益。

三、模型框架

3.1 一些定义

State:

简化司机的状态 s=(t, g), t-为时间戳, g-地理位置(h3no)

Action:

1)司机接单，进行服务；
2)司机空闲, 在某地长时间闲置( s=(t, g) -> s'=(t', g))
3)司机空闲, 且在游走(论文中不包含)

Reward:

1)action-1 订单的价格
2)action-2 0

Discout factor( $\gamma$):

将奖励基于时间段拆分成T段，基于折扣系数衰减累加
$R_{\gamma }={\sum }_{t=0}^{T?1}{\gamma }^t\frac{R}{T}$

3.2 策略及状态更新

action-1
$$\begin{gathered} V(s_t)=V(s_t)+\alpha [G_t?V(s_t)] \\ {G}_t=R_t+\gamma V(s_{t+1}) \\ {R}_t=0 \end{gathered}$$

action-2
$$\begin{gathered} V(s_t)=V(s_t)+\alpha [G_t?V(s_t)] \\ {G}_t=R_t+{\gamma }^{\Delta t}V(s_{t+\Delta t}) \\ {R}_t=R_{\gamma } \end{gathered}$$

关于学习率—$\alpha$

1. 可以设定固定值
2. 也可以设定为一个递减的值(论文用该方法)
   • 用$\frac{1}{N(s_i)}$, $N(s_i)$为该状态的迭代次数

四、优化与使用

4.1 优化目标

$$argma{x}_{a_{ij}}\sum _{i=0}^m\sum _{j=0}^n{Q}_{\pi }(i,j)a_{ij}$$
注:

• $Q_{\pi }(i,j)$: 订单i被司机j接起的价值
• $a_{ij}$: 订单是否被接起
• i: 当前时间所有可接单司机
• j: 当前时间所有订单

用KM算法去优化获取最佳组合, $Q_{\pi }(i,j)$作为边权重。

4.2 实际使用

$Q_{\pi }(i,j)$相当于评估从出发地到达目的地，给平台的带来的长期价值：
$$\begin{gathered} Q_{\pi }(i,j)=A_{\pi }(i,j)=G \\ G=R_t+{\gamma }^{\Delta t}V(s_{t+1}) \\ {R}_t=R_{\gamma }=\sum _{t=0}^{T?1}{\gamma }^t\frac{R}{T} \end{gathered}$$
注:

• 需要用到订单预估时长
• 需要用到订单预估价格

五、训练与使用

结合 section-3 和 section-4