一种基于图神经网络的改进邻域搜索算法

伍康 夏维 王子源

摘 要：近年来图神经网络与深度强化学习的发展为组合优化问题的求解提供了新的方法。当前此类方法大多未考虑到算法参数学习问题，为解决该问题，基于图注意力网络设计了一种智能优化模型。该模型对大量问题数据进行学习，自动构建邻域搜索算子与序列破坏终止符，并使用强化学习训练模型参数。在标准算例集上测试模型并进行三组不同实验。实验结果表明，该模型学习出的邻域搜索算子具备较强的寻优能力和收敛性，同时显著降低了训练占用显存。该模型能够在较短时间内求解包含数百节点的CVRP问题，并具有一定的扩展潜力。

关键词：组合优化；CVRP；邻域搜索；图注意力网络；深度强化学习

中图分类号：TP183   文献标志码：A    文章编号：1001-3695（2024）05-018-1402-07

doi： 10.19734/j.issn.1001-3695.2023.08.0410

Improved neighborhood search algorithm based on graph neural network

Abstract：In recent years， the development of graph neural network（GNN） and deep reinforcement learning provides new methods to solve combinatorial optimization problems. Currently， most of these methods do not consider the problem of algorithm parameter learning. This paper developed an intelligent optimization model based on graph attention networks to solve this problem. The model automatically learned neighborhood search operators and destructive sequence terminators according to a significant amount of problem data， and trained model parameters based on reinforcement learning. This article used standard examples to test the model and conducted three different groups of experiments. The experimental results show that the learned neighborhood search operator has a remarkable ability to optimize and converge， while significantly reducing the training memory occupation. It can solve CVRP problems containing hundreds of nodes in a short time and has the potential for expansion.

Key words：combinatorial optimization; CVRP; neighborhood search; graph attention network（GAT）; deep reinforcement learning（DRL）

0 引言

組合优化问题是一类在离散状态下求极值的最优化问题［1］，广泛应用于交通运输规划、生产流程优化等领域。常见的组合优化问题有车辆路径问题（vehicle routing problem，VRP）［2］、车间作业调度问题（Job-Shop scheduling problem，JSP）等。组合优化问题通常是NP-hard的，在多项式时间内无法寻找到最优解。目前求解组合优化问题的算法分为精确算法和近似算法两类，精确算法指可以求解出问题全局最优解的方法，包括分支定界法［3］、列生成法［4］和动态规划等。近似算法指可以求出问题局部最优解的方法，有近似算法［5］和启发式算法［6］两类，近似算法包括贪心算法［7］、线性规划等，启发式算法有模拟退火算法［8］、遗传算法［9］及迭代邻域搜索方法［10］等。精确算法虽然可以计算出最优解，然而当问题规模较大时，将耗费巨大计算资源，难以拓展到大规模问题。解决规模较大的组合优化问题时，多采用启发式算法获得近似最优解，然而启发式规则需要领域专家手工设计，高度依赖专业知识。随着图神经网络（GNN）结合深度强化学习（DRL）在求解组合优化问题领域的发展，基于深度神经网络学习启发式算子与操作符，并混合经典启发式求解框架已经成为求解组合优化问题的新途径。

基于DRL求解组合问题算法主要分为端到端算法与迭代搜索算法两类［11］。端到端算法将给定问题作为输入，通过训练好的深度神经网络直接输出问题最终解。Bello等人［12］引入强化学习训练指针网络模型（pointer network，Ptr-Net）。文献［13］首次利用GNN编码问题，使用深度Q-网络解决旅行商问题（travelling salesman problem， TSP）。Kool等人［14］引入了Transformer［15］的注意力机制，提出注意力模型求解TSP、VRP问题。上述基于端到端的算法能快速直接输出问题解，但在中大规模问题上优化结果与求解器差距较大。迭代搜索类算法根据学习到的启发式规则进行迭代搜索，通常具有良好的优化结果，但在求解速度上不如端到端方法。Chen等人［16］提出的邻域搜索模型Neuwriter求解JSP和VRP问题的表现均优于Google OR-tools。Yolcu等人［17］结合GNN与强化学习训练邻域搜索选择算子，寻找适定性问题最优解时，算法迭代步数少于传统启发式算法。此外许多学者利用DRL学习设计其他搜索类算法［18，19］，如蚁群算法、集束搜索等。文献［20，21］分别研究与提升了搜索模型的泛化性。根据上述研究可以看出迭代搜索类框架很适合与深度神经网络结合形成混合优化算法，这也是本文的主要研究动机。

