DEG: Diffusion-Enhanced GFlowNet for Solving Vehicle Routing Problems

AI summary

Overview

Research area: Neural combinatorial optimization — specifically learned solvers for vehicle routing problems (TSP and CVRP) that combine Generative Flow Networks (GFlowNets) with diffusion models.

Technical level: Advanced. The paper assumes familiarity with GFlowNets (forward/backward policies, Trajectory Balance), diffusion noise schedules, and standard VRP neural-solver benchmarks.

Scope: The paper proposes DEG, a framework that uses GFlowNet sampling diversity to produce edge-level "backward" signals, corrupts them with a diffusion noise schedule, and denoises them inside the GFlowNet training objective, plus a Graph-Scale Adapter (GSA) for cross-scale generalization, evaluated on synthetic TSP/CVRP and on TSPLib/CVRPLib with up to 10,000 nodes.

What This Paper Is About

Neural solvers for vehicle routing problems tend to produce solutions with limited diversity, and GFlowNet-based solvers in particular fail to spread probability mass into high-reward regions, converging on sub-optimal route subsets. Diffusion models explore more broadly but existing diffusion-based VRP solvers are largely restricted to the TSP and depend on supervised edge-level noise signals. The paper's goal is to fuse the two paradigms — diffusion guiding GFlowNet exploration, GFlowNet supplying structured edge-level signals — so that flow expands toward promising routes and higher-quality solutions are found, including at large scale.

Key Contributions

1. Diffusion-Enhanced GFlowNet (DEG). A framework that exploits GFlowNet's inherent sampling diversity to generate edge-specific backward signals (rather than a single aggregated trajectory-level value), perturbs them with a diffusion noise schedule, and denoises them within the GFlowNet Trajectory Balance objective — preventing premature convergence and promoting flow expansion toward high-reward regions.

2. A theoretical characterization of the noise schedule. The paper derives the learning target induced at each noise level (Proposition 1), shows the early-stage target up-weights trajectories containing high-scoring edges with expected reward above reward-proportional sampling when the edge product is positively correlated with reward (Proposition 2), and bounds the KL divergence to the reward-proportional distribution as noise approaches full corruption (Theorem 1); for CVRP it notes an endpoint bias toward fewer routes (Remark 2).

3. Graph-Scale Adapter (GSA). An inference-time module that rescales test graphs by a factor proportional to the square root of the ratio of test to training node counts, aligning spatial statistics (e.g. average neighbor distance, observation radius) so a model trained on one size generalizes to much larger instances.

4. Extensive evaluation. Synthetic TSP and CVRP from 500 to 10,000 nodes, plus real-world TSPLib and CVRPLib benchmarks, with ablations isolating the backbone, the diffusion component, and GSA.

Main Findings

• TSP solution quality (no 2-opt): On synthetic instances from 500 to 10,000 nodes, DEG reports the lowest objective among GFlowNet- and diffusion-based baselines — e.g. objective 18.47 (gap 11.60%, 0.28 s) at 500 nodes, 47.82 (gap 18.63%, 3.06 s) at 3,000, and 94.67 (gap 24.94%, 16.47 s) at 10,000. The paper states improvements of up to 67.43%, 34.19%, 5.10%, 16.10%, 17.17% and 12.05% over GFACS, AGFN, DIFUSCO, T2T, Fast T2T and DEITSP respectively, and notes the margin widens with instance size.

• Diffusion-based baselines do not scale: DIFUSCO, T2T, Fast T2T and DEITSP produce no results at 5,000, 8,000 and 10,000 nodes within the 90-minute limit or GPU memory; DEG completes all of these.

• CVRP: DEG reports objective 69.76 (gap 10.48%, 0.45 s) at 500 nodes, 362.11 (gap -4.77%, 4.08 s) at 3,000, and 1,125.04 (24.95 s) at 10,000. It improves over GFACS by 13.63%, 18.43%, 7.92%, 8.33%, 12.58% and 21.83% and over AGFN by 1.82%, 3.21%, 1.86%, 2.00%, 1.05% and 1.35% across the six sizes. Against LEHD it lowers objective by 1.24%, 3.28% and 7.26% at 5,000, 8,000 and 10,000 nodes while the paper reports inference-time reductions of 13.46% to 95.58%.

• Real-world benchmarks: On TSPLib, DEG without post-processing records gaps of 14.37 (50–200 nodes) and 17.68 (200–1,000 nodes) versus 29.60/51.67 for GFACS and 19.41/25.51 for AGFN; with 2-opt it reaches 0.21 and 1.03, better than DIFUSCO*, T2T*, Fast T2T* and DEITSP* (0.96/3.45, 0.37/1.84, 0.26/1.26, 0.81/1.46). On CVRPLib (3k–16k instances) DEG has lower gaps than all baselines on L1, L2, A1, A2, G1, G2, B1 and B2 except L1, where LEHD is better (14.04 vs 19.64).

• Ablation confirms both components matter: Adding diffusion to the GFlowNet backbone cuts TSP-500 gap from 32.69% to 12.02% and CVRP-500 gap from 21.76% to 12.23%; adding GSA brings them to 11.60% and 10.48% and is what makes 8,000- and 10,000-node instances solvable at all (backbone and backbone+diffusion report no results there).

