关于人工智能:2021KDD论文解读外卖配送服务中路径规划与时间预测的深度学习方法

美团配送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的链接信息