前言
近日，阿里本地生活智慧物流团队的一篇论文——Order Fulfillment Cycle Time Estimation for On-Demand Food Delivery被KDD’2020 Applied Data Science Track接收为Oral presentation（ACM Knowledge Discovery and Data Mining（SIGKDD），CCF A类会议，数据挖掘领域顶级会议，2020 年的口头报告接受率为 5.8%）。
外卖履约时间预估（OFCT：Order Fulfillment Cycle Time）问题相比一般的时间预估问题而言更为复杂，其中存在餐厅与用户的供需关系、餐厅出餐时间的未知性以及骑手行为的不确定性等问题。在论文中我们向学术界首次详细介绍外卖履约时间预估这一问题，并给出了有效的解决方案，最后得到了审稿人的一致认可。
通过逐步拆解整个外卖履约（履约：饿了么平台保障骑手能够将外卖准时送达给用户）的过程，我们分析了外卖履约时间预估相比常见的其他送达时间问题（例如打车）的显著差异，并针对影响履约时间长短的特征进行了解释和说明。对于用户而言可能只是看到外卖需要多久才能吃到，而在这背后需要我们提炼出丰富的影响因素，来保证履约时间预估的准确性。我们将这些影响因素输入深度神经网络来推断它们和履约时长的关系，同时我们进一步引入了餐厅、用户地址以及骑手的隐向量来增强模型的预测性能。最后，我们提出一个新颖的后处理神经网络算子，用于改善模型的收敛速度和准确度。我们所介绍的模型已在饿了么实际部署，每天服务于千万用户。
背景介绍
履约时间预估模型预估的是从用户下单到骑手将订单送达用户手上的这段时间（即预计送达时间）。饿了么平台每天产生千万级订单量，时间预估作为即时配送的其中一环，既影响用户体验同时也涉及到骑手履约，因此其准确性对平台而言至关重要，既不能预估的太长（影响用户体验），也不能预估的太短（骑手无法按时完成配送）。下图为时间预估涉及的各个环节。
主要环节包括：
- 用户：用户从下单到订单送达其手中。对于每一位用户而言，肯定是希望能够准时拿到下单的餐品。
- 餐厅：餐厅从接受订单到备餐完成。餐厅需要做到尽快完成备餐，这样才能够不影响骑手取餐及配送，如果骑手到达餐厅的时候需要等待很久的时间才能取走餐品，那么骑手容易焦虑，一部分用户也会在饿了么App上催促骑手。
- 骑手：骑手从接收到订单到完成配送。其中包括骑手到达餐厅，然后从餐厅处取走订单对应的餐品。同时，骑手可能从餐厅处取多餐，因此需要等拿到所有订单骑手才会离开并进行配送。
- 平台：饿了么平台需要从中协调用户、餐厅、骑手并兼顾配送效率。这其中包括订单指派与路径规划。订单指派是指将订单分给附近合适的骑手，而路径规划是指给骑手推荐合理的取送路径，此路径需要同时考虑骑手配送距离和订单超时风险。
下图即为大家日常在饿了么上面点外卖的时候能够看到的信息，其中配送时间就是我们履约时间预估模型计算出的。
外卖履约时间与 ETA 的差异
Estimated Time of Arrival (ETA)即“预估送达时间”，一般预估的是从出发地到目的地的时间，打车场景中的预估送达时间即为一类典型的ETA问题。
本文提出的外卖履约时间预估模型，预估的是从用户下单开始到骑手将餐品送达用户手中所花的时间，用户在饿了么点了外卖以后，订单在平台开始流转的过程如下图所示。
外卖履约时间预估相比预估送达时间而言更为特殊，主要体现在以下两方面：
1 需要考虑更多影响因素
一般的预估送达时间问题仅需考虑天气、交通状况，时空信息及路径信息等，而外卖履约时间预估问题除了考虑此类信息外，还需考虑餐厅的地理位置，餐厅订单备餐时间以及调度系统派单等信息。
2 无法获取关键信息
用户下单成功时饿了么已经为用户预估出预计送达时间，而此时订单并未被骑手接单，骑手需要被系统指派才能开始取餐和配送，因此我们无法提前获取骑手的信息及其实际的配送路径。
以上两方面的差异给外卖履约时间预估问题的准确性带来极大的挑战。
外卖履约时间预测一般需要哪些特征
为了建模外卖履约时间，一般需要充分利用与订单信息相关的数据，具体包括：
- 空间特征：包括大量id类特征，例如用户所在区域id，餐厅id，城市id及网格id等。
- 时间特征：包括小时时刻，当天是否工作日等，如下图（a）。
- 描述订单大小的特征：包括订单对应的菜品数量以及订单价格等。
大家应该会好奇订单价格会对外卖时间长短造成什么影响？当用户下单的金额较高时通常餐品对应的重量或体积较大，比如用户预订了蛋糕或者集体点了很多杯奶茶，这种总金额高的订单对于骑手而言属于难配送订单，因此需要花费较长的履约时间。下图（b）展示出了这种相关性，可以看到订单价格的高低在一定程度上可以刻画出订单是否难配送的隐含信息。
供需关系对履约时长的影响
从平台角度看，用户下单量和餐厅接单量不同时刻都在发生剧烈变化，这种供需维度上的变化对实际配送时长会造成极大影响。
在介绍供需特征构造的工作前，先为大家介绍外卖配送中“波次”的概念：对于骑手身上的一组订单，对给定的一组订单取送顺序进行分组，保证每组中所有相关订单的取和送行为都在该组中，该分组则为骑手当前配送的波次。针对供需变化，我们构造了基于时段的供需比和完成率等特征。当供需比越高时波次的平均长度会变长，此时履约时间越长。
另一方面当完成率越高时可以推断出骑手完成配送的订单越多，此时骑手可以继续承接系统接下来分派的订单。
此外，我们通过餐厅当前待取餐单量（餐厅接单后等待骑手来取的订单数）来刻画餐厅的繁忙程度，当餐厅接单数变多而产能受限时会导致订单积压，此时如果骑手已经到达餐厅则需要花费较长的等待时间才能取到餐品，相应的当餐厅变繁忙时，模型预估的履约时间将变长。
餐厅的出餐时间
订单的出餐时间是外卖履约时间预估模型的一个重要影响因素，这个特征我们是通过聚合餐厅的历史出餐时间得到的。但目前存在的难点问题对出餐时间计算的准确性带来极大考验，主要包括：
- 餐厅在备餐完成后缺乏人力来逐单点击出餐按钮，导致我们平台不能完全搜集到餐厅出餐的真实值，因此我们目前主要依靠系统采集的骑手点击出餐数据来标记餐厅的真实出餐时间。
- 饿了么平台目前主要计算的是餐厅在饿了么App产生的订单，缺乏餐厅在其他渠道产生的订单或堂食订单数据，因此较难获取餐厅的实际供需情况。
- 餐厅的真实出餐时间具有较大的随机性。例如餐厅针对某些餐品可能会提前进行备餐，这部分提前备好的餐品可以立即出餐。而对于用户下单时餐厅需要现做的餐品，骑手到达餐厅后可能需要等待一段时间才能取到餐，这部分现做的订单真实出餐时间将会偏长。
- 订单的先后顺序不一定表示餐厅出餐的先后顺序。由于餐厅灶台数量有限，相应的灶台只会处理固定的菜品，因此在一批订单中如果出现相同的菜品，后厨会选择一起做，这种情况下部分订单的出餐时间会明显偏短。
在实际运用时，我们是根据商家接单时间到骑手实际点击取餐时间来计算商户的真实出餐时间，而这其中存在一部分噪音数据：
- 骑手接单后即刻点击到达餐厅
- 骑手接单后即刻点击取餐按钮
此外，对于一部分训练样本，我们认为骑手在取到餐品时实际上餐厅已经备餐完成，例如骑手晚取餐或骑手同时点击取多餐。针对这些数据我们在计算餐厅出餐时间特征时进行了一定比例的剔除。
如何合理利用骑手信息
饿了么从平台角度出发，将每个城市划分成了以“网格”为最小单元的不同区域，每个蜂鸟配送站点内的骑手会服务于站点周边范围内固定的若干个网格，骑手对站点辐射的网格内的商圈或者小区的熟悉程度决定了其配送效率。从下图大家可以看到，因为骑手对餐厅所在位置、用户所在小区都比较熟悉，因此在取餐或者配送的过程中并没有发生绕路的情况。
而用户下单成功时饿了么App会立刻为用户显示外卖预估履约时间，此时订单指派给具体哪位骑手来配送是未知的。为了充分利用与骑手相关的影响因素，我们根据骑手取餐距离、骑手当前接了多少订单等特征来表征订单可能被接单的每一位骑手，然后将可能接单的骑手序列进行特征编码传入外卖履约时间预估模型中，随后利用注意力机制提取骑手序列信息，以此来增强模型的预测能力。
多维度相似订单的配送段 ETA
配送段ETA指的是预估骑手到达目的地（用户所在位置）附近下车后将餐品送到用户手中所花的时间，是骑手配送的最终环节。
为了估算配送段ETA，我们理论上可以直接采用回归模型来学习，但是常用的回归模型通常将输入转化为一系列的特征，并且通过有监督学习找到这些影响因素和输出目标之间的关系，为了方便学习和提高模型泛化能力通常基于神经网络和集成树模型将这些关系参数化为一个平滑的函数，但这种平滑假设的缺点是无法很好的处理长尾不规律case，可能会影响用户体验。例如当骑手送餐需要乘坐高层电梯时，如果遇上高峰期，可能需要等待很长的时间，而系统很难做到这种实时的预判。从下图可以看出，骑手送餐时在楼内花了7.6分钟。
为了部分缓解这种问题，我们借鉴了近期基于记忆的语言模型[1]的思想，将历史订单作为配送段时间预估的语料，通过构造多维特征来表征每个历史订单，当新的订单产生时我们基于K近邻来搜索出与新订单相似的若干个历史订单，然后对这若干个相似单的真实配送段时间做加权平均，以此作为新订单的预估配送段时间。最终我们将基于K近邻搜索出的预估配送段时间作为特征输入外卖履约时间预估模型中。
针对长尾数据如何解决
时间预估本质上属于回归问题，在训练模型的过程中我们发现模型收敛较慢且交叉验证的表现偏离预期，通过分析原因我们发现模型拟合的数据分布与真实履约时间的分布发生了偏移，真实的履约时间实际上是一个右偏长尾的分布，相当于有一小部分订单真实的配送时间偏长而模型没有学习到，针对此问题在本文中我们提出了一个新颖的后处理神经网络算子，针对外卖履约时间预估模型的拟合结果进行缩放和变换，用于改善模型的收敛速度和准确度。此后处理算子可描述为：
其中，
经过离线训练验证，后处理算子可有效提升外卖履约时间预估模型收敛速度和准确度。
近期，我们又探索出一种新的后处理算子：自适应Box-Cox逆变换，相比于本文提出的后处理算子，自适应Box-Cox逆变换算子更加能够拟合长尾数据分布，使模型效果得到了进一步改善，目前此算子已经应用于线上推断。
实验效果
我们提出的外卖履约时间预估模型以“编码及预测”作为模型主体结构，具体结构如下图所示。
其中，Nearest Courier Index这个模块实现了前面介绍的骑手信息编码，这个模块可以让模型充分利用可能接单的骑手信息；Postprocessing即为后处理算子，这个算子让模型能够更快收敛，同时也提升了模型的准确率。
在我们提出外卖履约时间预估模型前，线上时间预估模型已经稳定运行了一段时间，因此我们以线上已有模型作为baseline进行了AB实验。下图实验数据显示，外卖履约时间预估模型相比于原有模型，MAE相对降低9.8%，用户投诉率相对降低19.3%，预测误差和用户投诉率均有明显改善，对用户体验产生了明显的正向效果。
总结与展望
在本文中我们为大家介绍了饿了么目前线上实际运行并服务于用户的外卖履约时间预估模型，通过离线评测及在线测试均证明了其有效性。
未来我们主要将着力于如下两方面继续研究：
- 出餐时间作为外卖履约时间预估模型的影响因素之一对其相当重要，但目前出餐时间处理相对简单因此具有相当大的提升空间。
- 此外，我们将研发出一套通用的模型框架，即针对出餐时间和履约时间进行多任务学习。
参考文献
[1] Urvashi Khandelwal, Omer Levy, Dan Jurafsky, Luke Zettlemoyer, and Mike Lewis. Generalization through memorization: Nearest neighbor language models. In ICLR, 2020.
深度学习课程 | 神经网络概览及算法详解
人工神经网络（Artificial Neural Networks，简写为 ANN）是一种模仿动物神经网络行为特征，进行分布式并行信息处理的算法数学模型。本课程共 36 课时，主要介绍神经网络学习规则、感知神经网络、竞争神经网络及反馈神经网络等，帮助大家掌握神经网络的相关概念和算法模型。
识别下方二维码或点击文末“阅读原文”立刻学习吧：
