基于多任务学习的快件送达时间预测方法

王 强，林友芳，2，万怀宇，2

（1.北京交通大学 计算机与信息技术学院，北京 100044；2.综合交通运输大数据应用技术交通运输行业重点实验室，北京 100044）

0 概述

近年来，我国快递市场日益扩大［1］，快递员数量已超过300 万人，每日快件配送量超过1 亿件，市场的快速扩大也给快递公司的管理带来了巨大挑战。通过对时空轨迹数据的深入研究，预测快件送达时间一方面可以为用户提供更加准时的服务，提升用户体验［2-3］，另一方面可以帮助快递员进行路径规划，提高派送效率［4-6］，从而提升公司整体业务竞争力。

基于上述背景，利用深度学习技术对快递员的时空轨迹数据进行学习，从而准确预测快件送达时间，服务现实应用场景。虽然在时空数据挖掘领域，到达时间预测问题已有许多优秀研究成果，但快件送达时间预测仍面临许多困难与挑战，主要有快件派送受到多种复杂因素影响、快件派送状态存在动态性和多目的地预测3 个方面。其中快件派送受多种复杂因素影响主要是快件的送达时间不仅与交通状况、快件本身属性、外界天气等有关，快递员的派送偏好、快件所在地的环境、客户的个性化要求等因素都会对快件送达时间产生影响；快件派送状态存在动态性主要是在快递员派送快件过程中，快递员位置、已派送快件序列、待派送快件集合等均会发生改变，会导致快件的送达时间随派送过程动态变化；多目的地预测主要是研究需要同时预测快递员的所有待派送快件的送达时间，不同于单目的地预测问题，快件的组合、彼此之间距离、派送顺序均会对每个待派送快件产生影响，如何保证多目的地预测的整体准确性也是一大难点。

本文提出一种基于多任务学习的快件送达时间预测网络（Multi-Task Delivery Time prediction Network，MTDTN）模型，建模多种对快件送达时间产生影响的外部因素，并采用卷积神经网络［7］（Convolutional Neural Network，CNN）与长短期记忆［8］（Long Short-Term Memory，LSTM）网络相结合的网络结构捕获时空相关性，引入基于注意力机制的顺序预测辅助任务提升预测效果，最终通过多任务融合方法得到快件送达时间预测结果。

1 相关工作

虽然时空数据挖掘在近年来受到广泛关注并取得了许多优秀的成果［9-11］，但快件派送场景下的多目的地送达时间预测问题比较新颖，相关研究较少。本文参考时空数据挖掘领域的到达时间估计问题的优秀成果。

到达时间估计（Estimated Time of Arrival，ETA）指预估一个出发地到一个目的地之间所经过的时间［12］，出发地到目的地往往由一系列相关联的分路径组合而成。目前，在工业和学术界的解决方案分成两大类策略［12］。

第一类是基于分路径建立物理模型的解决方案。出发地到目的地的到达时间被定义为给定路径中没有岔路的道路行驶时间与所有交叉路口的延误时间之和，计算过程如式（1）所示：

其中：i表示第i段没有岔路的道路行驶预测时间；j表示第j个交叉路口预测的延误时间；Nroad和Ncross分别表示无岔路道路和交叉路口总数。

文献［13-14］将从出发地到目的地的到达时间预测划分为一些子问题，每个子问题预测一小段道路行驶时间或者单个岔路口的延误时间。文献［15］使用机器学习的回归算法和张量分解算法预测局部路段或岔路口的时间。但该方案存在以下问题：1）时空数据无法覆盖所有的分段路径以建模整个交通路网实时时间分布；2）使用固定模式的模型预测未来一段时间道路交通状态或者交叉路口延误时间，忽略了交通动态性以及研究对象的个性化差异和行为模式所带来的影响；3）分段预测进行累加带来了预测误差的累加，使整体预测准确率下降。

第二类是基于数据构建深度学习网络模型的解决方案。研究人员将到达时间预测问题转换为回归问题，通过建立端到端的深度学习模型，从海量的历史数据中学习输入到输出的映射函数，从而给出到达时间预测。

