菜鸟网络2022KDD论文：Graph2Route: A Dynamic Spatial-Temporal Graph Neural Network for Pick-up and Delivery Route Prediction

前文（2021KDD论文解读：外卖配送服务中门路布局与工夫预测的深度学习办法）曾阐明，骑手的门路预测与布局门路举荐之间存在比拟大的差距（前者的指标是预测骑手行为，后者的指标是给骑手举荐最佳门路），间接应用运筹优化等算法求解最优门路作为预测骑手将来拜访门路的后果，是一种十分不合理的形式。因而，并不适宜上游工作持续应用（e.g.送达工夫预测和订单指派）。

本文与前文指标相似，解决解决PDRP（Pick-up and Delivery Route Prediction task）问题，翻新点在于将图网络引入到门路预测中。

1.介绍

[3] A Deep Learning Method for Route and Time Prediction in Food Delivery Service.2021.
[17] Package Pick-up Route Prediction via Modeling Couriers’ Spatial-Temporal Behaviors.2021.
[20] Route prediction for instant delivery.2019.

截止目前，解决PDRP问题的论文次要有4篇（含本文）。

  • OSquare是解决PDRP问题的鼻祖，它将该问题看做next-location prediction问题，应用传统机器学习办法顺次预测下一个location。
  • FDNET提供一种深度学习解决办法，将LSTM作为decoder，Pointer作为decoder，一次性预测出整个拜访序列。（2021KDD论文解读：外卖配送服务中门路布局与工夫预测的深度学习办法）
  • DeepRoute应用Transfermer作为encoder，蕴含attention的RNN作为decoder，预测pickup问题的拜访门路


以上办法各有可取之处，但都存在以下问题（figure1 left所示）：

  • 仅将未实现工作的PDRP看做序列预测，进而应用一些序列预测算法（e.g.BiLSTM），短少利用时空关系的能力；
  • 不可避免的解码出显著不合理的route（figure1 t2，D是最远的工作，不应该呈现在该预测后果）
  • 仅应用以后时刻信息，疏忽了不同工夫步问题的相关性

为了解决以上问题，提出动静时空图网络模型Graph2Route（Figure1 right所示）：

  • 将已实现、未实现工作及其关系展现在图中，以图的视角对问题进行建模，利用节点、边的特色及网络结构进步预测精度（解决问题1）。
  • 将图构造退出到decoder中，利用mask机制过滤不合了解，放大解空间。（解决问题2）
  • 利用动态图构造对一直变动的图关系进行建模，充沛获取决策上下文，e.g.前几个step的决策环境。（解决问题3）

具体内容如下。

2.筹备工作：Graph视角

2.1.ST-Graph输出

将每个工作看做graph上的一个node（一个订单被分为取餐工作、配送工作两个node），针对骑手w在t时刻的时空图能够形容为 ，其中V示意node的汇合，e示意边的汇合，X示意节点的特色（\( n*d_v \)），E示意边的特色（\( n*n*d_e \)）,其中，\( d_v、d_e \)别离示意节点和边的特色维度。

graph中有两种类型的节点，已实现节点（\( V^F \)）和未实现节点（\( V^U \)），在模型构建中会充分利用这两类节点，这也是区别于其余模型的中央。

2.2.Route 束缚

理论的配送问题经常蕴含多种束缚，用C示意束缚汇合。例如

  • 取送先后顺序束缚
  • 载具容积束缚

2.3.问题定义

能够简略形容为：基于时空图预测unfinished node的骑手拜访程序。

如figure2所示。其中，_i示意预测第i次访问节点的编号。

3.Graph2Route模型

模型构造如图所示，次要包含两局部：动静时空图encoder，基于图的个性化decoder，前者将t时刻图中节点、边的特色转为node embedding，获取时空关系、决策上下文等信息，后者基于node embedding信息，在思考骑手个性化信息、图构造的状况下，预测出对应门路。

3.1.时空图输出

[16] DeepRoute+: Modeling Couriers’ Spatial-Temporal Behaviors and Decision Preferences for Package Pick-up Route Prediction. 2022.

与[16]（作者另外一篇paper）将已实现工作、未实现工作离开编码不同，这里将两种工作编码到同一个图构造中，因而也不须要设计两个不同的解决模块，两种工作之间的关系也可能更好的被捕捉。

