KDD2021:A Deep Learning Method for Route and Time Prediction in Food Delivery Service

参考资料：2021KDD论文解读：外卖配送服务中路径预测与时间预测的深度学习方法

摘要

Online food ordering and delivery service has widely served peo-ple’s daily demands worldwide, e.g., it has reached a number of34.9 million online orders per day in Q3 of 2020 in Meituan food delivery platform. For the food delivery service, accurate estimation of the driver’s delivery route and time, defined as the FD-RTP task, is very significant to customer satisfaction and driver experience. In the paper, we apply deep learning to the FD-RTP task for the first time, and propose a deep network named FDNET. Different from traditional heuristic search algorithms, we predict the prob-ability of each feasible location the driver will visit next, through mining a large amount of food delivery data. Guided by the proba-bilities, FDNET greatly reduces the search space in delivery route generation, and the calculation times of time prediction. As a re-sult, various kinds of information can be fully utilized in FDNET within the limited computation time. Careful consideration of the factors having effect on the driver’s behaviors and introduction of more abundant spatiotemporal information both contribute to the improvements. Offilne experiments over the large-scale real-world dataset, and online A/B test demonstrate the effectiveness of our proposed FDNET.

预备知识

长短期记忆网络（Long short-term memory,LSTM）

参考资料：LSTM从入门到精通

RNN循环神经网络的缺点

当序列太长时，容易导致梯度消失，参数更新只能捕捉到局部依赖关系，没法再捕捉序列之间的长期关联或者依赖关系，如果感到难以理解，不妨来看这样一个例子：

有这样一句话：The cat, which ate already, ..., was full。这句话后面的be动词用was还是were, 取决于前面是cat, 还是cats, "但是一旦中间的这个which 句子很长，cat的信息根本传不到was这里来。这对was的更新没有任何帮助，这是RNN一个很大的不足之处。

下面对梯度爆炸的公式做进一步推导：

我们假设损失函数为$L=\frac{1}{2}(y-O{)}^2$, $y$是实际值，$O$是预测值;反向传播我们需要对$W_o,W_x,W_s,b$四个变量都求偏导，在这里我们主要对$W_x$求偏导，其他三个以此类推。推导过程如下图所示：

根据推导的公式我们得到一个指数函数 $W_s^{(k-1)}$ ，指数函数的变化系数是极大的，因此在t趋于无穷大的时候（也就是我们的句子比较长的时候），如果 $W_s$ 比 1 小不少，那么模型的一部分梯度会趋于 0 ，因此优化会几乎停止；同理，如果 $W_s$ 比 1 大一些，那么模型的部分梯度会极大，导致模型和的变化无法控制，优化毫无意义。

LSTM模型

LSTM设计了一个记忆细胞，具备选择性记忆的功能，可以选择记忆重要信息，过滤掉噪声信息，减轻记忆负担。与传统的RNN不同，LSTM引入了三个门（ 输入门、输出门、遗忘门，如下图所示）和一个细胞状态（cell state，$C_t$），其中$\sigma$表示的是sigmoid激活函数。这些机制使得LSTM能够更好地处理序列中的长期依赖关系。

引言

在按需食品配送任务中，作者认为准确预测骑手的送货路线和时间对客户满意度和驾驶员体验至关重要，将这个问题命名为FD-RTP（Food Delivery Route and Time Prediction）任务。

动机

路线预测涉及每个订单的行驶距离和准时性考虑。此外，整个路线的时间预测包括在道路上的驾驶时间、取货和送货时的步行时间和餐厅等待时间。时间预测的不确定性也很大，并且随着路线长度的增加而增加。

以往的研究将FD-RTP任务作为单车辆PDPTW（pickup and delivery problem with time windows）问题，主要关注搜索算法的改进，这些工作很少致力于提高时间预测的准确性，这在食品配送服务中同样重要。

