Constraints Matrix Diffusion based Generative Neural Solver for Vehicle Routing Problems¶

日期: 2026-03-08
arXiv: 2603.07568
代码: 无
领域: 图像生成
关键词: vehicle routing, graph diffusion, constraint matrix, autoregressive solver, combinatorial optimization

一句话总结¶

用图扩散模型生成约束矩阵作为拓扑先验掩码，融入自回归 VRP 求解器——通过局部/全局双指针解码器缓解全连接注意力的过平滑问题，在 CVRPlib 378 种组合配置上达到 SOTA。

研究背景与动机¶

领域现状: 基于生成 AI 的 VRP 求解器分为自回归方法（类 Transformer 序列生成）和扩散方法（一次性生成边概率热图），前者速度快但缺乏约束感知，后者需大量后处理。
现有痛点: (a) 自回归模型的全连接注意力在节点表征相似时过平滑，解码退化为近随机采样；(b) RL 训练仅在完整轨迹结束时获得稀疏奖励，长决策序列下误差累积；(c) 扩散方法依赖高质量标签且在复杂约束下容易产生不可行解。
核心 idea: 将最优解的子路径成员关系编码为二值约束矩阵 \(\mathcal{M} \in \{0,1\}^{N \times N}\)，用离散噪声图扩散学习重构，生成的约束矩阵作为拓扑掩码注入自回归编码器和解码器。

方法详解¶

整体框架¶

数据增强（几何对称+需求置换） → 离散图扩散模型学习约束矩阵 → 掩码图编码器（冻结全局 GAT + 可训练局部 Masked GAT 融合） → 双指针解码器（局部+全局注意力融合）→ RL 训练（REINFORCE）。

关键设计¶

约束矩阵定义与扩散:
- 将最优 CVRP 解的子路径成员关系编码为对称二值矩阵
- 离散前向加噪：通过状态转移矩阵 \(\mathbf{Q}_t\) 逐步破坏矩阵
- 反向去噪：各向异性 GNN 学习从噪声恢复约束矩阵
- 测试集 AUC > 0.95，约束矩阵预测精度高
掩码图编码器:
- 全局分支：冻结的预训练 GAT，全连接注意力
- 局部分支：按约束矩阵掩码的 GAT，仅在同子路径节点间传递信息
- 融合：\(RO^{Encode} = \text{Mean}(\text{MLP}(h^\ell + h^{GAT}))\)
- 局部掩码限制消息传递范围 → 缓解过平滑
双指针融合解码器:
- 局部指针：仅在约束矩阵指示的邻域内注意力
- 全局指针：在所有未访问节点上注意力
- 双指针输出融合为上下文向量，结合约束先验和全局信息
数据增强:
- 几何增强：4 种轴对称变换（水平/垂直/对角线）
- 需求增强：子路径内需求反转/随机重分/循环置换
- 不同坐标和需求的实例映射到相同约束矩阵 → 鲁棒性

实验关键数据¶

主实验¶

首次在 CVRPlib XML100 数据集上系统评估——378 种组合配置（4 个维度：需求分布 × 节点分布 × 容量 × 规模），达到 SOTA。

方法类别	特点	本文优势
纯自回归 (POMO等)	节点相似时退化	约束掩码缓解过平滑
纯扩散	需后处理，复杂约束难处理	融合框架端到端
启发式改进	需搜索，实时性差	推理速度快

消融实验¶

配置	效果
w/o 约束矩阵掩码	过平滑显著，性能下降
w/o 双指针（仅全局）	相似节点区分能力弱
w/o 数据增强	泛化性下降
Full model	SOTA across 378 configs

关键发现¶

约束矩阵预测 AUC > 0.95，扩散模型能有效学习 VRP 的约束结构
双指针融合显著改善相似节点区分——局部提供约束先验，全局保留探索
在跨分布（需求/几何分布不同）测试中鲁棒性远超现有方法

亮点与洞察¶

约束矩阵抽象巧妙: 将组合优化的可行性约束编码为图结构先验，思路可推广到其他约束优化问题
扩散+自回归融合: 取两者之长——扩散学结构先验，自回归保证可行性和效率
过平滑诊断准确: 精确定位全连接注意力在 VRP 中的核心瓶颈并给出有效解

局限性 / 可改进方向¶

扩散模型预测约束矩阵需要高质量标签（HGS 启发式解），标签获取成本高
仅在 CVRP 上验证，VRPTW 等时间窗约束的扩展未测试
扩散推理增加了额外时间开销

评分¶

新颖性: ⭐⭐⭐⭐ 约束矩阵扩散+自回归融合的思路新颖
实验充分度: ⭐⭐⭐⭐⭐ 378 种组合配置的系统评估非常全面
写作质量: ⭐⭐⭐⭐ 层次清晰，公式详实
价值: ⭐⭐⭐⭐ 对组合优化的神经求解器设计有重要参考