Dispatching-in-Didichuxing-1

最近要写几个滴滴相关的论文的笔记,顺便解读一下目前的拼车算法等策略,顺带着科普。今天这篇是KDD2017的《A Taxi Order Dispatch Model based On Combinatorial Optimization》,这篇文章是比较早时候的分单算法的文章,跟现在的算法略有差异。

简介

传统的拼车算法是一种顺序的分配策略,在乘客周围选择最近的车辆,最大化每个司机对每个订单的接受概率,这样做有可能会导致一个较低的全局匹配成功率,本篇文章中提出了一种最大化全局的匹配概率的方法,改善用户体验,同时文中还提出一种基于贝叶斯框架的预测用户目的地的方法。

订单分配系统

我们的目标是最大化匹配成功率,记为\(E_{SR}\)\(N\)个订单分配给\(M\)个司机,分配结果矩阵为 \[ \left\{ \begin{matrix} a_{11} & \cdots & a_{1M} \\ \cdots & a_{ij} & \cdots \\ a_{N1} & \cdots & a_{NM} \end{matrix} \right\} \] 期中\(1\leq i\leq N\)\(1\leq j \leq M\),当\(a_{ij}=1\)的时候表示订单\(i\)分配给司机\(j\),在这种场景中,每个司机最多只能接一个订单,所以\(\forall j,\sum^N_{i=1}a_{ij}\leq1\)。在每轮的分配中,每个订单会分配给一些司机,每个司机根据自己的意愿决定是否接受这个订单。所以,订单分配的关键问题在于估计每个司机接受这个订单的概率,因此我们把分单模型分成两个子模型,一个模型用来估计司机接受订单的概略,另一个模型用估计的概率来最大化我们的目标\(E_{SR}\)

预测司机行为模型

我们用\(0-1\)变量\(y\)来表示司机接受或者拒绝,假设每个司机的行为都是独立同分布的。我们用\(p_{ij}\)表示订单\(o_i\)被司机\(d_j\)接受的概率,有很多因素都会影响这个概率,如这一单能赚的钱、行驶距离、目的地等等,这些因素记为特征向量\(\bf{x_{ij}}\),则接受概率可以表示为 \[ p_{ij}=p(y=1|\bf{x_{ij}}) \] 这个问题可以描述为一个典型的二分类问题,所以我们用历史数据进行模型训练。我们尝试了LR和GBDT,具体效果如下图所示:

lr&gbdt
lr&gbdt

实验结果表明LR的效果稍微好一点,所以我们选择LR作为预测模型,采用SGD训练模型。特征方面主要包括四方面:

  • 订单-司机相关的特征,接人的距离、订单通知司机数量、订单是否在司机的行驶方向上等等;
  • 订单相关特征,距离和ETA、目的地类型、路线上交通情况等等;
  • 司机相关特征,司机长期表现、司机之前接受订单概率、司机行驶偏好等等;
  • 附加特征,天气、时间、周围司机和订单数等等。

组合优化模型

假设\(N\)个订单需要被分配,订单\(i\)被接受的概率为: \[ E_i=1-\prod_{j=1}^M(1-p_{ij})^{a_{ij}} \] 其中\(p_{ij}\)就是之前估计的骑手接受概率,所以我们可以把我们的全局目标表示出来: \[ E_{SR}=\frac{\sum^N_{i=1}[1-\prod_{j=1}^M(1-p_{ij})^{a_{ij}}]}{N} \] 其中还有约束为: \[ \sum^N_{i=1}a_{ij}\leq 1,\forall j \] 这样的组合优化问题往往是NP-Hard的,通常采用启发式的方式求解,如爬山法、遗传算法、模拟退火等等。为了平衡精确度和算法的性能,我们选择爬山算法来求解这个问题:

HillClimbing
HillClimbing

目的地预测

通过长期的观察,我们发现几个有趣的现象:

  • 同一个乘客会在相近的时间去同一个目的地;
  • 同一个乘客会去固定几个地方;
  • 订单的位置会对目的地的预测提供很多有效的信息。