• 这些启发式搜索算法需要经过数千次迭代，并且每次迭代都需要预测整个路线的时间。很难充分利用相关的影响因素。然而，这些因素对时间预测的准确性有很大帮助，例如发生配送时的时间和地点信息、反映配送习惯和能力的骑手信息。（运筹优化类算法的一个重大缺陷）
• 骑手通常同时对多个订单进行取餐和配送（在高峰时段，甚至可以达到同时取送10单），对应的路径求解空间巨大，针对高峰期10单的情况，可以达到$2.376\ast {10}^{15}$个解。

贡献

作者提出了一个食品配送路线和时间预测的深度网络（(Food Delivery Route and Time Prediction Deep Network，FDNET）通过挖掘历史积累的大量配送数据，FDNET采用不同的方法：预测骑手将访问的每个可行位置的概率。在概率的引导下，FDNET大大减少了生成配送路线的搜索空间，并且减少了时间预测的计算次数。

相关工作

RR（Route Recommendation ）

路线推荐问题（Route Recommeddation，RR）是根据给定的起点和终点以及相关的上下文信息（如实时交通状况、道路条件、用户偏好等），为用户提供一条或多条从起点到终点的最佳路径。

例如：使用百度地图输入你当前的所在位置（起点）和你想到达的地方（终点),系统会为你推荐了几条不同的路线选项，其中可能包括：

• 路线A：路程最短，但因有轻微拥堵，预计耗时35分钟。
• 路线B：绕行一段距离，但目前无拥堵，预计耗时30分钟。
• 路线C：高速公路直达，但由于需要支付过路费，虽然预计耗时仅25分钟，但成本稍高。

在本例中，用户基于提供的路线推荐做出选择，而推荐是基于现有条件下的最优解。

RR问题的求解方式一般将其视为在图上的路径规划问题，研究重点主要在设计启发式搜索算法，降低搜索空间。启发式搜索算法需要大量的迭代轮次，设计合适的损失函数成为了算法的关键点。

RP（Route Prediction）

路线预测问题是基于历史行为模式、当前位置及环境因素等信息，预测个体（如车辆、行人）未来一段时间内的移动路径。它不仅仅关注单一的目的地选择，而是尝试理解并预测整个行程的行为模式，包括可能经过的地点、行驶顺序等。

例如：一名美团外卖骑手已经接到了几个订单。现需要决定接下来应该去哪个地点送餐和取餐，以便最大化收益或效率。

• 分析骑手过去的行为模式（例如，在特定时间段内通常选择哪些路线），并结合当前的情况（如附近的需求热点、交通状况等），预测出如果选择某条路线，接下来可能会接到更多的订单或是能够更快完成已有订单。预测到如果先前往市中心区域，则很可能在那里快速接到下一单，因为那里是高峰期的取餐点；或者预测如果直接送完手头上的订单再去其他地方，反而能避免高峰时段的拥堵，从而节省更多时间。

ETA（Estimated Time of Arrival）

定义：预测从一个起点（Origin, O）到终点（Destination, D）之间所需的时间。它主要分为两种典型场景：基于OD的方法和基于路线的方法。

• 基于OD的方法：
  • 主要提取起点和终点的特征。
  • 预测所需时间时不需要具体的路线信息。
• 基于路线的方法：
  • 基于可用的路线段数据，估计特定路线的旅行时间。
  • 例如，BusTr通过结合实时道路流量预测和上下文信息来推断公交车延误。Hong采用基于注意力机制的图神经网络（Attention-based GNN）来嵌入道路网络数据，并建模时间异质信息，超越了现有的方法

相比于传统的ETA问题，按需配送服务中的时间预测更加复杂，除了考虑驾驶时间外，还需要考虑取餐和送餐时的步行时间。因此，食品配送的ETA不仅包括车辆行驶的时间，还包括骑手在餐厅取餐以及将食物送到客户手中的时间。

问题定义

FD-RTP

订单分类

