求解时变速度型车辆路径问题的降维残差注意力模型

A dimension-reducing residual attention model for solving the time-dependent vehicle routing problems

摘要

现实中的车辆路径问题需要面对复杂的道路网络和频繁随时间变化的行驶速度。考虑真实路网下各路段速度的异质性和随时间频繁变化的行驶速度，极大地增加了车辆路径问题的求解复杂度。为了高效地求解这类真实路网下的时变速度型车辆路径问题，提出了一种新颖的基于编码-解码结构的注意力模型——降维残差注意力模型。该模型将节点坐标、货物需求量和行驶时间信息作为模型输入，使用降维注意力机制提取模型输入的关键特征，增强各节点特征向量的表征能力且降低计算成本；引入残差注意力机制实现更好的梯度传递，加速模型收敛。基于包含408个路口节点、1250条有向路段和240个连续时段的成都市区时变速度网络，利用广泛的时变速度型车辆路径问题实例进行模型训练与测试。实验结果显示，本文提出的模型较近期先进的DRL模型性能最高提升约7.8%，且较当前先进的禁忌搜索算法可将计算时间最多约降低至1/1500、并使解的性能最高提升9.6%。

Abstract

Real-world Vehicle Routing Problems （VRPs） are characterized by complex road networks and frequently varying travel speeds. Considering the spatial heterogeneity and frequent temporal variations of travel speeds on real-world road networks significantly increases the computational complexity of solving such problems. To efficiently address such Time-Dependent VRPs （TDVRPs） in real-world networks， this paper proposes a novel attention-based model with an encoder-decoder structure named the Dimension-Reduction Residual Attention Model （DRRAM）. The model accepts node coordinates， demands， and travel time information as inputs. Specifically， a dimension-reduction attention mechanism is employed to extract key features from the inputs， thereby enhancing the representational capacity of node feature vectors while reducing computational costs. Furthermore， a residual attention mechanism is introduced to facilitate better gradient backpropagation and accelerate model convergence. The proposed model is trained and tested using extensive TDVRP instances derived from a time-dependent speed network in Chengdu， which comprises 408 intersections， 1250 directed road links， and 240 consecutive time slots. Experimental results show that the proposed model improves performance by up to approximately 7.8% compared to recent advanced DRL models. Moreover， compared to the state-of-the-art Tabu Search algorithm， it reduces computation time to at most 1/1500 and improves solution quality by up to 9.6%.

Graphical abstract

关键词

城市交通 / 车辆路径 / 时变路网 / 深度强化学习 / 注意力模型

Key words

city transportation / vehicle routing / time-varying road network / deep reinforcement learning / attention model

车辆路径问题（Vehicle Routing Problem， VRP）是物流运输与组合优化领域的基本问题之一。受道路车流量、驾驶行为和限速等各种因素影响，现实的车辆行驶速度往往随时间频繁地变化，导致路网中各路段的行驶速度（时间）具有很高的时变性，这使得传统VRP模型已难以准确反映实际情况。在现有文献中，考虑行驶速度随时间变化的车辆路径问题通常被称为时间依赖型车辆路径问题（Time-dependent Vehicle Routing Problem， TDVRP），这类问题通常考虑整个计划周期包含3~9个不同的时间段，并假设同一时间段内所有路段上的行驶速度均相同，而不同时间段的路段行驶速度各不相同。然而，这种方式没有考虑到真实路网下路段行驶速度随时间频繁变化的特点。为了区别于现有TDVRP问题，本文将考虑频繁随时间变化行驶速度特征的VRP问题，称为时变速度型VRP问题。该问题对速度时变特征的考虑，进一步增加了VRP问题的求解难度。本文的创新性在于以2 min为时间间隔，更加精准地刻画了路网速度的时变性，并首次将降维注意力机制与残差注意力机制结合引入AM模型并应用于时变速度型VRP问题的求解，最后通过真实路网数据进行了验证。

求解TDVRP问题的常见方法主要包括精确算法、启发式与元启发式算法。精确式算法可以得到理论上的最优解。Liu等^［1］在考虑时间窗的绿色车辆的TDVRP问题（Time-dependent Green Vehicle Routing Problems with Time Window， TDGVRPTW）时，引入了TD（Time-dependent）弧这一概念描述服务客户的过程，并可以将无限多的TD弧简化为一组有限的非支配 TD 弧。他们采用分支定价算法求解这一问题，并能在客户数为100的情况下具有有效性。Monemi 等^［2］引入逻辑型Benders分解算法（Logic-Based Benders Decomposition， LBBD）进行求解：主问题负责生成满足容量约束的可行路径（忽略时间依赖性），子问题则针对每条路径验证其在时间依赖交通条件下的可行性，并通过生成最优性割或不可行性割反馈至主问题迭代优化。他们以加拿大魁北克市的实际路网和历史交通数据为基础构建实例，验证了算法能够在50的客户规模上能取得最优解。文献［3-5］将路径规划期分为7个时段并采用分支定价算法求解考虑不同问题特征的TDVRP问题，Vidal等^［3］解决了非完全连接无向路网上的TDVRP问题，客户数不超过75；Wölck等^［4］和Zhang等^［5］考虑了最多50个客户数，分别解决了考虑货物拣选和装载用时与考虑货物二维形状限制的TDVRP问题。精确算法虽然可以保证解的最优性，但由于VRP问题的NP-hard属性^［6］，上述研究都没有求解客户数超过75的问题，而实际中可能面对更大客户数的情况。

启发式和元启发式算法相比于精确式算法有更快的求解速度，作为典型的启发式算法，贪婪算法具有很快的求解速度，但寻优能力有限。而元启发式算法常被应用于大规模的、非线性、组合约束等问题^［7］。近年来，学者广泛使用元启发式算法求解TDVRP问题。采用此类方法的研究中，一些学者求解了包含3个时段的TDVRP问题，葛显龙等^［8］和吴瑶等^［9］提出改进的遗传算法，分别求解了真实路网下的TDVRP问题和带时间窗的易腐食品配送问题。一些学者求解了包含5个时段的TDVRP问题，张建同等^［10］采用改进的模拟退火算法求解TDVRPTW问题；Gmira等^［11］采用改进的禁忌搜索算法，求解了考虑非完全连接路网结构下考虑最多50个客户的TDVRPTW问题；张歆悦等^［12］和陈仕军等^［13］将路径规划时间划分为9个时段，前者采用一种混合遗传算法求解了TDVRPTW问题；后者提出了混合人工蜂群算法考虑同时取送货的VRP问题。此外，还有一些应用其他元启发算法的研究。如Fan等^［14］设计了一种两阶段混合蚁群算法：第一阶段利用改进的K-means聚类进行客户分配；第二阶段采用改进的蚁群算法（IACA）优化集群内路径。虽然元启发式算法已有广泛的应用且取得了良好的结果，但前述研究考虑的客户数通常为50~100，且随着客户数的增大，元启发式算法的计算时间大大增加。另外，当现实应用中有多个问题例需要同时求解时，上述方法只能依次计算每个问题例的解。此外，前人研究通常将路径规划时间划分为3~9个时段，难以表示车辆实际行驶中速度的频繁变化，且假设只有1种^{［10，12-13］}或者3种路段类型^{［9，10-11］}，并设定在同一时段中同类型的所有路段上车辆行驶速度相同，对各路段速度的异质性（差异）考虑不充分。在现实的道路网络中，车辆的速度频繁地随时间发生变化，以每2 min为一个时间周期计算，8 h的路径规划期包含240个时间周期，且同一时段不同路段上的行驶速度也可能不同。考虑真实路网下不同路段上行驶速度的异质性以及时变的行驶速度，能够更加真实地计算出生成解对应的目标函数值，有助于提高解的质量。而对这些现实特征的考虑，会大大增加时变速度型VRP问题的计算时间，亟需提出更加高效的求解方法。

