深度混合型邻域搜索模型求解CVRP问题-九八年世界杯-世界杯总决赛_男篮世界杯直播

2025-11-24 09:01:43 -

九八年世界杯

车辆路径问题（Vehicle Routing Problem，VRP）是组合最优化问题中的经典问题，带容量的车辆路径问题（Capacitated Vehicle Routing Problem，CVRP）是VRP的主要变体之一，在智能交通、物流领域等有广泛应用［1］.CVRP考虑的是带容量的车队为一系列客户提供服务的最佳路线，要求车队将货物从仓库运输到指定客户点，每个客户只允许被访问一次，其中车辆是同质的且只能从仓库出发，完成任务后需返回仓库，目标是使车队完成所有任务的总路线最短［2］.先前求解组合最优化问题的方法主要依赖传统算法［3］，例如利用精确算法、近似算法或启发式算法进行求解.针对CVRP问题的特点，国内外学者设计了各种优化算法对其进行求解，其中应用较多的是智能算法，如遗传算法、邻域搜索等.

高效的算法可以快速合理地规划路线，减少路径花费.在实际应用中具有挑战性的问题大多数是NP难的，传统算法在处理这类任务时会受到特定的限制（例如计算时间长、精度低等）.强化学习（Reinforcement Learning，RL）在处理自然语言处理问题上的最新进展［4］表明其在处理NP难问题上具有很大的潜力.Kool et al［5］基于注意力机制（Attention Mechanism，AM）提出的Transformer模型是首次解决旅行商问题（Travelling Salesman Problem，TSP）、CVRP和其他路径问题的模型，模型将输入元素分为静态、动态两种类型，利用嵌入的编码过程对静态和动态元素进行向量表示，解码阶段将静态元素向量输入解码中获得隐含层向量并与动态向量结合，通过AM获得下一个决策点的概率分布.AM模型的提出为后续深度强化学习（Deep Reinforcement Learning，DRL）求解路径问题奠定了基础，为组合最优化问题的求解提供了新思路［6］.DRL得到的策略有希望比人工设计的更高效，对于类似的问题能同样用基于学习的框架去求解，不需要人工重新设计算法.

基于DRL的方法通过归一化的AM获取隐藏层信息，但是AM模块的性能受到CVRP中动态和随机因素的影响，导致先前工作中的AM模块未能充分考虑多重头注意力机制（Multi⁃attention Mechanism，MHA）中查询向量Q和键向量K之间的相关性，导致在没有相关性的前提下也会输出关联值.同时，混合模型通常利用多个网络进行编码和解码，结合了来自不同模块的优点，但是向量编码及传输过程过于繁杂，可能出现信息解码错误等情况.

自适应大邻域搜索（Adaptive Large Neighborhood Search，ALNS）是受大邻域搜索（Large Neighborhood Search，LNS）发展启发而来的，在LNS的基础上，允许在同一个搜索中使用多个破坏算子和修复算子来获得当前解的邻域，根据生成的解的质量，选择表现好的破坏算子和修复算子，再次生成邻域进行搜索.邻域搜索算法的关键是邻域结构的选择，但每次迭代搜索的时间较长，缺少在解空间内自主搜索的能力.

现实中很多问题本质上是组合优化问题，因此，人们一直在修改ALNS来有效地求解组合优化问题，例如CVRP问题.针对上述问题，本文提出深度混合型邻域搜索（Deep Hybrid Neighborhood Search，DHNS）算法模型，即带有DRL的ALNS算法的修复解的更新，同时，将AOA （Attention on Attention）［7］加入编码和解码过程.在编码过程中，AOA可以提取节点的特征，并对节点间的关系进行建模；在解码过程中，AOA负责筛选有价值的信息，过滤不相关或误导性信息，进一步确定注意力结果和查询之间的相关性.实验结果表明AOA模块对于改善模型性能是有效的，优于之前基于DRL的所有模型.

本文的主要创新如下.

（1）为了提取丰富的节点特征向量，在传统编码结构上，提出一种Transformer［8］和指针网络（Pointer Network，PN）［9］混合编码结构，并在AM上改进同时具有MHA和AOA的编码和解码结构.MHA主要用于信息提取，AOA负责提高解码器的准确性.

