【Note】Large-Scale Order Dispatch
Large-Scale Order Dispatch in On-Demand Ride-Hailing Platforms A Learning and Planning Approach
将强化学习算法应用于分单，使得系统可以更加关注整个全局的最优化，并且克服现有分单算法中存在的“短视”现象，寻求更大时间尺度上的最优。
将订单调度建模为一个大规模序列决策问题，每个独立的匹配决策基于两个因素：根据实时信息得到的司机服务这一单得到的即时奖励＋一个表征该决策对未来影响的额外因素。
分单：对于较短一个时间片\(t\) ，有 \(m\)个待分配订单， \(n\) 个空闲司机，按照某种原则，将待分配订单分配给空闲司机。分单的目标是最大化成交总额(GrossMerchandise Volume,GMV)。
问题建模
将Markov Decision Process(MDP)用于建模序列决策问题：
目标：最大化收益gain \(G_t = \Sigma _{i=t}^T R_{t+1}\)
方法：学习价值函数 state-value function \(V_{\pi}(s)=\mathbb E_{\pi}[G_t|s_t=s]\) 和 action-value function \(Q_{\pi}(s,a)=\mathbb E_{\pi}[G_t|s_t=s,a_t=a]\)
MDP定义：
把每个独立的司机建模为一个agent，有利于简化其他定义。
State. 把所有时间 \(T\) 和所有区域 \(G\) 进行离散化，司机的状态可以定义为表征时空状态的二维向量\(s=(t,g)\in S, t\in T,g\in G\), 所有状态集就是时间和空间的笛卡尔积 \(|S|=|T|\times |G|\)
Action. 一是服务行为(serving action)，指定司机去服务一个特定的订单，完成后得到订单的奖励；二是闲置行为(idle action)，在该时间片内匹配不到任何订单，这一action会导致自动转换到下一轮分单且该轮分单奖励为0。
Reward. 考虑到预估价格和预计到达时间的不确定性，加入了折扣系数，即时奖励表示为\(R_\gamma=\sum_{t=0}^{T-1}\gamma^t \frac RT\).
举例，预估$30的订单，10min在接乘客，20min行驶，从A送到B，以10min为一个时间片 ，状态转移表示为\(s=(0,A)\rightarrow s'=(3,B)\)，折扣系数\(\gamma=0.9\)，那么最终的奖励为 \(R/T=30/3=10, r=10+10*0.9+10*0.9^2=27.1\)
State transition. 状态转移伴随行为发生,Temporal Difference(TD)更新规则如下：
对于idle action的司机:
\(V(s)\leftarrow V(s)+\alpha[0+\gamma V(s')-V(s)], s=(t,g)\rightarrow s'=(t+1,g)\)，时间片加一，地区不变；
对于serving action的司机:
\(V(s)\leftarrow V(s)+\alpha[R_\gamma +\gamma^{\Delta t}V(s'')-V(s)],s=(t,g)\rightarrow s'=(t+\Delta t,g_{dest})\)
算法介绍
实时订单分配算法 \[ \mathop{argmax}\limits_{a_{ij}} \sum_{i=0}^m \sum_{j=0}^nQ_{\pi}(i,j)a_{ij}\\ s.t. \space \space \sum_{i=0}^ma_{ij}=1, j=1,2,3,...,n\\ \sum_{j=0}^na_{ij}=1, i=1,2,3,...,m \] \(Q_{\pi}(i,j)\)表示将订单\(j\)分配给司机\(i\)预期增加的收益，\(i=0\)表示空司机的特殊状态，\(j=0\)表示空订单的特殊状态。
学习时空价值过程中也有时间片(状态的划分，状态由时间索引和空间索引组成)，这个时间片一般比较大(几分钟)，而分单时间片一般比较小(比如几秒)，这是为了保证分单的实时性。这就导致了对于该分单轮次，轮空的司机来说，其状态是不变的(时间索引和空间索引都不变)，也就是说其增益价值为空，所以分单算法应该保证尽量不让司机轮空。因此，可以去掉这两个特殊的状态，问题变为带边权的最大二分图匹配问题。该问题可以使用KM(Kuhn-Munkres)算法求解。
采用advantage function trick, 减去了\(V(i)\)连接到司机\(i\)的边。advatange function的计算方式为期待收益减去保持在原来状态的期待价值，删除了二分图中的大多数边，有利于更快的计算。 \[ \mathop{argmax}\limits_{a_{ij}} \sum_{i=1}^m \sum_{j=1}^nA_{\pi}(i,j)a_{ij}\\ s.t.\quad \space \sum_{i=1}^ma_{ij}\le1, j=1,2,3,...,n\\ \sum_{j=1}^na_{ij}\le1, i=1,2,3,...,m\\ where\quad A_{\pi}(i,j)=\gamma^{\Delta t_j}V(s'_{ij})-V(s_i)+R_{\gamma}(j)\quad is \space advantage\space funciton \] advantage function中主要考虑以下四个因素：
Order price. 订单j的价格越高，相应的\(R_{\gamma}(j)\)也越高
Drivers' location. 未来更难接到订单(即当前价值低的司机，\(V(s_i)\)小)更容易接到订单，司机当前的状态对应advantage function中的负面影响\(-V(s_i)\)
Order destination. 目的地为高价值区域的订单对应更高的\(V(s'_{ij})\)
Pickup distance. 更远的接客距离会导致更晚的到达时间，增加了\(\Delta t_j\)，增大了折扣
算法流程
离线部分：
收集历史数据中的订单信息，表示为强化学习中的四元组形式；
使用动态规划求解价值函数。将价值函数以查找表 (lookup table) 形式保存以供线上使用。
线上部分：
收集待分配的司机和订单列表;
计算每个司乘匹配对应的动作价值数 (State-Action Function)，并以此为权重建立二分图;
将上述匹配权值作为权重嵌入KM 算法，充分考虑接驾距离、服务分等因素，求解最优匹配，进入最终派单环节。
迭代部分：
离线+线上，根据新积累的数据离线更新价值函数，和使用更新后的价值函数指导派单的过程。