随着深度学习领域的飞速发展，利用深度学习算法求解路径优化等组合优化问题吸引了一些学者的关注。Vinyals 等^［15］提出指针网络（Pointer Network，PtrNet）解决旅行商问题等多个组合优化问题，标志着采用端到端的深度学习方式解决组合优化问题的开端。PtrNet采用编码器-解码器结构，编码器被用来提取输入信息，解码器被用来计算每步各节点被选择的概率，以监督学习的方式训练网络参数。Bello等^［16］在PtrNet的基础上，首次引入强化学习算法^［17］，让车辆通过不断探索学习到获得最优路径的策略，可避免监督学习需要大量时间构造测试集标签的弊端。Nazari等^［18］以线性嵌入层代替PtrNet模型编码器的循环网络结构，首次采用基于深度强化学习的方法求解考虑容量限制的VRP问题。Kool等^［19］提出注意力模型（Attention Model，AM），采用Transformer模型^［20］完成编码和解码，在求解考虑容量限制的VRP和其他组合优化问题时的求解性能优于Bello等^［16］提出的模型，求得的解的性能与LKH3算法^［21］和Gurobi优化求解器求得解的性能相当，但求解速度比后两者高出数百倍。还有一些学者进一步研究求解了考虑同时取送货^{［22–25］}、多车场^［26-27］和其他特征^{［28–30］}的VRP问题。

上述研究展示了深度强化学习算法求解VRP问题的巨大潜力，特别是远高于元启发算法的求解效率以及可以同时求解大量问题实例的并行优化能力，但该领域研究还处于早期阶段。如何利用深度强化学习求解TDVRP问题，特别是时变速度型VRP问题，还未见报道。另外，在前人利用深度强化学习求解VRP问题的研究中，通常基于人工生成的全连接路网和速度数据进行模型训练和测试。全连接路网的假设忽略了节点之间不直接相连、部分路段单向通行等现实情况；而人工生成速度数据往往难以表示现实路网中时变路段行驶速度的真实规律。另外，上述模型输入中均未考虑路网中的行驶速度或时间信息，而这些行驶速度信息对于TDVRP问题的求解至关重要。如何在前人研究的基础上，探索和提出适用于考虑真实路网和时变行驶速度特征的VRP问题求解的深度强化学习模型，是一个开放且重要的研究问题。

本文结合真实路网中路段速度随时间频繁变化的特征，将一个降维注意力机制与一个残差注意力机制引入到AM模型中，提出降维残差注意力模型（Dimension-reducing Residual Attention Model， DRRAM），用于高效求解现实中的时变速度型VRP问题。为了更好地验证模型性能，需要更加精细和真实地刻画路网。将整个路径计划期分为240个时长2 min的时间段，在包含408个路口节点和1250条有向路段的城市路网上对所提出的DRRAM模型进行训练和测试。将训练后的DRRAM模型与AM模型的性能以及求解TDVRP问题的代表性算法的性能进行对比，验证提出方法的有效性。

本文贡献主要有以下3点： 1） 研究了现实路网中一类行程时间频繁变化的TDVRP问题； 2） 提出了一类高效的DRL模型求解所研究的TDVRP问题，该模型在求解质量、计算时间和泛化性能方面都明显优于基准方法，包括一种代表性的启发式算法和两种DRL模型； 3） 本文提出的DRL模型在已有DRL模型的基础上做出了两点改进，包括集成降维注意力模块与残差注意力模块。

1 问题描述与模型建立

1.1 问题描述

以有向图G=(V,E)表示路网，其中V=\{\mathrm{0},\dots ,F\}表示路网节点集合，节点0表示仓库，E=\{\mathrm{0},\cdots ,L\}表示连接各道路节点之间的边，以N=\{\mathrm{1},\cdots ,n\}，N\subset V表示需要访问的客户点集合，N_{\mathrm{0}}=N\bigcup \{\mathrm{0}\}表示仓库点和所有客户点的集合。N_{\mathrm{0}}中节点i对应的二维地理坐标和货物需求量分别为(x_i^h,x_i^v)和d_i，仓库的货物需求量为0。车辆集合K=\{\mathrm{1},\cdots ,\gamma \}表示有\gamma辆容量均为Q的车辆，其中部分或者全部车辆从仓库出发向各个客户送货，以较小的时间周期（如2 min）将1个路径计划期（如8 h）均等地划分为B个连续时段。每个时间周期中，每个路段的行驶速度是恒定的，但是不同路段间的速度可能不同。在不同时间周期中，同一路段的行驶速度可能不同。T_{i,j,p}表示在时段p\left(p\in P=\left(\mathrm{1},\cdots ,B\right)\right)内某时刻由点i出发，直到驶达点j的最短行驶时间。T_{i,j,p}的具体计算方法考虑了实际路网结构和时变速度特性，详细介绍见第3.1节。基于T_{i,j,p}，可以将实际路网转换为仅由仓库和客户节点组成的全连接有向路网，其中全连接路网节点间的权重即为最短行驶时间。决策变量y_{i,j,p}^k表示车辆k是否在时段p内从节点i出发驶向节点j。假设每个客户只能送货一次，时变速度型VRP问题需要决定如何规划送货路线（即决定决策变量y_{i,j,p}^k的值），使得车辆完成所有客户的送货任务并返回仓库所花费的总旅行时间最短。

为更好地描述所研究的问题，结合图1进行说明。从图1中可看出每个路网节点只与周围的几个节点直接相连，与其他节点不直接相连。节点间的带箭头线段的长度表示节点之间的距离，线段越长表示距离越大。节点间的箭头数越多表示节点间的行驶速度越快。此外，双向箭头表示节点间可以双向行驶；单向箭头表示节点间只能按箭头方向行驶。可以看出时段1和时段2对应位置的箭头数有差异，说明不同时段下节点间的行驶速度有差异。另外，同一时段下节点间不同方向的行驶速度也可能不同。在时段1仓库中的两辆车从仓库出发开始送货。到了时刻2，车辆1在驶向客户3；车辆2已经服务完了客户1，正在驶向客户2。

1.2 数学模型

基于问题描述，本文所研究的数学模型表示如下：

\begin{array}{l}\mathrm{m}\mathrm{i}\mathrm{n}C=\sum _{p\in P}\sum _{i\in N_{\mathrm{0}}}\sum _{j\in N_{\mathrm{0}}}\sum _{k\in K}(y_{i,j,p}^k{T}_{i,j,p}),\mathrm{s}.\mathrm{t}.\\ \end{array}（1）

\sum _{p\in P}\sum _{j\in N_{\mathrm{0}}}\sum _{k\in K}{y}_{i,j,p}^k=\mathrm{1},\forall i\in N（2）

\sum _{p\in P}\sum _{i\in N_{\mathrm{0}}}\sum _{k\in K}{y}_{i,j,p}^k=\mathrm{1},\forall j\in N（3）

\sum _{p\in P}\sum _{i\in N}{y}_{i,j,p}^k-\sum _{p\in P}\sum _{i\in N}{y}_{j,i,p}^k=\mathrm{0},\forall j\in N,\forall k\in K（4）

a_j\le o_j,\forall j\in N（5）

\sum _{p\in P}\sum _{i\in N}\sum _{k\in K}{y}_{i,\mathrm{0},p}^k=\sum _{p\in P}\sum _{i\in N}\sum _{k\in K}{y}_{\mathrm{0},i,p}^k\le \gamma（6）