订单集合 $O=\{o_1,o_2,\dots ,o_n\}$ 需要由一个骑手 $u$ 在给定的情境信息 $c$ 下进行配送

这些订单被分为两类:

第一类：这些订单已经被餐厅取走，只需要送到指定地点。记为 $O^1=\{o_1^1,o_2^1,\dots ,o_{n_1}^1\}$

第二类：这些订单需要从餐厅取货并送到指定地点。记为 $O^2=\{o_1^2,o_2^2,\dots ,o_{n_2}^2\}$

订单属性

每个订单 $o$ 有一个最早的预计送达时间 $P{T}_o$ 和承诺给顾客的最晚送达时间 $D{T}_o$ 。对于第二类订单 $o\in O^2$ ，有对应的取货点 $l_p^o$ 和送货点 $l_d^o$

位置集合

• 所有的取货点集合 $P=\{l_p^o\mid o\in O^2\}$
• 所有的送货点集合 $D=\{l_d^o\mid o\in O\}$

约束条件

• 路线必须从骑手的起始位置 $l_0$ 开始
• 对于任何订单，其取货点必须在其送货点之前访问
• 每个订单不得早于其最早预计送达时间 $P{T}_o$ 前被取走，因为在此之前餐厅无法准备订单

数据集

原始数据集是美团公司近两周的业务数据，涉及4.3亿订单、160万骑手。由于骑手在配送过程中可能会接到新的订单，原始数据并不能直接用于模型建模，作者对原始数据做了如下处理：

将一位骑手的配送路线分割成多个样本，每个样本对应一次新订单的派发时刻。如下图所示：

骑手当前有3个订单需要配送，分别是$o_1、o_2、o_3$。在配送过程中，骑手收到了一个新的订单$o_4$。此时骑手已经取了之前的三个订单$o_1、o_2、o_3$，并且正在前往订单$o_3$的送餐地点。此时，骑手需要决定接下来的行动：先去取$o_4$还是按原本的计划继续配送。作者将其重新划分为两个样本

第一个样本

• 输入：未取的订单集合$o_1、o_2、o_3$(实际上此时都已取过，但为了模型训练，假设这些订单还未取)
• 标签：
  • 骑手的位置$l_0$（在完成$o_3$配送后的当前位置）
  • 各订单的取货时间和交货时间 $\{l_{o_1}^p,l_{o_2}^p,l_{o_3}^p,l_{o_3}^d\}$，其中$l_{o_1}^p,l_{o_2}^p,l_{o_3}^p$是已知的取货时间，$l_{o_3}^d$是已知的交货时间

这个样本反映了在没有新订单到来时，骑手原本的配送计划

第二个样本

• 输入：已取的订单集合$o_1、o_2、o_4$（其中$o_1$和$o_2$已经取过，$o_4$是新接到的订单）
• 标签：
  • 在接收到$o_4$后的当前位置$l_0^{\prime }$。
  • 各订单的取货和交货时间$\{l_0^{\prime },l_{o_4}^{\prime p},l_{o_1}^{\prime d},l_{o_2}^{\prime d},l_{o_4}^{\prime d}\}$

这个样本反映了在接收到新订单后，骑手基于更新后的订单集的新配送计划。

作者过滤掉驾驶员的驾驶速度过高的异常值。得到一个包含超过1亿3千5百万个样本的正常数据集，下图罗列了每条样本所用到的特征信息。

主要方法

FDNET的模型结构

FDNET的整体架构如上图所示，由RP和TP两个模块组成

• RP模块预测了驾驶员下一步将访问的节点的概率，进而预测完整的配送路线
• TP模块预测配送路线中两个位置（离开O，到达D）之间的旅行时间，并利用这段时间间隔来生成预计到达每个位置的时间

路线预测模型（Route Prediction Module）