（2）设计了一个依赖于DRL框架的ALNS，以探索解空间中邻域的关系，修复解决方案的任务留给通过DRL训练的新型网络模型.将DRL集成到ALNS中可以提高算法在解空间中的搜索范围，并提供启发式信息的指导.

1 相关工作

近年来，DRL成为一种解决路径问题的新方法，目前基于DRL求解VRP的框架主要是编码和解码结构，由Nazari et al［10］首次提出，强调路径问题与DRL的结合，这种编码⁃解码体系训练的模型效果与传统算法相比有很大的优势.在求解VRP的模型框架中，首先将问题转化为图，通过网络模型编码为带有节点信息的特征向量，然后通过解码器将其解码为城市输出序列.由于编码器⁃解码器的通用架构是循环神经网络（Recurrent Neural Network，RNN），但是RNN存在长距离依赖问题，会导致梯度消失和梯度爆炸.为了避免上述问题，Bresson and Laurent［11］提出一种基于Transformer模型的求解方法，在编码⁃解码中添加AM，为每个查询输出一个加权平均值，使模型能够关注更多有用的信息，有效缓解了梯度爆炸，降低计算成本.在此基础上，王扬和陈智斌［12］提出动态图Transformer （Dynamic Graph Transformer Model，DGTM）模型求解CVRP，并使用REINFORCE算法提高模型的训练效率，实验结果表明模型整体性能优于专业求解器，提高了CVRP问题求解速度，且具有较好的泛化性能.

为提高模型搜索效率，Kwon et al［13］提出一种具有多重策略优化（Policy Optimization with Multiple Optimal，POMO）的网络框架，使用DRL来训练MHA的多个初始节点嵌入，POMO的低方差基线使RL模型训练快速且稳定，且对局部最小值的抵抗力最高.实验结果表明模型性能显著提高，同时模型推理时间减少一个数量级以上.为提升智能体的选择效率，Wu et al［14］通过DRL框架改进启发式算法来求解CVRP，其中策略网络用于指导下一个解决方案的选择，并利用行动者⁃评论家（Actor⁃critic，AC）算法训练策略网络，然后通过启发式算法来提高解的质量，该模型学习到的策略明显优于传统的手工规则.

启发式算法通常需要改进其在解空间内的搜索能力，因此王原等［15］利用深度智慧型蚁群优化算法（Deep Intelligent Ant Colony Optimization，DIACO）求解TSP，DRL结合蚁群算法提高了DRL在解空间内的搜索能力以及蚁群算法的计算能力.此外，Ma et al［16］提出双方面协作Transformer （Dual⁃Aspect Collaborative Transformer，DACT）模型来解决具有动态和周期性变化的CVRP，使用双向编码器分别学习节点和位置特征的嵌入，同时使用课程学习训练模型，提高模型的采样速率.实验结果表明，DACT优于传统的启发式算法，且具有更优的泛化性能.

为了缩小基于DRL的方法与最先进优化方法之间的性能差距，Hottung and Tierney［17］提出了一种新颖的神经邻域搜索（Neural Large Neighborhood Search，NLNS）框架，该框架集成启发式算法以生成新的解决方案，学习机制基于具有AM的神经网络，并设计结合到大型邻域搜索设置中.实验结果表明，该模型明显优于仅使用手工启发式算法和著名的启发式算法，并接近于最先进的优化方法的性能.但上述方法仅考虑小规模CVRP，当问题规模变大时，优化效果不理想.

2 模型介绍

2.1 CVRP问题定义

CVRP考虑带容量的车队为一系列客户N=1,2,⋯,n提供服务的最佳路线，每个客户节点i的需求为qi，要求车队v=1,2,3,⋯,K将货物从仓库0运输到指定客户点，每个客户只允许被访问一次，客户i与客户j之间的距离为dij.其中车辆是同质的（容量为C）且只能从仓库出发，完成任务后需返回仓库，目标是使车队完成所有任务的总路线最短［2］.如果车辆K直接从客户i到达客户j，则令决策变量xijk=1，否则为0.若客户节点i的需求由车辆k满足，则yik=1，否则为0.因此，CVRP问题可建模如下.

目标函数：

min∑i=0n∑j=0n∑k=1Kdijxijk（1）

约束条件：

∑k=1Kyik=1,i=1,2,⋯,n（2）

∑i=1nqiyik≤C,k=1,2,⋯,K（3）

