Source-linked AI summary
DEG: Diffusion-Enhanced GFlowNet for Solving Vehicle Routing Problems
Ni Zhang, Zhiqin Zhang, Ling Pan, Hoong Chuin Lau, Zhiguang Cao
TL;DR
GFlowNet VRP solvers can insufficiently expand flow into high-reward regions, while diffusion offers complementary exploration guidance. DEG combines edge-specific GFlowNet signals with diffusion and a Graph-Scale Adapter; the paper reports favorable performance across TSP and CVRP, including instances up to 10,000 nodes.
Problem
GFlowNet-based VRP solvers may insufficiently expand flow into high-reward regions, limiting exploration of promising routes.
Source: §1 · p. 2Method
DEG perturbs edge-specific backward signals generated from GFlowNet diversity using a diffusion noise schedule, denoises them within GFlowNet, and uses a Graph-Scale Adapter for scale generalization.
Source: §1 · p. 2Results
DEG reports favorable results against baselines on TSP and CVRP across synthetic and real-world datasets, with robustness on instances up to 10,000 nodes.
Source: §1 · p. 2Takeaways & Limitations
The reported scope includes large-scale routing instances, with DEG reported robust on instances containing up to 10,000 nodes.
Source: §1 · p. 2DEG's parallel decoding falls short in small-scale settings where autoregressive models excel at fine-grained path construction.
Source: §6 · p. 10
Abstract
from arXiv · showhide
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.
1 Introduction
VRP neural solvers are motivated by the computational costs of traditional methods, but GFlowNet solvers can underexplore high-reward routes. DEG combines GFlowNet and diffusion, with a Graph-Scale Adapter intended to improve performance across problem scales.
1 Introduction
- Traditional VRP metaheuristics can be computationally expensive and require carefully designed components and extensive instance-specific hyperparameter tuning.Neural solvers aim to provide data-driven heuristics that improve inference efficiency and reduce reliance on expert knowledge.Source: §1 · p. 1
- GFlowNet-based VRP solvers can converge to sub-optimal route subsets and insufficiently explore high-reward regions, limiting discovery of better solutions.Diffusion and GFlowNet have complementary strengths: diffusion can guide flow expansion, while GFlowNet can provide edge-level signals.Source: §1 · p. 2
- DEG uses diverse GFlowNet trajectories to generate edge-specific backward signals, perturbs them with a diffusion noise schedule, and denoises them within the GFlowNet paradigm.The edge-specific signals provide richer structure for diffusion noise modeling than aggregated trajectory-level signals.Source: §1 · p. 2
- The Graph-Scale Adapter aligns spatial statistics across varying instance sizes to improve generalization to large-scale problems.The paper reports robustness on instances containing up to 10,000 nodes.Source: §1 · p. 2
- Experiments on TSP and CVRP report favorable DEG results on synthetic and real-world datasets.The introduction compares DEG with existing baselines and reports scalability up to 10,000 nodes.Source: §1 · p. 2
2 Related Work
Related work covers autoregressive and non-autoregressive neural solvers, including diffusion-based and GFlowNet approaches. The paper positions DEG as combining diffusion with GFlowNet for VRP exploration.
2 Related Work
- Autoregressive methods construct routes step-by-step, while non-autoregressive methods generate complete solutions in one forward pass for parallel generation.LEHD is described as a light-encoder, heavy-decoder autoregressive design; NAR methods are characterized by reduced inference time.Source: §2 · p. 2
- Existing diffusion-based VRP methods are mainly limited to TSP and rely on supervised learning with optimal solutions.The cited methods include DIFUSCO, T2T, Fast T2T, and DEITSP.Source: §2 · p. 3
- Prior GFlowNet VRP solvers include GFACS, which enhances ACO, and AGFN, which generates routes end-to-end adversarially; DEG uses diffusion to enhance high-reward-region exploration.Source: §2 · p. 3
3 Preliminary
The preliminaries define the TSP and CVRP objectives and outline diffusion and GFlowNet as generative approaches. GFlowNet learns to sample solutions in proportion to reward through forward and backward processes.
3 Preliminary
- TSP seeks a minimum-cost Hamiltonian circuit, while CVRP seeks depot-rooted routes that serve each customer once, respect vehicle capacity, and minimize total travel cost.Both problems use a complete graph with edge costs typically defined as Euclidean distances.Source: §3 · p. 3
- Diffusion corrupts a clean input with Gaussian noise at timestep t and learns to recover the original data from noisy states.The noise level is controlled by α_t.Source: §3 · p. 3
- GFlowNet learns a policy that samples objects in proportion to their reward using forward trajectory construction and backward transitions.Its forward pass includes a source flow and forward policy, while its backward pass includes the reward function and backward policy.Source: §3 · p. 3
4 Diffusion-Enhanced GFlowNet
DEG uses edge-specific backward signals from diverse GFlowNet trajectories as a structured basis for diffusion, then denoises the perturbed signals within the GFlowNet framework. Its Graph-Scale Adapter aligns spatial patterns across graph sizes.
4 Diffusion-Enhanced GFlowNet
- DEG combines GFlowNet’s edge-specific backward signals with a diffusion noise schedule, then denoises them within GFlowNet to encourage flow expansion toward high-reward regions.The framework also adds a Graph-Scale Adapter to align spatial statistics across problem sizes.Source: §4 · p. 3
4.1 Edge-specific Backward Signals and Noise Schedule
- Diverse GFlowNet trajectories supply edge scores: trajectory rewards are averaged over trajectories containing each edge, standardized, and mapped through a normal CDF.The resulting approximate reward distribution serves as the edge-specific backward signal and basis for Gaussian noise.Source: §4.1 · p. 4
- The noise schedule shifts the learning target from an edge-guided distribution toward reward-proportional sampling; for CVRP, its full-corruption endpoint also favors solutions with fewer routes.At the initial stage, trajectories containing high-scoring edges receive more weight; the CVRP endpoint is reward-proportional among solutions with equal route counts.Source: §4.1 · p. 5
4.2 Diffusion-enhanced GFlowNet Framework
- During training, DEG uses the noisy backward policy and trajectory reward in its GFlowNet objective, using the denoised signal’s informative weights to enhance forward-policy learning.The backward transition probability is taken from the noised policy at the edge removed from the partial route.Source: §4.2 · pp. 5–6
4.3 Graph-Scale Adapter for Inference
- Scale-specific neighbor distances and observation radii risk overfitting, so mismatched test graphs can yield suboptimal inference.The passage describes this issue for training and test instances of different sizes.Source: §4.3 · p. 6
- GSA scales test-graph distances and sparsity to match training-scale spatial patterns, alleviating spatial mismatch and improving generalization across instance sizes.For example, it aligns average neighbor distances and node observation radii between 100-node training graphs and 500-node test graphs.Source: §4.3 · p. 6
5 Experiments
The experiments evaluate DEG on synthetic TSP and CVRP benchmarks, public TSPLib and CVRPLib datasets, and component ablations. The reported comparisons favor DEG across tasks and scales, with a small-scale limitation noted in the conclusion.
5 Experiments
- The evaluation spans synthetic TSP and CVRP, public TSPLib and CVRPLib benchmarks, and component ablations; models are trained on 100-node synthetic instances.Synthetic tests cover 500–10,000 nodes; the experiments also assess generalization and individual component contributions.Source: §5 · pp. 6–7, §5.1 · p. 7
5.1 Comparison Study on TSP
- DEG outperforms GFlowNet- and diffusion-based solvers in TSP solution quality, with reported gains increasing as instance size grows.The reported maximum improvements over GFACS, AGFN, DIFUSCO, T2T, Fast T2T, and DEITSP are 67.43%, 34.19%, 5.10%, 16.10%, 17.17%, and 12.05%, respectively.Source: §5.1 · p. 7, Table 1 · p. 7
5.2 Comparison Study on CVRP
- On CVRP instances from 500 to 10,000 nodes, DEG beats GFACS and AGFN, delivers competitive large-scale results without post-processing, and reduces inference time versus LEHD.DEG also outperforms POMO in objective value and inference time across instance sizes; it reduces objective value versus LEHD by 1.24%, 3.28%, and 7.26% on 5,000-, 8,000-, and 10,000-node instances.Source: §5.2 · pp. 7–8, Table 2 · p. 8
5.3 Inference on Real-World Dataset
- On TSPLib, DEG outperforms GFlowNet- and diffusion-based solvers across the reported 50–200 and 200–1,000-node ranges.For 200–500 and 500–1,000 nodes, DEG’s gap improvements over GFACS and AGFN are 51.45% and 25.97%, and 65.78% and 30.69%, respectively.Source: Table 3 · p. 8, §5.3 · p. 9
- On CVRPLib instances of 3,000–16,000 nodes, DEG has lower optimality gaps than the baselines overall, though LEHD performs slightly better on L1.Against LEHD, reported gap improvements range from 0.84% on L2 to 52.59% on B1; against POMO, improvements are reported on L1, L2, A1, and A2.Source: §5.3 · p. 9, Table 4 · p. 9
5.4 Ablation Study
- Ablations report significant gains from adding diffusion to the GFlowNet backbone and further gains from GSA on both TSP and CVRP.GSA also reduces resource use by shortening observation distance and connections per node, allowing efficient solving of 10,000-node TSP and 5,000-, 8,000-, and 10,000-node CVRP instances.Source: §5.4 · pp. 9–10, Table 5 · p. 9
6 Conclusion
DEG combines GFlowNet and diffusion to address insufficient flow expansion in high-reward regions, with GSA intended to improve adaptation across instance sizes. The authors report favorable performance and efficient inference, while identifying weaker small-scale decoding as a limitation.
6 Conclusion
- DEG uses diverse GFlowNet trajectories to create edge-specific backward signals, perturbs them with a diffusion noise schedule, and denoises them through GFlowNet.GSA is incorporated to adapt across diverse instance sizes.Source: §6 · p. 10
- Experiments on synthetic and real-world datasets, including instances up to 10,000 nodes, show favorable performance against diffusion-, GFlowNet-based, and other neural baselines.The authors describe DEG as scalable, efficient in inference, and robust in generalization for VRPs.Source: §6 · p. 10
- DEG’s parallel decoding falls short in small-scale settings where autoregressive models excel at fine-grained path construction.Improving non-autoregressive local decision-making and extending DEG to more VRP variants are future directions.Source: §6 · p. 10
A More Methodology Detail
The forward network uses a GNN on a sparsified graph, retaining each node’s w shortest edges and using distance information as edge features. The final edge embedding supports the source-flow computation.
A.1 Forward Network and Training Paradigm
- The GNN sparsifies the input graph by retaining only the w shortest edges per node to reduce computational complexity.Distance information is used as edge features.Source: §A.1 · p. 15
- Node coordinates and edge distances are embedded into initial node and edge features, which the GNN processes to capture their relationships.The supplied passage describes layer-wise feature updates but does not provide the full update expressions.Source: §A.1 · p. 15
- A multilayer perceptron with sigmoid activation computes the denoised forward policy from final-layer GNN embeddings, while the source flow uses the final edge embedding.The source-flow expression is Z(G; θ) = M · ReLU(J · ed + b) + f, with learnable parameters.Source: §A.1 · p. 15
B Analysis of the Learning Target under the Noise Schedule
The analysis establishes the learning target under the noise schedule and examines how its endpoint behavior depends on edge-reward signals. At low noise, the target can favor high-reward trajectories over reward-proportional sampling under a stated covariance condition.
B.1 Setup and well-posedness
- Clamping makes the backward-side weight positive, so the trajectory-balance loss is well defined and is equivalent to using reward R(τ)Wt(τ).The analysis assumes fixed x0, full-support trajectory sampling, and optimization over strictly positive trajectory distributions and normalizers.Source: §B.1 · pp. 15–16
B.2 Exact target at every noise level
- At each noise level, Proposition 1 gives a unique population minimizer; the exact target applies to the current x0 but does not guarantee convergence of parameterized training dynamics.The population result is independent of the trajectory sampling distribution when it has full support.Source: §B.2 · p. 16
B.3 Low-noise endpoint: exploitation
- The low-noise target has higher expected reward than reward-proportional sampling whenever CovπR(R, W0) > 0.The CDF-based x0 construction does not satisfy edge decomposability exactly, so the R^2 form is a special case, not a general result.Source: §B.3 · p. 17
B.4 High-noise endpoint: exploration
At the high-noise endpoint, the target becomes reward-proportional for TSP, while CVRP retains a route-count factor. Thus the endpoint is exactly reward-proportional unconditionally only for TSP.
B.4 High-noise endpoint: exploration
- At ᾱt = 0, the noise-derived factor is constant per edge, so for TSP it is absorbed into the normalizer and the endpoint is reward-proportional.Every TSP tour contains n edges.Source: §B.4 · p. 17
- For CVRP, the endpoint target includes a factor favoring fewer routes, so it is reward-proportional among solutions with the same route count.For δ = 10^-10, numerical integration gives cT ≈ −11.9.Source: §B.4 · p. 17
- The unconditional reward-proportional endpoint is exact for TSP only; CVRP’s exploration benefit is evaluated empirically.The route-count preference does not imply that fewer routes are always preferable or that near-optimal solutions always use the minimum number.Source: §B.4 · p. 17
B.5 Rate between the endpoints
The analysis bounds how the TSP target approaches reward-proportional sampling as noise increases, with the bound tightening late in the schedule. The trajectory-to-solution relationship introduces a route-structure qualification for CVRP.
B.5 Rate between the endpoints
- As ᾱt → 0, the TSP target’s distance bound vanishes at rate O(nρ(t)), where ρ(t) = Θ(√ᾱt).The bound is mainly informative late in the schedule, when √ᾱt ≪ 1/n, and tightens throughout training.Source: §B.5 · p. 18
- The edge-dependent reward signal weakens through the noise schedule, and the TSP target converges to reward-proportional sampling; for CVRP, this holds among trajectories with the same route count.The analysis characterizes the target’s distance to reward-proportional sampling as decreasing toward zero.Source: §B.5 · p. 18
B.6 Trajectories and solutions
- For TSP, trajectory multiplicity is common across tours and cancels; for CVRP, solution multiplicity can vary with route structure.The qualification disappears when comparing CVRP solutions with the same route structure.Source: §B.6 · p. 19
C.1 GSA Comparison Results
DEG improves over diffusion-based TSP baselines on larger instances and also performs strongly on small TSP and CVRP problems. The Graph-Scale Adapter (GSA) stabilizes checkpoint behavior across instance sizes and improves performance over the setup without GSA.
C.1 GSA Comparison Results
- With GSA, optimal inference checkpoints fall in a consistent interval across instance sizes, and later checkpoints improve rather than degrade as training progresses.The prose reports overall better performance than the baseline without GSA and says GSA mitigates spatial-pattern overfitting to training instance size.Source: §C.1 · p. 19, Figure 3 · p. 19
C.2 TSP comparison on Diffusion-Based Solver with Two-Opt
- DEG reduces objective value versus DIFUSCO by 2.42%, 2.27%, and 2.74% on 500-, 1000-, and 3000-node instances, respectively, and scales to 10,000 nodes.It improves over Fast-T2T by 0.88%, 1.66%, and 4.17% on those sizes, and over DEITSP by 0.80%, 2.04% on 500-, 1000-, 3000-node instances. Other diffusion-based models fail to run at 5,000, 8,000, and 10,000 nodes due to memory limitations.Source: §C.2 · p. 19, Table 6 · p. 20
C.3 TSP and CVRP comparison in small-scale problems
- DEG surpasses all reported diffusion-based and GFlowNet-based methods on TSP200, CVRP100, and CVRP200, with competitive or superior performance on TSP100.Diffusion-based baselines are not reported for CVRP because they do not directly apply to that setting.Source: §C.3 · p. 20, Table 7 · p. 20
C.4 Multiple Scale training
The supplemental sections examine DEG’s scale robustness, route diversity, learning efficiency, and performance beyond routing, then outline GFlowNets and deployment safeguards.
C.4 Multiple Scale training
- DEG maintains strong performance without GSA across training scales, while GSA further strengthens generalization on very large instances.The experiments train on sizes 100, 200, 500, and 1000 and test up to 10000 nodes.Source: §C.4 · p. 20, Table 8 · p. 21, Table 9 · p. 21
C.5 Diversity Test
- DEG consistently achieves higher route-level diversity than standard GFlowNets on TSP and CVRP.Table 10 compares reinforcement learning, vanilla GFlowNet, and DEG; diversity is the average number of edges in one trajectory absent from another.Source: §C.5 · pp. 20–21, Table 10 · p. 22
C.6 Learning Efficiency
- Under matched training conditions, DEG shows strong optimization performance and superior learning efficiency to RL, standard GFlowNet, and PO.Models train on 10,000 instances at n = 200 and are evaluated at n = 200, 500, and 1000.Source: §C.6 · p. 21, Table 11 · p. 22
C.7 Applicability to Other Combinatorial Optimization Problems
- On SMTWTP and BPP, DEG outperforms DeepACO and GFACS, indicating potential beyond routing.The benchmarks cover scheduling instances with 100, 200, and 500 jobs and packing instances with 120, 250, and 500 items.Source: §C.7 · pp. 21–22, Table 12 · p. 23
D Detailed Introduction of GFlowNet
- A GFlowNet learns a policy that samples terminal objects in proportion to reward, with conditional policies adapting to input instances.Its formulation treats sampling as sequential decision-making over states and actions; conditional GFlowNets support generalization to unseen instances and variable-sized structured solutions.Source: D Detailed Introduction of GFlowNet · pp. 22–23
E Broad Impact and Safeguards.
- For real-world use, the paper recommends diverse-scenario testing, careful validation, and combining learned methods with classical optimization or constraint checks when appropriate.It also calls for documenting assumptions and limitations and encourages domain-specific validation.Source: E Broad Impact and Safeguards · p. 23