\sum _{i\in N}\sum _{j\in N}\sum _{p\in P}(d_i{y}_{i,j,p}^k)\le Q,\forall k\in K（7）

\sum _{p\in P}\sum _{i\in S}\sum _{j\in S}{y}_{i,j,p}^k\le |O|-\mathrm{1},O\subseteq N,O\ne \mathrm{\varnothing },k\in K（8）

y_{i,j,p}^k=\mathrm{0,1},\forall i,j\in N_{\mathrm{0}},\forall k\in K,\forall p\in P（9）

式（1）表示目标函数为最小化总旅行时间，即所有车辆的行驶时间之和最短。式（2）与式（3）共同表示每个客户只能被访问且必须被访问一次，其通过限制驶向和驶出任意客户的车辆数为1实现。式（4）表示某车辆在访问完客户后，必须从该客户离开。式（5）表示车辆达到客户的时间不晚于离开时间，其中a_j和o_j分别表示车辆到达和离开客户节点j的时刻。式（6）表示每个车辆由仓库出发，完成货物配送后返回仓库，且使用车辆数不超过\gamma。通过约束由仓库驶向客户的车辆数之和等于客户点驶向仓库的车辆数之和，且小于\gamma实现。式（7）表示每辆车配送的货物总量不超过其容量。式（8）表示消除子回路约束。O表示N的真子集，|O|表示O 中节点的个数。对于N的任意真子集，使得任意车辆在节点行驶所形成的边数（在此为方便表述，将由一个节点驶向另一个节点称为一条边），小于等于该真子集的顶点数减1。式（9）对0-1决策变量y_{i,j,p}^k进行定义，若车辆k在时段p内从节点i出发驶向节点j则为1，否则为0。

由上述数学模型可知，时变速度型车辆路径问题考虑了真实的道路速度随时间频繁变化的规律，导致在一个计划期需要考虑更多的时间周期。相对于时间依赖型车辆路径问题，这也导致了计算复杂度的大幅增加。利用传统方法进行求解，特别是对于大规模问题，其计算时间较长。

1.3 马尔科夫决策过程建模

对于时变速度型VRP问题，其解方案构造过程是一个序列决策过程。在每一决策步骤中，决策者的当前状态可以清晰定义，包括车辆位置和剩余容量等，构成了离散的状态空间；决策者需选择下一个访问的客户或返回仓库，形成有限的动作集；此决策依赖于当前状态，而不受之前状态序列的影响，符合马尔科夫性质，且状态转移是确定的；时变速度型VRP问题的目标为最小化总旅行时间，可以将总旅行时间的负数视为奖励函数。通过以上分析，可以看到时变速度型VRP问题的解构造过程可以用马尔科夫决策过程（Markov Decision Process，MDP）来表示。因此在本文中将其建模成一个由四元组M=\{S,A,\tau ,\mathrm{ℛ}\}表示的MDP。其中状态空间S，动作空间A，状态转移规则\tau和奖励函数\mathrm{ℛ}的详细介绍如下。

1） 状态：在我们的MDP中，每个状态s_t由车辆状态I_t^{\mathrm{v}\mathrm{e}\mathrm{h}}和节点状态I_t^{\mathrm{n}\mathrm{o}\mathrm{d}\mathrm{e}}两部分组成，即s_t=\left(I_t^{\mathrm{v}\mathrm{e}\mathrm{h}},I_t^{\mathrm{n}\mathrm{o}\mathrm{d}\mathrm{e}}\right)\in S，其中t\in \left(\mathrm{1},\cdots ,T\right)表示时间步。在每个解方案构造包括T个时间步，在每个时间步都会执行一个操作来选择下一个要访问的节点。两个连续时间步之间的持续时间可以包含多个时段p。车辆状态I_t^{\mathrm{v}\mathrm{e}\mathrm{h}}=(l_t,R_t)，其中l_t，R_t分别表示车辆所在位置和剩余容量。节点状态I_t^{\mathrm{n}\mathrm{o}\mathrm{d}\mathrm{e}}包括节点信息和节点间的行驶时间信息，其将在第2.1节中被详细介绍。

2） 动作：在我们的MDP中，a_t=i_t，其表示在时间步t，车辆会选择客户i作为下一个服务客户。

3） 状态转移规则：基于动作a_t，状态转移规则将前一个状态 s_t 转换到下一个状态s_{t+\mathrm{1}}。具体而言，车辆状态I_t^{\mathrm{v}\mathrm{e}\mathrm{h}}中的元素按下式进行更新：

l_{t+\mathrm{1}}=i（10）

R_{t+\mathrm{1}}=R_t-d_i（11）

其中，d_i表示节点i的需求。在节点状态I_t^{\mathrm{n}\mathrm{o}\mathrm{d}\mathrm{e}}中，节点信息不变，行驶时间信息随时间变化。具体而言，假设时段p和p^{\text{'}}分别对应时间步t和t+\mathrm{1}，从客户节点i到客户节点j的最短行驶时间，从T_{i,j,p}变为T_{i,j,p^{\text{'}}}。

4） 奖励：奖励\mathrm{ℛ}是MDP 中所有即时奖励 r_t的总和。对于时变速度型VRP问题，我们定义\mathrm{ℛ}=-{\sum }_{t=\mathrm{1}}^T{r}_t，即总的行驶时间和的负值。假设时间步t对应的时段为p，即时奖励r_t表示车辆从节点l_t驶向节点i的行驶时间，即T_{l_t,i,p}。

基于上文介绍的MDP中的4个元素，我们对基于MDP的时变速度型VRP问题的求解过程进行介绍。给定状态s_t，通过DRRAM的解码过程得到在时间步t车辆的服务客户为i。假设时间步t对应时段p，我们得到行驶时间T_{l_t,i,p}，也就是即时奖励r_t。接下来，通过状态转换规则\tau获得下一个状态s_{t+\mathrm{1}}。经过T个时间步后获得完整的解方案和奖励\mathrm{ℛ}。基于奖励\mathrm{ℛ}，使用REINFORCE 算法^［17］更新DRRAM的参数。重复上述过程，直到满足终止条件，将得到的奖励最大的解作为时变速度型VRP问题的最终解。

2 降维残差注意力模型

VRP问题可以视为序列决策问题，编码-解码结构是解决此类问题的有效框架。编码器将节点的信息映射为神经网络向量，作为对节点状态I_t^{\mathrm{n}\mathrm{o}\mathrm{d}\mathrm{e}}的表征。解码器根据每一步车辆的信息，即所处节点位置l_t和剩余容量R_t，对车辆状态I_t^{\mathrm{v}\mathrm{e}\mathrm{h}}进行表征；并根据解码器的结果，计算出当前时间步的执行动作a_t。DRRAM模型遵循AM模型^［19］中的编码-解码结构构建。两者的解码器采用相同的结构与计算方式，两者结构和计算方式上的差异在于DRRAM模型的编码器中引入了降维注意力机制和残差注意力机制。另外，在模型输入上，AM模型仅仅将节点位置和需求作为模型输入；对于时变速度型VRP问题，行驶时间信息很可能对于求解性能也有重要影响。因此，本文将行驶时间信息作为模型输入，使模型能够提取更多信息，以提高模型性能。

2.1 模型概述

DRRAM模型的结构如图2所示。该模型针对真实路网中速度时变的特征，创新性地引入降维注意力机制，以提取包括路网行驶时间在内的输入信息，可大幅降低因在模型输入包含路网行驶时间信息所带来的计算时间与内存成本增长；同时，率先将残差注意力机制引入到AM模型，可实现更好的梯度传递与性能优化。