大规模邻域搜索（large neighborhood search，LNS）［22］是一种主流的启发式搜索框架，每次迭代時通过搜寻现有解的邻域获得更优解，即破坏算子和修复算子的不断交替迭代。Gao等人［23］结合图注意力神经网络（GAT）［24］与DRL学习LNS的邻域算子以求解VRP问题。Wu等人［25］利用DRL和GNN学习解决整数规划问题的LNS策略，用以改进Gurobi等商业求解器求解效率。Cheng等人［26］在搜索的同时加入选择操作，加快了整体算法运行速度。然而上述研究未考虑LNS算法参数学习问题，例如破坏节点数目、邻域搜索步长及深度等。只采用单一的参数组合，算法探索空间过小，易陷入局部最优解［27］。

综上所述，本文受seq2seq［28］模型中序列终止符学习机制的启发，提出了一种学习邻域搜索算子的终止符-边-图注意力网络（terminator edge graph attention network，TE-GAT）模型。TE-GAT模型采用编码器-解码器架构，编码器负责提取问题图结构特征，基于GAT进行信息汇聚。解码器负责充当破坏算子输出有序破坏节点序列，根据学习获得的算法终止符进行有序解码，算法中的贪心算子接收该有序序列生成新的迭代解。模型通过构建虚拟节点的方式在编码器中加入可学习的终止符，并在网络训练过程中将最优的算法终止位置指向该虚拟节点。本文基于actor-critic架构使用近端策略优化（proximal policy optimization，PPO）算法训练所提模型，模型代表的策略网络在每回合与价值网络的互相改进中不断更新参数，训练后得到准确稳定的模型。通过终止符学习机制，TE-GAT模型进一步学习LNS算法参数，提升了算法对近似最优解的搜索能力与不同特征问题的适应性。

VRP问题是组合优化领域一类极具应用性的优化调度问题，本文以解决大规模具有容量限制的车辆路径规划问题（capacitated vehicle routing problem，CVRP）为例，进行三组不同实验以证明TE-GAT模型的实用性和可行性。第一组实验针对问题规模分别为51、101、200及251等CVRP问题，使用随机生成实例训练模型，从CVRPLIB［29］标准算例库中选择对应规模算例测试，并与Google OR-tools、Random-LNS算法及EGATE模型对比实验结果。第二组实验通过参数实验分析了终止符学习机制的实际效用。最后探索了模型求解服务节点数量超过500的大规模CVRP问题的性能表现，证明算法在大规模问题数据集下具有良好的寻优能力和进一步解决更大规模问题的潜力。

1 CVRP问题

VRP问题属于组合优化领域中的一类经典问题，可被简单描述为：一组车辆向多个需求有限用户运送货物，若车辆无法完成或已经完成用户需求，立即返回仓库。问题优化目标是在完成所有用户需求的情况下使运输路线总成本最小。本文主要解决CVRP问题，图1为CVRP问题示意图。问题定义在无向完全图Euclid Math OneGAp=（Euclid Math OneNAp，A）上，i={0，1，2，…，n}代表所有节点集合，如果i≠0，则节点i表示用户点。如果i=0，则节点i表示仓库。用户点i∈{1，2，…，n}的货物需求量为Q且满足约束μ1

2 基于图神经网络的邻域搜索算子策略网络

2.1 原始嵌入特征

为了从当前CVRP问题解决方案的图结构中获得节点与边信息表示问题特征，本文设计如下提取原始节点嵌入特征及边嵌入特征的向量化表示方法。

按式（1）定义原始节点嵌入特征xi：

xi=［D（j）i，D（j），Qi，Q（j）］（1）

其中：D（j）i表示在当前路线j下车辆到达节点i时已经行驶的距离；D（j）表示当前路线j的总距离；Qi表示节点i的需求量；Q（j）表示当前线路j的总需求量。

按式（2）定义原始边嵌入特征eij：

eij=［dij，bij］（2）

其中：dij表示节点i到j的边距离；bij表示是否存在路线经过aij，是则为1，否则为0。

以上特征向量的所有元素都会经过归一化处理，归一化后的原始特征向量将会作为CVRP图特征输入到编码器。此外，本文采取通用的稀疏矩阵存储格式（coordinate format，COO）［30］来存储节点连接信息，COO是一个形状为2×E（E为边的数量）的矩阵，其每列存储图中某对源节点与目标节点之间的连接信息，该格式为大多数学者［31，32］采用。嵌入特征和COO矩阵组合成可用于计算处理的图数据类，本文使用目前被广泛使用的PyTorch-Geometric［33］库合成与处理上述图数据。

