美团配送 2021KDD 论文：A Deep Learning Method for Route and Time Prediction in Food Delivery Service
背景
配送零碎存在一些要害预测环节。
- ETA：用户下单前，零碎会给用户一个承诺的预计送达工夫（ETA）；
- ETR：订单（A）调配到具体的骑手之后，在用户侧 APP 端能够看到骑手地位，以及更加精确、实时变动的预计送达工夫（ETR）；
-
预计配送程序：在后续的订单调配时，须要预测订单（B）调配到骑手之后，骑手新的配送程序（预估程序）以及新的达到各用户的工夫（ETR）。（须要留神的是，因为骑手受到 ETA 的束缚，并不会随便抉择配送程序）
- 评估指标 1：参考排序指标，LSD（location square deviation）、kendall 系数
- 评估指标 2：程序统一率，即，两个程序的公共前缀长度占比
- 评估指标 3：工夫指标，ME、MAE、N 分钟置信度
- 倡议配送程序 ：在骑手端，零碎会基于时效、途程、交通规则等给出倡议配送程序（倡议程序），对骑手没有强制力。 倡议程序为分单之后的动作，对分单策略不具备参考意义。
本文要解决的是外卖配送畛域的骑手门路预测和工夫预测工作，简称 FD-RTP (Food Delivery Route and Time Prediction)。FD-RTP 问题较为简单，次要体现在 3 个方面：
- 骑手通常同时对多个订单进行取餐和配送（在顶峰时段，甚至能够达到同时取送 10 单），对应的门路求解空间微小，针对高峰期 10 单的状况，能够达到 2.376*10^15 个解。此外，门路预测须要思考骑行间隔以及每个订单的准时性。
- 整个门路的工夫预测波及到骑行工夫、取餐配送阶段的步行工夫、骑手在餐厅的等餐工夫 3 局部。工夫预测过程中存在比拟大的不确定性，而且随着门路长度的增长，这种不确定性也随之减少。
- 作为一种线上算法，FD-RTP 工作会被其余利用频繁调用，因而，FD-RTP 工作须要在毫秒粒度返回后果。
之前（外卖配送门路布局算法：两阶段疾速启发式算法）将 FD-RTP 工作看做一个 PDPTW (pickup and delivery problem with time windows) 问题，重点通过优化搜索算法最小化启发式 cost（heuristic cost，由 time delay、delivery distance 两局部组成），鲜少晋升工夫预测的准确度，而工夫预测作为 PDPTW 中计算 time delay 的要害参数，其准确性降落也会导致搜寻出的门路后果准确性降落。以后的算法构造下，针对单个 FD-RTP 工作，启发式搜索算法在返回后果之前须要求解上千个轮次，每个轮次都须要调用工夫预测算法。正是因为这种算法构造，须要工夫预测算法疾速返回后果，所以，模型选型、特征选择总要做一些取舍，e.g. 工夫序列模型，骑手的历史行为习惯特色、时空关系特色、骑手所在位置的环境特色。
相干工作
RR (Route Recommendation)
RR 问题指的是，在给定 OD 的前提下，基于历史轨迹为用户举荐出适合的 routes。在之前的工作中，将该问题看做是一个在图（graphs）上的门路布局问题（pathfinding problem），钻研重点次要在设计启发式搜索算法，升高搜寻空间。启发式搜索算法须要大量的迭代轮次，同时，设计适合的 cost 函数成为了算法的关键点。
然而，大量的钻研将 cost function 设计成启发式的，导致算法应用性受限，不便于大范畴推广。同时，启发式搜索算法在搜寻过程中难以充分利用各种各样的环境特色，这基本上也是整个运筹优化方向类算法所面临的独特缺点。
针对以上问题，大量的钻研放在了利用机器学习办法引入更多的特色参加推断。
- Chen et al. propose a Maximum Probability Product algorithm based on the Absorbing Markov Chain to discover the most popular route between two locations [4]
- In [22], the authors adopt probabilistic models incorporating both temporal dynamics and spatial dynamics and address the data sparsity challenge for route recovery.
-
The development of deep learning sheds light on the RR problem using neural networks, especially the promising effectiveness of RNN for modeling sequential trajectory data.
- In [1], the authors propose Space Time Features-based RNN to predict people next movement by discovering the mobility patterns.
- Wu et al. design two RNN based models to capture variable length sequence of trajectory data and address the constraints of topological structure on trajectory modeling [21]
因为引入了订单准时率、骑手骑行老本，FD-RTP 工作比 RR 问题更加简单。
ETA
ETA 预测有两个流派：OD-based、route-based。
OD-based 类型的办法次要应用起始点特色，不思考 route 及 segment 粒度的特色。相干钻研如下：
- Jindal et al. propose ST-NN (Spatio-Temporal Neural Network), predicting the travel distance between OD and further predict the travel time combined with other time information [9]
- In [14], Wang et al. propose TEMP+R, which estimates the time duration as the weighted average travel times of similar historical trips.
route-based 类型的办法次要放在对组成 route 的多条路段的预测，最终对预测后果进行聚合。
- BusTr infers bus delays combining real-time road traffic forecasts and contextual information [2]. Using a restricted fea- ture set, BusTr can be generated to cities without training data. Besides, formulating ETA as a pure regression problem, Wang et al.
- formulating ETA as a pure regression problem, Wang et al. propose a Wide Deep Recurrent learning model to capture global spatiotemporal and route segment information in [17]
- Hong et al. further employ an Attention based GNN (Graph Neural Network) to embed road network data, and model temporal heterogeneous information, beyond the state-of-the-art methods [8].
与传统 ETA 相比，除了思考骑行工夫，FD-RTP 还须要思考取餐、交付阶段的步行工夫。
问题定义
FD-RTP 工作的指标是精确预测骑手的 location 汇合的拜访程序，即，l_0、P、D 中元素的排列组合。可行 route 须要满足 3 项束缚：
1）route 必须以 l_0 为终点；
2）一个订单的 pickup location 应该在 delivery location 之前；
3）订单 o 的取餐工夫必须晚于 PT_o（商家备餐实现工夫）。
Data Set
原始数据为最近两周的业务数据，波及 4.3 亿订单、160 万骑手。因为骑手配送过程中会继续有新订单退出，所以，原始数据并不能间接用于模型建模。因而，咱们依照骑手调配新订单的工夫点拆分骑手理论配送门路。以下图为例，咱们将订单 4 调配给骑手为分界工夫，将配送门路分为两段。
通过一些其余预处理（e.g. 剔除速度过高的异样骑手）之后，残余 1.35 亿条样本。下图列举了每条样本所用到的特色信息。
须要特地阐明的是，交付时长（drop off duration）、出餐工夫（earliest pickup time）由其余模型产出，这里看作是已知信息。在 RP 模块和 TP 模块中，应用的信息存在差别，具体查看 table2，这里不再赘述。
模型细节
如上图所示，本文提出了一种基于深度学习解决 FD-RTP 的办法，简称 FDNET (Food Delivery Route and Time Prediction Deep Network)。FDNET 通过对大量历史配送数据的开掘，预测将来骑手拜访 location 的概率，相比于启发式搜索算法，该办法可能较大的放大门路布局求解空间，同时升高工夫预测的调用频次。该办法仅生成大量高概率可行解，并预测其配送时长。计算量降落之后，便能够思考将更多的特色退出到模型中，又进一步提高了模型预测的准确性。
FDNET 由两局部组成：RP (route prediction) 模块和 TP (time prediction) module 模块。
RP 模块用于预测骑手下一步的拜访节点（location）的概率，进而预测出整个 route。咱们剖析影响骑手行为的因素后，基于 RNN 和 Attention 设计出工夫序列模型，借此更加详尽的描绘出骑手的决策过程。
TP 模块用于预测 route 上两相邻节点之间的通行工夫（来到 O，达到 D），并在思考出餐工夫、交付时长的状况下，生成每个订单的履约实现工夫。咱们将 TP 模块看作是 ETA (Estimated Time of Arrival) 问题的变种。
RP 模块和 TP 模块在 FDNET 中奇妙地联合在一起。TP 模块的 route 特色来自于 RP 模块，而 TP 模块的输入后果会作为骑手的将来特色退出到 RP 模块下一轮的预测中。
RP 模块
RP 模块能够形式化形容为如下模式：
其中，X 示意代表在 l_i 地点所能获取到的所有信息。
特色
特色方面，次要思考影响骑手决策的因素并借此设计特色，剖析后果如下图所示。
从图上能够看出，
1）准时率的思考，骑手优先取送剩余时间短的订单；
2）骑手偏向于先拜访较近的 location
3）雷同状况下，骑手偏向于曾经实现备餐的订单，实现工夫点越早越好
4）偏向于优先配送交付工夫长的订单，避免出现超时
模型
1. 预处理阶段，对浓密特色进行离散化解决，并 embedding 化。次要基于两方面思考：
- 浓密特色的强劲变动，并不会影响骑手的行为，同时，离散化能够进步模型稳定性；
- 咱们心愿模型能够学到奥妙的表征，而不是间接用 numerical values。
2. 应用 deepFM 模型，充分利用一阶特色、二阶穿插特色、高阶特色；
3. 最终失去长度为 m 的向量，表征环境特色 v_c，骑手特色 v_u，订单 o 的取餐特色 v^p_o，订单 o 的配送特色 v^d_o；
4. 利用 LSTM 解决时序数据，利用 Attention 计算倾向性
5. 确保「问题定义」章节中的前两项束缚。
LSTM Layer
在以后问题中，能够示意为如下模式：
其中，h_i-1、c_i-1 别离示意 i - 1 阶段计算所得的两个状态。
计算细节如下：
其中：
- σ 为 sigmoid 函数，σ(x)=1/(1+e^{-x})
- v_{l_{i-1}}示意地点 l_{i-1}的向量示意，包含环境特色、骑手特色、取餐或配送特色（依据 l_{i-1}的理论取送状况而定）。须要特地阐明的是，在 l_0 时，因为不是具体的取送点，此时向量只蕴含环境特色和骑手特色。
- 每一步计算，更新环境特色和骑手特色
- h_t 蕴含了前几个 step 的所有信息，作为后续预测的次要特色
- step 之间减少 dropout，防止过拟合
Attention Layer
在每一个 location，骑手都会从所有 pickup、delivery 工作（用 C _i 示意）中抉择一个作为接下来的拜访地点。这里利用 Attention 机制形容骑手的决策过程。在第 i 轮次，咱们首先获取骑手的全局信息（global view），而后，计算骑手在 i + 1 时拜访 location l 的概率 P(l)，其中 l 属于 C_i。
为了示意全局信息，
其中，h_i 示意 LSTM 单元第 i 轮次的输入示意，v_l_j 示意第 j 个 location 的特色。h_i 与 v_l_j 的乘积越大，a_ij 就越大，对应的，g_i 就更侧重于 v_l_j 向量（g_i 是 v_l_j 向量的加权向量）。实际上，就是依据暗藏层与特色的相关性，决定关注点 (attention) 应该放在哪个 location 上。须要留神的是，这里并没有额定减少待训练参数，集体认为，能够看作是 attention 的简化。咱们将 g_i 看作是骑手的全局信息（global view），对应下一个拜访点的概率如下：
到此，RP 模块根本就讲述完了。
后续训练和预测过程有两种不同的策略，greedy strategy 和 Beam Search strategy，前者每个轮次贪心的抉择一个最佳地位，并继续到所有轮次完结；后者每个轮次抉择 n 个最佳地位，在下一个轮次中基于 n * m 个候选后果中抉择 n 个最佳地位，直到所有轮次完结。
简略来讲，LSTM 用 i - 1 轮的信息失去 h_i，用候选 location（C_i）及 h_i 计算成为下一个拜访节点的概率。
Attention 的作用在于权重向量 g_i，它由 1）h_i 与 location 向量 v_l_j 的相关性 2）location 向量 v_l_j 两局部决定；P 由权重向量 g_i 和 location 向量 v_l_j 决定，所以，最重要的是 h_i 与 v_l_j 乘积的大小。
TP 模块
TP 模块用于预测达到各 location 的工夫，即，从来到上一个 location 开始到达到以后 location 的时间差。问题定义阶段提出了 3 个束缚，TP 模块解决第三个束缚问题，即，订单 o 的取餐工夫必须晚于 PT_o（商家备餐实现工夫）。通过组合各时间差及备餐工夫，咱们能够失去各 location 的预计达到工夫。如果骑手提前达到餐厅，他须要期待外卖筹备实现；否则，骑手能够立刻取餐。
咱们将 TP 模块看做是一个纯正的回归问题，形式化形容为如下模式：
其中，X^t_i 示意在 i 轮次能够利用到的信息。
特色
- 环境特色
- 骑手特色
- 天文特色：咱们利用了 GPS 经纬度的 embedding 信息
其中，dist 指网格之间球面间隔，本文采纳 300m 的网格。
- 天文特色：交付时长
- OD 特色：导航间隔，不同工夫粒度（昨天、前七天、上周同日）的导航工夫统计特色，思考到数据的稠密性，咱们利用 geohash 编码计算以上特色
模型
采纳 wide&deep 模型：
- deep 局部善于抽取与 location 相干的潜在特色
- wide 局部与 RP 模块有所不同，应用数值类型的浓密特色（因为预测指标与这类特色的变动十分敏感，e.g. 导航间隔）
针对预测 OD 类型的差异性，将 OD 分为 6 个局部。次要基于两个起因：
- 不同类型之间特色差别较大
- 不同类型之间的耗费工夫散布差别较大
模型训练与预测
训练
采纳 teacher forcing strategy 策略，即，波及工夫序列时训练采纳实在数据，预测采纳前几个轮次的预测后果序列。在咱们这个问题上，RP 模块、TP 模块均应用骑手的实在骑行序列作为输出；在 RP 模块中，当须要计算 l_i 的工夫特色时，均采纳骑手来到 l_i- 1 的实在工夫作为输出。
在 RP 模块，咱们应用穿插熵损失函数：
其中，D 示意训练集，i 示意样本中蕴含的轮次。
在 TP 模块中，咱们应用 MAE 作为损失函数：
咱们应用独立的 adam 优化器和学习率训练 RP 和 TP 模块，即，两局部是独立训练的。
预测
尽管训练时独立，但预测时 RP 模块和 TP 模块的协调十分严密。在 i 轮次，RP 模块应用 RP 模块在 i - 1 轮次所产生的 location 及 TP 模块的 i - 1 轮次对应更新后的特色（最早取餐工夫、残余配送工夫、导航间隔等）作为输出。尔后，TP 模块利用 RP 模块预测的 location 作为输出，产生 i 轮次的工夫预测后果。
试验成果
离线评估
RP 模块
route 长度对指标影响较大，这里依据业务特点拆分成 short route（小于等于 8 个 location）和 long route（8 个以以上 location）两类数据集。在确保特色尽量统一的状况下，测试 FDNET 与 LR、RF、XGB 的成果。指标上，看做 point-wise 排序，采纳[email protected]、MMR 指标。
- [email protected]：分母是所有的测试汇合，分子式每个用户 top- K 举荐列表中属于测试汇合的个数的总和
- MRR 是一个国内上通用的对搜索算法进行评估的机制，即第一个后果匹配，分数为 1，第二个匹配分数为 0.5，第 n 个匹配分数为 1 /n，如果没有匹配的句子分数为 0
从后果能够看出：
1）route 越长，解空间和不确定性越大，指标越差
2）LR 成果好于 RF 和 XGB，有点出其不意，揣测是 RF、XGB 这集成学习办法善于利用统计特色
3）FDNET 在两类数据集上均好于传统办法，揣测是因为 FDNET 利用 LSTM 学习行为序列、attention 刻画决策过程两方面起因
4）比照剔除环境特色、骑手特色的试验发现，因为环境特色对骑手决策影响较小，对应的与原始 FDNET 算法差异不大；从后果也能够揣测出，骑手特色对骑手决策影响更大。将来能够尝试在这方面扩大颗粒度进行优化。
除此之外，还用 XGB 测算了一下不同特色的重要水平，即，特色在 XGB 中作为决裂节点的次数。从后果能够看出，pickup 特色、delivery 特色更加重要。
TP 模块
在确保特色尽量统一的状况下，测试 FDNET 与线性回归、RF、XGB 的成果，（GPS 的 embedding 除外，其无奈在线性回归、RF、XGB 等传统办法中应用）比照指标为 MAPE。
剖析后果如下：
- 在传统办法中，XGB 好于其余两类办法
- FDNET 优于传统办法
- 与 RP 模块不同，骑手信息对工夫预测十分有帮忙。（但从 table 4 的特色重要性来看，骑手信息在以后利用率却不高，须要在将来做扩大）
location 粒度工夫准确性
将 RP 模块和 TP 模块组合，咱们可能计算达到每个 location 的工夫点，该局部将评估 location 粒度工夫预测的准确性。table 6 是 FDNET 绝对于传统启发式搜寻办法所升高的 MAPE 比例，value 越大代表算法成果越好。
从后果能够看出：
- 不论是 Greedy 还是 Beam Search（每次保留 2 条最高概率后果），FDNET 都优于传统办法；
- 针对 short 类型，pickup 样本中 greedy 办法优于 beam search 办法，delivery 样本中 greedy 办法持平 beam search 办法；针对 long 类型，beam search 均优于 greedy。所以，在理论我的项目中，短链采纳 greedy 办法，长链采纳 beam search 办法。
线上 AB 试验
AB 试验结果显示，FDNET 能够取得 0.08pp 的订单准时率晋升，订单生命周期升高 20 秒，骑手均匀行驶间隔升高 60 米。所以，FDNET 办法同时进步了用户满意度和骑手体验。
case study
Case #1
传统办法思考到 l1 剩余时间有余，存在超时危险，给出先送 l1，再取 l2、送 l2 的后果。凭教训均衡工夫分、途程分，是传统办法的一个劣势。
FDNET 思考了骑手习惯及历史行为，给出先取 l2、送 l2、再送 l1 的后果，该后果与理论拜访程序雷同。
Case #2
传统办法和 FDNET 办法在 case 上均预测谬误。有两个起因：
1）因为 l1、l2 取餐地位太近，先取 l1 还是 l2，存在十分高的随机性
2）备餐工夫存在比拟大的不确定性，该工夫来自于另外一套 ETA 零碎，预测后果存在偏差
个人观点：从理论业务来讲，先取 1 还是先取 2 并不影响骑手的总体途程和耗时。这里更像是一个评估体系存在的问题。
Case #3
交付难度是影响骑手行为的重要因素，o1 凑近路线，更容易交付；o2 须要停车进入社区，交付更难。骑手更偏向于优先解决容易的订单，这和之前的特征分析存在矛盾。后续须要更加关注骑手的个性化信息，e.g. 骑手对于配送先后顺序的偏好，骑手历史拜访程序。
将来优化方向
- 骑手对于配送先后顺序的偏好，骑手历史拜访程序
- 骑手对餐厅、配送地位的相熟水平
- 更加大量的环境信息，e.g. 交通状况
- 针对 TP 模块，引入 route link 的链接信息