今天来换换口味，看一篇阿里饿了么ETA相关的文章，这篇文章中了KDD2020，里面有很多真实的实践，包括特征构建、深度模型调优等等，总体看来下来还是含金量比较高的文章。

即时订餐配送平台上一个很重要的机器学习应用场景就是订单履约周期预测（Order Fulfillment Cycle Time prediction），OFCT的预估一般会在用户下单前展示出来，其准确性对于用户感知的确定性十分重要，同时也会影响平台对于分配订单的的决策。在这篇文章中，我们提出一种OFCT的预测模型，每日服务国内200+城市1000w+订单的配送。

OFCT预测可以看作是一种ETA预测的变种，广义的看，ETA是对起终点（Origin-Destination pair，OD对）的旅行时常的预估，一般分成两种方式：route-based和OD-based。前者是通过对不同子段的预估值进行聚合得到整段路程的预估值，后者则是通过od的起终点位置以及相应的时间作为输入。与一般的ETA问题相比，OFCT具有不同的挑战：

受到更多的影响，在广义的ETA问题中，一般只有考虑天气、交通条件，OD对的时间、地理信息，在OFTC中，还收到餐馆属性、位置、以及出餐时间、骑手分配的影响。
部分关键信息不可用，OFCT的预测必须在订单创建前告知用户，这就使得很多关键信息在这时是未知的，包括骑手以及具体送餐路径的信息。

由于这些问题，标准的ETA方法并不能应用于我们的场景。

Background

上图是订单履约周期的构成。

OFCT在用户下单前需要被展示出来，订单创建后，餐馆会被提醒准备订单，然后决策派单和路径规划，派单是指决策由哪个骑手来配送这个订单，路径规划则是决定骑手身上每一单的取送顺序。这个优化问题的损失函数由两部分组成，逻辑上的成本和用户超时/提前成本，前者是配送的时长或者距离，后者是这个订单超时或者提前送达对于用户造成的不便，一般这个问题会用贪心算法求解。
被指派的骑手会去餐厅去餐，当餐品准备好之后由骑手送出，骑手有可能会在这个餐厅取多个订单。
骑手根据配送终点依次完成订单。

符号定义 \[ \text{OFCT}_o=t_o^\text{receival} -t_o^\text{creation} \] 为了方便讨论，我们把OFCT拆成两部分，取餐时间和送餐时间，分为别 \[ \text{PT}_o=t_o^\text{departure} -t_o^\text{creation}\\ \text{DT}_o=t_o^\text{receival} -t_o^\text{departure} \] 其中，商家备餐时间为\(\text{CT}_o=t_o^\text{ready} -t_o^\text{creation}\)

Feature Extraction

订单信息（Order Information）

空间特征，起点、终点的格子id、经纬度
时间特征，一天中的小事，是否为工作日
订单大小特征，一个大的订单会需要更多的备餐时间，同时对于配送难度也会增加，此处采用sku数量\(\text{sku_num}_o\)和价格\(\text{price}_o\)来刻画订单的大小，sku数量是一个较为直观反应订单大小的指标，同时，因为会存在套餐的情况，多个sku会被当成一个单独的sku，同时存在好多相同sku的订单，所以在sku数量基础上增加价格作为补充

聚合特征（Aggregation Features）

聚合的方式一般会用20分位数、均值、标准差和80分位数，我们首先根据一些特定的规则选择一些订单，然后根据这些订单计算出聚合特征，不同特征会采用不同的筛选方式，比如说相同的城市、格子、餐馆、小时的订单，或者是当前时间前，不同时长度完成的订单。

餐品特征（Dish Features）

餐品特征，id类做embedding，此处用的是一个中文的BERT。

备餐时间特征（Cooking Time Features）

备餐时间对于OFCT的估计十分重要，但是我们往往又没有这个值的真实值，因为餐馆一般没有人力来记录这样的信息，为了改进模型，我们尝试通过历史订单数据来构建备餐时间。基于经验，我们做了以下假设，一个骑手进入餐馆取餐时，会有以下三种情况：

骑手来的太早，必须等到餐品准备好
骑手需要多取几单，需要等到最晚的订单的餐品准备好
骑手在餐品准备好之后来到餐馆，拿了就走