2.2 编码器

TE-GAT在编码过程中不仅考虑节点的信息，节点相连边的嵌入特征也参与到GAT信息传播的过程中。为节约计算资源，TE-GAT信息汇聚时，根据节点特征向量之间距离大小，只选取待更新节点最近的k个点作为邻居节点。图2描述了单层TE-GAT在GAT基础上如何使用最近邻算法更新边和节点信息的过程。在此基础上，本文提出如图3所示的编码器结构。

编码器以原始节点特征xi（i∈{0，1，2，…，n}）和原始边嵌入特征eij（i，j∈{0，1，2，…，n}）为输入，两种嵌入特征分别进入不同的全连接层，输出维度分别为dx和de的新嵌入特征，计算过程见式（3）（4）。

相对权重系数，计算过程见式（6）。TE-GAT层最后按式（7）更新节点i特征。

根据问题规模，编码器可包含多个TE-GAT层，设置2、3层可以满足大多数任务需求。编码器执行完所有TE-GAT层后，将所有节点特征按行顺序依次排列获得节点特征矩阵X。随后输入X到平均池化层，编码器按式（8）计算出可表征当前VRP问题的图嵌入特征向量xG。

2.3 解码器

解码器代替了LNS的破坏算子，生成带有后续修复算子接收顺序的破坏节点序列η={η1，η2，…，ηN}。解码器网络是一个能输出η的策略网络π，与传统破坏算子设计不同，π能在训练中改进启发式规则并能探索更多的参数空间，输入xG到π，其按式（9）计算不同η的概率分布并从中采样输出η。

p（π（［η1，η2，…，ηN］））=

p（η1）·p（η2|η1）·…·p（ηN|η1，…，ηN－1）（9）

其中：［·］表示有顺序排列的破坏节点序列η；p（π（η））表示策略网络π输出η的联合概率。解码器根据概率分布采样到η后，按序输入到修复算子重构路线。本文算法使用了单个贪心算子修复解，从而完成邻域搜索过程。该贪心算子按照最小成本插入的原则将η插入到破坏后的线路，构成新的解路线。

Google公司2014年提出的seq2seq［28］模型为解决断句问题，在目标字典中添加终止符，解码器在解码过程中遇到终止符或达到最大解码次数即停止解码，从而在训练中学习目标序列长度。借鉴于此，本文在解码器中添加了一种终止符学习机制，以此动态学习解码过程中破坏节点数目，解码器按图4所示结构执行解码过程。

当编码器输出特征矩阵X后，解码器在X向量维度方向末尾加上用于充当终止符的NV个虚拟节点特征xV，得到新的特征矩阵X′，具体节点个数NV根据问题规模决定。本文根据观察到的大量参数实验结果发现，当虚拟节点特征向量与图嵌入相同（即xV=xG）时，模型测试效果最佳，因此本文实验中所有虚拟节点特征向量均设置为图嵌入xG。

在进入下一解码单元前，解码器需要判断选择的破坏节点是否为终止节点。一旦终止节点被选择，对于该CVRP实例，本轮生成有效序列η的解码过程已经结束，但是模型在训练过程中需要同时并行训练批量不同CVRP實例，每个实例特征不同，对应合适的破坏节点数目也不尽相同，因此解码过程不可能恰好同时结束。解码过程结束较早的实例只能继续调用解码单元直到所有实例解码结束，因此解码器需要分别识别每个实例对应实际破坏数目和将不必要的解码单元考虑到后期梯度更新的计算过程。上述过程不仅增加了训练难度，而且显著降低了模型推理准确度，模型不再适合继续并行训练。

为实现批量训练以提高训练效率，本文设计了一种实时更新的mask机制：当前被选择ηt在mask矩阵对应位置所在元素更新为1，选择的破坏节点特征xi与当前GRU隐藏状态ht作为下一时间步GRU模块的输入，一旦解码器选择了终止节点，mask矩阵对应节点位置所在元素将被标记为-1，下一时间步，该终止节点（同时适用于所有节点）的注意力分数uti按式（12）更新，经过softmax函数后终止节点被选择的概率会与1充分接近，因此其他节点几乎无法再被解码器选择，修复算子可以直接剔除后续所有相同终止节点。所有时间步的解码过程结束后，解码器按式（13）计算联合概率p（π（η）），由于终止节点被选择的概率接近1，计算中其被取对数后接近于0，对后续的模型训练与推理造成的影响可以忽略不计。

