深度混合型邻域搜索模型求解CVRP问题

图1 模型架构及求解思路

Fig.1 Model architecture and solution ideas

2.2.1　破坏算子和修复算子

破坏算子 $O^{D}$ 主要通过随机破坏、点的破坏、路线的破坏对初始解进行破坏，其中随机破坏是随机破坏当前解的节点或边，基于点的破坏是删除最接近随机选择的节点，基于路线的破坏是删除最接近随机选择的节点的路线.如果一个节点 $v_{j}$ 从一条路 $\{v_{i}, \dots, v_{j}, \dots, v_{k}\}$ 移除，得到三条不完整的路.部分解 $\{v_{i}, \dots, v_{j - 1}\}$ 包含 $v_{j}$ 之前的所有节点，部分解 $\{v_{j}\}$ 只包含节点 $v_{j}$ ，部分解 $\{v_{j + 1}, \dots, v_{k}\}$ 包含 $v_{j}$ 之后的所有节点.图2仅显示在邻域中破坏和修复一个解决方案的过程，但是在整个邻域中还有许多其他可能的修复解决方案.

图2

图2 破坏算子和修复算子的操作过程

Fig.2 Operation process of destroying operator and repairing operator

修复算子 $O^{R}$ 主要通过DRL在智能体与环境之间的交互作用中学习修复的策略，如图2所示.破坏算子 $O^{D}$ 通过随机的破坏方法将初始解破

坏为七段不完整路径 $\{(x_{2}, x_{3}), (x_{0}, x_{4}), (x_{0}, x_{16}),$

$(x_{5}, x_{6}), (x_{7}, x_{8}), (x_{10}, x_{11}), (x_{14}, x_{15})\}$ 和四个独立的客户节点 $\{x_{1}, x_{9}, x_{12}, x_{13}\}$ .模型为被破坏的解的末端添加特征向量 $x_{i}$ ，并将不完整路径的末端特征向量作为输入，通过DRL模型计算不完整路径末端节点的相关性，自动学习路径的修复策略.为了防止不完整的路径选择其末端节点或产生不可行的解决方案（例如路线负载超过车辆容量限制），通过添加掩码来禁止该操作.

2.3　编码器结构

模型采用PN和Transformer混合编码，结合两者的优势增强数据特征.如图3所示，DHNS模型的编码器由PN，MHA，AOA，前馈层和归一化组成.首先，编码器将输入序列映射为高维向量，然后利用DPE提取节点的特征向量 $a = [a_{1}, a_{2}, \dots, a_{n}], a_{i} \in ℝ^{d}$ ， $n$ 为客户数目， $d$ 为特征向量的维数.MHA进一步促进网络提取深层次的特征信息，AOA则是减少在解码阶段进行错误解码的可能性.因此，特征向量不再是直接传到解码器，而是通过AOA和MHA来更加精确地表示节点特征向量 $a_{i}$ .编码部分可表示为：

A^{i} = s o f t m a x (\frac{Q^{l} K^{l}}{\sqrt[]{d}}) V^{l}

（7）

M H A (Q^{l}, K^{l}, V^{l}) = C o n c a t (A^{1}, A^{2}, \dots, A^{H}) W_{o}

（8）

其中， $W_{o}$ 是训练参数， $Q^{l}, K^{l}$ 和 $V^{l}$ 分别是自注意力机制的查询向量、键向量和值向量.

图3

图3 DHNS模型总架构

Fig.3 DHNS model master architecture