基于以上假设，对于\(\forall \tilde{o}\in\mathcal{O}^\mathbb{H}_o\)，用\(\mathcal{O}^r_\tilde{o}\)表示骑手\(c_\tilde{o}\)从\(r_\tilde{o}\)取的和\(\tilde{o}\)一起的订单的集合，我们把离店时间近似表示为 \[ \Bigg| t_\tilde{o}^\text{departure} - \max\Big\{ t_\tilde{o}^\text{arrival}, \underset{\tilde{o}\in\mathcal{O}^r_\tilde{o}}{\max} \big\{t_\hat{o}^\text{ready}\big\} \Big\} \Bigg| < \alpha \] 一个骑手，在这家店，取得若干个订单中，里面准备好最晚的时刻，和骑手到达时间取max，用离店时间减去这个值，其中\(\alpha\)是预先定义的超参数，用来衡量这种近似的潜在误差。这里\(\alpha\)应该是指骑手到店、找餐品的时间。定义在备餐的订单为 \[ \mathcal{O}^\text{CT}_o=\bigg\{ \tilde{o}\in\mathcal{O}^\mathbb{H}_o \bigg| t_\tilde{o}^\text{departure} - t_\tilde{o}^\text{arrival} > \alpha, \mathcal{O}^r_\tilde{o}=\{\tilde{o}\} \bigg\} \] 即骑手要取的订单，如果骑手在常规到店、找餐还付出额外的等待时间，那么这就是在等待商家备餐。对于备餐的订单，满足 \[ \max\Big\{ t_\tilde{o}^\text{arrival}, \underset{\tilde{o}\in\mathcal{O}^r_\tilde{o}}{\max} \big\{t_\hat{o}^\text{ready}\big\} \Big\} > t_\tilde{o}^\text{departure} - \alpha >t_\tilde{o}^\text{arrival} \] 可以推出\(\underset{\tilde{o}\in\mathcal{O}^r_\tilde{o}}{\max} \big\{t_\hat{o}^\text{ready}\big\} > t_\tilde{o}^\text{arrival}\)，且 \[ \begin{aligned} |\text{CT}_\tilde{o}-\text{PT}_\tilde{o}|&= |t^\text{ready}_\tilde{o}-t^\text{departure}_\tilde{o}|\\ &=\bigg| \max\Big\{ t_\tilde{o}^\text{arrival}, \underset{\tilde{o}\in\mathcal{O}^r_\tilde{o}}{\max} \big\{t_\hat{o}^\text{ready}\big\} \Big\}-t^\text{departure}_\tilde{o} \bigg| \\ &< \alpha \end{aligned} \] 通过以上方式来筛选出备餐的订单，然后通过统计这些订单的时长作为备餐时间特征。

（TODO：说实话这段写得太没逻辑了，到现在还没太看明白。）

供需特征（Supply and Demand Features）

由于用户需求的变化，订单量会有显著的变化，对OFCT有较大的影响，首先尖峰形状的需求，会被打包的策略（即一个骑手接多个相近起点的单）改善，当打包的大小增加时，会使得物流的效率更高（更加顺路，增加的边际时间比较少），同时也会增加每一个订单的OFCT。同时因为增加了订单，骑手无法选择最快的路径去送货，单个订单的配送时间会增加，但会降低总体的配送时常（顺路造成的额外成本）。我们用供需系数来描述这个现象 \[ \text{DSR}_o=|C|^{-1}\bigg| \mathcal{O}_o^\text{uncompleted}\bigg| \] 其中未完成订单是当前时间节点的未完成订单。同时我们定义派送系数特征 \[ \text{dropoff_ratio}_o=\bigg| \mathcal{O}_o^\text{uncompleted} \bigg|^{-1}\bigg| \mathcal{O}_o^\text{dropoff} \bigg| \] 其中派送订单是指当前未完成订单中处于派送途中的。如果DSR更高，平均打包的大小会增加，因此OFCT会变得更长，另一方遍，更高的dropoff_ratio表明有更大比例的订单接近完成，有更多的骑手会变成空闲状态来接受其他订单，这使得打包的大小和OFCT都会降低。

有些时候，客户订单会特别集中于某些店铺，超出了店铺的承受能力，我们通过未接单unfetched_order_count来衡量餐馆的忙碌程度，即订单请求到达但是上街未接单的数量。