文献［12］提出将到达时间估计问题公式化为纯粹的时空回归预测问题，使用线性模型、深度神经网络和循环神经网络模型相结合，提高预测效果。文献［16］提出辅助监督模型DeepTravel，使用双向长短时记忆（Bidirectional Long Short-Term Memory，Bi-LSTM）［17］神经网络捕获长期和短期的时间特征，在有效提取不同特征的同时，充分利用数据丰富的时间标签进行路径旅行时间的估算。文献［18］在预测给定路径的交通工具行驶时间问题中，考虑不同路段转移之间的空间与时间相关性，提出DeepTTE模型，使用卷积层捕获空间相关性，堆叠长短时记忆网络捕获时间相关性，引入多任务机制预测完整路径与路径各途经点到达时间。以上研究不足在于均假定路径已知，而且在捕获时间相关性时仅考虑时间维度信息，对于其他外部信息融合不足。

随着应用场景的复杂以及深度学习技术的发展，越来越多的研究人员将目光转向路径未知的预测问题。文献［19］提出未知具体行驶路径下的到达时间预测研究方法，在训练阶段使用多任务学习框架对现实世界行驶过程各种因素进行学习，提高该场景下的预测准确性。文献［2］在快递员送件的场景下，引入双层注意力机制捕获相似历史轨迹数据特征预测多快件到达时间，取得了良好的效果。以上研究虽然在路径未知情况下效果较好，但是对于多目的地间的相关性依然考虑不足。

本文提出基于多任务学习的快件送达时间预测模型MTDTN，该模型对影响送达时间的外部因素进行表示学习，通过派送路径表示模块捕获派送路径的时空相关性，继而基于注意力机制选择最相关的未派送快件组合预测派送顺序，最后融合各模块向量，准确预测快件送达时间。

本文的主要贡献如下：

1）提出一种基于多任务学习的快件送达时间预测网络（MTDTN）模型，该模型可以学习快递员的行为模式并捕获派送过程的时空动态性，准确预测快件送达时间。

2）为应对快件派送状态存在动态性这一挑战，提出一种基于地理信息编码的时空组件，使用Geo-Hash编码、卷积及长短时记忆网络建模已派送快件路径。

3）为解决多目的地同时预测问题，提出一种多任务学习机制，融合快件派送顺序信息，辅助快件送达时间预测任务，提高模型性能。

2 模型框架

2.1 相关定义

本文给出以下定义：

1）快件。将快递员派送的快件定义为ο={Llng,Llat,Ltype,Tacc}，其中：Llng表示快件地址经度；Llat表示快件地址纬度；Ltype表示快件地址类型；Tacc表示快件签收时刻。

2）快件派送轨迹。快递员派送过程会记录每个快件的地理信息及送达时刻，形成快件派送轨迹p={ο1,ο2,…,οn}，此外每条派送轨迹会有日期、周次、区域编码、快递员编号等信息。

3）送达时间。将快件οj的送达时间定义为dtj=其中表示快件οj的签收时刻；Tnow表示当前时刻。

4）研究目标。本文将未派送快件的送达时间预测问题定义为多目标回归任务，给定已派送快件Shad形成的派送轨迹phad，待派送快件集合Sto，本文的目标是构建模型F，预测Sto中每一个快件的送达时间：

2.2 MTDTN 模型

快件送达时间受到包含快递员本身和外界环境在内的复杂因素影响，因而在进行快件送达时间预测时，首先需要对影响送达时间的复杂因素进行建模，本文充分考虑可能的影响因素，通过组合、统计计算等方式得到新的特征信息，这些特征可以作为其他模块的输入。其次派送过程存在时空动态性，需要学习快递员派送的行为模式及隐含的时空相关性，本文通过设计时空组件来结合外部因素与已派送路径信息捕获派送过程的时空动态性。最后不同于单目的地到达时间估计问题，本文研究需要考虑预测不同快件的多个目的地，故而引入派送顺序预测这一辅助任务，基于注意力机制从历史数据中寻找相似待派送快件集合，并结合外部因素，实现顺序预测辅助任务。最终通过融合上述各种信息，得到快件送达时间预测结果。