∑k=1Kxijk=yjk=yiki,j=1,2,⋯,n,k=1,2,⋯,K（4）

∑i=0nxilk-∑j=0nxljk=0,k=1,2,⋯,K（5）

xijk∈0,1,yjk∈0,1i,j=1,2,⋯,n,k=1,2,⋯,K（6）

目标函数（1）表示最小化车辆总行驶距离，约束（2）表示每个客户节点仅能被一辆车访问一次，约束（3）用来保证运输路线上的客户总需求不能超过车辆自身承载容量，约束（4）表示若客户i,j均由车辆k配送，则车辆k必须由某点i到达j，或者车辆访问完客户i后立即访问节点j，约束（5）表示访问某点的车辆数等于离开该点的车辆数.

2.2 模型总框架

DHNS模型基于PN和Transformer混合编码，PN表示和提取各种浅层的节点特征，减少参数的冗余，在此基础上利用Transformer中MHA机制从不同维度提取节点特征信息，最后结合动态位置编码（Dynamic Positional Encoding，DPE）［12］表示隐层嵌入的绝对位置信息.而混合编码过程程序复杂，很可能出现解码失误的情况.

因此，本文通过MHA提取节点特征信息，AOA通过计算MHA中的查询向量和查询结果之间的相关性，提高解码器的精确性，结合DPE进一步提取节点间的相关性，提高模型在不同规模问题上的泛化能力.DHNS模型的总体架构和求解思路如图1所示，ALNS的主要思想是通过多组破坏算子OD和修复算子OR在解空间搜索并改善当前解，对性能较好的算子给予更高的权重.对于给定的初始解，由ALNS的破坏算子OD对初始解进行破坏，然后DRL自动学习修复解的策略，最后模型在修复解空间中探索最优的解.

图1

新窗口打开|

下载原图ZIP|

生成PPT

图1

模型架构及求解思路

Fig.1

Model architecture and solution ideas

2.2.1 破坏算子和修复算子

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

图2

新窗口打开|

下载原图ZIP|

生成PPT

图2

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

Fig.2

Operation process of destroying operator and repairing operator

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

坏为七段不完整路径x2,x3,x0,x4,x0,x16,

x5,x6,x7,x8,x10,x11,x14,x15和四个独立的客户节点x1,x9,x12,x13.模型为被破坏的解的末端添加特征向量xi，并将不完整路径的末端特征向量作为输入，通过DRL模型计算不完整路径末端节点的相关性，自动学习路径的修复策略.为了防止不完整的路径选择其末端节点或产生不可行的解决方案（例如路线负载超过车辆容量限制），通过添加掩码来禁止该操作.

2.3 编码器结构

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

Ai=softmaxQlKldVl（7）

MHAQl,Kl,Vl=ConcatA1,A2,…,AHWo（8）

其中，Wo是训练参数，Ql,Kl和Vl分别是自注意力机制的查询向量、键向量和值向量.

图3

新窗口打开|

下载原图ZIP|

生成PPT

图3

DHNS模型总架构

Fig.3

DHNS model master architecture

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

hi'=dt×cosπi2st+dt×sinπi2st（9）

hf'=hf×cosπi2st+hf×sinπi2st（10）

uiH=VAtanhWAhi+hi',hf+hf'（11）

c=∑i=0nsoftmaxu0H,u1H,⋯,unHhi+hi'（12）

其中，⋅,⋅表示两向量的串联，VA，WA是可训练的参数矩阵.

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中的权重可以有效地解决梯度消失问题，因此使用如下表达式来计算权重向量：

li,j=fsimqi,kj,li,j¯=eli,j∑jeli,j（13）

Hi=∑jli,j¯vj（14）

其中，qi属于Q的第i个查询向量，kj和vj分别属于K，V的第j个键向量和值向量，fsim是用来计算kj和qi相似分数的函数，Hi表示qi和kj的相似性.

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是当前上下文向量和注意力结果v^通过线性变换得到并存储，注意力门G是当前上下文向量c与注意力结果v^通过另一个线性变换得到的.

I=Wqic+Wviv^+bi,（15）

G=sigmoidWqgc+Wvgv^+bg（16）

其中，Wqi,Wvi和bi,Wqg,Wvg和bg分别表示信息向量I和注意力门G的参数矩阵，Wqi,Wvi,Wqg,

Wvg∈RD×D.

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