3.1.1.邻近关系

假如在t时刻，给定一个蕴含实现工作汇合、未实现工作汇合的问题，咱们将其构建成图模式： 。\( V_t \)由\( V^F_t、V^U_t \)组成，边汇合。其中，\( a_{ij} \)示意邻近矩阵中i、j两个对象之间的时空邻近关系。邻近关系次要用于领导decoding环节，减速学习过程（因为，理论中发现在route中的node通常具备时空相关性）。空间k邻近关系依据节点之间的间隔计算，工夫邻近关系依据节点的承诺送达工夫计算（如果承诺送达工夫靠近，则认为在工夫维度是邻近的）。用-1示意本身关系，0示意其余状况。

3.1.2.节点与边的特色

节点特色示意如下：

其中，Co示意地理坐标，AT示意接单工夫，PT示意承诺工夫，FT示意理论实现工夫，Dis示意当前任务间隔骑手的间隔。

边特色示意如下：其中，\( d_{ij} \)示意工作之间的间隔，\( a_{ij} \)示意邻近关系。

最终，节点、边均被转为d_h大小的向量，转换模式如下：

其中，激活函数为Relu，\( W_v \)的大小为\( d_v*d_h \)，\( b_v \)大小为\( d_h \)；\( W_e \)的大小为\( d_e*d_h \)，\( b_e \)大小为\( d_h \)。

3.2.动静时空图encoder

[8] Semi-supervisedclassificationwithgraph convolutional networks.2017.
[19] A comprehensive survey on graph neural networks.2020.

由两局部组成：

  • Spatial-Correlation encoding：利用一个GCN构造捕捉不同节点之间的空间关系。与规范GCN只应用节点特色来执行信息交融过程[8,19]不同，该文还引入了边特色来独特生成的embedding。
  • Temporal-Correlation encoding：利用一个RNN构造对决策上下文变动建模，在不同step中继续对embedding进行校对，进而捕捉其历史信息。

3.2.1.Spatial-Correlation encoding

应用一个L层的GCN，对节点embedding、边embedding进行编码。用\( h^l_i \)示意node i在l层的embedding，\( z^l_{ij} \)示意示意边<i,j>在l层的embedding。初始阶段，对底层embedding进行初始化，e.g.。如下所示，GCN的计算过程同时思考节点embedding和边embedding。

其中，N_i示意node i的邻近节点的汇合，Agg()示意聚合办法，更新算法f、g为非线性变换函数，如下所示：

其中，

  • W1...W5均为训练参数矩阵，大小为\( d_h*d_h \)
  • 为relu函数
  • ，W6均为训练参数矩阵，大小为\( d_h*1 \)

通过L层计算，最终失去节点、边的编码\( H_t \)和\( Z_t \)，维度大小均为\( d_h \)。

3.2.2.Temporal-Correlation encoding

依据菜鸟物流平台的总结，配送员通常具备其习惯性的路线，因而，这里提出工夫相关性编码模块，试图捕捉这种习惯。通常，t时刻配送员的门路安顿，与之前时刻的门路安顿具备相关性，特地的，间隔t时刻越近，相关性越大。例如，在t1和t2之间并没有新增已实现订单，那么这两个时刻具备雷同的决策。为了连贯不同step之间的工夫相关性，咱们尝试应用历史node信息更新以后node embedding。

这里采纳GRU构造，利用图网络、t-1时刻多个节点的embeddings计算t时刻多个节点的embeddings。留神，此时\( H_t \)为矩阵模式，须要将矩阵转为向量模式（e.g.通过行拼接的模式）。

3.3.基于图的个性化门路decoder

该局部包含两局部：

  • mask机制，解决route束缚问题
  • 个性化解码，输入每一轮工作抉择

3.3.1.mask机制

mask机制次要用来“遮蔽”轮次j内的不可用工作，咱们用\( N_i \)示意i节点的邻近节点，\( R_j \)示意j轮次之前曾经输入的节点，\( v^o_d、v^o_p \)别离示意一个订单的配送工作和取餐工作。

mask机制蕴含4种规定：
1）遮蔽曾经实现的工作
2）遮蔽曾经输入的工作，即，\( R_j \)
3）如果订单o的取餐工作（\( v^o_p \)）还未实现，则遮蔽其配送工作
4）遮蔽上一轮输入节点的非邻近工作（因为，事实当中配送员偏向于间断实现邻近工作）