具体而言，本文将快递派送过程中已送达快件序列、复杂外部因素以及历史相似快件序列集合作为输入，首先建模影响送达时间的多种外部因素，并使用地理信息编码和卷积操作、双向长短时记忆网络捕获已派送快件路径的时空相关性，同时通过引入顺序预测辅助任务增强模型学习能力，最后使用多任务融合输出快件送达时间预测结果，提出MTDTN 模型。该模型共包含4 个模块（如图1 所示）：

图1 MTDTN 模型框架Fig.1 Framework of MTDTN model

1）外部因素表示模块。为建模整个派送过程中时间不变性特征、待预测快件的特征以及快递员的画像表示，本模块对外部因素进行信息嵌入，输出将作为其他3 个模块的输入。

2）派送路径表示模块。已派送快件序列对剩余快件的送达时间至关重要，本模块通过卷积神经网络及双向LSTM 捕获时空轨迹的空间及时间相关性，建模已派送路径。

3）顺序预测模块。为更好地解决多目的地预测问题，本模块选择历史轨迹数据中相似快件序列集合，使用注意力机制完成信息提取与组合，继而与外部因素模块拼接，进行派送顺序预测。

4）多任务融合模块。本模块作为预测任务的输出层，融合其他模块表示向量，结合顺序预测的辅助任务与送达时间预测的主任务，输出快件送达预测时间。

2.2.1 外部因素表示

如上文所述，快件派送场景复杂，影响因素繁多，模型在有限的数据条件下应尽可能将影响快件送达时间的外部因素进行信息提取。如图1 所示，将影响送达时间的因素分为3 类：全局相关信息，待预测的快件οj的相关信息，快递员的特征统计信息。

全局相关包括轨迹数据对应的日期、周次、区域编码、快递员编号等，由于4 个特征均为离散的数值，无法直接输入网络。一种方式是使用one-hot 编码方式，将4 个特征编码为向量形式，但是这样会导致编码后得到高维向量（快递员数量近千人，则该特征维度将在近千维），极大增加模型复杂度，同时每个特征向量之间的余弦相似性为0，无法表达区域之间相邻关系。因此，本文使用嵌入层［20］表达全局信息，嵌入层通过乘以一个学习的参数矩阵W∈RF×E，将全局特征转为RE实域的向量，其中：F表示各全局特征的类别数；E表示自定义嵌入向量的维度，E≪F。本文将上述4 个特征分别经过嵌入表示的向量进行拼接，得到全局相关向量Vglobal。

预测快件οj相关信息包括οj相对于快递员首个派送快件οfirst的转移方向、实际距离与οj的地址类型。其中转移方向使用οj与οfirst经纬度差值归一化后表示，实际距离使用百度地图API 计算两者距离后归一化表示，地址类型则使用one-hot 编码。快递员的特征统计信息，则使用历史数据计算得到其过去一周派送过程平均驾驶速度，日均快件量、快件平均派送时间归一化后表示，连同此次派送轨迹平均驾驶速度归一化信息，输入模型以学习其日常工作行为特征。

将Vglobal、预测快件相关信息、快递员的特征统计信息拼接后得到向量Vconcat。将Vconcat输入到两层全连接层中，得到外部因素表示向量Vfea。计算过程如式（3）所示：

其中：权重Wfea和偏差系数bfea均是全连接层的学习参数。

2.2.2 派送路径表示

快件派送状态随着时间动态变化，已派送快件路径对其余待派送快件的送达时间有着巨大影响。本模块从已派送快件序列轨迹数据中捕获时间和空间相关性，建模已派送路径。主要由三部分组成：首先使用Geo-hash 对快件轨迹进行地理信息编码；然后将输入的轨迹序列使用卷积捕获空间转移的局部相关性；最后输入双向LSTM 捕获时间相关性，得到派送路径的向量表示。

1）地理信息编码。地理信息的应用多数使用二维卷积［21］，首先将地理坐标点聚类，然后划分到矩形或者六边形的栅格中，但是这样会丢失空间坐标的地理和语义信息，且在本文研究中对于快件送达问题，需要更加细小的粒度划分，因而本文研究不使用栅格划分方法。本文使用Geo-hash 对经纬度地理信息进行编码，Geo-hash 编码是一种地址编码方法，将二维空间经纬度表示为二进制编码，它的优点一是易于神经网络输入，二是可以表达地点之间的空间相近性，当二进制编码相同前缀越长时，表明两者空间上越相近。首先使用Geo-hash Encoder 将已派送快件与派送路径phad中所有快件οi的经纬度转为Geo-hash 编码，命名为Gi，每个编码长度为32。