作者设计了一个RP模块，RP模块基于RNN和Attention设计出时间序列模型，根据过去的行为和当前位置状况预测骑手接下来访问每个节点的概率，更加详尽的描绘出骑手的决策过程。具体的形式化定义如下

$$P(l_{i+1}\mid l_0,l_1,\dots ,l_i;X_i^r)$$

在已知从起点 $l_0$ 到当前位置 $l_i$ 的路径以及当前位置的信息 $X_i^T$ 下，下一个位置 $l_{i+1}$ 的概率

特征数据

作者根据主要影响骑手决策的因素并借此设计接单特征（Pickup Features）和送货特征（Delivery Features），选择的特征或属性具体阐述和分析如下：

• 剩余交货时间（Due time left）：出于订单准时性的考虑，骑手们一般倾向于优先取送剩余交货时间较少的订单
• 导航距离（Navigation distance）：距离也是骑手关心的一个方面。骑手们一般倾向于前往较近的位置
• 最早取货时间（Earliest pickup time）：当同时有几个订单需要取货时，骑手通常先取已经餐厅已经准备好的订单，以避免长时间等待
• 送达持续时间（Drop-off duration）：为了避免订单超时，骑手通常愿意优先配送需要较长配送时间的订单

作者首先获取全局的个性化特征，包括环境特征（context features）和骑手特征（driver features）这些特征在上文的表格中已经列出。此外根据上文的分析结果，当在第$i$步时，当骑手位于位置$l_{i-1}$时，设计了取货特征（pickup features）和送货特征（delivery features）

对于每一个订单的接单特征包含了：

• 从当前位置$l_{i-1}$出发到达餐厅所需的最短导航距离
• 从当前位置$l_{i-1}$出发到达餐厅所需的时间
• 预计的最早取餐时间

对于每一个订单，送货特征包含了：

• 从当前位置$l_{i-1}$出发到达顾客所在地所需的最短导航距离。
• 从当前位置$l_{i-1}$出发到达顾客所在地所需的时间。
• 预计的订单送达所需时间

RP模型

作者使用了deepFM模型对不同类型的特征进行了预处理嵌入嵌入。

deepFM由FM component（因子分解机组件）、Deep component（深度组件）两部分组成。细节如下图所示

LSTM层

在做完特征预处理后，使用LSTM单元更新隐藏状态 $h_i$ 和内存状态 $c_i$ 的公式如下:

$$h_i,c_i=\mathrm{LSTM}(v_{l_{i-1}},h_{i-1},c_{i-1})$$

$v_{l_{i-1}}$ 是位置 $l_{i-1}$ 的向量表示，它是上下文特征、骑手特征以及订单接送点特征的拼接。

tips

由于骑手的起始位置 $v_{l_0}$不是取餐点和送餐点，所以只包含上下文特征和骑手特征。同时每一步计算都会更新更新环境特征和骑手特征

在每一时间步 t，LSTM执行以下操作来更新其内部几个门的状态

忘记门 (Forget Gate) 忘记门 $f_t$ 根据前一时刻的隐藏状态 $h_{t-1}$ 和当前时刻的输入 $x_t$ 计算出一个介于 0 和 1 之间的值。这个值越接近1，意味着越多的信息会被保留在记忆单元中；反之，则更多的信息会被清除。

$$f_t=\sigma (W_f[h_{t-1};x_t]+b_f)$$

注：$\sigma$ 是sigmoid激活函数， $W_f$ 是权重矩阵， $b_f$ 是偏差项。

输入门 (Input Gate) 输入门 $i_t$ 基于前一时刻的隐藏状态和当前时刻的输入计算得出一个介于 0 和 1 之间的值。这个值越大，意味着更多信息将会被写入记忆单元。

$$i_t=\sigma (W_i[h_{t-1};x_t]+b_i)$$

注：$W_i$ 是权重矩阵， $b_i$ 是偏差项

输出门 (Output Gate)

$$o_t=\sigma (W_o[h_{t-1};x_t]+b_o)$$