当反向传播梯度累积时，模型需要随时了解动态元素的信息变化，因此使用AM和cos⁃AM^［18］提供双隐层信息，分别表征动态信息和静态信息.用元组 $(X_{t}, f_{t})$ 表示不完整解在 $t$ 时刻的状态，对于输入 $x_{t} \in X_{t}$ ，包含上述过程在时间步长 $t$ 时产生的嵌入 $h_{i}$ 和 $h_{i}^{'}$ ， $h_{i}$ 和 $h_{i}^{'}$ 通过 $E m b_{c}$ 和注意层转换计算得到， $f_{t}$ 表示相关嵌入， $E m b_{f}$ 使用与 $E m b_{c}$ 相同的结构不同的参数，通过 $E m b_{f}$ 和注意层生成嵌入 $h_{f}$ 和 $h_{f}^{'}$ .所有节点信息嵌入都被注意层AM和cos⁃AM用来计算上下文向量 $c$ 来表示所有相关嵌入.上下文向量 $c$ 计算如下：

h_{i}^{'} = (d_{t} \times c o s (\frac{π i}{2 s_{t}})) + (d_{t} \times s i n (\frac{π i}{2 s_{t}}))

（9）

h_{f}^{'} = (h_{f} \times c o s (\frac{π i}{2 s_{t}})) + (h_{f} \times s i n (\frac{π i}{2 s_{t}}))

（10）

u_{i}^{H} = V^{A} t a n h (W^{A} [h_{i} + h_{i}^{'}, h_{f} + h_{f}^{'}])

（11）

c = \sum_{i = 0}^{n} s o f t m a x (u_{0}^{H}, u_{1}^{H}, \dots, u_{n}^{H}) [h_{i} + h_{i}^{'}]

（12）

其中， $[\cdot, \cdot]$ 表示两向量的串联， $V^{A}$ ， $W^{A}$ 是可训练的参数矩阵.

AOA主要生成两个信息，即信息向量 $I$ 和注意力门 $G$ ，然后对AOA使用逐元素乘法将注意力门 $G$ 应用到信息向量 $I$ 来添加另一个注意力机制，AOA可以应用于各种注意力机制.对于传统的单头注意力机制，AOA有助于确定注意结果与查询之间的相关性.对于MHA，AOA有助于在不同注意力头之间建立关系，过滤所有注意力结果并仅保留有用的注意力.对于编码器，AOA机制将自我注意应用于向量以对节点之间的关系进行建模，进而确定不同向量之间的关系.对于解码器，应用AOA过滤掉不相关或误导性的注意结果，并仅保留有用的结果.

2.3.1　MHA

MHA首先计算了 $Q$ ， $K$ 的注意分布，并将其附加到 $V$ 上，此步骤准确地捕获输入序列的特征信息.然后计算 $Q$ 和 $V$ 的相似度并归一化，根据相似度和相应的 $V$ 值加权和获得最终的注意值，此步骤通过在全局特征中分配不同的权重给不同的特征向量以提取局部特征，同时生成包括全局和局部特征在内的联合特征向量序列.根据Huang et al^［7］研究使用缩放点积方法计算MHA中的权重可以有效地解决梯度消失问题，因此使用如下表达式来计算权重向量：

l_{i, j} = f_{s i m} (q_{i}, k_{j}), \bar{l_{i, j}} = \frac{e^{l_{i, j}}}{\sum_{j} e^{l_{i, j}}}

（13）

H_{i} = \sum_{j} \bar{l_{i, j}} v_{j}

（14）

其中， $q_{i}$ 属于 $Q$ 的第 $i$ 个查询向量， $k_{j}$ 和 $v_{j}$ 分别属于 $K$ ， $V$ 的第 $j$ 个键向量和值向量， $f_{s i m}$ 是用来计算 $k_{j}$ 和 $q_{i}$ 相似分数的函数， $H_{i}$ 表示 $q_{i}$ 和 $k_{j}$ 的相似性.

2.3.2　AOA

模型对AM有着全局依赖性，因为输出的结果取决于AM的权重分配，但解码器对注意力分配的合理性或者与查询向量的相关程度一无所知.先前模型的AM通过对每个时间步生成的特征向量做加权平均值来指导解码过程.传统的AM不管 $Q$ ， $K$ 或 $V$ 是否相关，都会为 $Q$ 生成一组归一化的权重，通过给出与任务相关的查询向量 $q$ 的过程，通过缩放点积方法计算 $Q$ ， $K$ 的注意分布，并将其附加到值向量 $V$ 上，从而得到注意值.若二者不相关，会输出误导或错误的信息.最后的注意力结果可能不是解码器期望得到的，而是注意力分配造成的，将导致解码器被误导输出错误的结果.

为了避免上述误导性信息，使用AOA模块衡量注意力结果和查询之间的相关性，来解决这种不合理的现象.AOA通过MHA中的 $Q$ ， $K$ 和 $V$ 获得的权重结果执行两个独立的线性变换来生成信息向量 $I$ 和注意力门 $G$ ，同时利用逐元素乘法聚合信息向量 $I$ 和注意力门 $G$ 以预防不合理的现象，从而提高解码器的准确性.MHA寻找节点间的潜在联系，AOA测量它们之间的关联程度，更新特征向量.AOA首先使用得到的注意结果和当前上下文向量 $c$ 生成信息向量 $I$ 和注意力门 $G$ ，信息向量 $I$ 是当前上下文向量和注意力结果 $\hat{v}$ 通过线性变换得到并存储，注意力门 $G$ 是当前上下文向量 $c$ 与注意力结果 $\hat{v}$ 通过另一个线性变换得到的.

I = W_{q}^{i} c + W_{v}^{i} \hat{v} + b^{i},

（15）

G = s i g m o i d (W_{q}^{g} c + W_{v}^{g} \hat{v} + b^{g})

（16）

其中， $W_{q}^{i}, W_{v}^{i} 和 b^{i}, W_{q}^{g}, W_{v}^{g} 和 b^{g}$ 分别表示信息向量 $I$ 和注意力门 $G$ 的参数矩阵， $W_{q}^{i}, W_{v}^{i},$ $W_{q}^{g},$

W_{v}^{g} \in R^{D \times D}

AOA机制通过注意力门 $G$ 对信息向量 $I$ 添加另一个注意力，应用逐元素乘法得到最终的信息向量，AOA可建模表示为：

\begin{array}{l} A o A (f_{a t t}, Q, K, V) = s i g m o i d (W_{q}^{g} Q + W_{v}^{g} f_{a t t} + b^{g}) ⊙ \\ (W_{q}^{i} Q + W_{v}^{i} f_{a t t} + b^{i}) \end{array}

(17)

其中， $f_{a t t}$ 是注意力模块， $⊙$ 表示逐元素乘法.

2.4　解码器结构

解码器的输入是编码器中所有节点的隐藏层信息 $e_{g r a p h}$ 、最后时间的节点嵌入 $e_{l a s t}$ 以及车辆在当前时间 $t$ 的容量状态和位置 $l_{t}$ ，给定输入，解码器采用批次搜索采样策略，为了防止生成不合理的路线（例如总路线负载超过车的容量或者重复访问一个客户），设置一个掩码向量来标记已访问的客户节点，确保每个节点在旅行路线中只出现一次，同时节点在下一个时间步长的权重设置为负无穷大.上下文向量 $C_{t}$ 在任意时刻 $t$ 的表达式如下：

C_{t} = \{\begin{array}{l} f_{c o n c a t} [e_{g r a p h}, l_{t}, e_{l a s t}], t \geq 1 \\ f_{c o n c a t} [e_{g r a p h}, l_{0}, e_{l a s t}], t = 1 \end{array}

（18）

其中， $f_{c o n c a t}$ 是隐藏层的级联函数，在MHA中使用获得的上下文向量来获得权重向量.

AOA计算解码器中时间 $t$ 的所有节点的上下文向量 $C_{t}$ 和隐藏层向量之间的权重，然后将计算出的权重转换为上下文向量并发送到自我注意层.单个输出向量 $q$ 使用嵌入 $h_{0} + h_{0}^{'}, \dots, h_{n} + h_{n}^{'}$ 计算所有动作的输出分布，如下所示：

\bar{C_{t}} = A o A (M H A (C_{t}, e_{t}, m a s k))

（19）

q = F F ({\bar{C}}_{t}) + F F (h_{f} + h_{f}^{'})

（20）

P_{θ} (a_{t}| π_{t}) = σ (V^{B} t a n h (h_{i} + h_{i}^{'} + q))

（21）

其中， $e_{t}$ 表示时刻 $t$ 的节点隐藏层，mask是标记已访问节点的掩码向量， $V^{B}$ 是可训练的参数.

3 训练与推理方法

3.1　模型训练算法

在训练阶段，需要花费大量时间来训练网络参数，但当模型训练完成后，可以在测试阶段快速获得预测结果.首先，通过贪婪算法为DHNS模型提供初始解，DRL中智能体根据当前环境状态（车的容量或顾客总需求）作出适当的决策，结合奖励机制不断调整参数，直至模型可以修复得到完整解.

模型基于损失函数 $L$ 来衡量模型操作的有效性，同时使用AC算法对策略参数进行训练，并利用此算法计算梯度来最大化预期奖励 $J$ ：

J (θ |π_{0}) = E_{π_{t} - p θ (.| π_{0})} L (π_{t}| s)

（22）

\begin{array}{l} \nabla J (θ |π_{0}) = \\ E_{π_{t} - p θ (.| π_{0})} [(L (π_{0}, π_{t}) - b (π_{0})) \nabla l g p_{θ} (π_{t}| s)] \end{array}

（23）

其中， $π_{0}$ 为破坏后的解， $π_{t}$ 是智能体执行动作 $a_{1}, a_{2}, a_{3}, \dots, a_{t - 1}$ 之后修复的解，基线 $b (π_{0})$ 可以有效地减少方差.

模型采用AC算法进行训练，通过随机策略学习行为网络的参数，行为网络基于概率分布做动作，评判网络基于行为网络生成的行为评判得分，行为网络再根据评判网络的评分调整行为选择的概率.解决VRP问题的传统策略梯度算法的主要缺点是高维离散空间中不同路径之间的方差大，训练不稳定，但AC算法可以单步更新，不需要完成整个动作再更新网络参数.传统策略梯度方法对价值的估计虽然是无偏的，但方差较大，AC算法能够有效降低方差.为了保证策略梯度方差的稳定性，类似于Nazari et al^［10］，本文使用评判网络为修复解 $π_{0}$ 生成一个值 $c_{0}$ 作为评判网络估算修复的成本，评判网络根据行为网络状态预测奖励值 $b (π_{0})$ ，并以预测奖励值 $b (π_{0})$ 和实际奖励值 $L (π_{0}, π_{t})$ 之间的均值误差作为优化目标.

3.2　模型推理算法

基于DRL策略，为了提高解的精确性，有时仍需要结合传统优化算法（例如波束搜索、采样）进一步提高解的质量.在推理阶段采用批次搜索算法进一步提升解的质量.首先模型采样 $n$ 条不同的路径作为起始节点，使用贪婪启发式方法为每个轨迹创建初始解，在构建步骤中，所有解决方案都使用成对的破坏和修复运算符进行破坏和修复，最后是为每个解决方案创建一个相邻的解决方案.整个搜索直到达到整个批次的终止标准.

4 数值实验

所有实验均基于Pytorch 1.9.0深度学习平台，Windows 11操作系统，使用单张Nvidia RTX 3050 GPU和i5⁃11300H CPU运行本文模型和其他DRL模型.实验中节点的坐标在 $[0,1] \times [0,1]$ 单位平方形中生成，分别在CVRP20，CVRP50和CVRP100上进行训练和测试，车辆的容量限制分别设置为 $D = 30,40,50$ .DHNS模型在8 G显存下运行（100回合）20，50，100节点的训练时间分别为11，40和160 h.最优间隙以LKH3为基准，其他结果均来自于原文献.聚合函数使用单层的全连接神经网络，批次大小为256，MHA中的头部 $H = 8$ ，前馈输入层和输出层的维度都是512维，Adam优化器的学习率为0.0001，权重衰减率为0.95，隐含层设置为128维.

4.1　CVRP的实验方案及其模型性能对比实验

表1显示了DHNS模型求解的CVRP性能与以前的关键工作进行比较，例如NeuRewriter^［19］，NLNS^［17］，AM^［5］，POMO^［13］，DACT^［16］，MDAM^［20］，DPDP^［21］和其他启发式方法.由表1可知，DHNS模型在推理阶段快于传统算法（LKH3和CW）以及NLNS，RL（BS），DACT等模型，优化效果超越目前基于DRL的模型和专业求解器OR⁃Tools.与DGTM比较，DHNS模型的精度较高，但计算推理时间比DGTM长，这是由于DGTM模型属于构造解的模型，模型推理时间较短，而本文模型是改善解的模型，结合传统启发式算法进行搜索，导致推理时间较长，但是解的精度得到保证.进一步分析，模型在CVRP20，CVRP50和CVRP100的间隙明显优于目前基于DRL的方法，与DGTM相比，CVRP20，CVRP50和CVRP100的最优间隙分别由原来的0.13%，0.15%和0.19%降低到0.06%，0.09%和0.12%，超越目前基于DRL的方法.DRL有希望设计出比启发式规则更好的策略，打破人为设定的限制，智能体自主探索解空间中的最优解.DRL充分利用同类型问题之间的相似特征，避免传统算法不断重复求解的过程和数据资源的浪费.

表1 DHNS模型在CVRP问题上的优化结果比较

Table1 Comparison of CVRP optimization results of DHNS model

模型	CVRP20			CVRP50			CVRP100
模型	Obj	Gap	Time	Obj	Gap	Time	Obj	Gap	Time
Random CW	6.81	11.64%	-	12.25	18.07%	-	18.96	21.18%	-
LKH3	6.12	0.00%	2 h	10.38	0.00%	7 h	15.65	0.00%	13 h
ALNS	6.69	9.31%	1 s	11.24	8.28%	2 s	17.33	10.7%	5 s
OR⁃Tools^*	6.42	4.84%	2 min	11.22	8.12%	12 min	17.14	9.34%	1 h
RL(BS)^*	6.40	4.39%	27 min	11.15	7.46%	39 min	16.96	8.39%	74 min
AM (sampling)^*	6.25	1.91%	6 min	10.62	2.40%	28 min	16.23	3.72%	2 h
AM⁃D (greedy)^*	6.28	2.95%	$≪$ 1 s	10.78	3.85%	$≪$ 1 s	16.40	4.79%	$≪$ 1 s
NeuRewriter^*	6.16	0.48%	22 min	10.51	1.25%	35 min	16.10	2.88%	66 min
POMO	6.35	3.42%	$≪$ 1 s	10.74	3.52%	1 s	16.15	3.00%	3 s
NLNS	6.14	0.61%	1 h	10.55	1.65%	2 h	16.11	2.99%	3 h
DACT	6.13	0.24%	11 min	10.39	0.18%	32 min	15.71	0.38%	1.5 h
MDAM(BS)	6.14	0.26%	3 min	10.50	1.18%	9 min	16.03	2.49%	31 min
DPDP^*	-	-	-	-	-	-	15.69	0.26%	6 h
DGTM	6.13	0.13%	2 s	10.39	0.15%	5 s	15.68	0.19%	20 s
DHNS	6.12	0.06%	3 min	10.39	0.09%	9 min	15.67	0.12%	20 min

注：带有“∗”的结果是从其他作品中发布的，粗体是基于DRL的最佳方法，花费精确到 $10 - 3$

新窗口打开| 下载CSV

DHNS模型的关键是AOA在编码和解码阶段发挥着重要的作用，DPE提取了更多的隐藏和动态的节点结构信息以及贪婪算法提供了较好的初始解.DRL模型能够自适应地为不同的修复算子分配相应的权重，加速产生更好的解方案.对比ALNS算法，DRL能够进一步减少启发式信息的指导和时间成本，能极大地提高算法在解空间的搜索范围.DRL根据算子的历史表现与使用次数自动选择下一次迭代使用的算子，通过算子间在RL环境中的相互竞争来生成当前解的邻域结构，这种结构很大概率能够找到更好的解.实验结果表明，与ALNS结合的DRL以及AOA调整后的模型优化性能很好.

4.2　泛化性能及收敛性分析

考虑到问题实例会根据模型所作的决策而改变，节点特征也会发生变化，使用AC算法训练模型的策略有利于网络学习特征.DHNS模型对求解CVRP的泛化能力比较如图4所示.图5和图6展示了模型在20节点和50节点的收敛性.结果表明对于固定的问题大小，DHNS模型可以很好地推广和解决任何类似规模的问题.更重要的是，尽管CVRP20需要10 h的训练，但训练过程仅需一次，并且在推理阶段仅需花费2 min就可以获得高质量的解决方案，不需要针对不同的问题实例进行再次训练.DHNS模型具有较好的泛化性能的原因在于DHNS是基于改善初始解的方式不断提高解，通过ALNS扩大解的搜索范围，寻求高质量的解决方案，并且通过AOA防止信息在传输过程中出现误导性信息，更加精确地进行信息传递，进一步提高解的质量.

图4

图4 CVRP泛化性能的比较

Fig.4 Comparison of CVRP generalization performance

图5

图5 CVRP20模型收敛图

Fig.5 Diagram of CVRP20 model convergence

图6

图6 CVRP50模型收敛图

Fig.6 Diagram of CVRP50 model convergence

4.3　真实数据集实例测试

本文成功地将DHNS模型从训练模型推广到现实世界的数据集.表2是真实数据集CVRPlib上的22个实例的实验结果，表中黑体字表示结果最优.由表可见，平均差距进一步缩小到2.89%，证明其差距优于AM，POMO，Wu et al，DACT和OR⁃Tools.在混合随机和群集类型以及大多数随机类型的实例上，DHNS的性能也优于其他基准.鉴于其优势，DHNS在各种大小和分布的CVRPlib基准实例上的泛化性能方面优于现有的基于DRL的模型.

表2 模型在CVRPlib基准数据集上的实验结果

Table 2 Experimental results of the model on the CVRPlib benchmark dataset

实例	最优	OR⁃Tools	AM	Wu et al	NLNS	POMO	DACT	DHNS
平均间隙	0.00%	8.06%	31.62%	14.27%	11.67%	6.10%	3.41%	3.07%
X⁃n101⁃k25	27591	29405	37702	29716	29845	28595	27996	27999
X⁃n106⁃k14	26362	27343	28473	27642	27688	26850	26855	26809
X⁃n110⁃k13	14791	16149	15443	15927	15247	15094	14810	14099
X⁃n115⁃k10	12747	13320	13745	14445	14256	13191	12961	12875
X⁃n120⁃k6	13332	14242	13937	15486	13986	13615	13649	13602
X⁃n125⁃k30	55539	58665	75067	60423	57896	59504	58560	56912
X⁃n129⁃k18	28940	31361	30176	32126	31045	29221	29678	29665
X⁃n134⁃k13	10916	13275	13619	12669	12430	11377	11203	11188
X⁃n139⁃k10	13590	15223	14251	15627	14652	13900	13873	13886
X⁃n143⁃k7	15700	17470	17397	18872	18689	16166	16257	16106
X⁃n148⁃k46	43448	46836	79514	50563	49692	52085	44413	44104
X⁃n153⁃k22	21220	22919	37938	26088	27103	23800	22606	22394
X⁃n157⁃k13	16876	17309	21330	19771	19862	17347	17403	17289
X⁃n162⁃k11	14138	15030	15085	16847	15426	14812	14508	14520
X⁃n167⁃k10	20557	22477	22285	24365	22359	21390	21270	21412
X⁃n172⁃k51	45607	50505	87809	51108	52968	55636	47162	47366
X⁃n176⁃k26	47812	52111	58178	57131	58023	52722	50647	50654
X⁃n181⁃k23	25569	26321	27520	27173	27179	26101	26201	26055
X⁃n186⁃k15	24145	26017	25757	28422	26896	24664	25345	24452
X⁃n190⁃k8	16980	18088	36383	20145	20356	18551	18123	18102
X⁃n195⁃k51	44225	50311	79276	51763	48562	48307	46153	46012
X⁃n200⁃k36	58578	61009	76477	64200	62495	61513	62011	61280

新窗口打开| 下载CSV

4.4　AOA机制的消融实验

为了进一步验证AOA机制对DHNS模型的有效性，设计了AOA在编码和解码阶段的消融实验，实验结果如表3所示，表中黑体字表示结果最优.实验结果表明，AOA可以有效提高DHNS的优化性能，解决混合模型中可能出现的解码错误，提升解码效率，显著降低CVRP问题的最优间隙.其中推理时间稍长的原因是AOA增加了网络层中的参数.

表3 AOA机制在编码和解码阶段的消融实验

Table 3 Ablation experiment of AOA mechanism in encoding and decoding stage

模型	CVRP20			CVRP50			CVRP100
模型	Obj	Gap	Time	Obj	Gap	Time	Obj	Gap	Time
DHNS(编码无AOA)	6.13	0.16%	2 min	10.40	0.19%	9 min	15.70	0.31%	21 min
DHNS(解码无AOA)	6.13	0.24%	2 min	10.40	0.24%	8 min	15.70	0.35%	20 min
DHNS	6.12	0.06%	3 min	10.39	0.09%	10 min	15.67	0.12%	22 min

新窗口打开| 下载CSV

5 结论

本文介绍了一种新的求解CVRP的深度学习方法DHNS，利用传统启发式与DRL相结合的混合模型，将AOA添加到编码器和解码器中，并使用AC算法来训练Transformer网络中的参数.

在问题规模中等且解精度高的情况下，DHNS模型非常可取.在保证解的精度的前提下，模型自动从数据中学习启发式方法并使决策过程自动化.实验结果表明，DHNS模型对100规模CVRP的优化效果优于现有的DRL模型和部分传统算法.真实数据集上的测试结果也显示出本文模型的优越性.

未来的工作会首先考虑进一步扩展模型以解决VRP的其他变体或其他组合最优化问题以及多目标VRP，其次考虑提高基于DRL方法的解决方案质量.未来主要挑战更有效地处理问题的动态特征，开发更好的机制，使智能体能够了解在访问一个城市后其他城市和环境的变化以及这种动态变化如何影响策略.

参考文献

原文顺序

文献年度倒序

文中引用次数倒序

被引期刊影响因子

[1]

Cook

W J

, Cunningham

W H

, Pulleyblank

W R

, et al. Combinatorial optimization. New York, USA： Wiley⁃Interscience,2010：11-22.

[2]

Augerat

， Belenguer

J M

， Benavent

，et al.

Separating capacity constraints in the CVRP using tabu search

European Journal of Operational Research，1998，106(2-3)：546-557.

[3]

代婉玉，张丽娟，吴佳峰，等.

改进TEB算法的局部路径规划算法研究

计算机工程与应用，2022，58(8)：283-288.

Dai

W Y

， Zhang

L J

， Wu

J F

，et al.

Research on local path planning algorithm based on improved TEB algorithm

Computer Engineering and Applications，2022，58(8)：283-288.

[4]

Yogatama

， Blunsom

， Dyer

，et al.

Learning to compose words into sentences with reinforcement learning

2016，arXiv：.

[5]

Kool

， Van Hoof

， Attention

Welling M.

，learn to solve routing problems. 2019，arXiv：.

[6]

王扬，陈智斌，吴兆蕊，等.

强化学习求解组合最优化问题的研究综述

计算机科学与探索，2022，16(2)：261-279.

Wang

， Chen

Z B

， Wu

Z R

，et al.

Review of reinforcement learning for combinatorial optimization problem

Journal of Frontiers of Computer Science and Technology，2022，16(2)：261-279.

[7]

Huang

， Wang

W M

， Chen

，et al.

Attention on attention for image captioning

∥Proceedings of the IEEE/CVF International Conference on Computer Vision. Seoul，Korea (South)：IEEE，2019：4633-4642.

[8]

Vaswani

， Shazeer

， Parmar

，et al.

Attention is all you need

∥Proceedings of the 31st International Conference on Neural Information Processing Systems. Long Beach，CA，USA：Curran Associates Inc.，2017：6000-6010.

[9]

Vinalys

， Fortunato

， Jaitly

Pointer networks

∥Proceedings of the 28th International Conference on Neural Information Processing Systems. Montreal，Canada：MIT Press，2015：2692-2700.

[10]

Nazari

， Oroojlooy

， Takáč

，et al.

Reinforcement learning for solving the vehicle routing problem

∥Proceedings of the 32nd International Conference on Neural Information Processing Systems. Montréal，Canada：Curran Associates Inc.，2018：9861-9871.

[11]

Bresson

， Laurent

The transformer network for the traveling salesman problem

2021，arXiv:2103. 03012.

[12]

王扬，陈智斌.

一种求解CVRP的动态图转换模型

计算机工程与科学，2023，45(5)：859-868.

Wang

， Chen

Z B

A dynamic graph transformer model for solving CVRP

Computer Engineering and Science，2023，45(5)：859-868.

[13]

Kwon

Y D

， Choo

， Kim

，et al.

Pomo：Policy optimization with multiple optima for reinforcement learning

∥Proceedings of the 34th International Conference on Neural Information Processing Systems. Vancouver，Canada：Curran Associates Inc.，2020：21188-21198.

[14]

Y X

， Song

， Cao

Z G

，et al.

Learning improvement heuristics for solving routing problems

IEEE Transactions on Neural Networks and Learning Systems，2022，33(9)：5057-5069.

[15]

王原，陈名，邢立宁，等.

用于求解旅行商问题的深度智慧型蚁群优化算法

计算机研究与发展，2021，58(8)：1586-1598.

Wang

， Chen

， Xing

L N

，et al.

Deep intelligent ant colony optimization for solving travelling salesman problem

Journal of Computer Research and Development，2021，58(8)：1586-1598.

[16]

Y N

, Li

J W

, Cao

Z G

, et al.

Learning to iteratively solve routing problems with dual⁃aspect collaborative transformer

Advances in Neural Information Processing Systems,2021(34)：11096-11107.

[17]

Hottung

， Tierney

Neural large neighborhood search for the capacitated vehicle routing problem

2020，arXiv：.

[18]

Qin

， Sun

W X

， Deng

，et al.

cosFormer：Rethinking softmax in attention

2022，arXiv：2202. 08791.

[19]

Chen

X Y

， Tian

Y D

Learning to perform local rewriting for combinatorial optimization

∥Proceedings of the 33rd International Conference on Neural Information Processing Systems. Vancouver，Canada：Curran Associates Inc.，2019：6281-6292.

[20]

Xin

， Song

， Cao

Z G

，et al.

Multi⁃decoder attention model with embedding glimpse for solving vehicle routing problems

∥Proceedings of the 35th AAAI Conference on Artificial Intelligence. Palo Alto，CA，USA：AAAI Press，2021：12042-12049.

[21]

Kool

， Van Hoof

， Gromicho

，et al.

Deep policy dynamic programming for vehicle routing problems

2021，arXiv：.