菜鸟网络 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 试验
略