鉴于以上几个现象,我们先将时间划分成工作日和节假日两个部门,工作日的目的地通常是家或者公司,节假日则更多的是购物中心或者娱乐场所,我们发现贝叶斯模型会更适合这样的场景。我们先做如下的标记:

notation
notation

因为\(D\)仅有两类,所以我们先以此把用户历史数据划分成两类,除此之外,我们根据时间对训练的历史数据进行加权,削弱历史对现在的影响。我们定义如下贝叶斯模型: \[ p(Y=y_i|X)=\frac{p(X|Y=y_j)p(Y=y_j)}{\sum^n_{j=1}p(X|Y=y_j)p(Y=y_j)} \] 其中\(X=(T,Lng,Lat)\)表示出发时间、经度和纬度。我们用乘客的历史数据估计\(p(Y=y_j)\)\[ p(Y=y_j)=\frac{\text{freq}(y_j)}{\sum^n_{j=1}\text{freq}(y_j)} \] 剩下的问题就是如何去估计出发时间和位置的联合分布了。通过分析数据,我们发现给定\(y_j\)之后,时间的分布近似正态分布,因此我们用正态分布来估计出发时间的条件概率 \[ T|Y=y_i\sim N(\mu_i,\sigma_i^2) \] 因为时间变量是从\(0-23\)变化然后重复的,所以\(\mu_i\)\(\sigma_i\)并不能用传统的方式进行估计,比如如果时间是8:00,9:00,10:00,他们的均值就是9:00,但是如果是3:00,15:00,21:00,,他们的均值是21:00,而不是\((3+15+21)/3=13\)。时间变量是一个循环的量,一种常用的方式是将其转化到单位向量上,计算向量的均值,然后再转换回去。给定时间\(t_1,t_2,\cdots,t_m\),他们的均值\(\mu\)可以表示成: \[ \mu=\frac{24}{2\pi}\cdot\arctan[\frac{1}{m}\sum^m_{k=1}\sin(\frac{2\pi}{24}\cdot t_k), \frac{1}{m}\sum^m_{k=1}\cos(\frac{2\pi}{24}\cdot t_k)] \] 这种方法足够简单明了,但会有略微的偏差,比如00:00:00,00:00:00,03:00:00的均值应该是01:00:00,这种方法计算出来是00:58:33。为了解决这个问题,我们提出了另一种计算出发时间均质的方法。出发时间的均值可以表示成如下二次优化问题: \[ \left\{ \begin{aligned} \min_\mu &&& \sum^m_{k=1}[\text{distance}(t_k,\mu)]^2 \\ \text{s.t.} &&& \mu\in[0,24) \end{aligned} \right. \] 其中\(\text{distance}(t_1,t_2)\)表示两个循环变量\(t_1\)\(t_2\)之间的距离: \[ \text{distance}(t_1,t_2)=\left\{ \begin{aligned} |t_1-t_2| &&& \text{if}\quad |t_1-t_2|\leq12 \\ 24-|t_1-t_2| &&& \text{if}\quad |t_1-t_2|>12 \end{aligned} \right. \] 上面式子可以写为 \[ \text{distance}(t_1,t_2)=-|(|t_1-t_2)-12|+12 \] 则约束问题可以写成 \[ \left\{ \begin{aligned} \min_\mu &&& \sum^m_{k=1}[|(|t_1-t_2|)-12|-12]^2 \\ \text{s.t.} &&& \mu\in[0,24) \end{aligned} \right. \] 通过求解上述问题我们可以得到均值\(\mu\),同样的方法也可以用来估计方差, \[ \sigma^2=\frac{1}{m-1}\sum^m_{k=1}\sum^m_{k=1}[|(|t_1-t_2|)-12|-12]^2 \] 为了找到一个近似的模型来描述三维的联合分布,我们观察了大部分用户的散点图,基本上与三维的高斯分布相同,因此我们假设对于一个给定的用户和一个预期的目的地, \[ Lat,Lng,T|Y=y_j\sim N_3(\pmb{\mu}_i,\Sigma_i) \] 为了证实我们的假设,我们做了正态性检验。完整的计算方法如下:

algorithm
algorithm

实验

具体细节参考论文。