实时更新的mask机制可以设置模型学习参数的范围。例如破坏节点数目范围［Nmin，Nmax］：通过设置GRU调用次数约束模型学习到的最大破坏节点数目Nmax。针对最小破坏节点数目Nmin，解码器在解码前将所有终止节点对应mask值都设置为1（即uti=－∞），经softmax函数输出的被选择概率接近于0。一旦已生成Nmin个待破坏节点，解码器就恢复终止节点的初始mask值（默认为0），进而可以选择到终止节点，继续终止符学习过程。

解码器完成上述所有解码任务后，最后输出破坏节点序列η。修复算子从η中删除所有虚拟节点，得到可用于与环境实际交互的破坏节点序列η′，之后严格按照η′中节点顺序依次修复路线。

3 基于PPO的强化学习训练算法

本文采用基于actor-critic架构的PPO算法训练模型，其核心思想在于：PPO每次更新策略时，会根据一种叫clipped surrogate objective的损失函数，对当前策略的优化幅度进行限制，从而保持网络优化过程的稳定性。本文将由编码器和解码器构成的TE-GAT模型作为训练算法框架的策略网络即actor，负责输出动作，再单独设计一个两层的前馈神经网络作为价值网络即critic，负责评估当前训练状态的价值函数。θ和分别表示actor和critic的网络参数。

3.1 马尔可夫过程定义

利用LNS算法框架解决VRP问题时，解路线会根据接受规则从当前解迭代到另一个解，此过程是一个马尔可夫决策过程（Markov decision process，MDP）［34］。在使用PPO算法训练神经网络前，需要对该MDP建模，具体定义MDP基本元素：状态、动作、奖励函数、折扣因子及状态转移函数等。由于PPO是基于策略梯度的强化学习算法，无须定义一个显式的状态转移函数，本文只讨论前四项基本元素：

b）奖励。在训练过程中的每一步，将奖励定义为这一步路线成本与上一步路线成本之差，具体定义见式（14）（15）。

Ccost（t）=Ddist（t）+C×K（14）

Rt=Ccost（t）-Ccost（t-1）（15）

其中：Ddist（t）表示当前第t时间步时所有解路线总距离；K表示当前解路线总数；C表示单辆车单次出车的固定成本；Ccost（t）表示第t时间步时所有解路线总距离与固定成本之和；Rt表示第t时间步环境给出的奖励。

c）折扣因子。折扣因子是一个介于0～1的实数，用于调节当前奖励和未来奖励之间的重要性比重。本文使用γ表示折扣因子，实验中设定为0.99。

d）动作。在状态st下，动作为解码器输出的有序排列破坏节点序列at。

3.2 基于经验回放的数据采样

为了充分利用数据，提高样本使用效率，本文使用经验回放（experience replay）［35］来收集训练数据。经验回放会构建一个回放缓冲区（replay buffer）：某一个特定策略与环境交互之后储存收集数据的地方。

具体到本文，从初始解出发，TE-GAT模型可以从环境中采样得到一系列四元组数据（状态st、动作at、奖励Rt、下一状态st+1），通过对MDP设置限定的步数，得到由若干四元组数据构成的轨迹。收集训练数据的过程：训练算法使用当前策略下的actor与环境不断交互，生成大量轨迹数据。为训练actor和critic，算法需要收集的数据与四元组数据不同，具体为状态st、动作at、对数动作概率ln pt及优势函数A^t等，由此组成新四元组数据。训练算法将轨迹数据包含的新四元组数据收集起来，打乱顺序按训练批量BS分别存储到回放缓冲区，后续训练网络参数时再从中采样数据。

3.3 价值网络和策略网络训练

针对critic的训练，本文按式（16）定义损失函数［36］：

其中：V（st）表示当前状态st和网络参数下critic的策略梯度；α为学习率。

针对actor的训练，本文采用PPO-截断LCLIP（θ）作为目标函数，按式（20）最大化LCLIP（θ）。

3.4 模拟退火算法

为提升学习效果，本文LNS算法框架根据模拟退火（simulated annealing，SA）［8］算法更新每次迭代的解，以此获得高质量的问题解作为训练数据。SA是一种迭代类算法，能够很好地应用于邻域搜索算法［37］。模型需要大量随机问题的较优问题解来指导学习，而SA在解决大规模问题方面能提供较优解，从而形成强化学习的环境［38～40］。具体针对训练过程中解的迭代即MDP轨迹上的每一步，若新产生的解在成本上优于现有解或者满足式（21），则可替代现有解进行下一次迭代。

