80％的美国家庭使用 Instacart。对于Instacart配送系统，为确保按时，有效的交付订单。需要解决具有时间窗（DCVRPTW）的动态容量车辆路径问题。Instacart 的配送算法实时确定如何将采购者引导至杂货店地点以挑选杂货并将其在短短一小时内送到客户家门口。
图 1 配送流程
为了完成订单，采购者需要开车到商店，挑选杂货，然后开车到客户所在地进行交货。
为了优化采购者路线，我们需要知道采购者交付订单需要花费多少时间。这就是为什么我们建立了一个预测交货时间模型的原因。此预测模型的确切功能以及模型的构建方式并非本文的目的。
假设有一个客户下订单 1pm–2pm。这意味着我们需要计划行程，以使预计到达时间（ETA）在 1pm 和之间 2pm。1pm 之前是早到，2pm 之后是晚到。
图 2 计划按时交付行程的示例，即预计到达时间早于预定时间
但是，要确保按时交货，仅预测出在规定的时间（2pm）之前达到是不够的。我们希望采购者在预定时间之前实际交付订单。
图 3 实际按时交付的行程示例，即实际到达时间早于到期时间
换句话说，要确保订单确实按时交付，我们需要：
实际到达时间 = ETA + 预测误差 < 到期时间
显然，直到交付订单后我们才知道预测误差，因此我们需要一种方法来预测误差的大小。即使我们的预测模型是无偏的，这意味着误差的分布范围很广。以下是不同城市的预测误差分布：
图 4 模型误差的分布，误差=实际-预测
因此，考虑到这一点，用缓冲时间覆盖模型预测误差。因此，在计划前往采购者的行程时，我们需要使用缓冲时间：
ETA + 缓冲时间 < 到期时间
现在的问题是：我们该为缓冲时间选择什么值？
1. 简单方法
作为简单的解决方案，我们查看了延迟交货的百分比，具体取决于我们计划的交货时间。
图 5 延迟百分比取决于我们计划的交货时间
例如，在旧金山，如果我们计划所有交付都在结束前10分钟交付，我们会发现约18％的交付迟到。我们根据最大延迟百分比来选择固定缓冲时间。通过上图，并选择了一个缓冲时间，以便在最坏的情况下可以得到10％的延迟交货。使用这种方法，我们为芝加哥北部选择了13分钟，为曼哈顿选择了15分钟，为旧金山和迈阿密选择了18分钟。但是，这种方法显然不是最佳的。在某些情况下，风险较高，而在某些情况下，风险较低。因此，固定的缓冲时间有时可能过于保守（迟到的风险更高），有时可能过于激进（效率降低）。更好的方法是计算交货时间的预测间隔，并使用间隔的上限。这就是分位数回归起作用的地方。
2. 分位数回归
首先，来解释什么是分位数回归。典型的回归旨在拟合分布的均值。我们尝试在给定预测变量x的某些值情况下响应变量y的条件均值。在这种情况下，目标是使平方误差之和最小。
$$\sum_{i=0}(y_i-\hat y_i)^2$$
分位数回归是估计一组回归变量 X 与被解释变量 Y 的分位数之间线性关系的建模方法。以往的回归模型实际上是研究被解释变量的条件期望。而人们也关心解释变量与被解释变量分布的中位数，分位数回归是 Koenker 和 Bassett 针对最小二乘的不足提出来的一种新的估计方法，它不仅能够度量回归变量对分布中心的影响，而且能度量回归变量对分布上尾和下尾的影响，在不同的分位数下进行预测，得到的信息更为全面和精确。在分位数回归中，对于给定的分位数 $q$ 得到一组预测值 Q。在这种情况下，我们尝试最小化以下损失函数：
$$\sum_{i=0}\rho_q(y_i-\hat y_i),\,\,with\,\, \rho_q(u)=u(q-1_{u<0})$$
特殊情况q = 0.5对应于中位数回归，其中成本函数是绝对偏差：
图 6 不同q值的线性回归和分位数回归的成本函数
现在，假设要构建一个简单的线性模型来预测交货时间，它是距离的函数。
图 7 线性回归可预测交货时间与距离的关系
通过分位数回归，我们可以获得交货时间的预测间隔。让我们选择 q=0.1 下限和 q=0.9 上限。
图 8 q=0.1和q=0.9的分位数回归，用作预测间隔
分位数回归提供了交货时间的预测间隔。预测间隔随着配送距离的增加而增加，这是合理的，因为对于长距离而言，准确预测变得越来越困难（方差更大，数据更少）。因此，我们看到此预测间隔比平均预测值要好得多。
在案例中建立了交货时间的分位数回归q=0.9。此模型将为我们提供交货时间的上限，用于确保90％订单的交货不会延迟的时间。在向采购者发送交货时，我们需要：
从第 90 个分位数预测 < 到期时间
3. 多目的地配送
实际上，我们的履行引擎会尝试生成最多包含 5 个交付的行程，以节省采购者的时间并提高系统效率。
图 9 订单履行过程
在计划此类配送时，我们需要确保所有订单都会按时交付，并且我们需要管理迟到的风险。此风险是累积性的。例如，如果采购者花费的时间比给定订单的预期时间长，那么这将影响行程中剩余的交货。为了解决此累积风险，我们需要用于给定交付的缓冲时间必须是旅途中先前交付的缓冲时间的函数。让我们首先以两次交付为例，即一次履行包含 2 个交付 D1 和 D2。
图 10 包含2次送货的路程示例
- $D_{t0 -> 1} = 从商店到 D1 的预计交货时间$。
- $D_{t1 -> 2} = 从 D1 到 D2 的预计交货时间$。
- $Q_{t0 -> 1} = 从商店到 D1 的第 90 个百分位预测时间$。
- $Q_{t1 -> 2} = 从 D1 到 D2 的第 90 个百分位数预测时间$。
- $B_{0 -> 1} = Q_{t0 -> 1} - D_{t0 -> 1} = 从商店到 D1 的交付时间缓冲$。
- $B_{1-> 2}= Q_{t1 -> 2} - D_{t1 -> 2} = 从 D1 到 D2 的传送时间缓冲$。
- $B_{0 -> 2} = 我们需要使用以确保 D2 不会延迟的缓冲时间$。
现在，我们需要计算所需的缓冲时间 $B_{0->2}$，以确保 D2 将在适当的时间之前交付。
$D_{t0 -> 1} + D_{t1 -> 2} + B_{0 -> 2} < D2$ 的到期时间
为了近似此缓冲时间，我们假设交付时间遵循正态分布，并且它们是独立的。
$$D_{t0->1}\sim N(\mu_1,\sigma_1^2) ,\,\,\,D_{t1->2}\sim N(\mu_2,\sigma_2^2)$$
两个独立正态随机变量的总和仍遵循正态分布：
$$D_{t0->2}=D_{t0->1}+D_{t1->2} \sim N(\mu_1+\mu_2,\sigma_1^2+\sigma_2^2)$$
我们知道，对于正态分布，可以轻松地将预测间隔计算为 $[\mu - z * \sigma, \mu + z * \sigma] $（z=1.67对于 90％ 的预测间隔）。因此意味着：
$$\begin{eqnarray*}
B_{0->1} &=& z*\sigma_1 \\
B_{1->2} &=& z*\sigma_2 \\
B_{0->2} &=& z*\sqrt{\sigma_1+\sigma_2} &=& \sqrt{B_{0->1}^2+B_{1->2}^2}
\end{eqnarray*}$$
最后，以下公式可用于概括为 N 个交货行程，第 N 次行程交付的累积缓冲时间：
$$B_{0->N}=\sqrt{\sum_{i=1}^NB_{(i-1)->i}^2}$$
4. 结果
当使用分位数回归与固定缓冲时间进行比较时，我们执行了 A/B 测试以衡量对效率/延迟折中的影响效果。
图 11 借助分位数回归，我们可以在不增加延迟时间百分比的情况下更接近计划到期时间
从上图可以看出，通过分位数回归，我们能够在接近到期时间的情况下计划交货，而不会增加延迟百分比。这种效果使我们能够在配送履行引擎中探索更多的行程组合，从而将效率（最重要的指标之一）提高4％。
结论
在许多预测问题中，可能不仅需要平均水平。分位数回归允许近似分布的任何百分比，因此可以提供变量之间关系的更全面分析。在 Instacart，分位数回归已被用来更好地理解和管理延迟交付的风险。
1. 分位数回归的优点
(1)能够更加全面的描述被解释变量条件分布的全貌，而不是仅仅分析被解释变量的条件期望（均值），也可以分析解释变量如何影响被解释变量的中位数、分位数等。
(2)不同分位数下的回归系数估计量常常不同，即解释变量对不同水平被解释变量的影响不同。
(3)中位数回归的估计方法与最小二乘法相比，估计结果对离群值则表现的更加稳健，而且，分位数回归对误差项并不要求很强的假设条件，因此对于非正态分布而言，分位数回归系数估计量则更加稳健。
2. 普通回归优化为分位数回归的过程：
在一般线性回归中，我们估计的是一些变量y的平均值，条件是自变量x的值。
当我们在数据上拟合一般最小二乘回归模型时，我们对线性模型中的随机误差项做了一个关键假设。我们假设误差项在自变量x的值上有一个常数方差。
- 当这个假设不再成立时会发生什么？
- 另外，除了估计自变量的平均值，我们还能估计自变量的中位数、0.3分位数或0.8分位数吗？
这就是分位数回归发挥作用的地方。
评论