2）卷积层。已派送快件经过地理信息编码后，使用一维卷积神经网络［7］捕获已派送轨迹的空间相关性。运用l×32 的卷积核，步长为1，对phad中所有快件的地理编码序列进行卷积操作，则输出向量第i维如式（4）所示：

其中：W为学习的参数矩阵；bconv为学习的参数偏差系数；Gi,i+l-1表 示Gi到Gi+l-1的编码 矩阵。

此外，时间差、距离、快件地址类型无法从地理编码序列卷积过程直接获得，因而本文将οi到οi+l-1之间的签收时间差、距离以及οi+l-1的快件地址类型one-hot 编码与卷积层输出Vhad_conv拼接，得到卷积层最终输出向量Vconv∈R(k+2+m)×(n-l+1)，其中m为快件地址类型种类数。

3）双向LSTM。循环神经网络通过引入状态变量存储过去信息，与当前信息共同决定输出，从而可以更好地处理序列信息［7］。但随着时间步增长，出现梯度衰减或爆炸，无法有效利用较远的历史信息。LSTM 通过引入输入门、遗忘门、输出门，自动学习哪些信息遗忘、哪些信息保存，解决了常规循环神经网络无法捕获长距离依赖的问题。而双向LSTM 通过引入负反馈信息，与LTSM 相比，增强了网络的学习能力。

本文使用双向LSTM 捕获派送路径的时间相关性，将外部因素模块的输出Vfea与卷积层Vconv拼接，得到向量VLSTM∈R(k+2+m+df)×(n-l+1)，df为Vfea特征维度。VLSTM可以看作长度为n-l+1 的序列数据，将其输入到双向LSTM 中，得到隐藏状态，计算过程如式（5）、式（6）所示：

2.2.3 顺序预测辅助任务

在派送快件的过程中，存在多个目的地快件需要同时预测。虽然派送路径表示模块结合外部因素模块降低了预测的难度，但是仍有提升空间。因此，本文引入派送顺序预测辅助任务应对多目的地预测这一问题。通过对派送顺序预测，可以使模型从相关任务提取特征，得到待派送快件大致派送顺序，使得到达时间预测更加精准。

顺序预测辅助任务首先从历史快件派送轨迹数据中选择场景相似未派送快件组合提取特征向量，然后使用注意力机制基于外部因素表示向量Vfea选择最相似历史模式，最后与外部因素表示向量Vfea输入全连接层，得到顺序预测结果。

如果将当前快递员的所有历史快件输入模型，一方面造成模型过于复杂，计算困难，另一方面可能引入过多噪声和无关信息，导致无法提取有效特征。因此，本文选择与当前场景相似未派送快件组合，具体方法如下：假定当前快递员已派送最后一个快件地理坐标Geo-hash 编码为Glast，待派送快件个数为a，此次待预测快件为οpredict，其地理编码为Gpredict。查找该快递员的历史轨迹中地理编码为Glast的快件οhis，且οhis之后派送的a个快件包含某个快件οsimilar地理编码同样为Gpredict，将该轨迹中N-1 个οsimilar派送相邻的快件与οsimilar组合，并根据οsimilar在组合中的派送顺序将多种组合分为N类，n为οsimilar在快件组合中的派送顺序，dο为快件特征数，N为超参数。将输入全连接层，得到相关快件组合向量，计算过程如式（7）所示：

其中：权重Whis、偏差bhis均为学习参数。

注意力机制是仿照人类处理信息时大脑有意或无意地选择更具有价值的信息所发明的一种数学机制，使用注意力机制可以从众多信息中选择最有价值的信息。因而，本文使用注意力机制获取最相关的历史快件组合。

首先使用全连接层来计算外部因素模块的输出Vfea与相关快件组合向量的相关性分数，然后使用类似SoftMax 计算方式，将相关性分数转换为和为1 的概率分布，最后根据权重分布对相关快件组合向量进行加权求和，得到最相关组合向量Vatten，计算过程如式（8）～式（10）所示：