AoAfatt,Q,K,V=sigmoidWqgQ+Wvgfatt+bg⊙WqiQ+Wvifatt+bi(17)

其中，fatt是注意力模块，⊙表示逐元素乘法.

2.4 解码器结构

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

Ct=fconcategraph,lt,elast,t≥1fconcategraph,l0,elast,t=1（18）

其中，fconcat是隐藏层的级联函数，在MHA中使用获得的上下文向量来获得权重向量.

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

Ct¯=AoAMHACt,et,mask（19）

q=FFC¯t+FFhf+hf'（20）

Pθatπt=σVBtanhhi+hi'+q（21）

其中，et表示时刻t的节点隐藏层，mask是标记已访问节点的掩码向量，VB是可训练的参数.

3 训练与推理方法

3.1 模型训练算法

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

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

Jθπ0=Eπt-pθ.π0Lπts（22）

∇Jθπ0=Eπt-pθ.π0Lπ0,πt-bπ0∇lgpθπts（23）

其中，π0为破坏后的解，πt是智能体执行动作a1,a2,a3,⋯,at-1之后修复的解，基线bπ0可以有效地减少方差.

模型采用AC算法进行训练，通过随机策略学习行为网络的参数，行为网络基于概率分布做动作，评判网络基于行为网络生成的行为评判得分，行为网络再根据评判网络的评分调整行为选择的概率.解决VRP问题的传统策略梯度算法的主要缺点是高维离散空间中不同路径之间的方差大，训练不稳定，但AC算法可以单步更新，不需要完成整个动作再更新网络参数.传统策略梯度方法对价值的估计虽然是无偏的，但方差较大，AC算法能够有效降低方差.为了保证策略梯度方差的稳定性，类似于Nazari et al［10］，本文使用评判网络为修复解π0生成一个值c0作为评判网络估算修复的成本，评判网络根据行为网络状态预测奖励值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×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充分利用同类型问题之间的相似特征，避免传统算法不断重复求解的过程和数据资源的浪费.

Table1

表1

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

Table1 Comparison of CVRP optimization results of DHNS model

模型CVRP20CVRP50CVRP100ObjGapTimeObjGapTimeObjGapTimeRandom CW6.8111.64%-12.2518.07%-18.9621.18%-LKH36.120.00%2 h10.380.00%7 h15.650.00%13 hALNS6.699.31%1 s11.248.28%2 s17.3310.7%5 sOR⁃Tools*6.424.84%2 min11.228.12%12 min17.149.34%1 hRL(BS)*6.404.39%27 min11.157.46%39 min16.968.39%74 minAM (sampling)*6.251.91%6 min10.622.40%28 min16.233.72%2 hAM⁃D (greedy)*6.282.95%≪1 s10.783.85%≪1 s16.404.79%≪1 sNeuRewriter*6.160.48%22 min10.511.25%35 min16.102.88%66 minPOMO6.353.42%≪1 s10.743.52%1 s16.153.00%3 sNLNS6.140.61%1 h10.551.65%2 h16.112.99%3 hDACT6.130.24%11 min10.390.18%32 min15.710.38%1.5 hMDAM(BS)6.140.26%3 min10.501.18%9 min16.032.49%31 minDPDP*------15.690.26%6 hDGTM6.130.13%2 s10.390.15%5 s15.680.19%20 sDHNS6.120.06%3 min10.390.09%9 min15.670.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

新窗口打开|

下载原图ZIP|

生成PPT

图4

CVRP泛化性能的比较

Fig.4

Comparison of CVRP generalization performance

图5

新窗口打开|

下载原图ZIP|

生成PPT

图5

CVRP20模型收敛图

Fig.5

Diagram of CVRP20 model convergence

图6

新窗口打开|

下载原图ZIP|

生成PPT

图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的模型.

Table 2

表2

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

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