DRRAM模型的编码器根据各节点的输入特征信息计算得到对应的节点嵌入，即对各节点信息在高维空间进行表征。具体而言，对于节点（客户或仓库）i，其输入特征信息表示为f_i=\{f_{i,\mathrm{0}},f_{i,\mathrm{1}},\cdots ,f_{i,n}\}，其中n为节点规模，子特征f_{i,j}=(x_i^h,x_i^v,d_i,T_{i,j,\mathrm{0}})，仓库节点的货物需求量d_{\mathrm{0}}=\mathrm{0}，T_{i,j,\mathrm{0}}表示路径优化的起点时刻0从节点i到节点j的最短行驶时间。各节点的输入特征信息\left\{f_{\mathrm{0}},\cdots ,f_n\right\}在DRRAM模型的编码器中，依次经过一个全连接层，一个降维注意力模块和两个结构相同但网络参数不同的残差注意力模块进行相应的计算，便可得到各节点的节点嵌入\left\{h_{\mathrm{0}},\cdots ,h_n\right\}。两个残差注意力模块在模型中承担不同的功能角色，前一个模块处理低级特征而后一个处理高级特征整合，在DRRAM模型训练学习的过程中，这两个模块被自动赋予不同的参数。降维注意力模块的结构如图3所示，残差注意力模块与降维注意力模块结构相同，但计算方式有一定差异，具体详见第2.2节和2.3节的介绍。

DRRAM模型中的解码器由一个多头注意力层和一个单头注意力层组成。其基于编码器输出的节点嵌入和上一步访问的节点索引，计算出每个节点被选中的概率，由此选择下一个需要访问的节点（客户或仓库）。每次选择下一个节点的过程被称为一次解码运算。解码器需要进行多次解码运算，直到完成所有客户的配送任务并返回仓库。在这个过程中，DRRAM模型依次规划每个车辆的行驶路径，即构建完前一辆车的配送路线后，才能开始构建下一辆车的路线。具体而言，以第r次解码运算为例，首先将所有节点嵌入的平均\overline{H}、车辆当前货物余量D^{\mathrm{r}\mathrm{e}\mathrm{s}\mathrm{t}}和车辆所处节点对应的节点嵌入h_{{\pi }_{r-\mathrm{1}}}拼接成一个状态向量，然后与编码器输出的节点嵌入一起输入给解码器中的多头注意力层，从而计算状态向量与各节点的相关性（当某客户节点已被访问或需求量超过车辆剩余容量时，设置与该节点的相关性为0），再根据关联性对各节点信息加权求和，得到当前环境的表征。在单头注意力层中，根据约束条件、当前环境的表征和各节点的嵌入，计算各节点被选择作为下一步访问节点的概率（不满足第1.2节中约束条件的节点对应的概率设为0），然后基于此概率选出下一个访问节点{\pi }_t\in N_{\mathrm{0}}。在选择节点时，可采用sample策略和greedy策略，sample策略表示根据概率随机选择节点，其中概率越大的节点越有可能被选中；greedy策略表示只选择概率最大的节点。对于某时变速度型VRP问题实例，最终求解得到一个使得总旅行时间最小的车辆行驶路径\Phi（即由仓库和客户节点组成的节点序列\Phi =({\phi }_{\mathrm{1}},\dots ,{\phi }_t,\dots ,{\phi }_T)，t\in \{\mathrm{1},\dots ,T\}）。T为节点序列\Phi的长度，即解码运算的次数。由于不同解方案使用的车辆数可能不同，所以在不同的解方案中R的值也可能不同。给定问题实例s，令\theta表示DRRAM模型的网络参数，根据链式法则，DRRAM模型得到解方案\Phi的概率为：

P(\Phi |s)={\displaystyle \prod _{r=\mathrm{1}}^R}{p}_{\theta }({\phi }_r|s,{\phi }_{\mathrm{1}:r-\mathrm{1}}),

其中，表示在第r次解码前已经访问过的节点，p_{\theta }({\phi }_r|s,{\phi }_{\mathrm{1}:r-\mathrm{1}})表示第r次解码时模型选择访问节点为{\phi }_r的概率。

2.2 降维注意力模块

降维注意力模块由包含多个注意力头的多头降维注意力层和一个前馈层组成，如图3所示，\mathrm{D}\mathrm{R}-\mathrm{H}\mathrm{e}\mathrm{a}{\mathrm{d}}_m表示编码器中降维注意力模块中的第m个注意力头，\oplus表示向量拼接运算，即将各个注意力头的输出向量拼接成一个向量。

在AM模型等求解带容量的VRP问题的深度强化学习模型中，每个节点的输入特征信息为由经纬度和需求值组成的\mathrm{1}\times \mathrm{3}的向量。在客户数为n的情况下，将行驶时间信息按前文所述的方式包含进节点输入特征信息后，单个节点的输入特征信息可表示为(n+\mathrm{1})\times \mathrm{4}的矩阵。行驶时间信息的导入会使模型的输入特征信息矩阵的维度由(n+\mathrm{1})\times \mathrm{3}变为(n+\mathrm{1})\times (n+\mathrm{1})\times \mathrm{4}。由于模型的输入特征信息矩阵的维度升高，如果仍然使用AM模型中的注意力机制，会导致计算时间和内存大幅度增加。为了在提取节点位置、需求与时间信息的同时减少计算时间和内存，提出降维注意力机制。

注意力机制可理解为将各节点之间的信息按关联程度相互融合，有利于增强节点特征向量的表征能力。此外，为了使得模型能够从多个不同的角度计算各节点之间关联程度，使用了多头注意力机制进行信息融合。降维多头注意力层中第m个注意力头\mathrm{D}\mathrm{R}-\mathrm{H}\mathrm{e}\mathrm{a}{\mathrm{d}}_m的计算过程如（13）~（19）式所示：

q_{i,m}^{\mathrm{1}}=W_m^Q{h}_i^{\mathrm{0}}（13）

k_{i,m}^{\mathrm{1}}=W_m^K{h}_i^{\mathrm{0}}（14）

v_{i,m}^{\mathrm{1}}=W_m^V{h}_i^{\mathrm{0}}（15）

其中，h_i^{\mathrm{0}}表示节点i的输入特征信息f_i通过全连接层映射得到对应的初始特征向量，其维度为(n+\mathrm{1})\times d_k。q_{i,m}^{\mathrm{1}}，k_{i,m}^{\mathrm{1}}，v_{i,m}^{\mathrm{1}}分别表示节点i在第l个编码器模块（即降维注意力模块）的第m个注意力头中所对应的查询向量（query）、键向量（key）和值向量（value），维度均为(n+\mathrm{1})\times \frac{d_k}{M}，M为注意力头的个数。W_m^Q，W_m^K，W_m^V为对应的可学习的网络参数。再按式（16）~式（18）的方式计算节点i与节点j之间的相关性即注意力权重：

\mathrm{s}(q_{i,m}^{\mathrm{1}},k_{j,m}^{\mathrm{1}})=\frac{q_{i,m}^{\mathrm{1}}(k_{j,m}^{\mathrm{1}}{)}^{\mathrm{T}}}{\sqrt[]{d_k}}（16）

u_{i,j,m}^{\mathrm{1}}=\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{g}\mathrm{n}\mathrm{o}\mathrm{a}\mathrm{l}(s(q_{i,m}^{\mathrm{1}},k_{j,m}^{\mathrm{1}}))（17）