其中：权重Wscore、偏差bscore均为学习参数；n为顺序类别。

得到相关组合向量后，将其与外部因素表示向量Vfea连接，通过堆叠的全连接层对待派送快件顺序进行预测。计算过程如式（11）所示：

其中：权重Wseq、偏差bseq为学习参数；[]表示连接操作。损失函数使用均方根误差损失，计算过程如式（12）所示：

2.2.4 多任务融合

本文使用全连接层对快件送达时间的预测结果进行输出。具体而言，将外部因素表示向量Vfea，派送路径表示向量H，最相关组合向量Vatten进行拼接得到最终输入向量X=[Vfea,H,Vatten]，将其输入堆叠的全连接层后，得到送达时间预测结果。计算过程如式（13）、式（14）所示：

其 中：权重Wfull、Warrive和偏差bfull、barrive均为学习参数。损失函数使用平均绝对误差，计算过程如式（15）所示：

最终将多任务的损失函数与lseq、larrive结合，计算过程如式（16）所示：

其中：α、β为超参数。

3 实验与结果分析

3.1 数据集描述

本文的实验数据集来自某快递企业在上海市2 个运营区域：2019 年11 月1 日—12 月31 日共计61 天的快递员派送数据，共有931 个快递员、45 万条快件数据。每个快件数据均有对应快递员ID、签收时间、地址类型以及经纬度坐标。本文选择11 月1 日—12 月10 日共计40 天的派送数据作为训练集，12 月11 日—20 日共计10 天的派送数据作为验证集，12 月21 日—31 日共计11 天的派送数据作为测试集。

3.2 基准方法与评价指标

本文将MTDTN 模型与以下6 种现有的预测方法进行对比：

1）HA（History Average）。即平均值方法，根据特定快递员的历史平均送达时间进行预测。

2）LR（Linear Regression）。使用岭回归方法（L2正则）作为线性回归方法。

3）DNN。使用三层全连接神经网络进行预测，隐藏状态神经元个数分别为128、64、32。

4）LSTM。使用两层LSTM 堆叠进行预测，隐藏状态神经元分别为128 和128。

5）DeepTTE［18］。用于道路货车行驶时间预测的深度神经网络模型。使用卷积和堆叠LSTM 表示原始GPS 轨迹，引入分段路径时间辅助任务完成到达时间预测，将分段路径时间辅助任务转为每个已派送快件送达时间，其他参数和网络结构不变。

6）DeepETA［2］。用于快件送达时间预测的深度神经网络模型，将快件地址聚类为AOI后，使用地理信息嵌入和双向LSTM 表示派送模式，并引入注意力机制建模历史频繁派送信息。将AOI坐标替换为本文研究中的快件地理坐标，其他参数和网络结构不变。

上述所有模型与MTDTN 输入相同，本文根据不同模型所需的数据格式进行了相应调整。

评价指标采用平均绝对误差（MAE）和平均绝对百分比误差（MAPE），计算过程如式（17）和式（18）所示：

3.3 参数设置

本文模型基于Keras深度学习网络框架实现，批量大小为1 024，学习率为0.001。在外部因素表示模块，将日期、周次、区域编码、快递员编号分别嵌入为R2、R2、R2、R10的向量；堆叠两层全连接层隐藏单元神经元个数分别为64、64。在派送路径表示模块，使用右填充方式输入派送路径的快件序列，长度为20。在卷积层，卷积核个数为32，卷积核形状为R3×32。双向LSTM 隐藏单元神经元个数为64。在顺序预测模块，相似未派送快件分类数N设置为10，全连接网络隐藏单元神经元个数为128；计算输出Vfea与相似快件组合向量的相关性分数的全连接网络隐藏单元神经元个数为64；顺序预测子任务，最终融合向量预测顺序时堆叠两层全连接神经网络，隐藏单元神经元个数分别为32、32。在多任务融合模块中，α=0.7，β=0.3。

3.4 结果分析

本文模型与各基准模型的实验结果如表1 所示。可以看出，本文提出的MTDTN 在MAE 以及MAPE 两个指标均优于其他方法，相对于基准方法中最优的DeepETA 模型，本文模型MAE 降低16.11%，MAPE 降低12.88%。