实例最优OR⁃ToolsAMWu et alNLNSPOMODACTDHNS平均间隙0.00%8.06%31.62%14.27%11.67%6.10%3.41%3.07%X⁃n101⁃k252759129405377022971629845285952799627999X⁃n106⁃k142636227343284732764227688268502685526809X⁃n110⁃k131479116149154431592715247150941481014099X⁃n115⁃k101274713320137451444514256131911296112875X⁃n120⁃k61333214242139371548613986136151364913602X⁃n125⁃k305553958665750676042357896595045856056912X⁃n129⁃k182894031361301763212631045292212967829665X⁃n134⁃k131091613275136191266912430113771120311188X⁃n139⁃k101359015223142511562714652139001387313886X⁃n143⁃k71570017470173971887218689161661625716106X⁃n148⁃k464344846836795145056349692520854441344104X⁃n153⁃k222122022919379382608827103238002260622394X⁃n157⁃k131687617309213301977119862173471740317289X⁃n162⁃k111413815030150851684715426148121450814520X⁃n167⁃k102055722477222852436522359213902127021412X⁃n172⁃k514560750505878095110852968556364716247366X⁃n176⁃k264781252111581785713158023527225064750654X⁃n181⁃k232556926321275202717327179261012620126055X⁃n186⁃k152414526017257572842226896246642534524452X⁃n190⁃k81698018088363832014520356185511812318102X⁃n195⁃k514422550311792765176348562483074615346012X⁃n200⁃k365857861009764776420062495615136201161280

新窗口打开|

下载CSV

4.4 AOA机制的消融实验

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

Table 3

表3

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

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

模型CVRP20CVRP50CVRP100ObjGapTimeObjGapTimeObjGapTimeDHNS(编码无AOA)6.130.16%2 min10.400.19%9 min15.700.31%21 minDHNS(解码无AOA)6.130.24%2 min10.400.24%8 min15.700.35%20 minDHNS6.120.06%3 min10.390.09%10 min15.670.12%22 min

新窗口打开|

下载CSV

5 结论

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

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

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

参考文献

View Option

原文顺序

文献年度倒序

文中引用次数倒序

被引期刊影响因子

[1]

Cook W J, Cunningham W H, Pulleyblank W R, et al. Combinatorial optimization. New York, USA： Wiley⁃Interscience,2010：11-22.

[本文引用: 1]

[2]

Augerat P， Belenguer J M， Benavent E，et al. Separating capacity constraints in the CVRP using tabu search

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

[本文引用: 2]

[3]

代婉玉，张丽娟，吴佳峰，等. 改进TEB算法的局部路径规划算法研究

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

[本文引用: 1]

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.

[本文引用: 1]

[4]

Yogatama D， Blunsom P， Dyer C，et al. Learning to compose words into sentences with reinforcement learning

2016，arXiv：.

[本文引用: 1]

[5]

Kool W， Van Hoof H， Attention Welling M.，learn to solve routing problems. 2019，arXiv：.

[本文引用: 2]

[6]

王扬，陈智斌，吴兆蕊，等. 强化学习求解组合最优化问题的研究综述

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

[本文引用: 1]

Wang Y， 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.

[本文引用: 1]

[7]

Huang L， Wang W M， Chen J，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.

[本文引用: 2]

[8]

Vaswani A， Shazeer N， Parmar N，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.

[本文引用: 1]

[9]

Vinalys O， Fortunato M， Jaitly N. Pointer networks

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

[本文引用: 1]

[10]

Nazari M， Oroojlooy A， Takáč A，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.

[本文引用: 2]

[11]

Bresson X， Laurent T. The transformer network for the traveling salesman problem

2021，arXiv:2103. 03012.

[本文引用: 1]

[12]

王扬，陈智斌. 一种求解CVRP的动态图转换模型

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

[本文引用: 2]

Wang Y， Chen Z B. A dynamic graph transformer model for solving CVRP

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

[本文引用: 2]

[13]

Kwon Y D， Choo J， Kim B，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.

[本文引用: 2]

[14]

Wu Y X， Song W， 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.

[本文引用: 1]

[15]

王原，陈名，邢立宁，等. 用于求解旅行商问题的深度智慧型蚁群优化算法

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

[本文引用: 1]

Wang Y， Chen M， 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.

[本文引用: 1]

[16]

Ma 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.

[本文引用: 2]

[17]

Hottung A， Tierney K. Neural large neighborhood search for the capacitated vehicle routing problem

2020，arXiv：.

[本文引用: 2]

[18]

Qin Z， Sun W X， Deng H，et al. cosFormer：Rethinking softmax in attention

2022，arXiv：2202. 08791.

[本文引用: 1]

