本文已参与「新人创造礼」活动，一起敞开创造之路。

《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=∑t=0T−1tRTR_{\gamma}=\sum_{t=0}^{T-1}{\gamma ^ t \frac{R}{T}}

3.2 战略及状态更新

action-1

V(st)=V(st)+[Gt−V(st)]Gt=Rt+V(st+1)Rt=0V(s_t) = V(s_t) + \alpha[G_t – V(s_t)] \\ \\ G_t = R_t + \gamma V(s_{t+1}) \\ \\ R_t = 0

action-2

V(st)=V(st)+[Gt−V(st)]Gt=Rt+tV(st+t)Rt=RV(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}

关于学习率—\alpha

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

四、优化与使用

4.1 优化目标

argmaxaij∑i=0m∑j=0nQ(i,j)aijargmax_{a_{ij}}\sum_{i=0}^m\sum_{j=0}^nQ_{\pi}(i, j)a_{ij}

注:

  • Q(i,j)Q_{\pi}(i, j): 订单i被司机j接起的价值
  • aija_{ij}: 订单是否被接起
  • i: 当前时刻一切可接单司机
  • j: 当前时刻一切订单

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

4.2 实际使用

Q(i,j)Q_{\pi}(i, j)相当于评价从出发地抵达意图地，给渠道的带来的长时刻价值：

Q(i,j)=A(i,j)=GG=Rt+tV(st+1)Rt=R=∑t=0T−1tRTQ_{\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}}

注:

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

五、练习与使用

结合 section-3 和 section-4