D（t）dist

其中：rnd表示随机数，服从［0，1］的均匀分布；T（t）为MDP第t步时的温度，随迭代次数的增加，按照T（t+1）=αTT（t）计算更新，αT为温度更新参数。

算法1 TE-GAT训练算法框架

算法描述了使用基于PPO的强化学习算法训练TE-GAT模型的流程，当达到设定训练回合数Nepoch后，训练算法终止。通过引入PPO算法，能够有效地控制策略更新幅度，避免过大的策略变动，从而提高训练的稳定性和效果。

4 计算实验

本文通过三组实验验证TE-GAT模型的实用性和可行性。三组实验都需训练与测试模型：训练时，根据问题规模的不同，使用随机生成的CVRP实例训练对应模型。测试时，从公开数据集CVRPLIB选取对应规模标准算例测试。第一组实验包含四种规模CVRP，将TE-GATE与Google OR-tools、基于相同LNS框架的EGATE［23］及Random-LNS算法进行比较，测试本文模型的实际性能。第二组实验针对EGATE设置了六组破坏节点数目参数实验，验证学习算法参数的效用价值。第三组实验探索本文所提改进邻域搜索算法求解大规模CVRP问题时的寻优能力。

4.1 实验数据和参数设置

本文将考虑解决的CVRP问题规模设置为n，对训练中的每个CVRP实例，n个节点的坐标都在100×100或1 000×1 000的方格网络中按均匀分布随机生成，第一个生成的节点默认为仓库。根据对应测试标准算例设置需求区间与最大负载Ccap，例如标准算例E-n51-k5，每个需求点的需求满足［1，41］的均匀分布，每辆车的最大负载设为160。每一回合训练中，算法通过上述设定随机生成128个CVRP实例数据，不断迭代更新实例。每回合共收集了640 000个实例数据，每个实例数据分布相同，总共训练500回合。

对于不同规模训练任务超参数的设置，BS=100，Nmin均设为0，Nmax依次为5、10、20和25，NV依次为5、10、20和25。Nrollout=10，dx=64，de=16，TE-GAT层数为2，邻居数目k=5，模型优化器选择Adam［41］算法，學习率为3×10－4，测试评估批量大小为100。

实验主要在Ubuntu操作系统下使用一台配置单张2.20 GHz Intel Xeon Gold 5220R CPU和NVIDIA Geforce RTX 2080Ti GPU的服务器训练测试TE-GAT和其他对比模型。对问题规模在200节点以上的模型，额外使用一台搭载Tesla V100 GPU的服务器训练。本文利用PyTorch构造模型，使用Python 3.6编写。

4.2 实验结果分析

4.2.1 基于标准算例的对比实验

本组实验选取四种不同规模的CVRP问题，对应使用的测试标准算例是E-n51-k5，M-n101-k10、M-n200-k16和X-n251-k28。实验分别对比了Google OR-tools、Random-LNS和EGATE模型。其中Google OR-tools求解器内置了专门解决VRP问题的模块，Random-LNS所用邻域搜索基本框架与本文设计相同，但其邻域算子通过随机函数生成破坏节点。

实验中，EGATE与TE-GAT测试时输入数据批量设置成100，在SA框架下迭代1 000次。由于模型并行计算特性，本文将一份问题算例复制100批次，在一次模型评估时间下计算出100份测试结果，实验计算最终这100次测试的平均成本和最小成本。Random-LNS算法测试过程与前述一致。调用Google OR-tools时，基于局部搜索启发式算法求解问题算例，搜索时间设置为其他方法运行的最长时间。

表1列举TE-GAT、EGATE、Google OR-tools和Random-LNS在标准算例集上的测试结果。表中算法的组成结构为{模型名}{评估批次}-{迭代次数}，例如TE-GAT100-1K表示TE-GAT模型在实验中的评估批量为100，迭代次数为1 000。由表1可以看出，对于不同规模的CVRP问题，除求解器外，本文TG-GAT模型优化结果均优于其他方法。随着问题规模增大，TE-GAT测试结果的优势更显著，但与最优值的求解差距也在增大，在n=51、200的情况下其最小值的gap分别优于求解器1.19%、9.96%。其他规模下，两者gap相差不超过1.2%，但求解器搜索时间显著长于本模型。

