DEG: Diffusion-Enhanced GFlowNet for Solving Vehicle Routing Problems¶
会议: NeurIPS 2026
arXiv: 2610.39512
代码: https://github.com/ZHANG-NI/DEG
领域: 优化/理论
关键词: GFlowNet, 扩散模型, 车辆路径问题, 组合优化
一句话总结¶
针对传统 GFlowNet 求解车辆路径问题（VRP）在高奖励区域流扩展受限、以及扩散模型缺乏自适应奖励信号的缺陷，本文提出 DEG 框架，利用 GFlowNet 轨迹多样性构建边级别反向信号并引入连续高斯加噪-去噪轨迹平衡学习，配合图尺度自适应模块 GSA，在高达 10,000 节点的合成与真实大规模 VRP/TSP 实例上均显著超越现有神经与启发式基线。
研究背景与动机¶
车辆路径问题（VRP）及其特例旅行商问题（TSP）是运筹学与工业物流中的经典 NP-hard 组合优化问题。传统的精确算法与元启发式（如 LKH）在大规模求解时面临高昂的计算开销。近年来，基于深度学习的神经求解器发展迅速，主要涵盖自回归（AR）与非自回归（NAR）两类范式。AR 方法通过 Transformer 等注意力机制逐步构建路径，解质量高但由于自回归串行解码存在严重的时间瓶颈，难以扩展到超大规模图；NAR 方法虽能单次前向并行生成完整解，但在复杂拓扑下的搜索质量较弱。
为提高 NAR 求解器的解空间探索质量，生成流网络（GFlowNet）作为概率变分推理算法被引入组合优化，旨在学习一种能按奖励分布成比例采样的生成策略。然而，现有 GFlowNet 求解器往往因局部最优而过早收敛，在高奖励区域（high-reward regions）无法充分进行流扩展（flow expansion），限制了对全局更优解的探索。另一方面，扩散概率模型（Diffusion Models）具有极强的全局结构引导与分布探索能力，但现有组合优化扩散方法多依赖离线监督学习或高质量标注，且基本局限于 TSP，无法自然扩展到带复杂容量约束的 CVRP。
这两种生成范式存在天然的互补性：GFlowNet 固有的轨迹多样性能在无监督状态下沉淀出全局边级别的奖励分布先验；而扩散模型的渐进加噪过程则能够平滑引导策略分布，打破局部早熟陷入。核心 idea：将 GFlowNet 固有的解采样多样性转化为边级别的连续反向引导信号，以此作为扩散过程的先验噪声基底，并在 GFlowNet 的轨迹平衡损失（Trajectory Balance）下对扰动后的信号联合去噪与流拓展优化，实现从早期结构利用到全局充分探索的平滑演进。
方法详解¶
整体框架¶
DEG 架构包含边级反向信号提炼模块、前向图神经网络（GNN）预测器、扩散加噪调度器、轨迹平衡（TB）损失联合优化器，以及用于跨尺度推理泛化的图尺度自适应器（Graph-Scale Adapter, GSA）。
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
A[输入图 G: 坐标与距离矩阵] --> B[GNN 前向策略网络 eta]
B --> C[GFlowNet 采样生成多样化轨迹集合 T]
C --> D[边级反向信号提炼 R_e 与正态 CDF 映射 x0]
D --> E[扩散加噪调度器: 注入高斯噪声 xt]
E --> F[截断约束 xt~ 与轨迹反向权重 Wt]
B --> G[前向轨迹构建概率 PF 与配分函数 Z]
F --> H[扩散增强轨迹平衡损失 L_TB 联合优化]
G --> H
A --> I[推理阶段: 图尺度自适应器 GSA]
I --> J[动态调整近邻距离与稀疏因子 w]
J --> K[大规模图高效并行解码]关键设计¶
1. 边级别反向信号构造（Edge-specific Backward Signals）
传统的 GFlowNet 训练多采用标量轨迹级反向信号，导致结构维度的信用分配（credit assignment）严重塌缩。DEG 利用 GFlowNet 自身前向策略采样的 \(m\) 条多样化候选轨迹集合 \(\mathcal{T}=\{\tau_1, \ldots, \tau_m\}\)，首先计算每条轨迹相对于平均路径长度的相对奖励：
$\(-\log R(\tau_k) = D(\tau_k) - \frac{1}{m}\sum_{l=1}^{m} D(\tau_l)\)$
其中 \(D(\tau_k)\) 表示轨迹的总欧氏距离。在此基础上，定义单条边 \(e\) 的统计奖励为包含该边的所有采样轨迹的平均奖励：
$\(R(e) = \frac{1}{|\{\tau_k \in \mathcal{T} \mid e \in \tau_k\}|} \sum_{\tau_k \in \mathcal{T}, e \in \tau_k} R(\tau_k)\)$
为了在不同实例间实现尺度统一，对 \(R(e)\) 执行 z-score 标准化：\(\hat{R}(e) = \frac{R(e) - \mu_R}{\sigma_R}\)。随后，采用标准正态分布的累积分布函数（CDF）\(\Phi(\cdot)\) 将标准化分数映射为 \([0, 1]\) 范围内的有界置信度数值：
$\(x_0[e] = \Phi(\hat{R}(e))\)$
该连续边级先验矩阵 \(x_0\) 构成了后续扩散过程的干净信号基底。
2. 连续高斯噪声调度与反向轨迹重赋权（Continuous Noise Schedule & Trajectory Weighting）
在训练步 \(t \in [1, I]\) 中，引入线性衰减扩散调度参数 \(\bar{\alpha}_t = \prod_{k=1}^t (1 - \beta_k)\)，向边信号注入连续高斯噪声：
$\(x_t[e] = \sqrt{\bar{\alpha}_t} x_0[e] + \sqrt{1 - \bar{\alpha}_t} \epsilon[e], \quad \epsilon[e] \sim \mathcal{N}(0, 1)\)$
为保证数值稳定性与 GFlowNet 反向权重的正定性，对扰动信号进行截断操作：
$\(\tilde{x}_t[e] = \max(\mathrm{clamp}(x_t[e], 0, 1), \delta), \quad \delta = 10^{-10}\)$
在计算轨迹平衡损失时，不再使用固定的均匀反向转移，而是将状态转移 \(s_{k-1} \to s_k\) 对应边的反向权重乘积作为非归一化轨迹权重：
$\(W_t(\tau) = \prod_{e \in \tau} \tilde{x}_t[e]\)$
3. 图尺度自适应器（Graph-Scale Adapter, GSA）
针对非自回归图神经网络在固定规模（如 100 节点）训练后直接迁移至大规模图（如 1,000 至 10,000 节点）时面临的空间密度与感知域失配问题，作者设计了 GSA 解码模块。当图规模由 \(|\mathcal{V}_{\text{train}}|\) 扩大至 \(|\mathcal{V}_{\text{test}}|\) 时，节点的平均邻近距离从 \(\frac{1}{\sqrt{|\mathcal{V}_{\text{train}}|}}\) 急剧缩减至 \(\frac{1}{\sqrt{|\mathcal{V}_{\text{test}}|}}\)。GSA 引入动态重缩放因子 \(\alpha \propto \sqrt{\frac{|\mathcal{V}_{\text{test}}|}{|\mathcal{V}_{\text{train}}|}}\)，动态调整坐标欧氏距离尺度与 \(k\)-近邻稀疏化阈值 \(w\) 的感知半径，使得测试阶段的特征感受野统计量严格对齐于训练分布，从而杜绝大图推理时的早期过拟合退化。
扩散增强与轨迹平衡损失¶
DEG 在轨迹平衡目标下联合优化前向策略参数 \(\theta\) 与可学习配分函数 \(Z(\mathcal{G}; \theta)\)： $\(\mathcal{L}(\mathcal{T}; \theta) = \sum_{k=1}^{m} \left( \log \frac{Z(\mathcal{G}; \theta) P_F(\tau_k; \theta)}{R(\tau_k) W_t(\tau_k)} \right)^2\)$ 理论分析表明，在总体期望下，加噪水平 \(t\) 对应的全局最优策略满足： $\(P_F^t(\tau) \propto R(\tau) \exp\left( \sum_{e \in \tau} \mathbb{E}_\epsilon [\log \tilde{x}_t[e]] \right)\)$ 在训练初期（\(\bar{\alpha}_t \to 1\)），噪声极低，目标偏向 \(P_F^0(\tau) \propto R(\tau) \prod_{e \in \tau} x_0[e]\)，促使模型集中利用高置信度优质边，加速向高奖励区域聚集；随着训练推进（\(\bar{\alpha}_t \to 0\)），边特定偏置逐渐衰减，对于 TSP，学习目标严格收敛至无偏奖励采样 \(P_F^T(\tau) \propto R(\tau)\)；对于 CVRP，目标收敛至 \(P_F^T(\tau) \propto R(\tau) e^{c_T K(\tau)}\)（\(c_T < 0\)），在兼顾奖励采样的同时自然倾向于惩罚冗余车辆数 \(K(\tau)\)。此机制实现了从前期聚焦利用到后期全局充分流扩展的自然平滑过渡。
实验关键数据¶
1. 合成大规模 TSP 实例对比（无 2-opt 后处理）¶
所有神经网络求解器均仅在 100 节点合成实例上训练，直接泛化测试规模达 500 至 10,000 节点（Gap 基于 LKH 启发式，数值越小越优；Obj. 为平均路径长度；“–” 表示超过 90 分钟超时或显存溢出 OOM）：
| 模型 | 500 Obj. | 500 Gap(%) | 1000 Obj. | 1000 Gap(%) | 3000 Obj. | 3000 Gap(%) | 5000 Gap(%) | 8000 Gap(%) | 10000 Gap(%) | 10000 Time(s) |
|---|---|---|---|---|---|---|---|---|---|---|
| LKH | 16.55 | – | 23.14 | – | 40.31 | – | – | – | – | 5350.91 |
| GFACS (AISTATS'25) | 22.97 | 38.79 | 38.58 | 66.72 | 69.63 | 72.74 | 88.91 | 83.28 | 85.85 | 326.04 |
| AGFN (ICLR'25) | 19.04 | 15.05 | 27.10 | 17.11 | 55.37 | 37.36 | 56.12 | 79.89 | 89.83 | 14.07 |
| DIFUSCO (NeurIPS'23) | 19.12 | 15.17 | 27.70 | 19.71 | 50.39 | 25.01 | – | – | – | – |
| T2T (NeurIPS'23) | 18.91 | 14.26 | 27.31 | 18.02 | 56.99 | 41.38 | – | – | – | – |
| Fast T2T (NeurIPS'24) | 18.76 | 13.35 | 27.25 | 17.76 | 57.73 | 43.22 | – | – | – | – |
| DEITSP (KDD'25) | 18.64 | 12.63 | 27.11 | 17.16 | 54.37 | 34.81 | – | – | – | – |
| DEG (本文) | 18.47 | 11.60 | 26.46 | 14.35 | 47.82 | 18.63 | 22.57 | 26.16 | 24.94 | 16.47 |
在 500 至 3,000 节点尺度下，DEG 显著优于所有对比 GFlowNet 与扩散基线；在 5,000 至 10,000 节点超大规模下，传统扩散求解器均因显存暴涨无法完成推理，而 DEG 仅需 16.47 秒即完成 10,000 节点求解，相比同类 GFlowNet AGFN 差距（89.83%）缩减超过 64 个百分点。
2. 合成 CVRP 跨尺度性能对比¶
对比包含代表性自回归重解码模型 LEHD 与 POMO，以及先进 GFlowNet 求解器 GFACS、AGFN（Gap 相对 LKH）：
| 模型 | 500 Obj. | 500 Gap(%) | 1000 Obj. | 1000 Gap(%) | 3000 Obj. | 3000 Gap(%) | 5000 Obj. | 8000 Obj. | 10000 Obj. | 10000 Time(s) |
|---|---|---|---|---|---|---|---|---|---|---|
| LKH | 63.14 | – | 119.52 | – | 380.26* | – | 642.95* | – | – | – |
| GFACS (AISTATS'25) | 80.77 | 27.92 | 158.97 | 33.01 | 393.27 | 3.42 | 650.62 | 1038.30 | 1439.19 | 607.26 |
| AGFN (ICLR'25) | 71.05 | 12.53 | 133.97 | 12.09 | 368.97 | -2.97 | 608.58 | 917.24 | 1140.46 | 18.58 |
| POMO (NeurIPS'20) | 80.21 | 27.04 | 164.17 | 37.36 | 1094.48 | 187.82 | 1438.97 | – | – | – |
| LEHD (NeurIPS'23) | 64.68 | 2.44 | 122.85 | 2.79 | 355.95 | -6.39 | 603.89 | 938.06 | 1213.13 | 556.88 |
| DEG (本文) | 69.76 | 10.48 | 129.67 | 8.49 | 362.11 | -4.77 | 596.43 | 907.65 | 1125.04 | 24.95 |
DEG 在 5,000、8,000 和 10,000 规模的 CVRP 上超越了强自回归基线 LEHD，路径成本分别优化 1.24%、3.28% 和 7.26%，同时推理时间在 10,000 节点实例上从 LEHD 的 556.88 秒暴降至 24.95 秒（提速 95.5%）。
3. 真实世界数据集泛化表现（CVRPLib 经典基准）¶
在包含 3,000 至 16,000 客户节点的实际物流拓扑分布测试集上，DEG 展现出优越的泛化稳定性：
| 实例规模 | GFACS Gap(%) | AGFN Gap(%) | LEHD Gap(%) | POMO Gap(%) | DEG (本文) Gap(%) |
|---|---|---|---|---|---|
| L1 (3k) | 120.21 | 1144.20 | 14.04 | 75.30 | 19.64 |
| L2 (4k) | 1800.04 | 27.88 | 26.30 | 78.16 | 26.08 |
| A1 (6k) | 114.37 | 29.64 | 18.90 | 112.27 | 14.95 |
| A2 (7k) | 238.19 | 24.58 | 26.40 | 159.22 | 23.80 |
| G1 (10k) | 278.11 | 142.65 | 27.23 | – | 23.18 |
| G2 (11k) | 2242.09 | 27.21 | 38.45 | – | 24.41 |
| B1 (15k) | 348.54 | 20.63 | 35.94 | – | 17.04 |
| B2 (16k) | 2634.74 | 160.24 | 40.76 | – | 23.47 |
4. 关键模块消融实验（Ablation Study）¶
在 TSP 和 CVRP 上逐步引入扩散增强（Diffusion）与图尺度自适应器（GSA）：
| 任务 | 模块变体 | 500 Gap(%) | 1000 Gap(%) | 3000 Gap(%) | 5000 Gap(%) | 8000 Gap(%) | 10000 Gap(%) |
|---|---|---|---|---|---|---|---|
| TSP | Backbone (纯 GFlowNet) | 32.69 | 53.03 | 60.80 | 76.81 | – | – |
| + Diffusion (扩散扰动与去噪) | 12.02 | 15.56 | 20.19 | 25.33 | – | – | |
| + GSA (完整 DEG) | 11.60 | 14.35 | 18.63 | 22.57 | 26.16 | 24.94 | |
| CVRP | Backbone (纯 GFlowNet) | 21.76 | 24.34 | 2.35 | – | – | – |
| + Diffusion (扩散扰动与去噪) | 12.23 | 10.74 | -2.96 | – | – | – | |
| + GSA (完整 DEG) | 10.48 | 8.49 | -4.77 | -7.24 | - | - |
消融表明，边级扩散信号的注入极大降低了各尺度下的 Optimality Gap（TSP 500 尺度从 32.69% 降至 12.02%）；而 GSA 模块有效解决了 5,000 节点以上的显存与空间分布退化问题，是模型能够无障碍扩展至 10,000 节点的核心保障。