A Taxi Order Dispatch Model based On Combinatorial Optimization /基于组合优化的出租车订单调度模型
论文来源
- https://dl.acm.org/doi/pdf/10.1145/3097983.3098138
- KDD cup
- 滴滴团队
- 中文参考：https://baijiahao.baidu.com/s?id=1575765326502914&wfr=spider&for=pc
- 辅助资料：https://blog.csdn.net/DiDi_Tech/article/details/100806477
摘要
- 背景：打车软件很流行方便，其中调度系统尤为关键
- 传统方法及不足：传统的调度系统按顺序向乘客调度车辆，目的是最大化每个订单的司机接受率。但是这样会导致整体成交率(global success rate)低，降低用户体验
- 改进1：提出了新的调度系统，目的是最大化整体成交率,优化整体的旅行效率，提高用户体验。
- 改进2：提出了一种用户目的地预测算法，该算法基于用户过去的旅行记录，利用贝叶斯框架对其目的地分布进行建模。
- 结果：在北京区域的数据上基于A/B tests和SOTA模型进行了对比，整体成交率从80%提高到了84%。在用户等待时间和上车距离上也得到了很大提升。对于目的地预测算法，前三准确率从89%到了93%。
- 个人疑问：整体成交率是如何定义的。传统的按顺序调度又是如何实现的。
1 引言
调度部分
- GPS+4G发展的好，轨迹数据越来越多，提供了一个构建智能实时决策系统的机会，包括旅客查找、出租车需求预测、路径规划、派单算法。
- 调度算法很重要且核心。过去的算法主要是通过为每一单找距离最近或者行驶时间最短的司机。这些方法的缺点在于它们只考虑最适合当前这一单的司机，却不考虑这个司机是否更适合别的订单。(个人理解：比如说在乘客1的左右两边分别有A车和B车。乘客2也在乘客1的右边。假设A车和B车到乘客1的距离差不多，但是B车要近一点点，如果乘客1先打车的话，那么B车就很有可能就直接被派给乘客1了，然后乘客2就只能打到A车了，但是这样显然就太远了，没有更好的利用资源。理想的当然是乘客1上A车，乘客2上B车)因此这些方法不能保证所有订单的全局行驶时间最短。一些作者基于多代理架构提出了一种叫做NTuCab的新模型。他们为了最小化全局的等车时间或者接驾时间，他们将每一个代理视为一个计算单元。每个计算单元处理N个司乘匹配对，每个订单只分配给一个司机。如果匹配的司机不接受订单，则将订单分派给另一个司机。(没有很明白NTuCab模型)
- 上述方法的缺点在于调度时间长、成功率低，因为它们都没有优化全局成功率。滴滴的场景下，每秒的司乘匹配量很大，因此订单的全局成功率很重要。
- 本文提出了一种新的组合优化模型来解决滴滴出行的订单调度问题。在这个模型中，我们将一个订单分派给几个司机，目标是最大化这些订单的总成功率。当多个司机收到同一个订单时，谁接的快给谁。如果订单未被接受，它将进入下一轮配送，直到被接受或取消。
目的地预测部分
- 调度系统中有三要素：出发时间、起点和终点。通常，可以选取当前时间和司机位置作为出发时间和起点，这适用于大部分叫车场景。但是不同的人会去不同的地点，甚至同一个人，在不同的出发时间和起点的情况下，终点也可能不同。因此，要让用户每次都要把目的地的全程输出来很麻烦。所有如果APP能提前预测好用户要去哪儿的话，就很方便。目前大部分的方法使用所有用户的轨迹数据来训练模型，然后使用当前行程的信息，结合一些辅助信息，例如时间、交通条件等来预测预定的当前目的地。
- 一个非常经典的方法基于了多层感知机，以用户的初始轨迹信息以及驾驶员id、用户信息、出发时间等作为输入。经过训练后，它可以预测大部分行程。但是该模型不太依赖于problem specific information
that can be derived from the data(啥意思？)。它在很大程度上取决于旅程的初始连续轨迹数据，一旦这部分没了，那么预测精度就会大大降低。还有一种方法使用了驾驶员自己的历史行程数据来训练HMM模型。该模型把一天的时间分成几个主观部分，如早晨、中午和晚上，这种处理方式破坏了时间的连续性。 - 过去的这些方法并不适合于滴滴出行的目的地预测问题，因为滴滴出行需要到达用户打开APP后很快就出预测结果的效果，然而当前行程的轨迹数据并不能很快获取(这里指的是用户过去很长时间的轨迹数据呢还是指打开APP前那点很短的轨迹数据呢？)。此外，与大多数以前试图最小化预测目的地和实际目的地之间的距离的方法不同，我们的目标是确定用户想要去的确切目的地。事实上，即使预测的目的地是真实目的地的别名，乘客也可能把它当作不熟悉的目的地，然后重新输入目的地。因此我们的系统将用户的历史目的地当作候选集。每个人的个人历史行程统计差别都很大。拿2015年为例，对于至少使用过一次滴滴出行的用户来说，每个用户每年的出租车预约使用量约为二十次。但是分布不均匀，高频用户每天打开APP，低频用户一年打开APP不到十次。从这种稀疏的数据中获得准确的个人统计数据是一项重大挑战。
- 经过对滴滴数据的观测分析，研究提出了基于贝叶斯决策的目的地预测模型，该模型考虑了三元高斯分布下的出发经度、纬度和出发时间。利用个人行程数据进行训练，训练好的模型可以根据出发经度、纬度和出发时间计算用户历史目的地的概率，然后按概率排序给出一个预测排行。
2 派单系统
-
本研究的目标就是最大化派单成功率。
-
假设有N单，M个司机，那么可以把派单表示成一个矩阵：
( a 11 ⋯ a 1 M ⋮ a i j ⋮ a N 1 ⋯ a N M ) , where 1 ≤ i ≤ N , 1 ≤ j ≤ M and a i j = { 1 order i is dispatched to driver j 0 order i is not dispatched to driver j \begin{array}{l} \left(\begin{array}{ccc} a_{11} & \cdots & a_{1 M} \\ \vdots & a_{i j} & \vdots \\ a_{N 1} & \cdots & a_{N M} \end{array}\right), \text { where } 1 \leq i \leq N, 1 \leq j \leq M \\ \text { and } a_{i j}=\left\{\begin{array}{ll} 1 & \text { order } i \text { is dispatched to driver } j \\ 0 & \text { order } i \text { is not dispatched to driver } j \end{array}\right. \end{array} ⎝⎜⎛a11⋮aN1⋯aij⋯a1M⋮aNM⎠⎟⎞, where 1≤i≤N,1≤j≤M and aij={10 order i is dispatched to driver j order i is not dispatched to driver j
在该场景下，假定每个司机一轮只能接收到一个订单，但是一个订单可以派给多个司机，该约束的数学形式为： ∀ j , ∑ i = 1 N a i j ≤ 1 \forall j, \sum_{i=1}^{N} a_{i j} \leq 1 ∀j,∑i=1Naij≤1 -
在滴滴的业务场景中，一个订单被分派给多个司机，每个司机根据自己的喜好决定是否接受。对于每个订单，是否被其中一个司机接受，直接取决于每个司机接受的概率。因此，订单调度的关键问题是估计每个司机接受订单的概率。如果我们可以估计出每个司机对每个订单的接单概率，那么我们就可以得出每个订单能够被司机接单的概率。因此我们将订单调度模型分为两个子模型：
- 一个模型预测司机行为，也就是司机接受每个订单的概率。
- 另一个模型使用接受概率来制定一个使目标收益最大化的优化问题，然后解决底层的优化问题。
2.1 司机行为预测模型
- 由于司机只有接收和拒绝两种行为，因此用0-1变量y来表示行为，1接收，0拒绝。并假设司机行为独立同分布。
- 利用
p
i
j
p_{ij}
pij来表示订单
o
i
o_i
oi被司机
d
i
d_i
di接收的概率。概率取决于很多因素，比如订单价值、行驶距离、方向等。这些信息可以编码为一个特征向量
x
i
j
\textbf{x}_{ij}
xij，对应订单
o
i
o_i
oi被司机
d
i
d_i
di。给定
x
i
j
\textbf{x}_{ij}
xij，则估计的接收概率如下：
p i j = p ( y = 1 ∣ x i j ) p_{ij}=p(y=1|\textbf{x}_{ij}) pij=p(y=1∣xij)
这是一个典型的二分类问题，可以利用历史订单-司机对产生的特征来进行训练。 - 研究中，他们尝试了LR和GBDT。不同城市分别训练。评价指标采用了准确率(ACC),AUC,召回率(Sensitivity),Specificity(所有负例中被预测为负的比例，和召回率相对应)。
- 结果如论文中表一所示，在他们的数据上，LR表现更好些，因此采用了LR模型：
p i j = p ( y = 1 ∣ o i , d j ) = 1 exp ( − w T x i j ) p_{i j}=p\left(y=1 \mid o_{i}, d_{j}\right)=\frac{1}{\exp \left(-\mathbf{w}^{\mathrm{T}} \mathbf{x}_{i j}\right)} pij=p(y=1∣oi,dj)=exp(−wTxij)1
疑问：难道不应该是下面的吗
p i j = p ( y = 1 ∣ o i , d j ) = 1 1 + exp ( − w T x i j ) p_{i j}=p\left(y=1 \mid o_{i}, d_{j}\right)=\frac{1}{1+\exp \left(-\mathbf{w}^{\mathrm{T}} \mathbf{x}_{i j}\right)} pij=p(y=1∣oi,dj)=1+exp(−wTxij)1 - 优化器选择：随机梯度下降(SGD)
- 特征选择(值得学习！)：
- “订单-司机对”特征：接驾距离、每轮订单向司机的传播数量。
- 订单相关特征：订单距离和预估到达时间，目的地类型，路线上的交通状况，该目的地历史订单频率
- 司机端特征：长期行为(司机的历史接收率、司机的活跃区域、对不同广播距离的喜好？)，短期兴趣（最近是否接收订单）
- 补充特征：周几、几点、附近订单和司机数量
2.2 组合优化方法
- 由于一个订单会被派发到多个司机，假设N单M个司机，则订单
o
i
o_i
oi被接收的概率为：
E i = 1 − ∏ j = 1 M ( 1 − p i j ) a i j E_{i}=1-\prod_{j=1}^{M}\left(1-p_{i j}\right)^{a_{i j}} Ei=1−j=1∏M(1−pij)aij
a i j = { 1 order i is dispatched to driver j 0 order i is not dispatched to driver j a_{i j}=\left\{\begin{array}{ll}1 & \text { order } i \text { is dispatched to driver } j \\ 0 & \text { order } i \text { is not dispatched to driver } j\end{array}\right. aij={10 order i is dispatched to driver j order i is not dispatched to driver j
其中 p i j p_{ij} pij的定义见2.1节.
则，成功率 E S R E_{SR} ESR可表示为：
E S R = ∑ i = 1 N [ 1 − ∏ j = 1 M ( 1 − p i j ) a i j ] N E_{S R}=\frac{\sum_{i=1}^{N}\left[1-\prod_{j=1}^{M}\left(1-p_{i j}\right)^{a_{i j}}\right]}{N} ESR=N∑i=1N[1−∏j=1M(1−pij)aij]
同样存在约束： ∀ j , ∑ i = 1 N a i j ≤ 1 \forall j, \sum_{i=1}^{N} a_{i j} \leq 1 ∀j,∑i=1Naij≤1，代表一个司机一次只能接收一单。那么派单的整体目标可以建模为：
{ max a i j E S R = ∑ i = 1 N [ 1 − ∏ j = 1 M ( 1 − p i j ) a i j ] N s.t. ∀ j , ∑ i = 1 N a i j ≤ 1 , a i j ∈ { 0 , 1 } . \left\{\begin{array}{l}\max _{a_{i j}} E_{S R}=\frac{\sum_{i=1}^{N}\left[1-\prod_{j=1}^{M}\left(1-p_{i j}\right)^{a_{i j}}\right]}{N} \\ \text { s.t. } \forall j, \sum_{i=1}^{N} a_{i j} \leq 1, a_{i j} \in\{0,1\} .\end{array}\right. {maxaijESR=N∑i=1N[1−∏j=1M(1−pij)aij] s.t. ∀j,∑i=1Naij≤1,aij∈{0,1}.
这是一个约束组合优化问题。 - 许多组合优化问题都是NP hard的，在多项式时间内无法解决。一种典型的方法是使用启发式算法来寻找近似解。常用的方法有爬山法、遗传算法、模拟退火算法等。考虑精度和性能的平衡，他们选择了爬山法。
- 爬山法在该问题上的应用过程如下（已知司机接收订单概率矩阵，大小：N单*M司机）：
- 利用矩阵D（大小：M*1）来记录分给每个司机的订单编号，然后先用对该司机接单概率最大的订单编号进行初始化：对概率矩阵P的每一列，找最大值对应的位置即可
- 利用矩阵E（大小：N*1）来记录每一单能够被成功接收的概率：对于每一行采用2.2节的第一个公式。
- 遍历每个订单编号i：
- 统计没有被分配到订单i的司机编号，汇总为U
- 遍历U中的每个司机编号k：
- 如果把订单i派发给司机k能够增加E0(全局成功率)，那就把订单i派给司机k