表2展示了TE-GAT与EGATE在训练规模n=51、101、200及251的CVRP问题时模型所占用的显卡内存大小。随着问题规模从51～251的增大，EGATE模型占用显存增长速度显著快于TE-GAT模型，求解X-n251-k28时TE-GAT模型占用的显存与EGATE相差12.9倍，实验数据证明对于更大规模的问题，TE-GAT更适合用于训练。

图5描绘了不同问题规模下不同模型的平均成本收敛曲线图。由曲线图可知，与其他算法相比，TE-GAT在所有问题规模下收敛速度最快，收敛值也更接近最优值。问题规模越大， TE-GAT相对其他算法的平均收敛值差距与收敛速度逐渐增大。实验结果表明本文设计的终止符学习机制可以提升邻域搜索算子寻求最优解的能力。

4.2.2 破坏节点数目分析

本文选择学习破坏节点数目的一个潜在研究假设是：针对同规模CVRP问题，破坏节点数目与模型的寻优能力并不一直保持正相关。为验证假设，采用标准算例M-n101-k10测试具有不同固定破坏节点数目的EGATE模型，根据组成结构{模型名}-{破坏节点数目}依次定义6个模型，分别训练与测试模型，实验结果如表3和图6所示。

由表3和图6可知，伴随破坏节点从10～60的增长，破坏节点数目与模型求解性能数量关系呈先上升后下降趋势。针对平均值，EGATE-40求解结果最优，节点数目增加到60时，计算与最优值之间的gap，EGATE-60比EGATE-10增加了约1.1%。求解最小值时，对比EGATE-30，EGATE-40反而无法寻找到最优解。上述分析充分证明了破坏节点数目与模型求解性能并不一直呈正相关，破坏节点数目增加过多，模型求解性能逐渐下降，表明本文设计的终止符学习机制具有实际的效用价值。

4.2.3 求解大规模CVRP问题

为测试TE-GAT模型在大规模CVRP问题上的表现，本文选择X-n561-k42算例为测试数据集，每个需求点的需求满足［1，10］的均匀分布，每辆车的最大负载设为74。训练问题规模增大使得模型训练与推理所需计算资源较大，因此本文将训练回合数减小至200，测试批次减小到50。同时为扩大模型的视野域，将TE-GAT层数增大到3层，其他参数设定与前述实验相同。测试结果如图7所示，TE-GAT的求解表现优于OR-tools和SISR［42］算法，后者是当前解决CVRP问题较为优秀的手工启发式算法。TE-GAT寻找到的近似解与最优值差距仅为9.2%。

5 结束语

本文基于图神经网络与深度强化学习，提出了一个可学习的邻域搜索算子神经网络模型TE-GAT，以此混合LNS算法形成了一种求解组合优化问题的改进邻域搜索算法。TE-GAT模型由编码器和解码器组成，编码器使用图注意力网络对不同问题的图结构进行编码。解码器基于GRU解码单元配合终止符实现有序解码。终止符学习机制通过控制算法解码过程学习LNS算法参数。本文采用PPO算法训练邻域搜索智能模型，根据多种规模的CVRP标准算例，设置三组实验检验模型可行性与实用性。实验结果证明，本文改进邻域搜索算法在相同迭代次数或计算时间内，相较对比算法模型有更好的优化效果与收敛性。对基于深度神经网络的改进邻域搜索类算法，通过终止符学习算法参数是一条可行的优化方向。针对求解大规模组合优化问题，TE-GAT具有显著的性能优势与进一步求解更大规模组合优化问题的潜力。

实验考虑参数变化范围越大，相关计算量随之显著增加，收敛效果也会波动，因此本文模型在实际训练中学习的参数范围较小。进一步的研究方向可以考虑：a）面对学习参数数量范围较大的问题，设计能快速收敛的终止符学习机制；b）拓展本研究到其他组合优化问题，如TSP问题、JSP问题和多星多任务调度问题等。

參考文献：

［1］Korte B，Vygen J. Combinatorial optimization： theory and algorithms［M］. 5th ed. Berlin： Springer-Verlag，2012： 2-8.

［2］Dantzig G B，Ramser J H. The truck dispatching problem［J］.Mana-gement Science，1959，6（1）： 80-91.

［3］Muter I，Cordeau J F，Laporte G. A branch-and-price algorithm for the multidepot vehicle routing problem with interdepot routes［J］. Transportation Science，2014，48（3）： 425-441.

［4］蓝伯雄，吴李知. 铁路客运网络列车开行方案优化模型的列生成算法［J］. 运筹与管理，2012，21（1）： 1-10. （Lan Boxiong，Wu Lizhi. A column-gneration approach to line planning in rail passenger transport［J］. Operations Research and Management Science，2012，21（1）： 1-10.）