• Training/evaluation mismatch: The paper shows best large-scale results occur at earlier training stages, before the model overfits scale-specific spatial statistics; GSA is presented as the fix for this.

Methodology in Plain English

The pipeline has four moving parts.

First, a GFlowNet generates many diverse candidate routes and scores each one by its total distance. Every edge in the graph gets a reward equal to the average reward of the trajectories containing it, which is then z-scored and passed through the normal CDF so it lands in [0, 1]. This value, x₀, is the "edge-specific backward signal" — a heat map of which edges tend to appear in good routes, aggregated across many mediocre-but-varied samples rather than a single best tour.

Second, a diffusion-style noise schedule (linear, β from 10⁻⁴ to 0.02 over 6,000 training steps) progressively corrupts x₀ by adding Gaussian noise, producing a noisy backward policy x_t. Values are clamped to [δ, 1] with δ = 10⁻¹⁰ so trajectory weights stay strictly positive.

Third, training uses the GFlowNet Trajectory Balance loss, with the backward-policy term replaced by the product of these noisy per-edge values. Because early training is barely noised, the target is effectively reward × edge-quality product — exploitation of edges that worked before. As noise grows, the edge term washes out and the target relaxes toward plain reward-proportional sampling — exploration. Theory in the appendix describes this interpolation.

Fourth, because everything is trained on 100-node instances but evaluated up to 10,000, the GSA rescales the test graph's distances and sparsity factor by a factor proportional to √(|V_test| / |V_train|), so the model sees spatial statistics resembling its training distribution. Decoding then proceeds by sampling a |V|×|V| edge-probability "heatmap" step by step, masking visited nodes and infeasible capacity moves.

Why This Matters

The work shows that two generative-model families with complementary weaknesses can be composed rather than merely compared: GFlowNet supplies structured, edge-level training signal (no optimal solutions needed, unlike supervised diffusion solvers), and diffusion supplies the exploration pressure GFlowNets lack. It also extends diffusion-style reasoning for routing beyond the TSP, which prior diffusion methods did not handle.

Real-world applications named in the paper:

• Logistics and distribution planning — dispatching a depot-rooted fleet under capacity constraints.
• Agricultural field operations — routing machinery across fields.
• Urban delivery systems — sequencing customer visits in dense city networks.

Industry relevance: the practical claim is a compute/quality trade-off. On the 10,000-node TSP, LKH took 5,350.91 s per instance versus 16.47 s for DEG, and on the 10,000-node CVRP, 24.95 s versus LEHD's 556.88 s — with the caveat that DEG's gaps to best-known solutions remain substantial (about 25% on large synthetic TSP). For settings where near-optimal routes are needed in seconds rather than minutes, that is a meaningful operating point.

Future Directions

• Closing the residual optimality gap at extreme scale. Gaps of roughly 25% on 10,000-node TSP after 16.47 s of inference leave clear headroom versus LKH's much longer runs; whether more noise steps, longer training, or hybrid post-processing closes this is untested here.

• CVRP endpoint bias. Remark 2 notes that at full corruption the CVRP target favors trajectories with fewer routes, so reward-proportionality holds only among solutions with equal route counts. Correcting that bias is an open design question.

• Principled scale adaptation. GSA is a heuristic rescaling with no reported optimality theory; learning the scale adapter, or training across mixed scales (explored in the appendix), could replace it.

• Transfer beyond routing. The authors report preliminary applicability to other combinatorial optimization problems in the appendix; how far the edge-signal-plus-noise recipe generalizes to other structured generation tasks is unresolved.

Target Audience

Graduate students and researchers in machine learning and operations research working on neural combinatorial optimization, generative modeling (GFlowNets, diffusion), or structured prediction over graphs. It is also relevant to practitioners building fast large-scale routing heuristics who can trade a few percent of solution quality for orders-of-magnitude inference speedup, and who want a route into the GFlowNet literature without starting from the TSP-only diffusion baselines.

Authors’ abstract

Traditional neural solvers for solving vehicle routing problems (VRPs) often suffer from limited solution diversity, motivating the development of Generative Flow Network (GFlowNet)-based models. However, the effectiveness of these models is frequently constrained by insufficient flow expansion in high-reward regions, limiting their ability to distribute probability across promising solution routes. Deeper exploration could yield superior results. Diffusion models, in contrast, provide stronger structural guidance for exploration. These two paradigms are naturally complementary: GFlowNet can supply edge-level signals for diffusion to embed, while diffusion can guide broader exploration. Leveraging this synergy, we propose Diffusion-Enhanced GFlowNet (DEG), a novel framework that integrates GFlowNet with a diffusion model to encourage richer flow expansion toward high-reward regions and derive higher-quality solutions. Specifically, DEG exploits GFlowNet's inherent diversity to generate edge-specific backward signals, applies the stochastic noise schedule of diffusion to perturb these signals, and then denoises them within the GFlowNet paradigm. To further improve scalability, we introduce a specialized decoder capable of dynamically adapting to diverse problem scales. Extensive experimental evaluations on synthetic and real-world datasets, including instances with up to 10,000 nodes, demonstrate that DEG consistently achieves favorable performance compared to baseline methods.