表1 不同模型预测结果对比Table 1 Comparison of prediction results of different models

HA 模型依赖快递员的历史平均送达时间对快件送达时间进行预测，对于派送过程中的时空相关性无法有效利用，且忽略了特定场景下的派送情况及相关因素，效果最差；使用岭回归可以对时间序列信息加以利用，但是依然无法捕获序列数据的短期和长期依赖，因而效果与HA 模型相比仅得到部分提升；DNN 模型将数据按照时间维度展开输入，通过堆叠神经网络可以捕获各时间步的相关性，且对于特定场景下的相关因素进行表示学习，辅助预测任务，效果得到显著提升；LSTM 模型通过引入状态变量与门控机制，克服了DNN 模型对于长序列信息学习能力的不足，可以更好地捕获序列中的长距离依赖，挖掘时空轨迹数据的时序语义信息，与DNN 相比，预测效果大幅提升。

DeepTTE 通过卷积网络及堆叠LSTM 捕获了轨迹数据中的时空相关性，并且引入了分路径的到达时间预测，增加了网络学习能力，与LSTM 模型相比，MAE 降低30%；而DeepETA 模型除了对时空轨迹数据中的时空相关性进行学习，还通过注意力机制对历史数据中频繁模式进行选取，充分考虑历史派送模式对于预测任务的影响，效果在基准实验中最优。而本文提出的MTDTN 模型与DeepETA 模型相比，除了对快递员等影响送达时间的外部因素进行特征提取与表示学习外，还增加了对于地理信息的编码和卷积操作，以进一步捕获地理空间的相关性，同时通过引入未派送快件派送顺序预测辅助任务，充分建模了未派送快件之间的相互影响，从而使得模型效果有了极大提升。

3.5 消融实验

为进一步验证模型各部分的有效性，本文设计了原模型的3 种变体，将这3 种变体与MTDTN 进行比较，各模型描述如下：

1）MTDTN。本文完整模型。

2）MTDTN-A。外部因素模块中将嵌入层转为one-hot 编码，待预测快件特征及快递员的特征以原始值替代额外统计及计算结果。

3）MTDTN-D。将原先的路径表示模块更替为堆叠的两层LSTM。

4）MTDTN-M。在MTDTN 基础上，去除顺序预测子任务，只对快件送达时间进行单任务预测。

消融实验结果如表示2 所示，实验结果充分说明了MTDTN 各模块的有效性。

表2 不同模型消融实验结果对比Table 2 Comparison of ablation experiment results of different models

MTDTN-A 与MTDTN 模型相比，减少了外部因素表示模块中相关因素的特征提取与表示，MAE 上升了近28%，证明了外部因素表示作为其他模块的输入，对于快件送达时间预测问题是有效的。MTDTN-D 与MTDTN 模型相比，无法有效捕获地理空间的相关性，且因为原始地理信息直接输入到LSTM 中，可能引入过多噪声，使得模型对于时间相关性的捕获能力也受到影响，因而预测准确率下降，从另一方面证明了派送路径表示模块对于提高模型效果的作用。MTDTN-M 与MTDTN 模型相比，由于顺序预测辅助任务的缺失，在多目的地预测问题中，无法有效建模未派送快件间的相互影响，MAE 上升62%，MAPE 上升15.5%，说明了本文引入的多任务学习机制对于提升多目的地场景下的到达时间预测准确性具有重要作用。

4 结束语

本文针对快递员派送场景，提出一种基于多任务学习的快件送达时间预测模型。该模型使用多种角度和方式建模影响送达时间的外部因素，通过Geo-hash 编码方式对地理信息编码，使用卷积操作和双向长短时记忆网络捕获派送路径中的时空相关性，并且引入顺序预测辅助任务，基于注意力机制选择历史相似快件组合完成预测子任务，最终通过多任务融合模块输出结果。在真实数据集上的实验结果表明，本文提出的模型在MAE、MAPE 两个指标上明显优于HA、LR 等模型。由于该模型仅引入顺序预测作为辅助任务，下一步将对其他相关事件与快件送达时间预测之间的内在关系进行研究，优化模型结构与计算方式，从而提高快件送达时间预测的准确率。