一、布景
出行场景下的司乘匹配非常复杂。一方面，高峰期出行途径每分钟会接到大量出行需求；另一方面车辆会在路上不停地移动，或许几秒后这个司机就通过了一个路口，或是跋涉上了高速路；不仅如此，每一次派单的抉择也都在影响未来的司机散布。
这些挑战对算法提出了更高的要求：
总而言之：
- 途径需求秒级进行派单抉择方案，每次抉择方案的优化方针均为提高长时间收益。这种抉择方案场景正好满足序列抉择方案 (Sequential Decision Making) 的定义，可以运用马尔可夫抉择方案进程 (MDP) 进行建模，并用强化学习求解。
- 针对司乘间多对多的匹配，建模成一个组合优化问题，以取得大局最优解。
二、MDP模型
2.1、MDP介绍
强化学习使命通常运用马尔可夫抉择方案进程（Markov Decision Process，简称MDP）来描述，具体而言：机器处在一个环境中，每个情况为机器对其时环境的感知；机器只能通过动作来影响环境，当机器实行一个动作后，会使得环境按某种概率转移到另一个情况；一同，环境会依据潜在的奖励函数反馈给机器一个奖励。归纳而言，强化学习首要包括四个要素：情况、动作、转移概率以及奖励函数。
依据上图，agent（智能体）在进行某个使命时，首要与environment进行交互，产生新的情况state，一同环境给出奖励reward，如此循环下去，agent和environment不断交互产生更多新的数据。
2.2、分单MDP模型
- 智能体 (agent) ：定义每个司机为一个智能体。虽然此定义会使问题变为一个多智能体学习 (multi-agent) 求解问题，但单司机作为智能体的办法可大大减少情况和动作空间，使得求解变得或许。
- 情况 (state) ：情况定义了司机地点的周边信息。为简化起见，定义司机地点的时间和空间为其情况，并将时空进行量化为 10 分钟的时间段和固定巨细的区域。这样，一个无缺的 episode（记为一天）由 144 个时间片组成，每个城市包括着数千至数万的区域单位。
- 动作 (action) ：动作定义了司机的结束订单或闲暇操作。对结束订单而言，司机会通过前往接乘客、等待乘客和送乘客到目的地等进程。
- 情况转移 (state transition) 与奖励函数 (rewards) ：结束订单的动作会主动使司机产生时空情况的转移，其一同会带来奖励，我们定义奖励 r 为订单的金额。
司机的一次情况转移，可以从“服务乘客”或许“空跑”中产生。
如果是空跑，司机并不会立刻取得其时的奖励，表达式为:
V(s)←V(s)+[0+V(s′)−V(s)]V(s) ← V(s) + [0 + V(s’)-V(s)]
s′=(t+1,g)s’=(t+1, g)：标明下一个时间司机空跑的情况。
：标明对未来收益的扣头因子。
如果是服务乘客，则司机会立刻取得奖励，表达式为：
V(S)←V(S)+a[Rr+tV(s′′)−V(S)]V(S) ← V(S) + a[R_r+^{t}V(s”)-V(S)]
s′′=(t+t,gdest)s′′=(t+t,g_{dest}): 标明服务这个乘客结束时的司机的情况。
tt：标明司机去接乘客、等待和送乘客的总时间。
司机的情况转移示例图如下：
三、匹配办法
利用学到的价值函数作为输入，并且抉择哪些司机和哪些订单进行匹配，在每轮匹配中，我们的方针是为每个司机寻觅最好的动作来优化未来大局的收益。
采用KM算法来求解上述问题。因为一个司机要么选择接单要么选择空跑，所以这个二分图是彻底图，每个边都是可以存在的。为了下降核算的复杂度，我们消除了全部默许行为的边。因为在实践中，每两轮之间的距离远远小于价值函数中考虑的时间长度，一个司机不做任何行为可以认为是保持在原情况，因此行为价值函数Q(i,0)实际上等于情况函数，这使得我们可以取消掉全部司机的不作为动作，这使得边的数量大大减少。
通过上述技巧，模型变成：
我们继续剖析advantage function，它包括了我们需求考虑的四个要素：
- 订单价格，高价格订单会更具有优势，R(j)R_(j)；
- 司机方位，司机其时的方位有一个负的影响，−V(si)−V(s_i)，因此，在相同的条件下，司机在价值更小的方位时更容易被选择服务订单；
- 订单目的地，选择高价值目的地区域的订单更有优势，因为它会有一个更大的V(s′ij)V(s′_{ij})；
- 接乘客的距离，接乘客的距离也会影响advantage function，更长的距离需求更多的时间来接乘客，使得订单的未来价值下降，总体的值下降。
除此之外，实际中还会通过一系列超参数，来平衡用户体会和途径功率，达到用户和途径的双赢。