({\alpha }_{i,j,m}^{\mathrm{1}}{)}_{j^{\mathrm{\text{'}}}}=\mathrm{s}\mathrm{o}\mathrm{f}\mathrm{t}\mathrm{m}\mathrm{a}\mathrm{x}((u_{i,j,m}^{\mathrm{1}}{)}_{j^{\mathrm{\text{'}}}})=\frac{{\mathrm{e}}^{(u_{i,j,m}^{\mathrm{1}}{)}_{j^{\mathrm{\text{'}}}}}}{\sum _{j^{\text{'}}}{\mathrm{e}}^{{}^{(u_{i,j,m}^{\mathrm{1}}{)}_{j^{\mathrm{\text{'}}}}}}}（18）

其中，(k_{j,m}^{\mathrm{1}}{)}^{\mathrm{T}}表示向量k_{j,m}^{\mathrm{1}}的转置，s(\cdot )表示缩放点积函数，\mathrm{s}(q_{i,m}^{\mathrm{1}},k_{j,m}^{\mathrm{1}})为维度等于(n+\mathrm{1})\times (n+\mathrm{1})的矩阵，\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{g}\mathrm{n}\mathrm{o}\mathrm{a}\mathrm{l}(\cdot )函数表示提取矩阵的对角线元素，从而使得u_{i,j,m}^{\mathrm{1}}的维度变为(n+\mathrm{1})。u_{i,j,m}^{\mathrm{1}}中的(n+\mathrm{1})个元素衡量了节点j的(n+\mathrm{1})个子特征信息与节点i的相关性，再将这些元素通过\mathrm{s}\mathrm{o}\mathrm{f}\mathrm{t}\mathrm{m}\mathrm{a}\mathrm{x}(\cdot )归一化函数映射到(\mathrm{0,1})的范围，得到注意力权重{\alpha }_{i,j,m}^{\mathrm{1}}。(u_{i,j,m}^{\mathrm{1}}{)}_{j^{\mathrm{\text{'}}}}，{\left({\alpha }_{i,j,m}^{\mathrm{1}}\right)}_{j^{\text{'}}}分别表示u_{i,j,m}^{\mathrm{1}}和{\alpha }_{i,j,m}^{\mathrm{1}}的第j^{\mathrm{\text{'}}}个元素。

式（19）表示根据注意力权重汇总各节点的值向量，由此实现不同节点信息的加权传递。

h_{i,m}^{{\mathrm{1}}^{\text{'}}}={\displaystyle \sum _{j=\mathrm{0}}^n}{\alpha }_{i,j,m}^{\mathrm{1}}{v}_{j,m}^{\mathrm{1}}（19）

然后利用式（20）将M个注意力头的结果进行融合汇总，得到节点i经过多头降维注意力层计算之后对应的特征向量{h_i^{\mathrm{1}}}^{\mathrm{\text{'}}}。

{h_i^{\mathrm{1}}}^{\mathrm{\text{'}}}=W_M^O\left(\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{c}\mathrm{a}\mathrm{t}\left(h_{i,\mathrm{1}}^{{\mathrm{1}}^{\text{'}}},\cdots ,h_{i,M}^{{\mathrm{1}}^{\text{'}}}\right)\right)（20）

式中，\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{c}\mathrm{a}\mathrm{t}(\cdot )函数对应图3中的\oplus操作，表示向量的拼接。由此经过式（13）~式（20）的过程可将维度为(n+\mathrm{1})\times (n+\mathrm{1})\times d_k的 特征矩阵变为维度为(n+\mathrm{1})\times d_k特征矩阵。前馈层的主要作用为防止梯度爆炸和加速收敛，需经过（21）~（23）式的计算，最终得到节点i经过降维注意力模块计算得到的节点特征h_i^{\mathrm{1}}：

{\widehat{h}}_i^{\mathrm{1}}=\mathrm{B}\mathrm{N}\left(h_i^{\mathrm{0}}+{h_i^{\mathrm{1}}}^{\mathrm{\text{'}}}\right)（21）

\mathrm{F}\mathrm{F}\left({\widehat{h}}_i^{\mathrm{1}}\right)=W_{\mathrm{1}}^F(\sigma \left(W_{\mathrm{0}}^F{\widehat{h}}_i^{\mathrm{1}}+b_{\mathrm{0}}^F\right))+b_{\mathrm{1}}^F（22）

h_i^{\mathrm{1}}=\mathrm{B}\mathrm{N}\left({\widehat{h}}_i^{\mathrm{1}}+\mathrm{F}\mathrm{F}\left({\widehat{h}}_i^{\mathrm{1}}\right)\right)（23）

式中，W_{\mathrm{0}}^F,W_{\mathrm{1}}^F,b_{\mathrm{0}}^F,b_{\mathrm{1}}^F表示可学习的网络参数，\sigma \left(\cdot \right)表示ReLu激活函数，\mathrm{B}\mathrm{N}(\cdot )为批量归一化函数。

2.3 残差注意力模块

残差注意力机制将前一个模块中查询向量与键向量的点积缩放结果传递到当前模块，可实现更好的梯度下降，有助于模型更好地收敛^［31］。受此启发，本文将残差注意力机制引入AM模型中，提出了残差注意力模块，以获得更好的优化性能。其中，查询向量和键向量可理解为VRP问题中客户和仓库节点特征（位置、需求和行驶时间信息）的高维表征。残差注意力模块与前文所述的降维注意力模块具有相同的结构，唯一的区别在于注意力头的计算方式不同。即，将式（17）替换为如式（24）：

u_{i,j,m}^l=\mathrm{s}(q_{i,m}^l,k_{j,m}^l)+\mathrm{s}(q_{i,m}^{l-\mathrm{1}},k_{j,m}^{l-\mathrm{1}})（24）

u_{i,j,m}^l代表第l个注意力模块中第m个注意力头内，节点i与节点j未经归一化前的关联性，其表示为当前注意头内的查询向量q_{i,m}^l和键向量k_{j,m}^l的缩放点积\mathrm{s}(q_{i,m}^l,k_{j,m}^l)与第l-\mathrm{1}个注意力模块中的对应缩放点积\mathrm{s}(q_{i,m}^{l-\mathrm{1}},k_{j,m}^{l-\mathrm{1}})之和。

2.4 训练方法

前文描述了如何构造DRRAM模型的输入，以及给定模型输入，DRRAM模型如何构建可行解。在使用DRRAM模型有效求解时变速度型VRP问题前，还需要对该模型进行训练，使得模型具备很好的寻优性能。采用REINFORCE算法^［17］训练DRRAM模型，该算法的核心思想在于让车辆不断探索，即构造不同的路径，并通过梯度下降算法优化网络参数，以学习到最优的路径构造策略。具体而言，对于给定的问题实例s，将损失函数设为\mathrm{ℒ}(\mathit{\theta }\left|s\right.)，该问题实例下网络参数\theta的梯度如式（25）所示：

\nabla L(\theta |s)=E_{p_{\theta (\phi |s)}}[(L(\phi |s)-b(s))\nabla \mathrm{l}\mathrm{o}{\mathrm{g}}_{p_{\theta }}(\phi |s)]（25）

式（25）中的L(\pi \left|s\right.)和b\left(s\right)分别表示策略网络和基准网络对于问题实例s求解得到的目标值，即所有车辆的总用时，其中策略网络和基准网络是参数分别为\theta和\omega的DRRAM模型。在每次选择下一步拟访问节点时，策略网络和基准网络都计算出当前状态下各节点被选择的概率，并分别采用sample策略和greedy策略选择下一步访问的节点，从而逐步构建出问题实例s的解方案。基准网络的作用为减少梯度方差，提高训练效率。训练过程开始时，将策略网络的参数\theta和基准网络的参数\omega进行初始化，即在(-\frac{\mathrm{1}}{\sqrt[]{d_k}},\frac{\mathrm{1}}{\sqrt[]{d_k}})的区间内通过随机采样为\theta和\omega赋值；在训练过程中，策略网络使用反向传播算法对参数进行迭代更新，而基准网络不通过反向传播更新参数。当L(\phi |s)在sample策略下求解的目标值优于b(s)在greedy策略下求解的目标值时，则将基准网络的参数，更新为策略网络的参数\theta。

为了得策略网络参数\theta的梯度值，利用蒙特卡洛采样的方式通过下式近似计算：

\nabla L(\theta )\approx (L({\phi }_a^s|s_a)-b(s_a))\nabla \mathrm{l}\mathrm{o}{\mathrm{g}}_{p_{\theta }}({\phi }_a^s|s_a)（26）

其中，S为采样的问题实例数量，即同时被求解的问题实例数，s_a为S个问题实例中第a个问题实例。{\phi }_a^s为策略网络使用sample策略产生的问题实例s_a的解。基于式（26）计算得到参数\theta的梯度，采用Adam优化器^［32］更新\theta。经过多个回合（epoch）的训练，每个回合包含多个批量数的训练算例，可得到训练好的策略网络参数\theta。

3 算例与分析

3.1 算例设定

本文基于文献［33］中的路网来构造实验中的问题实例。该路网为成都市一环路网，包括408个节点和1250条有向边。采用Guo等^［34］的方法，根据成都市区内出租车于2017年6月1日至9月18日期间在该市一环路及以内区域的GPS行驶数据，计算出110 d的路段行驶速度数据集。在该数据集中，以2 min为时间间隔，将每天早上8点至下午4点的时间划分为240个时段。每一个时段中，各边对应不同的恒定行驶速度。各时段各条边上的行驶速度根据110 d的记录可计算出对应的110个值，在建模时变路网时，各时段各条边的速度由110个值中的中位数表示。根据Huang等^［35］提出的时变最短路算法，在计算过程中，我们考虑了以下关键因素： 1） 出发时段的初始速度； 2） 行程跨越多个时段和多个路段时发生的速度变化，即当车辆行驶跨越时段边界或进入新的路段时，我们会更新使用相应的速度； 3） 路网的实际结构（如路段长度、单向路、不直接相连的节点等）。通过动态更新车辆在不同路段和时段的行驶速度，我们确保了计算结果能够准确反映实际路况下的最短行驶时间。最终，我们得到了一个\mathrm{240}\times \mathrm{408}\times \mathrm{408}的三维矩阵，表示在240个时间周期中的任意一个时间周期出发，408个节点相互之间的最短行驶时间。为了训练模型和测试完成训练模型的性能，需要构造训练集和测试集。以客户数为30、50、80、100构造4组不同规模的训练集、验证集和测试集，在每组训练集、验证集和测试集中，分别包含640 000、5120和10 000个算例。对于含有客户点数为n的算例，从408个道路节点中随机选择n个节点作为客户点，再另外随机选择一个节点作为仓库点。各点的二维坐标以通用横轴墨卡托投影（Universal Transvers Mercator）坐标系统表示，货物需求量在1~9之间随机采样，车辆容量均为30，车辆数足够满足配送需求。

3.2 超参数设定

在实验中，DRRAM模型与AM模型中共同存在的超参数的取值相同。节点嵌入的维度为128，DRRAM模型编码器中的降维注意力模块与残差注意力模块以及解码器中的多头注意力层都包含8个注意力头。模型训练回合设定为100，Adam优化器的学习率设为0.000 1。考虑到运行内存和训练所需时间，将训练过程中的批量数设为256，即同时被输入给模型进行求解的问题实例数。

3.3 性能分析

为测试训练好的DRRAM模型的性能，将其与适用于求解所研究问题的算法性能进行对比。由于所研究问题实际上是一个考虑行驶速度频繁随时间变化的TDVRP问题，而当前还没有适用于该问题的精确算法被提出和报道^［11］。因此，本文将改进型禁忌搜索（GmiraTS）算法^［11］ 、贪婪算法、AM模型和Wang等^［36］提出的模型用作基准算法，与所提出方法进行性能对比。GmiraTS 算法在NEWLET测试集^［37］上的结果与精确算法的差距小于1%；贪婪算法在每个当前节点，选择当前时段行驶时间最短且满足约束条件的剩余客户节点作为下一个访问的节点；AM模型在求解带容量的VRP问题时，在极短的计算时间内即可达到媲美主流商业优化求解器Gurobi需要长时间计算才能得到的求解性能^［19］；Wang等^［36］提出的模型（原文未命名，本文称之为W-M模型）在带回程的VRP问题（VRP with Backhauls）的多个规模上的测试结果均优于AM模型。基于Pytorch深度学习框架构建DRRAM模型、AM模型和W-M模型，其模型训练和测试在以 Intel Xeon Platinum 8260为 CPU和以NVIDIA RTX A6000为GPU的计算环境上进行。

表1展示了DRRAM模型和4个对比算法在4组不同问题规模（不同的客户数n）的测试集上的性能比较结果。对于DRRAM模型和AM模型，由于使用第2.4节中描述的greedy或sample策略来构造解方案会导致不同的寻优性能，本文分别呈现两个策略下所对应的实验结果。

“DRRAM（sample）”和“DRRAM（greedy）”表示训练得到的DRRAM模型在测试过程中分别使用sample策略和greedy策略构造解方案。另外，采用sample策略时，会将测试集中的每个问题实例复制320次，再作为模型的输入，为每个问题实例生成320个解，并从中选择目标值最优的解作为该算例的最终解。值得注意的是，DRRAM模型在使用sample策略时，增大每个问题实例的复制次数，可能会导致更好的寻优性能，但是计算时间也随之会增加^［19］。

给定特定客户数（n）下的测试集，表1展示了各个不同方法所产生的性能值，包括针对所有测试例的平均目标值（Average Objective Valve， AOV）、性能提升率（Performance Improvement Rate， PIR）与计算时间（CPU Time， CPU）。本节中PIR定义为各算法的平均目标值相对于GmiraTS的平均目标值的相对差异。此外，由于实验中设定深度强化学习模型测试数据的输入批量数（即同时输入待求解的问题实例数）是1000，计算时间列显示求解1000个问题实例所需的平均时间。由于表格宽度的限制，且训练过程是一次性过程，其不对求解计算时间产生大的影响，类似于文献［19］中的结果展示方式，本文不展示训练过程所需时间而仅展示测试过程的计算时间。

从表1可以看出，DRRAM模型的性能明显优于几个基准算法。具体表现如下。1） 相较AM模型，DRRAM模型性能提升率有1.3%~2.3%。这表明本文提出的两个注意力机制有助于提高AM模型对时变速度型VRP问题的寻优性能。2） 与GmiraTS相比，采用greedy策略的DRRAM模型可以使用少2~3个数量级倍数的计算时间（约\mathrm{1}/\mathrm{1500}~\mathrm{1}/\mathrm{400}）生成更优的解（在n=\mathrm{30}时除外）。而采用sample策略的DRRAM模型，虽然计算时间相较采用greedy策略显著增加，但相较于GmiraTS可以获得更大（2.8%~9.6%）的性能提升，且求解时间仍比GmiraTS更短。3） 与W-M模型相比，采用greedy策略的DRRAM模型可以使用少2~3个数量级倍数的计算时间（约\mathrm{1}/\mathrm{70}~\mathrm{1}/\mathrm{18}）并生成更优（0.3%~4.6%）的解，采用sample策略的DRRAM模型计算时间更长但可以获得更大（4.2%~7.8%）的性能提升。4） 随着客户节点数量的增加，这两种策略都会导致模型搜索能力的不断提高，但计算时间的优势会降低。5） 与计算速度最快的贪婪算法相比，采用greedy策略DRRAM模型的计算时间与其相当，但其性能有着高达15.3%~17.7%的显著优势。

类似于上述实验过程，本文还在不同的时间周期（包括4 min、6 min和8 min/周期）下，进一步对比了所提出的DRRAM模型与其他基准算法的性能差异，对比结果与上述结论类似，再次验证了DRRAM模型的有效性和性能优势。

3.4 消融实验

DRRAM模型是在AM模型的基础上，引入降维注意力机制和残差注意力机制而构建的，这两个机制使得DRRAM模型在求解所研究问题上的性能优于AM模型。为了评估降维注意力机制和残差注意力机制对DRRAM模型性能提升的贡献，在客户数为50的问题规模下进行了消融实验，即测试AM模型，仅使用降维注意力的AM模型，与同时使用降维注意力机制与残差注意力机制的AM模型（即DRRAM模型）三者在测试集上的求解速度与性能，相关实验结果如表2和图4所示。

表2各列与表1类似，展示了平均目标值，各算法相对于AM模型的平均性能提升率以及计算1000个问题实例所需的计算时间。AM+DR（greedy）表示仅使用降维注意力机制以及greedy策略求解的AM模型。PIR定义为使用greedy策略或sample策略下，各算法的平均目标值相对于AM模型的平均目标值的相对差异。图4表示了在客户数为50时，AM模型、AM+DR模型和DRRAM模型在训练过程中的收敛趋势图，即在验证集上的平均目标值的变化曲线图。根据图4可发现，降维注意力机制对模型效果提升有较大贡献。在训练12个回合后，DRRAM模型在验证集上的表现一直优于AM+DR模型，说明残差注意力机制可以加速模型收敛，从而有助于模型性能提升。从表2发现，降维注意力机制和残差注意力机制都可以提升AM模型在测试集上的寻优能力。在采用greedy与sample策略的AM模型上，使用降维注意力机制分别可以导致1.5%与1.2%的模型性能提升，同时使用两种机制分别导致模型性能提升1.9%与1.6%。综上，降维注意力机制和残差注意力机制都有助于提高DRRAM模型的寻优能力。

3.5 泛化性能

在第3.3节中，对于客户数量为n的问题实例，采用在相同客户数的训练集下训练好的DRRAM模型求解。而对于深度神经网络模型而言，通常有一定的泛化性能，本节将进一步探究DRRAM模型的泛化性能，即在客户数量为n的问题上训练好的DRRAM模型是否可以推广到解决其他客户数量的问题上。具体而言，给定一个客户数为n的问题，我们针对该问题分别训练了AM模型和DRRAM模型，然后评估这两个模型在客户数为\beta \cdot n（\beta \cdot n别取值为30、50、80、100、150、200、250）的问题上的性能，并将其与GmiraTS模型的性能进行比较。实验结果如表3所示，表3中各行展示的是针对特定规模的问题训练得到的模型使用greedy策略对其他规模问题求解的性能（平均目标值）。例如，“DRRAM， 30”那行中的值225.3表示，针对30个客户数的问题训练得到的DRRAM模型，在使用greedy策略求解50个客户的问题例时，其得到的评价目标值是225.3。从表3中可以得到如下结果。

1） 当训练问题实例中的客户数与测试集中的客户数差异在一定范围内（\mathrm{1}/\mathrm{2}\lesssim \beta \lesssim \mathrm{5}）时，DRRAM模型有更好的泛化性能。在针对7个测试集的方法对比中，DRRAM模型在24个实验结果（总共28个结果）中优于AM模型。例如，“DRRAM，50”在求解客户数为50~250的问题实例时，性能均优于GmiraTS，有1.1%~5.5%的性能提升。

2） 在28个结果中，DRRAM模型有4个结果不如AM模型。原因可能在于，DRRAM模型相较于AM模型引入了更多参数。这虽然显著提升了模型的准确性，但也伴随着泛化能力的一定损失。具体而言，增加的参数量增强了模型对特定节点数据内在规律的拟合能力，但也使其过度依赖于当前的数据分布，从而降低了模型在面对差异化数据分布时的适应性。因此在泛化实验中，当客户数发生极端变化（即\beta \le \mathrm{1}/\mathrm{3}或\beta \ge \mathrm{5}时）时，模型机制无法完全适应，导致模型性能相对下降。

3） 在求解客户数为30的问题时，DRRAM模型和AM模型性能都不如GmiraTS，原因之一为两种模型都采用的greedy策略求解。采用sample策略可得到更好的性能，如表1所示。

4 结论

为了考虑真实道路网络中行驶速度频繁变化的特征，本文提出了时变速度型VRP问题，并提出新颖的降维残差注意力模型（DRRAM）有效求解该问题。该模型提出了以一种新的输入构造方式，将节点间的行驶时间信息与节点位置和需求信息相结合，构造模型输入。提出和引入了降维注意力机制与残差注意力机制，对AM模型的编码器进行改进，通过改进的编码器提取节点的位置信息、需求信息和行驶时间信息，提高了节点嵌入的表征能力，从而得到更好的性能。基于真实的路网和行驶速度数据集，我们进行了广泛的数值实验来评估DRRAM模型的性能。结果表明对于处理时变速度型VRP问题，DRRAM模型的性能明显优于AM模型、WM模型和GmiraTS这3种高效的模型（算法）和一种经典的启发式算法——贪婪算法。实验结果还表明，所提出的两种机制均有助于提高AM模型的寻优能力，且所提出的DRRAM模型具有优于AM模型的良好泛化能力。

尽管本文基于成都市区时变速度网络进行了广泛的实验验证，但路网结构的单一性可能使模型学习到的规律具有一定地域特异性。未来的研究可以进一步评估本文模型在不同道路网络上的求解性能，以提高结论的普适性。未来的研究可进一步评估本文模型在不同道路网络上的求解时变型VRP问题以及考虑路网时变速度特征的其他VRP问题变体的性能，如考虑同时取送货^［24］和带时间窗^［30-31］等问题特征的时变速度型VRP问题。

参考文献

[1] Liu Y， Yu Y， Zhang Y， et al. Branch-cut-and-price for the time-dependent green vehicle routing problem with time windows［J］. Inf J Comput， 2023， 35（1）： 14-30.

[2] Castellucci P B， Darvish M， Coelho L C. A Benders decomposition algorithm for the time-dependent vehicle routing problem［M］. Montreal：Bureau de Montreal， Université de Montreal， 2021.

[3] Vidal T， Martinelli R， Pham T A， et al. Arc routing with time-dependent travel times and paths［J］.Transp Sci 2021， 55（3）： 706-724.

[4] Wölck M， Meisel S. Branch-and-price approaches for real-time vehicle routing with picking， loading， and soft time windows［J］. Informs J Comput，2022， 34（4）： 2192-2211.

[5] Zhang X， Chen L， Gendreau M， et al. Learning-based branch-and-price algorithms for the vehicle routing problem with time windows and two-dimensional loading constraints［J］. Informs J Comput， 2022， 34（3）： 1419-1436.

[6] Lenstra J K， Kan A H G R. Complexity of vehicle routing and scheduling problems［J］. Networks， 1981， 11（2）： 221-227.

[7] Zhang M T， Zhang J， He C F. A review of metaheuristic algorithms research［J］. Computer Engineering and Applications，2026，62（2）： 40-53.

[8] 张梦婷， 张军， 何承烽.元启发式算法研究综述［J］.计算机工程与应用， 2026， 62（2）： 40-53.

[9] Ge X L， Zhang H. Study on the optimization of vehicle routing problem in urban real time traffic network ［J］. Industrial Engineering and Management， 2018，23（3）：140-149+156.

[10] 葛显龙，张慧.城市实时交通路网车辆路径优化问题研究［J］.工业工程与管理，2018，23（3）：140-149+156.

[11] Wu Y， Ma Z J. Time-dependent production-delivery problem with time windows for perishable foods［J］. Systems Engineering-Theory & Practice， 2017， 37（1）： 172-181.

[12] 吴瑶，马祖军.时变路网下带时间窗的易腐食品生产-配送问题［J］.系统工程理论与实践，2017，37（1）：172-181.

[13] Zhang J T， Ding Y. Simulated annealing with variable neighborhood for time-dependent vehicle routing problem with time window［J］. Operations Research and Management Science， 2019， 28： 77-84.

[14] 张建同，丁烨.变邻域模拟退火算法求解速度时变的VRPTW问题［J］.运筹与管理，2019，28：77-84.

[15] Gmira M， Gendreau M， Lodi A， et al. Tabu search for the time-dependent vehicle routing problem with time windows on a road network［J］. Eur J Oper Res， 2021， 288（1）： 129-140.

[16] Zhang X Y， Jin P， Hu X X， et al. Research on the time-dependent multi-depot open vehicle routing problem with time windows［J］. Chinese Journal of Management Science， 2024， 32（1）： 146-157.

[17] 张歆悦， 靳鹏， 胡笑旋， 等. 时间依赖型多配送中心带时间窗的开放式车辆路径问题研究［J］. 中国管理科学， 2024， 32（1）： 146-157.

[18] Chen S J， Luo W， Wu H W， et al. Time-dependent vehicle routing optimization strategy for simultaneous pickup and delivery［J］. Journal of Chongqing Jiaotong University （Natural Science Edition）， 2025，44（6）： 82-96.

[19] 陈仕军，骆维，吴华伟，等.时间依赖型同时取送货车辆路径优化策略［J］.重庆交通大学学报（自然科学版）， 2025， 44（6）： 82-96.

[20] Fan L. A two-stage hybrid ant colony algorithm for multi-depot half-open time-dependent electric vehicle routing problem［J］. Complex Intell Syst， 2024， 10（2）： 2107-2128.

[21] Vinyals O， Fortunato M， Jaitly N. Pointer Net works［C］//29th Conference on Neural Information Processing Systems， 2015：2692-2700.

[22] Bello I， Pham H， Le Q V.Neural combinatorial optimization with reinforcement learning［C］//5th International Conference on Learning Representations， 2017： 1-13

[23] Williams R J. Simple statistical gradient-following algorithms for connectionist reinforcement learning［J］. Mach Learn， 1992， 8（3）： 229-256.

[24] Nazari M， Oroojlooy A， Snyder L， et al. Reinforcement learning for solving the vehicle routing problem ［C］//32nd Conference on Neural Information Processing Systems， 2018： 9861-9871.

[25] Kool W， van Hoof H， Welling M. Attention， learn to solve routing problems！［C］//7th International Conference on Learning Representations， 2019： 1-12.

[26] Vaswani A， Shazeer N， Parmar N， et al. Attention is all you need［C］//31st Advances in Neural Information Processing Systems， 2017： 5998-6008.

[27] Helsgaun K. An extension of the lin-Kernighan-helsgaun TSP solver for constrained traveling salesman and vehicle routing problems［R］. Roskilde： Roskilde Universitet， 2017.

[28] Li J， Wu G， Fan M， et al. Heterogeneous attention-based graph convolutional network for solving asymmetric pickup and delivery problem［J］. IEEE Trans Autom Sci Engin， 2025.

[29] Li J， Xin L， Cao Z， et al. Heterogeneous attentions for solving pickup and delivery problem via deep reinforcement learning［J］. IEEE Trans Intell Transport Syst， 2021， 23（3）： 2306-2315.

[30] Li X， Luo W， Yuan M， et al. Learning to optimize industry-scale dynamic pickup and delivery problems ［C］//2021 IEEE 37th International Conference on Data Engineering （ICDE）， 2021： 2511-2522.

[31] He M L， Yang M， Wu X H. Vehicle routing problem with simultaneous pickup-delivery and soft time windows from low-carbon perspective［J］. Journal of Jiangsu University（Natural Science Edition）， 2026， 47： 283-291.

[32] 何美玲， 杨梅， 武晓晖. 低碳视角下带软时间窗的同时取送货车辆路径问题研究［J］. 江苏大学学报（自然科学版）， 2026， 47： 283-291.

[33] Wang W L， Chen H L， Li G Q， et al. Deep reinforcement learning for multi-depot vehicle routing problem［J］. Control and Decision， 2022，37（8）：2101-2109.

[34] 王万良，陈浩立，李国庆，等.基于深度强化学习的多配送中心车辆路径规划［J］.控制与决策，2022，37（8）：2101-2109.

[35] Lei K， Guo P， Wang Q X， et al. End-to-end deep reinforcement learning framework for multi-depot vehicle routing problem［J］. Application Research of Computers，2022，39（10）：3013-3019.

[36] 雷坤，郭鹏，王祺欣，等.基于end-to-end深度强化学习的多车场车辆路径优化［J］.计算机应用研究，2022，39（10）：3013-3019.

[37] Xu Y， Fang M， Chen L， et al. Deep reinforcement learning for solving the heterogeneous capacitated vehicle routing problem［J］. IEEE Trans Cybern， 2022， 52（12）： 13572-13585.

[38] Li J， Dai B， Niu Y， et al. Multi-type attention for solving multi-depot vehicle routing problems［J］. IEEE Trans Intell Transport Syst， 2024， 25（11）： 17831-17840.

[39] Lin B， Ghaddar B， Nathwani J. Deep reinforcement learning for the electric vehicle routing problem with time windows［J］. IEEE Trans Intell Transport Syst， 2022， 23（8）： 11528-11538.

[40] He R， Ravula A， Kanagal B， et al. Realformer： Transformer likes residual attention［C］//Findings of the Association for Computational Linguistics： ACL-IJCNLP 2021， 2021： 929-943.

[41] Kinga D， Adam J B. A method for stochastic optimization［C］//Int Conf Learn Represent （ICLR）. 2015.

[42] Zhang D， WallaceS W， GuoZ， et al. On scenario construction for stochastic shortest path problems in real road networks［J］. Transp Res Part E Logist Transp Rev， 2021， 152： 102410.

[43] Guo F， Zhang D， Dong Y， et al. Urban link travel speed dataset from a megacity road network［J］. Sci Data， 2019， 6： 61.

[44] Huang Y， Zhao L， Van Woensel T， et al. Time-dependent vehicle routing problem with path flexibility［J］. Transp Res Part B Methodol， 2017， 95： 169-195.

[45] Wang C， Cao Z， Wu Y， et al. Deep reinforcement learning for solving vehicle routing problems with backhauls［J］. IEEE Neur Net Lear Syst， 2025， 36（3）： 4779-4793.

[46] Ben Ticha H， Absi N， Feillet D， et al. Empirical analysis for the VRPTW with a multigraph representation for the road network［J］. Comput Oper Res， 2017， 88： 103-116.

基金资助

国家自然科学基金面上项目(72171159)