［5］Ehrgott M，Shao Lizhen，Schbel A. An approximation algorithm for convex multi-objective programming problems［J］. Journal of Global Optimization，2011，50（3）： 397-416.

［6］Halim A H，Ismail I. Combinatorial optimization： comparison of heuristic algorithms in traveling salesman problem［J］. Archives of Computational Methods in Engineering，2019，26（2）： 367-380.

［7］饒卫振，金淳. 求解大规模CVRP问题的快速贪婪算法［J］. 管理工程学报，2014，28（2）： 45-54. （Rao Weizhen，Jin Chun. An efficient greedy heuristic for solving large-scale capacitated vehicle routing problem［J］. Journal of Industrial Engineering and Enginee-ring Management，2014，28（2）： 45-54.）

［8］Yu V F，Lin S W，Lee W，et al. A simulated annealing heuristic for the capacitated location routing problem［J］. Computers & Industrial Engineering，2010，58（2）： 288-299.

［9］Wang Jiangjiang，Jing Youyin，Zhang Chunfa. Optimization of capacity and operation for CCHP system by genetic algorithm［J］. Applied Energy，2010，87（4）： 1325-1335.

［10］Loureno H，Martin O，Styutzle T，et al. Iterated local search： framework and applications［M］// Gendreau M，Potvin J Y. Handbook of Metaheuristics. Boston： Springer，2019： 129-168.

［11］李凯文，张涛，王锐，等. 基于深度强化学习的组合优化研究进展［J］. 自动化学报，2021，47（11）： 2521-2537. （Li Kaiwen，Zhang Tao，Wang Rui，et al. Research reviews of combinatorial optimization methods based on deep reinforcement learning［J］. Acta Automatica Sinica，2021，47（11）： 2521-2537.）

［12］Bello I，Pham H，Le Q V，et al. Neural combinatorial optimization with reinforcement learning［EB/OL］. （2016-11-29） ［2023-10-21］. https：//arxiv. org/abs/1611. 09940.

［13］Khalil E，Dai Hanjun，Zhang Yuyu，et al. Learning combinatorial optimization algorithms over graphs［C］// Proc of the 31st International Conference on Neural Information Processing Systems. Cambridge，MA： MIT Press，2017： 6351-6361.

［14］Kool W，Van H H，Welling M. Attention，learn to solve routing problems！ ［EB/OL］. （2018-03-22） ［2023-10-21］. https：//arxiv. org/abs/1803. 08475.

［15］Vaswani A，Shazeer N，Parmar N，et al. Attention is all you need［C］// Proc of the 31st International Conference on Neural Information Processing Systems. Cambridge，MA： MIT Press，2017： 6000-6010.

［16］Chen Xinyun，Tian Yuandong. Learning to perform local rewriting for combinatorial optimization［C］// Proc of the 33rd International Conference on Neural Information Processing Systems. Cambridge，MA： MIT Press，2019： 6281-6292.

［17］Yolcu E，Póczos B. Learning local search heuristics for Boolean satisfiability［C］// Proc of the 33rd International Conference on Neural Information Processing Systems. Cambridge，MA： MIT Press，2019： 7992-8003.

［18］Ye Haoran，Wang Jiarui，Cao Zhiguang，et al. DeepACO： neural-enhanced ant systems for combinatorial optimization ［EB/OL］. （2023-11-04）. https：//arxiv.org/abs/2309.14032.

［19］Choo J，Kwon Y D，Kim J，et al. Simulation-guided beam search for neural combinatorial optimization［C］// Proc of the 36th International Conference on Neural Information Processing Systems. Cambridge，MA： MIT Press，2022： 8760-8772.

［20］Zhou Jianan，Wu Yaoxin，Song Wen，et al. Towards omni-generalizable neural methods for vehicle routing problems ［EB/OL］. （2023-06-20）. https：//arxiv.org/abs/2305.19587.

［21］Geisler S，Sommer J，Schuchardt J，et al. Generalization of neural combinatorial solvers through the lens of adversarial robustness ［EB/OL］. （2022-03-21）. https：//arxiv.org/abs/2110.10942.

［22］Ropke S，Pisinger D. An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows［J］. Transportation Science，2006，40（4）： 455-472.

［23］Gao Lei，Chen Mingxiang，Chen Qichang，et al. Learn to design the heuristics for vehicle routing problem ［EB/OL］. （2020-02-20）. https：//arxiv.org/abs/2002.08539.