通过以上规定，能够升高算法的求解空间。所有被遮蔽的节点用\( V^j_{mask} \)示意。
随着解码过程的推动，\( V^j_{mask} \)应该每个轮次都须要从新计算。

3.3.2.个性化解码

每一个轮次解码器都须要计算每个候选node的概率，并抉择最大概率的node输入。整个门路预测过程能够看做不同节点调配概率乘积的过程。

其中，s示意问题实例，示意训练参数。f()示意编码器，\( _e \)为编码器可训练参数，\( _d \)示意解码器可训练参数，\( _{1:j-1} \)示意前j-1轮输入后果，w示意骑手相干信息。

值得注意的是,传统门路布局办法采纳对立的指标函数,e.g.间隔最短。在门路预测中，不同骑手有不同的指标函数，当然这种指标函数难以被零碎辨认，因而，十分有必要将骑手信息退出到decoder中。

这里应用RNN对曾经输入的门路\( _{1:j-1} \)进行编码，f()的输入后果为H矩阵。公式（9）能够转为如下模式：

其中，W为已输入门路embedding、骑手特色的拼接向量。

解码过程中，每一步输入的后果须要不反复的从graph中抉择。在本文中，设计成如上基于graph的循环decode模式。即，解码过程循环执行，每次抉择上一轮node邻近汇合中最大概率的候选节点，而后将后果输出到RNN以更新以后状态，不便下一轮decode。

须要特地留神的是，这里应用了attention机制：将\( m_{j-1} \)和w拼接作为attention query，将候选节点的embedding作为attention key，失去候选节点的attention score。

其中，

而后，通过softmax变动，失去最终概率。

[3] A Deep Learning Method for Route and Time Prediction in Food Delivery Service.2021.
[16] DeepRoute+: Modeling Couriers’ Spatial-Temporal Behaviors and Decision Preferences for Package Pick-up Route Prediction. 2022.

另外，与之前间接在encoder阶段把骑手特色、工作特色的工作[3]、[16]不同，这里将骑手相干的特色放在了decoder中，防止编码过程中信息失落，更有助于预测准确性。

3.4.模型训练与预测

3.4.1.样本构建

当工作实现或有新任务分配给骑手时，则创立一条新样本。
在时刻t，咱们将已实现工作、未实现工作同时退出到graph中。
应用t与t'之间的实现工作作为label，其中t'示意新工作插入的工夫。
以figure3为例，在t1时刻输出蕴含了工作{1,2,3}，label为\( _{t_1:t'}=_{t_1:t_2}=[2] \)

3.4.2.训练

看作是多分类问题，用穿插熵损失函数：

其中，W为骑手汇合，T为采样工夫步。

3.4.3.预测

预测阶段，对所有未实现工作进行预测。

最终，Graph2Route算法如下所示。

4.试验

离线试验

别离应用了饿了么和菜鸟物流的数据。

比照试验基线算法有以下几类：

  • DisGreedy，间隔排序
  • TimeRank，残余时长排序
  • 基于ortools，以最短行驶间隔为指标的启发式搜寻
  • OSquare，利于LightGBM做step by step的节点预测
  • DeepRoute，Transformer encoder、attention-based decoder，因为其不反对pickup，所以对其做了改良，在decoder环节退出了mask机制
  • DeepRoute+，在encoder中退出了骑手最新的pickup门路信息
  • FDNET，利用LSTM和指针算法做门路预测（2021KDD论文解读：外卖配送服务中门路布局与工夫预测的深度学习办法）

其中后三者为深度学习模型，应用验证集确定超参数。

评估指标包含：

  • KRC: Kendall Rank Correlation
  • ED: Edit Distance
  • LSD and LMD: The Location Square Deviation (LSD) ，the Location Mean Deviation (LMD)
  • [email protected]
  • [email protected]

不同算法成果如table3所示：

能够看出，Graph2Route在各项指标均优于其余算法。

模块重要性试验：

  • 能够看出，GCN模块最为重要，阐明了图构造捕捉时空关系的能力。
  • temporal-correlation encoding（GRU）作用次之，证实了利用时序构造的能力。
  • worker info则证实了骑手信息的重要性。

线上AB试验

略