《Neural Networks》：Learning Constraints-Based Adaptive Hypergraph Neural Networks for Solving Vehicle Routing Problems
编辑推荐：
据研究人员所知，这是超图学习在车辆路径问题中的首次应用，用于捕获高阶节点表示。研究人员开发了一种端到端超图网络，具有自适应超边构造机制，可将路径约束动态纳入超边集合，从而在编码器内实现约束感知的超图表示学习。研究人员提出了一种双指针解码器，整合全局与局部注意力
据研究人员所知，这是超图学习在车辆路径问题中的首次应用，用于捕获高阶节点表示。研究人员开发了一种端到端超图网络，具有自适应超边构造机制，可将路径约束动态纳入超边集合，从而在编码器内实现约束感知的超图表示学习。研究人员提出了一种双指针解码器，整合全局与局部注意力，以在逐步决策过程中平衡探索与利用。
## 约束感知超图神经网络：为车辆路径问题引入高阶结构表示
### 一、研究背景与问题
车辆路径问题（Vehicle Routing Problem, VRP）是运筹学与物流领域的经典组合优化问题，其核心目标是在满足各类约束（如车辆容量、时间窗等）的前提下，确定一组从仓库出发、服务所有客户节点并返回仓库的最优路径集合。VRP被广泛认为是NP-hard问题，随着问题规模的扩大，解空间呈组合爆炸式增长，传统精确算法（如线性规划、整数规划）往往在可接受时间内难以求得最优解。为此，近似方法（如局部搜索、遗传算法等）被广泛采用，但其性能高度依赖人工设计的算子与问题参数的精确估计，在不确定性场景下鲁棒性不足。
近年来，基于机器学习的方法为组合优化提供了新的解决思路。其中，以注意力模型（Attention Model, AM）为代表的序列到序列构造式方法，通过强化学习（Reinforcement Learning, RL）训练策略网络，以自回归方式逐步生成解。另一类方法基于图神经网络（Graph Neural Networks, GNN）利用VRP的天然图结构进行节点表示学习。然而，现有GNN方法大多依赖成对关系（pairwise relations）的消息传递机制，存在三方面显著局限：其一，VRP的特征空间有限，制约了节点表示的表达能力；其二，路径特有的约束（如容量、时间窗等）在图的表示学习过程中未被充分利用，形成性能瓶颈；其三，成对图模型难以捕获高阶（high-order）与序列信息。尤为关键的是，容量、时间窗、路径时长等约束并非由单条边或孤立客户对决定，而是由一组客户及其累积状态共同决定。成对稠密注意力虽能连接所有节点对，却无法保留约束组的语义身份，且堆叠成对层易导致节点表示模糊与过平滑（over-smoothing）。因此，亟需一种能将约束诱导的客户群作为一阶结构对象进行建模的表示机制。
### 二、研究内容与贡献
针对上述问题，研究人员提出了一种新颖的端到端超图学习框架，将超图学习引入车辆路径问题的求解，发表于《Neural Networks》。该框架在编码器中通过自适应超边构造动态融入问题特定约束信息，利用多注意力头机制融合超边表示与原始节点特征，实现约束感知的图表示学习；在解码器中提出双指针机制，结合当前节点状态与历史路径状态进行注意力计算，以平衡探索与利用。模型通过REINFORCE算法和自批评基线进行RL训练，无需最优标签即可持续提升解质量。实验表明，该框架在VRP及其变体上取得了最高可达7.38%的性能提升。
### 三、主要技术方法
研究人员所提框架的核心方法包括三部分。第一，图特征增强：受POMO启发，通过旋转、对称、折叠等变换对节点坐标进行数据增强，并引入极坐标特征，丰富节点输入表示。第二，基于约束感知的自适应超边构造编码器：每个主节点（master node）通过线性层映射到高维空间，以点积相似度超过阈值δ的节点作为候选集，并按特定约束类型构造异构超边，通过节点相关损失与约束损失的复合损失函数动态优化超边重建；随后利用多头注意力融合超边嵌入与节点嵌入，完成约束感知的表示学习。第三，双指针解码器：提出路径记录器（route recorder）存储历史访问节点表示，分别计算当前状态与历史状态两类注意力得分，加权融合概率分布以实现鲁棒的自回归解生成。
### 四、研究结果
#### 4.1 模型性能
在随机生成的CVRP20、CVRP50、CVRP100数据集上，研究人员评估了模型性能。结果显示，超图模型在中小规模数据集上建立了端到端模型的新SOTA结果。与其他端到端模型相比，所提模型取得了0.82%至7.38%的性能提升。在CVRP20上，所提方法配合8倍数据增强的gap达到0.49%；CVRP50上达到0.19%。在CVRPTW任务上，得益于超边构造中对下一节点到达状态的显式惩罚项，所提模型的改进幅度远超标准CVRP——例如CVRPTW100上目标值从E-GAT的76.87与GASE的69.63大幅降至44.93，验证了时间窗可行性并非纯成对空间关系，约束感知的超边为解码器提供了有用的组级信号。在CVRPLIB基准测试中，所提模型的平均gap为5.01%，优于E-GAT的7.51%和POMO×8Aug的5.30%。XML100数据集分析进一步表明，在集群（clustered）和混合（mixed）客户分布下，超图模型优于POMO，说明超边编码器在几何聚簇分布下能有效缓解稠密成对注意力导致的表示过平滑问题。鲁棒性实验中，在需求分布扰动下，所提模型的性能下降为3.42%~6.38%，优于E-GAT的2.27%~8.24%，展示了较好的抗干扰能力。
#### 4.2 消融研究
研究人员通过移除各创新模块进行了消融实验。去除动态超图模块后，CVRP20的gap从0.65%增至2.95%，CVRP50从2.60%增至7.42%，退化幅度最大，证明约束感知超边身份的保持对解码器信息传递起到关键作用。去除双指针记录器后CVRP50的gap从2.60%增至6.64%，验证了路径历史上下文在利用高阶表示进行序列构造中的必要性。数据增强模块在中小规模数据上的贡献不显著，且会降低收敛速度，其原因可能在于小规模问题中有限的动作空间对注意力得分扰动较为敏感。
#### 4.3 超参数敏感性分析
研究人员对超边重建阈值δ和正则化系数λ进行了网格搜索。结果表明，δ=0、λ=0.2时性能最优。过大的阈值或过强的L1正则化会减少每条超边的节点数，弱化编码器表示能力；过小的阈值或过弱的L1正则化则会使超边包含过多节点，导致超图表示的过平滑。这一敏感性模式反映了超边阈值在约束选择性与信息保持之间的权衡作用。
### 五、讨论与结论翻译
研究结论指出：本文提出了一种基于编码器-解码器架构的端到端框架以求解路径问题。在编码器中，为每个节点构造约束导向超边以进行数据增强并增强节点表示学习，并通过超图重建损失进一步优化；在解码器中引入双指针机制，同时结合路径记录器存储的部分解状态与当前节点状态进行多头注意力解码，经掩码与加权聚合渐进式构建路径解。本工作的主要意义在于将约束感知的高阶表示视角引入神经路径求解领域。超图学习通过保留约束诱导的客户组来结构化输入表示，而强化学习通过无标签的路径级反馈优化序列路径构造策略。实验结果表明，该方法在中小规模CVRP实例上效果显著，在CVRPTW上提升明显，在CVRPLIB上的平均gap与强神经基线相当。同时也揭示了局限性：在固定规模超图编码器配合贪婪解码时，大规模迁移仍具挑战。未来工作将聚焦分层超图构造与更强的解码/搜索策略。