[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.

[本文引用: 1]

[20]

Xin L， Song W， 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.

[本文引用: 1]

[21]

Kool W， Van Hoof H， Gromicho J，et al. Deep policy dynamic programming for vehicle routing problems

2021，arXiv：.

[本文引用: 1]

2010

... 车辆路径问题（Vehicle Routing Problem，VRP）是组合最优化问题中的经典问题，带容量的车辆路径问题（Capacitated Vehicle Routing Problem，CVRP）是VRP的主要变体之一，在智能交通、物流领域等有广泛应用［1］.CVRP考虑的是带容量的车队为一系列客户提供服务的最佳路线，要求车队将货物从仓库运输到指定客户点，每个客户只允许被访问一次，其中车辆是同质的且只能从仓库出发，完成任务后需返回仓库，目标是使车队完成所有任务的总路线最短［2］.先前求解组合最优化问题的方法主要依赖传统算法［3］，例如利用精确算法、近似算法或启发式算法进行求解.针对CVRP问题的特点，国内外学者设计了各种优化算法对其进行求解，其中应用较多的是智能算法，如遗传算法、邻域搜索等. ...

Separating capacity constraints in the CVRP using tabu search

1998

... CVRP考虑带容量的车队为一系列客户N=1,2,⋯,n提供服务的最佳路线，每个客户节点i的需求为qi，要求车队v=1,2,3,⋯,K将货物从仓库0运输到指定客户点，每个客户只允许被访问一次，客户i与客户j之间的距离为dij.其中车辆是同质的（容量为C）且只能从仓库出发，完成任务后需返回仓库，目标是使车队完成所有任务的总路线最短［2］.如果车辆K直接从客户i到达客户j，则令决策变量xijk=1，否则为0.若客户节点i的需求由车辆k满足，则yik=1，否则为0.因此，CVRP问题可建模如下. ...

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

2022

Research on local path planning algorithm based on improved TEB algorithm

2022

Learning to compose words into sentences with reinforcement learning

2016

... 高效的算法可以快速合理地规划路线，减少路径花费.在实际应用中具有挑战性的问题大多数是NP难的，传统算法在处理这类任务时会受到特定的限制（例如计算时间长、精度低等）.强化学习（Reinforcement Learning，RL）在处理自然语言处理问题上的最新进展［4］表明其在处理NP难问题上具有很大的潜力.Kool et al［5］基于注意力机制（Attention Mechanism，AM）提出的Transformer模型是首次解决旅行商问题（Travelling Salesman Problem，TSP）、CVRP和其他路径问题的模型，模型将输入元素分为静态、动态两种类型，利用嵌入的编码过程对静态和动态元素进行向量表示，解码阶段将静态元素向量输入解码中获得隐含层向量并与动态向量结合，通过AM获得下一个决策点的概率分布.AM模型的提出为后续深度强化学习（Deep Reinforcement Learning，DRL）求解路径问题奠定了基础，为组合最优化问题的求解提供了新思路［6］.DRL得到的策略有希望比人工设计的更高效，对于类似的问题能同样用基于学习的框架去求解，不需要人工重新设计算法. ...

2019

... 表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充分利用同类型问题之间的相似特征，避免传统算法不断重复求解的过程和数据资源的浪费. ...

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

2022

Review of reinforcement learning for combinatorial optimization problem

2022

Attention on attention for image captioning

2019

... 现实中很多问题本质上是组合优化问题，因此，人们一直在修改ALNS来有效地求解组合优化问题，例如CVRP问题.针对上述问题，本文提出深度混合型邻域搜索（Deep Hybrid Neighborhood Search，DHNS）算法模型，即带有DRL的ALNS算法的修复解的更新，同时，将AOA （Attention on Attention）［7］加入编码和解码过程.在编码过程中，AOA可以提取节点的特征，并对节点间的关系进行建模；在解码过程中，AOA负责筛选有价值的信息，过滤不相关或误导性信息，进一步确定注意力结果和查询之间的相关性.实验结果表明AOA模块对于改善模型性能是有效的，优于之前基于DRL的所有模型. ...

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

Attention is all you need

2017

... （1）为了提取丰富的节点特征向量，在传统编码结构上，提出一种Transformer［8］和指针网络（Pointer Network，PN）［9］混合编码结构，并在AM上改进同时具有MHA和AOA的编码和解码结构.MHA主要用于信息提取，AOA负责提高解码器的准确性. ...

Pointer networks

2015

Reinforcement learning for solving the vehicle routing problem

2018

... 近年来，DRL成为一种解决路径问题的新方法，目前基于DRL求解VRP的框架主要是编码和解码结构，由Nazari et al［10］首次提出，强调路径问题与DRL的结合，这种编码⁃解码体系训练的模型效果与传统算法相比有很大的优势.在求解VRP的模型框架中，首先将问题转化为图，通过网络模型编码为带有节点信息的特征向量，然后通过解码器将其解码为城市输出序列.由于编码器⁃解码器的通用架构是循环神经网络（Recurrent Neural Network，RNN），但是RNN存在长距离依赖问题，会导致梯度消失和梯度爆炸.为了避免上述问题，Bresson and Laurent［11］提出一种基于Transformer模型的求解方法，在编码⁃解码中添加AM，为每个查询输出一个加权平均值，使模型能够关注更多有用的信息，有效缓解了梯度爆炸，降低计算成本.在此基础上，王扬和陈智斌［12］提出动态图Transformer （Dynamic Graph Transformer Model，DGTM）模型求解CVRP，并使用REINFORCE算法提高模型的训练效率，实验结果表明模型整体性能优于专业求解器，提高了CVRP问题求解速度，且具有较好的泛化性能. ...

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

The transformer network for the traveling salesman problem

2021

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

2023

... DHNS模型基于PN和Transformer混合编码，PN表示和提取各种浅层的节点特征，减少参数的冗余，在此基础上利用Transformer中MHA机制从不同维度提取节点特征信息，最后结合动态位置编码（Dynamic Positional Encoding，DPE）［12］表示隐层嵌入的绝对位置信息.而混合编码过程程序复杂，很可能出现解码失误的情况. ...

A dynamic graph transformer model for solving CVRP

2023

Pomo：Policy optimization with multiple optima for reinforcement learning

2020

... 为提高模型搜索效率，Kwon et al［13］提出一种具有多重策略优化（Policy Optimization with Multiple Optimal，POMO）的网络框架，使用DRL来训练MHA的多个初始节点嵌入，POMO的低方差基线使RL模型训练快速且稳定，且对局部最小值的抵抗力最高.实验结果表明模型性能显著提高，同时模型推理时间减少一个数量级以上.为提升智能体的选择效率，Wu et al［14］通过DRL框架改进启发式算法来求解CVRP，其中策略网络用于指导下一个解决方案的选择，并利用行动者⁃评论家（Actor⁃critic，AC）算法训练策略网络，然后通过启发式算法来提高解的质量，该模型学习到的策略明显优于传统的手工规则. ...

Learning improvement heuristics for solving routing problems

2022

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

2021

... 启发式算法通常需要改进其在解空间内的搜索能力，因此王原等［15］利用深度智慧型蚁群优化算法（Deep Intelligent Ant Colony Optimization，DIACO）求解TSP，DRL结合蚁群算法提高了DRL在解空间内的搜索能力以及蚁群算法的计算能力.此外，Ma et al［16］提出双方面协作Transformer （Dual⁃Aspect Collaborative Transformer，DACT）模型来解决具有动态和周期性变化的CVRP，使用双向编码器分别学习节点和位置特征的嵌入，同时使用课程学习训练模型，提高模型的采样速率.实验结果表明，DACT优于传统的启发式算法，且具有更优的泛化性能. ...

Deep intelligent ant colony optimization for solving travelling salesman problem

2021

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

2021

Neural large neighborhood search for the capacitated vehicle routing problem

2020

... 为了缩小基于DRL的方法与最先进优化方法之间的性能差距，Hottung and Tierney［17］提出了一种新颖的神经邻域搜索（Neural Large Neighborhood Search，NLNS）框架，该框架集成启发式算法以生成新的解决方案，学习机制基于具有AM的神经网络，并设计结合到大型邻域搜索设置中.实验结果表明，该模型明显优于仅使用手工启发式算法和著名的启发式算法，并接近于最先进的优化方法的性能.但上述方法仅考虑小规模CVRP，当问题规模变大时，优化效果不理想. ...

cosFormer：Rethinking softmax in attention

2022

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

Learning to perform local rewriting for combinatorial optimization

2019

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

Deep policy dynamic programming for vehicle routing problems

2021

Apple Pay 使用教學｜完整設定與支付指南
獵字的笔画顺序