［24］Velikovic＇ P，Cucurull G，Casanova A，et al. Graph attention networks［EB/OL］. （2017-10-30） ［2023-10-21］. https：//arxiv. org/abs/1710. 10903.

［25］Wu Yaoxin，Song Wen，Cao Zhiguang，et al. Learning large neighborhood search policy for integer programming［C］// Proc of the 34th International Conference on Neural Information Processing Systems. Cambridge，MA： MIT Press，2021： 30075-30087.

［26］Cheng Hanni，Zheng Haosi，Cong Ya，et al. Select and optimize： learning to solve large-scale TSP instances［C］// Proc of the 26th International Conference on Artificial Intelligence and Statistics. New York： PMLR，2023： 1219-1231.

［27］Chen Mingxiang，Gao Lei，Chen Qichang，et al. Dynamic partial removal： a neural network heuristic for large neighborhood search ［EB/OL］. （2020-05-19） ［2023-10-21］. https：//arxiv.org/abs/2005.09330.

［28］Sutskever I，Vinyals O，Le Q V. Sequence to sequence learning with neural networks［C］// Proc of the 27th International Conference on Neural Information Processing Systems. Cambridge，MA： MIT Press，2014： 3104-3112.

［29］Mavrovouniotis M，Menelaou C，Timotheou S，et al. A benchmark test suite for the electric capacitated vehicle routing problem［C］// Proc of IEEE Congress on Evolutionary Computation. Piscataway，NJ： IEEE Press，2020： 1-8.

［30］Qiu Shenghao，You Liang，Wang Zheng. Optimizing sparse matrix multiplications for graph neural networks［C］// Proc of 34th International Workshop on Languages and Compilers for Parallel Computing. Cham： Springer International Publishing，2021： 101-117.

［31］Foo L G，Li Tianjiao，Rahmani H，et al. Unified pose sequence mode-ling［C］// Proc of IEEE/CVF Conference on Computer Vision and Pattern Recognition. Piscataway，NJ： IEEE Press，2023： 13019-13030.

［32］Réau M，Renaud N，Xue L C，et al. DeepRank-GNN： a graph neural network framework to learn patterns in protein-protein interfaces［J］. Bioinformatics，2023，39（1）： btac759.

［33］Fey M，Lenssen J E. Fast graph representation learning with PyTorch geometric［EB/OL］. （2019-03-06） ［2023-10-21］. https：//arxiv. org/abs/1903. 02428.

［34］Sutton R S，Barto A G. Reinforcement learning： an introduction［M］. 2nd ed. Cambridge，MA： MIT Press，2018.

［35］Mnih V，Kavukcuoglu K，Silver D，et al. Playing Atari with deep reinforcement learning［EB/OL］. （2013-12-19） ［2023-10-21］. https：//arxiv. org/abs/1312. 5602.

［36］胡尚民，沈惠璋. 基于強化学习的电动车路径优化研究［J］. 计算机应用研究，2020，37（11）： 3232-3235. （Hu Shangmin，Shen Huizhang. Research on electric vehicle routing problem based on reinforcement learning［J］. Application Research of Computers，2020，37（11）： 3232-3235.）

［37］Zhou Yangming，Xu Wenqiang，Fu Zhanghua，et al. Multi-neighborhood simulated annealing-based iterated local search for colored traveling salesman problems［J］. IEEE Trans on Intelligent Transportation Systems，2022，23（9）： 16072-16082.

［38］He Feng，Ye Qing. A bearing fault diagnosis method based on wavelet packet transform and convolutional neural network optimized by simulated annealing algorithm［J］. Sensors，2022，22（4）： 1410.

［39］Zhao Jiuxia，Mao Minjia，Zhao Xi，et al. A hybrid of deep reinforcement learning and local search for the vehicle routing problems［J］. IEEE Trans on Intelligent Transportation Systems，2020，22（11）： 7208-7218.

［40］Kosanoglu F，Atmis M，Turan H H. A deep reinforcement learning assisted simulated annealing algorithm for a maintenance planning problem［J/OL］. Annals of Operations Research. （2022-03-15）. https：//doi.org/10.1007/s10479-022-04612-8.

［41］Kingma D P，Ba J. Adam： a method for stochastic optimization［EB/OL］. （2014-12-22） ［2023-10-21］. https：//arxiv.org/abs/1412.6980.

［42］Christiaens J，Berghe G V. Slack induction by string removals for vehicle routing problems［J］. Transportation Science，2020，54（2）： 417-433.