调节后的输入 (Modulated Input) 调节后的输入 ${\tilde{C}}_t$ 是一个新的候选记忆值，它将在输入门的控制下被写入记忆单元。这个值通过tanh激活函数产生，确保结果在-1到1之间。

$${\tilde{C}}_t=\tanh (W_C[h_{t-1};x_t]+b_C)$$

注意力机制

由于骑手下一步有许多可行的节点位置，作者使用注意力机制来模拟骑手在不同位置间的决策过程，通过计算骑手的全局视图和访问概率来预测骑手下一步的行为。注意力层的结构如图所示

对于每一个位置 $l_j$ ，骑手可能会考虑到所有未完成的接送任务，然后决定下一步去哪里。在每一步 $i$ ，骑手有一个可行的访问地点集合 $C_i$ ，其中包括未取货的接送地点和已取货的送货地点。接下来计算骑手的全局视图(权重向量):

首先计算骑手在第 $i$ 步的全局视图 $g_i$ ，这个向量用于骑手决策某些位置相对于其他位置的重要性：

$$a_{ij}=\{\begin{array}{ll}\frac{\exp (h_{i^{\prime }}\cdot v_{lj})}{\sum _{l_k\in C_i}\exp (h_{h_i}\cdot v_{lk})},& l_j\in C_i\\ 0,& l_j\notin C_i\end{array}$$

$h_i$ 表示骑手在LSTM单元第$i$轮次的输出表示， $v_{lj}$ 是第$j$个位置节点的特征

全局视图 $g_i$ 是通过公式8对所有位置 $l_j$ 的加权求和得到的

$$g_i=\sum _j{a}_{ij}\cdot v_{lj}$$

权重向量 $g_i$ 是基于两部分决定的:

• $h_i$ 与 $v_{lj}$ 的乘积大小，这决定了 $g_i$ 中对应位置 $l_j$ 的权重
• 位置向量 $v_{lj}$ 自身也会影响最终的权重

骑手的全局视图 $g_i$ 后，进一步计算骑手在第 $i+1$ 步访问每个位置 $l_j$ 的概率 $P(l_j\mid g_i)$ 如下:

$$P(l_j\mid g_i)=\{\begin{array}{ll}\frac{\exp (g_i\cdot v_{lj})}{\sum _{l_k\in C_i}\exp (g_i\cdot v_{lk})},& l_j\in C_i\\ 0,& l_j\notin C_i\end{array}$$

tips

如果 $h_i$ 与 $v_{lj}$ 的乘积较大，那么该位置 $l_j$ 在 $g_i$ 中的权重就大，从而导致更高的访问概率 $P(l_j\mid g_i)$

TP模块

TP模块用于生成司机到达每个位置的预计时间，TP模块也使用环境特征和骑手特征，除此之外还特别关注了时空特征，作者将其分为了两类：

• Location features: 利用GPS坐标嵌入作为每个位置的空间信息。同时，订单的持续时间也被用作交付地点的时间信息。
• 导航距离，和不同时间粒度（昨天、前七天、上周同日）的导航时间统计特征

在TP模块，作者设计了一个名为Wide & Deep Model的模型，Wide & Deep模型结合了线性和非线性两种方法来提高预测性能。模型的输出是宽部分和深部分结果的总和

wide layer

wide layer使用了一个线性模型，主要用于捕捉输入特征之间的低阶相互作用。他的输出定义为：

$$y^{\text{wide }}(x)=\sum _{i=1}^{d_x}{w}_i\cdot x_i+b$$

Deep layer

深部分采用了一个深层神经网络（DNN），用于捕获高阶特征之间的复杂相互作用。

$$y^{\text{deep }}(x)=DNN(x)$$

整体的输出是宽部分和深部分输出之和

$$y(x)=y^{\text{wide }}(x)+y^{\text{deep }}(x)$$

实验结果

RP模块

TP模块