以上供需类特征都是采用实时特征，一个很自然的担心点就是这些特征可能是有偏的，因为未来的用户需求被忽略了。这个可以通过增加一个对于未来需求的预估来进行改善，然而，在我们的实践中，我们很难通过这种方式改进模型。其中潜在原因在于用户的需求很难被准确的孤寂，同时需求预测自身也依赖于OFCT所用到的特征，这使得需求的预测很难带来一些额外的信息。

骑手特征

正如前面解释的，具体哪个骑手来接单，在OFCT预估前是未知的，为了解决这个问题，我们使用模型中分离出来的部分来预测骑手可能接到订单概率的排序，并且将排名靠前的骑手信息加入模型，来增加模型准确率。骑手相关的特征包括：

取餐距离，取最短路面距离
工作负重，骑手身上的订单数，因为背的订单越多，会增加总的绕路距离，因此新增订单会产生更多的配送时长和用户的超时成本
紧急程度，骑手在满足时间窗约束时，完成身上的订单需要的最少时长，因为违反时间窗的约束会导致最终成本的增加
相互距离，骑手身上订单的终点和餐馆的平均或者最小路径，这个值越大，说明骑手接这个订单绕路越远，产生的成本越高

配送时间特征（ETA-based Drop-off Time Features）

历史相似订单的配送时长的加权平均作为特征。用TEMP+R的方式来刻画起终点的ETA距离，包含起终点的时间、经纬度，首先将订单映射为一个5维的向量，然后计算订单间的相近程度（欧氏距离），选出k个跟当前订单最相近的订单，然后加权求和得到预计的配送时长（公式太长懒得打...）

这个是一个看着比较简单的操作，但是这个检索匹配难度应该还是挺大的，此处应该有一些工程优化，文中没有提及。

气象特征（Meteorological Features）

天气相关特征，温度、空气质量、风速以及天气条件。前面几个是连续数值类型特征，后者是类别特征。

模型

我们也采用encode&predict的范式来构建我们的模型，首先不同的特征被encode为一个固定长度的向量，这些向量被拼接在一起喂进模型。

特征编码

连续特征，标准化到[0,1]范围内，原始连续特征维度相对较低（小于100），这可能会限制NN的表达能力，所以我们增加了2层200维的ELU全联接层来增加向量的表征
类别特征会转化成embedding，同时上层增加dropout层来避免过拟合
骑手特征的编码，骑手需要用相关特征进行排序，我们采用一个两阶段的策略：首先先从所由骑手中召回一个子集，然后再对这个子集进行重排序，为了简化模型，第一步的召回我们采用取餐距离作为筛选标准，在重排序阶段我们采用QILCM进行排序，对于召回子集中的骑手，都会产生一个表征向量，最终我们采用排序得分来对这些骑手的表征向量加权求和。

回归模型

回归模型整体是一个简单的多层神经网络，此处我们提出一个后处理模块。因为在之前的训练中，我们发现这个网络的收敛速度比较慢，同时表现不如预期，我们发现原因在于真实的OFCT分布和初始化预测时候的OFCT分布并不一致，这使得模型需要先去校准整体的分布，使得收敛速度非常慢，我们将回归模块的结果进行一个校准 \[ \text{OFCT}_o^\text{predict}=\mu^\text{real} +\sigma^\text{real}\cdot \frac{y_o^\text{out}-\mu^\text{ini}}{\sigma^{ini}} \] 这些统计值由整个训练集计算得出。

目标函数

我们同时对预测值和排序值进行优化 \[ \begin{aligned} &\ell_\text{predict} +\lambda \ell_\text{rank} \\ &\ell_\text{predict} =\big| \text{OFCT}_o^\text{predict} - \text{OFCT}_o\big| \\ &\ell_\text{rank}=-\sum_{\forall c\in C^\text{candidate}}\big( \mathbb{I}(c=c_o)\log(s_c) \big) \end{aligned} \]

实验

离线实验采用一个月做训练，未来的一个星期做测试，评估指标为MAE和MAPE，我们分别对比了相同的模型，去掉某一类特征对于MAE以及MAPE的影响

以及不同模型的相关指标

对于在线的AB测试，是和GBM的基线对比

建议阅读

官方解读：履约时间预估：如何让外卖更快送达？

Introduction & Related Work