betaFeedback

WorksComputer Science

DEG: Diffusion-Enhanced GFlowNet for Solving Vehicle Routing Problems

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.

Introduction

The Vehicle Routing Problem (VRP) is a fundamental NP-hard combinatorial optimization problem that generalizes the Traveling Salesman Problem (TSP) by incorporating practical constraints such as vehicle capacity limitations and route feasibility requirements. The objective of VRPs is to minimize overall travel costs by determining optimal routes for a fleet of vehicles dispatched from a central depot to serve multiple customers while satisfying these constraints. VRPs are central to a wide range of applications, including logistics and distribution planning [6, 7, 11, 22, 29, 33, 67], agricultural field operations [57, 60, 55], and urban delivery systems [10, 17, 14]. Owing to their importance, VRPs have attracted extensive research attention. Traditional metaheuristics [8, 2, 40, 44, 13, 31, 48, 41, 3] have demonstrated effectiveness in solving VRPs. However, they are often computationally expensive and heavily dependent on carefully designed solution components and extensive hyperparameter tuning tailored to specific instances. These limitations have spurred growing interest in deep learning–based neural solvers, which aim to provide data-driven heuristics that improve inference efficiency while reducing reliance on expert knowledge.

Recent neural solvers for VRPs can be broadly categorized into Autoregressive (AR) and Non-Autoregressive (NAR) models. AR models, such as those based on pointer networks and Transformer 40th Conference on Neural Information Processing Systems (NeurIPS 2026). architectures [32, 38, 9, 24, 62], have achieved strong solution quality. However, their sequential decoding process introduces significant computational bottlenecks, limiting scalability to large instances. NAR models provide a promising alternative by generating complete solutions in a single forward pass, greatly improving inference efficiency. Early NAR methods, however, struggled with solution quality, motivating the development of Generative Flow Network (GFlowNet) [4, 5]. While GFlowNet-based solvers [68, 27, 66] leverage sampling diversity to improve solution quality, they often converge to sub-optimal route subsets and fail to fully explore high-reward regions, leading to insufficient flow expansion into these more promising areas and hindering the discovery of higher-quality solutions.

Diffusion models [52, 21] recently emerged as a powerful approach in the VRP domain for their strong exploration capability [54, 34, 35, 56]. Yet existing diffusion-based methods remain largely confined to the TSP and depend on supervised frameworks to generate edge-level noise signals. While GFlowNet and diffusion models each have distinct strengths and limitations, their integration for VRP solving has not been explored. These two paradigms are naturally complementary: diffusion can guide GFlowNet toward more effective flow expansion in high-reward regions, and GFlowNet can provide edge-level signals and extend the applicability of diffusion methods.

Based on this, we propose Diffusion-Enhanced GFlowNet (DEG), a novel framework that integrates GFlowNet with diffusion models for solving VRPs. DEG leverages the intrinsic diversity of GFlowNet to generate edge-specific backward signals, which serve as a noise basis for the diffusion process. Unlike conventional trajectory-level backward signals that collapse into a single aggregated value, edge-specific signals provide richer structure for diffusion noise modeling. DEG perturbs these signals with a stochastic noise schedule and denoises them within the GFlowNet paradigm, preventing premature convergence to sub-optimal policies and promoting broader exploration of high-reward regions. This mechanism enhances forward probability allocation across promising routes and enables more effective flow expansion, enabling the discovery of higher-quality solutions. To further enhance generalization across varying problem scales, we develop the Graph-Scale Adapter (GSA), a specialized module that aligns spatial statistics across different graph scales and significantly improves scalability. Experimental evaluations demonstrate DEG’s strong performance and scalability on both TSP and Capacitated Vehicle Routing Problem (CVRP), achieving competitive results compared to existing baselines and exhibiting robustness on instances containing up to 10,000 nodes. Our contributions are summarized as follows:

  • We propose Diffusion-Enhanced GFlowNet (DEG), which leverages intrinsic diversity of GFlowNet to generate edge-specific backward signals that serve as the adaptive noise basis for integrating diffusion, then applies the diffusion’s noise schedule to inject noise into these signals, and denoises them through the GFlowNet paradigm, enabling deeper flow expansion toward high-reward regions to derive better solutions.

  • We design the Graph-Scale Adapter (GSA) to align spatial statistics across varying instance sizes, which enhances the model’s ability to generalize to large-scale problems.

  • We conduct comprehensive experiments on TSP and CVRP, and results show that DEG consistently achieves favorable results on both synthetic and real-world datasets.

Related Work

The deep learning based neural solvers for VRPs can be broadly classified into Autoregressive (AR) and Non-Autoregressive (NAR) methods, respectively.

AR methods sequentially construct solutions step-by-step, conditioned on previously selected nodes. Transformer-based architectures have been particularly influential due to their ability to effectively capture long-range dependencies. A notable early example is the Attention Model (AM) [30], which applies self-attention mechanisms to enable end-to-end routing policy learning. To further enhance solution diversity and robustness, POMO [32] builds on AM by employing multi-start policy optimization, exploring multiple potential optimal paths simultaneously. Building on the strengths of autoregressive architectures, LEHD [38] introduces a light-encoder, heavy-decoder design, achieving substantial performance gains across standard VRP benchmarks.

NAR methods, by contrast, generate complete solutions in a single forward pass, drastically reducing inference time and enabling parallel solution generation. This characteristic makes them particularly appealing for large-scale applications. Diffusion-based models represent a recent and promising class of NAR approaches. DIFUSCO [54] is a pioneering diffusion-based model tailored for the TSP variant of VRPs. Building upon this foundation, T2T [34], Fast T2T [35] and DEITSP [56] significantly improve solution quality while retaining inference efficiency. However, all these diffusion-based methods rely on supervised learning with optimal solutions and are mainly limited to TSP. GFlowNet-based solvers form another mainstream approach. GFACS [27] employs GFlowNet to enhance the ACO heuristic. AGFN [68] adopts an adversarial strategy to generate routes in an end-to-end manner. Different from those methods, in this work, we propose Diffusion-Enhanced GFlowNet (DEG), which leverages diffusion to enhance the exploration of high-reward regions, thereby improving the solution quality for VRPs.

Preliminary

Problems Definition. In both the TSP and CVRP, the instance is defined on a complete graph G=(V,E)\mathcal{G} = (\mathcal{V}, \mathcal{E}), where V={n0,n1,…,nv}\mathcal{V} = \{n_0, n_1, \ldots, n_v\} denotes the set of nodes and E\mathcal{E} the set of edges. The cost d(ni,nj)d(n_i, n_j) associated with each edge is typically defined as the Euclidean distance between nodes nin_i and njn_j. In the TSP, the objective is to find a minimum-cost Hamiltonian circuit that visits all nodes exactly once. In the CVRP, n0n_0 represents the depot, and the remaining nodes correspond to customers with non-negative demands did_i. The goal is to construct a set of depot-rooted routes τ={q1,…,qN}\tau= \{q_1, \ldots, q_N\} such that each customer is visited exactly once, the total demand on each route does not exceed the vehicle capacity CC, and the overall travel cost is minimized.

Diffusion Models. Diffusion models have recently emerged as powerful generative approaches, achieving favorable results in domains such as image synthesis [52, 21, 49, 15], audio generation [23, 28], and drug design [51, 58]. Diffusion models operate by corrupting clean inputs with noise and denoise them to reconstruct the original data. Typically, given a clean input x0x_0, the noise process perturbs it by adding Gaussian noise to obtain a noisy sample xtx_t at time step tt, following

q(xt∣x0)=N(xt;αtx0,(1−αt)I),(1)q(x_t \mid x_0) = \mathcal{N}(x_t; \sqrt{\alpha_t}x_0, (1-\alpha_t)I), \tag*{(1)}

where αt∈(0,1)\alpha_t \in(0, 1) controls the noise level. The model can capture the structure of the target distribution by extracting meaningful signals from noisy states and recovering the original data.

GFlowNet. Generative Flow Network (GFlowNet) is a variational inference algorithm that treat sampling from a target probability distribution as a sequential decision-making process [4, 5], and is widely applied to structured generation tasks, including molecule design [43, 26, 69], neural architecture search [53, 25], and combinatorial optimization [65, 63, 12]. The objective of GFlowNet is to learn a policy that samples objects in proportion to a given reward distribution. From a high-level perspective, a GFlowNet consists of two complementary components: forward sampling policy and backward policy. The forward pass includes the source flow Z(G;θ)Z(\mathcal{G}; \theta) and a forward policy PF(τ;θ)P_F(\tau; \theta) that governs trajectory construction from initial to terminal states. The backward pass includes the reward function R(τ)R(\tau) and a backward policy PB(τ)P_B(\tau) that defines reverse transitions. Together, these bidirectional passes form the basis for training via trajectory balance objectives [39], defined as:

LTB(τ;θ)=(log⁡Z(G;θ)PF(τ;θ)R(τ)PB(τ))2.(2)\mathcal{L}_{\mathrm{TB}}(\tau; \theta) = \left(\log\frac{Z(\mathcal{G}; \theta)P_F(\tau; \theta)}{R(\tau)P_B(\tau)}\right)^2. \tag*{(2)}

Diffusion-Enhanced GFlowNet

We introduce Diffusion-Enhanced GFlowNet (DEG), a framework designed to overcome a core limitation of existing GFlowNet-based VRP solvers, namely, their inability to effectively expand flow toward high-reward regions. DEG integrates GFlowNet with diffusion by leveraging edge-specific backward signals, which serve as a structured noise basis for the diffusion process. A stochastic noise schedule perturbs these signals, which are subsequently denoised within the GFlowNet paradigm, enabling richer exploration and more sufficient flow expansion. To further strengthen scalability and inference quality across varying problem sizes, DEG incorporates a Graph-Scale Adapter (GSA) decoder, which dynamically aligns spatial statistics across different graph scales.

Edge-specific Backward Signals and Noise Schedule

Figure 1 illustrates the generation of edge-specific backward signals and noise schedule. We first use GFlowNet to generate a diverse set of trajectories and assign standardized scores to each edge, estimating an approximate reward distribution that serves as edge-specific backward signals. Although the individual trajectories produced during GFlowNet sampling may not be optimal, their collective information forms a robust reward distribution that guides the diffusion learning process. A noise schedule then injects controlled noise into this distribution to derive a noised backward policy.

Figure 1. Illustration of Edge-specific Backward Signals Generation and Noise Schedule.

By leveraging the inherent diversity of GFlowNet, the model can generate a wide range of trajectories, after which the edge score calculation is applied. The edge score calculation begins by normalizing the reward of each trajectory τk∈T\tau_k \in\mathcal{T} using the following formulation:

−log⁡R(τk)=D(τk)−1m∑l=1mD(τl),(3)-\log R(\tau_k) = D(\tau_k) - \frac{1}{m}\sum_{l=1}^{m} D(\tau_l), \tag*{(3)}

where D(τk)D(\tau_k) is the total distance of trajectory τk\tau_k, defined as: D(τk)=∑l=1N−1d(ql,ql+1)D(\tau_k) = \sum_{l=1}^{N-1} d(q_l, q_{l+1}). Here, d(ql,ql+1)d(q_l, q_{l+1}) denotes the Euclidean distance between nodes qlq_l and ql+1q_{l+1}. A higher reward R(τk)R(\tau_k) corresponds to a shorter, higher-quality trajectory. We define the reward of an edge ee as the average reward of the trajectories in which it appears:

R(e)=1∣{τk∣τk∈T, e∈τk}∣∑τk∈T, e∈τkR(τk),(4)R(e) = \frac{1}{|\{\tau_k \mid\tau_k \in\mathcal{T},\ e \in\tau_k\}|}\sum_{\tau_k \in\mathcal{T},\ e \in\tau_k} R(\tau_k), \tag*{(4)}

where the denominator counts the number of trajectories containing edge ee. This edge-level reward R(e)R(e) reflects the global significance of edge ee across the sampled solution space. To standardize R(e)R(e) across different instances, we use z-score normalization [42]: R^(e)=R(e)−μRσR\hat{R}(e) = \frac{R(e)-\mu_R}{\sigma_R}, where μR\mu_R and σR\sigma_R denote the mean and standard deviation of edge rewards within the instance. To convert the standardized scores into bounded confidence values, we apply the cumulative distribution function (CDF) [50] of the standard normal distribution:

x0=Φ(R^(e)),(5)x_0 = \Phi\left(\hat{R}(e)\right), \tag*{(5)}

where Φ(⋅)\Phi(\cdot) denotes the CDF of the standard normal distribution. The value x0x_0 represents an approximate reward distribution that provides edge-specific backward signals and serves as the basis for adding noise to integrate diffusion into GFlowNet. The noise schedule then injects Gaussian noise at each training step to obtain a noised backward policy xtx_t:

xt=αt⋅x0+1−αt⋅ϵ,ϵ∼N(0,1),(6)x_t = \sqrt{\alpha_t}\cdot x_0 + \sqrt{1-\alpha_t}\cdot\epsilon,\quad\epsilon\sim\mathcal{N}(0,1), \tag*{(6)}

where αt=∏k=1t(1−βk)\alpha_t = \prod_{k=1}^{t}(1-\beta_k), and βk∈(0,1)\beta_k \in(0,1) is the corruption ratio at diffusion step kk. To ensure full transformation of the clean signal into noise by the final training iteration TT, βk\beta_k should be defined such that ∏k=1T(1−βk)≈0\prod_{k=1}^{T}(1-\beta_k) \approx0. We use continuous Gaussian noise to match the inherently continuous nature of the backward policy in GFlowNet.

Effect of Edge-specific Backward Signals and Noise Schedule on High-Reward Region Exploration. DEG uses a noise schedule that progressively corrupts the edge-specific backward signals during training, together with the Trajectory Balance (TB) objective [39]. We characterize the learning target induced by this schedule at each noise level, with proofs provided in Appendix § 8. In practice, the noised signal is clamped as x~t[e]=max⁡(clamp⁡(xt[e],0,1),δ)∈[δ,1]\tilde{x}_t[e] = \max(\operatorname{clamp}(x_t[e], 0, 1), \delta) \in[\delta, 1], with δ=10−10\delta= 10^{-10}, ensuring that the backward-side trajectory weight Wt(τ)=∏e∈τx~t[e]W_t(\tau) = \prod_{e \in\tau} \tilde{x}_t[e], which replaces PB(τ)P_B(\tau) in LTB\mathcal{L}_{\mathrm{TB}} (Eq. (2)), remains strictly positive.

Because TB minimizes a squared log-ratio, the injected noise affects the optimum through Eϵ[log⁡Wt(τ)]\mathbb{E}_{\epsilon}[\log W_t(\tau)]. For a fixed graph G\mathcal{G} and signal x0x_0, the population minimizer at noise level tt is

PFt(τ)∝R(τ)eμt(τ),μt(τ)=∑e∈τEϵ[log⁡x~t[e]],(7)P_F^t(\tau) \propto R(\tau)e^{\mu_t(\tau)}, \qquad\mu_t(\tau) = \sum_{e \in\tau} \mathbb{E}_{\epsilon}[\log\tilde{x}_t[e]], \tag*{(7)}

which holds exactly at every noise level (Proposition 1). The target can therefore be viewed as reward-proportional sampling modified by an edge-specific factor, whose dependence on x0x_0 is gradually reduced by the noise schedule. At the beginning of training, no noise is added (αˉt=1\bar{\alpha}_t = 1), giving

PF0(τ)∝R(τ)∏e∈τx0[e].(8)P_F^0(\tau) \propto R(\tau)\prod_{e \in\tau} x_0[e]. \tag*{(8)}

Compared with πR∝R\pi_R \propto R, this distribution gives more weight to trajectories containing high-scoring edges. Its expected reward is higher than that of πR\pi_R whenever ∏e∈τx0[e]\prod_{e \in\tau} x_0[e] is positively correlated with R(τ)R(\tau) (Proposition 2), which motivates constructing x0x_0 from edge-reward statistics. This early stage therefore favors exploitation. Only when ∏e∈τx0[e]∝R(τ)\prod_{e \in\tau} x_0[e] \propto R(\tau) does Eq. (8) reduce to PF∝R(τ)2P_F \propto R(\tau)^2; our CDF-based construction of x0x_0 does not assume this special case.

As the noise increases, the influence of x0x_0 weakens. At full corruption (αˉt=0\bar{\alpha}_t = 0), x~t[e]\tilde{x}_t[e] is independent of x0x_0, and μt(τ)=cT∣τ∣\mu_t(\tau) = c_T|\tau| for a constant cTc_T. For TSP, all tours contain exactly nn edges, so this term is identical across trajectories and

PF(τ)∝R(τ).(9)P_F(\tau) \propto R(\tau). \tag*{(9)}

Before reaching this endpoint, KL⁡(PFt∥πR)\operatorname{KL}(P_F^t \parallel\pi_R) admits a bound that decreases to zero as $\bar{\alpha}_t \to 0 ({xref}Theorem 1), providing a useful characterization of the late training stage. For CVRP, a trajectory with $K(\tau)$ routes contains $n + K(\tau)$ edges. The endpoint target therefore becomes $P_F(\tau) \propto R(\tau)e^{c_TK(\tau)}$ with $c_T < 0$. It is reward-proportional among solutions with the same number of routes, while additionally favoring solutions with fewer routes ({xref}Remark 2`).

Overall, the noise schedule gradually removes the edge-specific factor from the learning target, moving from the edge-guided distribution in Eq. (8) toward the reward-proportional distribution in Eq. (9). This gives a natural transition from early exploitation to broader exploration.

Diffusion-enhanced GFlowNet Framework

In our framework, the model learns to construct solutions by drawing on both the noisy backward policy and the reward within the GFlowNet paradigm, which denoises the noised backward policy during training by extracting its informative weights, and using them to enhance forward-policy learning. The loss over a set of trajectories T={τ1,τ2,…,τm}\mathcal{T} = \{\tau_1, \tau_2, \ldots, \tau_m\}, based on the denoised forward policy which estimates reward distribution, is defined as:

L(T;θ)=∑k=1m(log⁡Z(G;θ)PF(τk;θ)R(τk)PB(τk))2.(10)\mathcal{L}(\mathcal{T}; \theta) = \sum_{k=1}^{m} \left(\log\frac{Z(\mathcal{G}; \theta)P_F(\tau_k; \theta)}{R(\tau_k)P_B(\tau_k)}\right)^2. \tag*{(10)}

Here, source flow Z(G;θ)Z(\mathcal{G}; \theta) is a learnable partition function derived from Eq. (15), and reward R(τk)R(\tau_k) is defined in Eq. (3). The forward probability PF(τk;θ)P_F(\tau_k; \theta) is computed as:

PF(τk;θ)=∏t=1NPF(st∣st−1;θ),(11)P_F(\tau_k; \theta) = \prod_{t=1}^{N} P_F(s_t \mid s_{t-1}; \theta), \tag*{(11)}

where st={q1,q2,…,qt}s_t = \{q_1, q_2, \ldots, q_t\} denotes the state at step tt during the construction (or destruction) of the trajectory. The term PF(st∣st−1)P_F(s_t \mid s_{t-1}) is obtained from the forward policy η(G∗,θ)\eta(\mathcal{G}^*, \theta), which is derived from the GFlowNet forward network described in Sec. A.1.

Moreover, η(G∗,θ)\eta(\mathcal{G}^*, \theta) can be viewed as a heatmap over all edges of the current graph: it is a ∣V∣×∣V∣|V| \times|V| probability matrix where each entry η(i,j)\eta(i,j) gives the likelihood of selecting the edge (vi,vj)(v_i,v_j) from the current node viv_i to a candidate node vjv_j. During decoding, the next node of the route is sampled according to these edge probabilities. After each selection, the graph state G∗G^* is updated by marking the chosen node as visited and updating feasibility masks (e.g., vehicle capacity), and the process is repeated until all customers are visited and a complete route is constructed.

Similarly, the backward transition probability PB(τk)P_B(\tau_k) in Eq. (10) is computed as:

PB(τk;θ)=∏k=1NPB(sk−1∣sk;θ),(12)P_B(\tau_k;\theta) = \prod_{k=1}^{N} P_B(s_{k-1} \mid s_k;\theta), \tag*{(12)}

where PB(st−1∣st;θ)P_B(s_{t-1} \mid s_t;\theta) is derived from the noised backward policy xtx_t. Specifically, for a partial route state st={q1,q2,…,qt}s_t = \{q_1, q_2, \ldots, q_t\}, this corresponds to removing the last node qtq_t from the current partial route, which eliminates the edge (qt,qt−1)(q_t, q_{t-1}). Thus PB(st−1∣st;θ)P_B(s_{t-1} \mid s_t;\theta) is taken directly from the value of xtx_t at the position (qt,qt−1)(q_t, q_{t-1}).

Graph-Scale Adapter for Inference

During training, we adopt GFlowNet’s inherent sampling strategy to generate diverse trajectories to provide edge-specific signal. This enables efficient sampling and strengthens training effectiveness, with a dedicated model trained for a specific problem size. However, this strategy does not generalize well at inference time due to scale mismatches between training and test instances.

Specifically, the DEG forward policy learns an approximate reward distribution guided by feedback from the noisy backward flow. However, this design may increase the risk of overfitting to spatial patterns specific to the training scale, such as average neighbor distances and node observation radii defined by the sparsity factor ww. For example, when trained on 100-node instances, the model implicitly learns to solve instances with an average neighbor distance of approximately 1100\frac{1}{\sqrt{100}} and a node observation distance of 1w\frac{1}{\sqrt{w}}. When evaluated on a 500-node instance, however, the average neighbor distance drops to 1500\frac{1}{\sqrt{500}}, while the observation distance becomes 15w\frac{1}{\sqrt{5w}}. This spatial inconsistency hampers generalization and often leads to suboptimal inference. The best outcomes of large-scale instances appear at earlier training stages, when the model has not yet overfitted and its estimation of spatial structures remains effective and less biased. We empirically validate this behavior, with details provided in Appendix § 9.§ 1.

To mitigate this issue, we propose the Graph-Scale Adapter (GSA), which aligns the spatial patterns of test instances to those of fixed-size training instances. GSA introduces a scaling factor α\alpha that adjusts node distances and the sparsity factor in the test graph to match the spatial characteristics of the training graph. The scaling factor is defined as: α∝∣Vtest∣∣Vtrain∣\alpha\propto\sqrt{\frac{|V_{\mathrm{test}}|}{|V_{\mathrm{train}}|}}. This adjustment ensures structural consistency across different scales. For instance, if the model is trained on 100-node graphs and evaluated on 500-node graphs, applying GSA ensures that the average neighbor distances and node observation radius remain consistent, approximately 1100\frac{1}{\sqrt{100}} and 1w\frac{1}{\sqrt{w}}. To assess the effectiveness of GSA, we apply it during inference on instances of varying sizes. As shown in Appendix § 9.§ 1, GSA effectively alleviates spatial mismatches caused by scale-specific overfitting and significantly improves the model’s ability to generalize across a broad range of instance sizes.

Experiments

We present experimental results to evaluate the performance of DEG. We first assess its effectiveness on both synthetic instances for TSP and CVRP following previous works [27, 68]. Since our model integrates GFlowNet with diffusion, we primarily compare it against GFlowNet-based and diffusion-based baselines. We then evaluate the model’s generalization ability on public benchmarks, including TSPLib [1] and CVRPLib [47]. Finally, we conduct ablation studies to examine the contribution of individual components in DEG. We additionally conduct more experiments on multiple scale training, GSA applicability, diversity test, learning efficiency and applicability to other COPs, the details of which are presented in Appendix § 9.§ 4 to C.7.

Following prior work on VRP [54, 27, 68, 64, 56], we use synthetic datasets for training both TSP and CVRP models. Each TSP instance consists of nodes represented only by their 2D coordinates, sampled independently from the unit square [0,1]2[0,1]^2, without any depot or demand. The objective is to compute the shortest tour that visits each node exactly once and returns to the start. For CVRP, each instance includes a single depot and multiple customer nodes served by a vehicle with a fixed capacity C=50C = 50. Node locations (both depot and customers) are uniformly sampled from [0,1]2[0, 1]^2. Each customer is assigned a demand independently drawn from a uniform distribution U[a,b]U[a, b], where a=1a = 1 and b=9b = 9. For training, DEG is trained on 100-node instances for both TSP and CVRP. For evaluation, we generate synthetic test sets containing 128 instances per problem size, ranging from 500 to 10,000 nodes (500, 1,000, 3,000, 5,000, 8,000 and 10,000).

Following standard practice [54, 56, 18], we adopt a linear noise schedule with β1=10−4\beta_1 = 10^{-4} and βI=0.02\beta_I = 0.02. The model is trained for I=6000I = 6000 steps, using a batch size of 10 instances per step. We use the AdamW optimizer [36] with an initial learning rate of 10−410^{-4}, decayed to 10−510^{-5} via a CosineAnnealingLR schedule [37]. All experiments are conducted on a NVIDIA H100 NVL GPU and an AMD EPYC 9554 CPU.

Comparison Study on TSP

As prior diffusion-based work has primarily focused on the TSP [54, 34, 35, 56] in the VRP domain, we first evaluate DEG on synthetic TSP instances. Besides the heuristic solver LKH [20], we mainly compare it against both GFlowNet-based solvers including GFACS [27] and AGFN [68], and diffusion-based solvers including DIFUSCO [54], T2T [34], Fast T2T [35], and DEITSP [56]. All models are trained on 100-node instances. To ensure fair comparison, and due to space constraints, Table 1 reports the performance of models without 2-opt post-processing. Following [54, 34, 35, 56], results with 2-opt post-processing are provided in Appendix § 9.§ 2 and Table 6 for completeness. We also provide the comparison on small-scale instances in Appendix § 9.§ 3 and Table 7.

Method500 Obj.500 Time(s)500 Gap(%)1000 Obj.1000 Time(s)1000 Gap(%)3000 Obj.3000 Time(s)3000 Gap(%)
LKH16.5531.80–23.1497.62–40.31776.23–
GFACS (AISTATS’25)22.978.4338.7938.5818.9066.7269.6381.1572.74
AGFN (ICLR’25)19.040.2515.0527.100.6817.1155.372.9137.36
DIFUSCO (NeurIPS’23)19.123.5215.1727.7013.6019.7150.39125.0225.01
T2T (NeurIPS’23)18.913.1814.2627.3112.9518.0256.99115.7141.38
Fast T2T (NeurIPS’24)18.760.3713.3527.251.5417.7657.734.7643.22
DEITSP (KDD’25)18.640.4212.6327.111.6817.1654.375.3534.81
DEG18.470.2811.6026.460.7214.3547.823.0618.63
Method5000 Obj.5000 Time(s)5000 Gap(%)8000 Obj.8000 Time(s)8000 Gap(%)10000 Obj.10000 Time(s)10000 Gap(%)
LKH51.841608.11–65.894123.37–75.785350.91–
GFACS (AISTATS’25)97.93143.1988.91120.76275.2283.28140.84326.0485.85
AGFN (ICLR’25)80.936.6556.12118.5313.0979.89143.8514.0789.83
DIFUSCO (NeurIPS’23)–––––––––
T2T (NeurIPS’23)–––––––––
Fast T2T (NeurIPS’24)–––––––––
DEITSP (KDD’25)–––––––––
DEG63.646.8222.5783.1314.9726.1694.6716.4724.94

Table 1. Comparison of performance and runtime on TSP with varying node sizes. Obj. denotes the total route length; Gap (%) is computed relative to LKH; and Time (s) indicates the average time required to solve a single instance. For all metrics, lower values indicate better results. “–” indicates that the model was unable to produce a result for a given instance either within the 90-minute time limit or due to GPU memory constraints.

TSP500100030005000800010000
Obj.Gap(%)Obj.Gap(%)Obj.Gap(%)Obj.Gap(%)Obj.Gap(%)Obj.Gap(%)
DIFUSCO (NeurIPS’23)17.324.6524.224.6643.417.69––––––
T2T (NeurIPS’23)17.143.5624.184.4942.976.60––––––
Fast T2T (NeurIPS’24)17.053.0224.074.0244.069.30––––––
DEITSP (KDD’25)16.982.6023.863.1543.106.92––––––
DEG16.902.1123.672.3042.224.7454.615.3469.465.4280.055.69

Table 6. Comparison of performance on TSP with varying node sizes with two-opt post processing. Obj. denotes the total route length and Gap (%) is computed relative to LKH. For all metrics, lower values indicate better results. “–” indicates that the model was unable to produce a result for a given instance either within the 90-minute time limit or due to GPU memory constraints.

TSP100200
Obj.Time(s)Gap(%)Obj.Time(s)Gap(%)
LKH7.761.50-10.629.80-
GFACS8.800.5313.5413.201.1524.29
AGFN8.490.059.5511.820.0811.30
DEG8.400.068.2511.650.109.42
DIFUSCO (w/ LS)7.880.421.6810.801.531.70
T2T (w/ LS)7.800.370.6510.801.151.72
DEITSP (w/ LS)7.780.080.3910.761.201.32
Fast T2T (w/ LS)7.820.110.9010.781.191.51
DEG (w/ LS)7.790.070.5210.761.151.32
CVRP100200
Obj.Time(s)Gap(%)Obj.Time(s)Gap(%)
LKH15.5718.80-28.0450.83-
GFACS19.261.9023.7035.363.1426.11
AGFN17.780.0614.1931.600.1612.70
DEG17.070.079.6331.000.1810.56

Table 7. Comparison on small-scale TSP and CVRP instances (100 and 200 Nodes). Obj. denotes the total route length; Gap (%) is computed relative to LKH; and Time (s) indicates the average time required to solve a single instance. For all metrics, lower values indicate better results.

As shown in Table 1, DEG outperforms all GFlowNet-based and diffusion-based solvers in terms of solution quality. Specially, it achieves 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. Notably, the performance gap between our model and other baselines becomes more significant as the instance size increases.

Comparison Study on CVRP

We present results on the CVRP instances, focusing primarily on comparisons with GFlowNet-based solvers, as no existing diffusion-based model is capable of solving CVRP. Besides the heuristic solver LKH [20], we compare DEG against GFlowNet-based solvers including GFACS [27] and AGFN [68], as well as other neural solvers such as LEHD [38] and POMO [32] to ensure comprehensive evaluation. For LKH, we use a setting of 1000 iterations on 3000-, 5000-, 8000- and 10000-node instances, as larger-scale problems require substantial computational time. Also, all neural models are trained on 100-node synthetic instances, and the routes are evaluated directly without post-processing. Experimental results on small-scale instances are further provided in Appendix § 9.§ 3, and the corresponding comparisons are summarized in Table 7.

As shown in Table 2, DEG achieves better results than GFACS by 13.63%, 18.43%, 7.92%, 8.33%, 12.58% and 21.83% on the 500-, 1000-, 3000-, 5000-, 8000- and 10000-node instances, and outperforms AGFN by 1.82%, 3.21%, 1.86%, 2.00%, 1.05% and 1.35% on the same instance sizes. When compared to Transformer-based AR solvers, NAR methods often struggle to match their performance without the aid of improvement techniques, partly due to inherent limitations in network depth and complexity. Without relying on additional post-processing techniques, our model DEG is able to deliver competitive performance on large-scale instances, while also offering notable advantages in inference efficiency. Compared to state-of-the-art AR mode, LEHD, which adopts a heavy decoder transformer network, our model reduces the objective value by 1.24%, 3.28% and 7.26% on the 5000-, 8000- and 10000-node instances, respectively, and reduces inference time by 13.46%, 92.61%, 87.91%, 87.37%, 93.96% and 95.58% on 500-, 1000-, 3000-, 8000- and 5000-node instances. Furthermore, our model consistently outperforms POMO in objective value and achieves shorter inference time across all instance sizes. Overall, our model achieves competitive results against GNN- and NAR-based solvers and other neural models, and offers significantly shorter inference time, particularly on large-scale instances. Notably, DEG achieves better performance than both LEHD and POMO on real-world datasets, as detailed in § 5.3 and Table 4.

Method500500500100010001000300030003000
Obj.Time(s)Gap(%)Obj.Time(s)Gap(%)Obj.Time(s)Gap(%)
LKH63.14134.40–119.52638.40–380.26*671.68–
GFACS (AISTATS’25)80.7710.4327.92158.9722.0733.01393.27130.813.42
AGFN (ICLR’25)71.050.4312.53133.970.7512.09368.973.84-2.97
LEHD (NeurIPS’23)64.680.522.44122.8510.152.79355.9533.75-6.39
POMO (NeurIPS’20)80.210.5027.04164.170.9237.361094.487.01187.82
POMO(*8) (NeurIPS’20)75.450.6719.50135.743.1312.74704.9918.2685.40
DEG69.760.4510.48129.670.808.49362.114.08-4.77
Method500050005000800080008000100001000010000
Obj.Time(s)Gap(%)Obj.Time(s)Gap(%)Obj.Time(s)Gap(%)
LKH(1000)642.95*2263.34–––––––
GFACS (AISTATS’25)650.62262.631.191038.30529.04–1439.19607.26–
AGFN (ICLR’25)608.587.42-5.35917.2415.24–1140.4618.58–
LEHD (NeurIPS’23)603.8996.75-6.08938.06336.70–1213.13556.88–
POMO (NeurIPS’20)1438.9719.32123.81––––––
POMO(*8) (NeurIPS’20)1381.6341.86114.89––––––
DEG596.4310.22-7.24907.6520.32–1125.0424.95–

Table 2. Comparison of performance and runtime on CVRP with varying node sizes. Obj. denotes the total route length; Gap (%) is computed relative to LKH; and Time (s) indicates the average time required to solve a single instance. For all metrics, lower values indicate better results.

“–” indicates that the model was unable to produce a result for a given instance either within the 90-minute time limit or due to GPU memory constraints. * denotes LKH run with 1,000 iterations due to time limits.

Table 4: Comparison of performance on CVRPLib. Gap (%) is computed relative to existing best-known solutions, and lower values indicate better results.

Gap(%)L1 (3k)L2 (4k)A1 (6k)A2 (7k)G1 (10k)G2 (11k)B1 (15k)B2 (16k)
GFACS120.211800.04114.37238.19278.112242.09348.542634.74
AGFN1144.2027.8829.6424.58142.6527.2120.63160.24
LEHD14.0426.3018.9026.4027.2338.4535.9440.76
POMO75.3078.16112.27159.22––––
DEG19.6426.0814.9523.8023.1824.4117.0423.47

Table 4.

Inference on Real-World Dataset

To assess the generalization ability of our model, we evaluate it on real-world benchmark datasets, TSPLib [1] and CVRPLib [47].

Following prior works [54, 34, 35, 56], we evaluate our model on TSPLib with test instances ranging from 50 to 200 nodes and from 200 to 1000 nodes, respectively. We adopt the same experimental setup and baseline methods as described in § 5.1. The results are reported in Table 3 in the Appendix. Our model outperforms GFACS and AGFN in gap by 51.45% and 25.97% on 200-500 node instances, and 65.78% and 30.69% on 500-1000 node instances, respectively. Compared to the diffusion-based models with two-opt post-processing, DEG achieves superior gap performance over DIFUSCO, DEITSP, T2T, and Fast T2T by 88.59%, 84.56%, 72.73% and 74.07% on 200-500 node instances, and 70.72%, 45.11%, 19.84% and 30.82% on 500-1000 node instances. Overall, our model outperforms both GFlowNet-based models and diffusion-based solvers on TSPLib, across both 50-200 and 200-1000 instances.

TSPGFACSAGFNDEGDIFUSCO*T2T*Fast T2T*DEITSP*DEG*
50-20029.6019.4114.370.960.370.260.810.21
200-100051.6725.5117.683.451.841.261.461.03

Table 3. Comparison of performance on TSPLib. Gap (%) is computed relative to existing best-known solutions, and lower values indicate better results.

“–” indicates that the model was unable to produce a result for a given instance either within the 90-minute time limit or due to GPU memory constraints. * represents using two-opt after trajectories are generated.

We test CVRPLib containing instances with the number of node ranging from 3000 to 16000. The experiment setting and baselines are same with comparison on CVRP benchmarks. As shown in Table 4, DEG achieves consistently lower optimality gaps than all baseline methods across a wide range of real-world CVRPLib instances. Compared to GFACS, DEG reduces the gap on the same set of instances. Compared to AGFN, our model reduces significant gap on the same set of instances. Relative to LEHD, DEG achieves gap improvements of 0.84% on L2, 20.89% on A1, 9.85% on A2, 14.87% on G1, 36.51% on G2, 52.59% on B1, and 42.42% on B2, while LEHD performs slightly better on L1. Finally, compared to POMO, our model significantly reduces the gap by 73.92%, 66.63%, 86.68%, and 85.05% on L1, L2, A1, and A2. These results demonstrate the superior scalability and generalization ability of DEG in solving large-scale real-world CVRP instances.

Ablation Study

Component Evaluation. We evaluate the contribution of each key component in DEG through an ablation study. We begin by training the backbone model, which involves learning a pure GFlowNet to generate trajectories, serving as the baseline for subsequent comparison. Next, we integrate the diffusion mechanism into the backbone by incorporating the reward-level feedback and noise schedule described in § 4.1, in order to evaluate the effectiveness of the diffusion component. Finally, the GSA decoder (§ 4.3) is applied on top of the previous model to assess its impact.

The results are presented in Table 5. Incorporating diffusion into the backbone leads to significant performance improvements. Adding the GSA module on top of the diffusion-enhanced model further improves performance on the TSP and CVRP across the same instance sizes. In addition to improving performance, GSA also reduces computational resource consumption by shortening the observation distance and decreasing the number of connections per node. As a result, the model is able to efficiently solve 10000-node TSP instances as well as 5000-, 8000- and 10000-node CVRP instances.

Table 5: Ablation Study on TSP and CVRP. Obj. denotes the total route length, and Gap (%) is computed relative to LKH; lower values indicate better results.

TSP500100030005000800010000
Obj.Gap(%)Obj.Gap(%)Obj.Gap(%)Obj.Gap(%)Obj.Gap(%)Obj.Gap(%)
Backbone21.9632.6935.4153.0364.8260.8091.6676.81––––
+ Diffusion18.5412.0226.7415.5648.4520.1964.9725.33––––
+ GSA18.4711.6026.4614.3547.8218.6363.6422.5783.1326.1694.6724.94
CVRP500100030005000800010000
Obj.Gap(%)Obj.Gap(%)Obj.Gap(%)Obj.Gap(%)Obj.Gap(%)Obj.Gap(%)
Backbone76.8821.76148.6124.34389.182.35––––––
+ Diffusion70.8612.23132.6510.74368.99-2.96––––––
+ GSA69.7610.48129.678.49362.11-4.77596.43–907.65–1125.04–

Table 5. “–” indicates that the model was unable to produce a result for a given instance either within the 90-minute time limit or due to GPU memory constraints.

Conclusion

In this paper, we introduce Diffusion-Enhanced GFlowNet (DEG), a generative framework that integrates GFlowNet with diffusion to overcome key limitations of existing GFlowNet-based solvers for vehicle routing problems (VRPs). Specifically, their insufficient flow expansion in high-reward regions. To enable this integration, DEG leverages the intrinsic diversity of GFlowNet to provide edge-specific backward signals as a noise basis for diffusion integration. It then employs the diffusion’s noise schedule to inject noise into these signals, and denoises them through the GFlowNet paradigm, guiding sufficient flow expansion toward high-reward regions to derive better solutions. Furthermore, to enhance scalability and generalization ability, we incorporate a Graph-Scale Adapter (GSA) that enables effective adaptation across diverse instance sizes. Extensive experiments on synthetic benchmarks and real-world datasets, including instances with up to 10,000 nodes, show that DEG delivers favorable performance compared to diffusion-, GFlowNet-based and other neural baselines. These results demonstrate that DEG has strong scalability, efficient inference, and robust generalization for solving VRPs.

While DEG outperforms the strong AR model like LEHD in inference time and generalization, one of the limitations is that DEG’s parallel decoding still falls short in small-scale settings, where AR models excel at fine-grained path construction. Bridging this gap remains an important direction for our future work, which involves enhancing the local decision-making capacity of NAR models. In addition, extending DEG to a wider range of VRP variants is another venue we plan to explore.

More Methodology Detail

Forward Network and Training Paradigm

Following prior work [27, 68, 54, 59], we adopt a Graph Neural Network (GNN) as the forward network θ\theta, incorporating distance information as edge features. GNN employs a sparsification strategy on the input graph G\mathcal{G} to reduce computational complexity. Specifically, the graph retains only the ww shortest edges per node, resulting in a sparse graph G∗=(V,E∗)\mathcal{G}^{*} = (\mathcal{V}, \mathcal{E}^{*}). The node coordinates uv∈R2u_v \in\mathbb{R}^{2} and edge distances ue∈Ru_e \in\mathbb{R} are first embedded into initial node and edge features hi0,eij0∈Rdh_i^0, e_{ij}^0 \in\mathbb{R}^{d} by learnable linear layers, where dd represents the number of hidden units per layer. Then, hi0h_i^0 and eij0e_{ij}^0 are processed by GNN to capture the underlying relationships between nodes and edges. At each layer ll, node and edge features are updated as:

hil+1=hil+ACT⁡(BN⁡(Ulhil+Aj∈Ni(σ(eijl)⊙Vlhjl))),(13)h_i^{l+1} = h_i^l + \operatorname{ACT}\left(\operatorname{BN}\left(U^l h_i^l + \mathop{\mathcal{A}}_{j \in\mathcal{N}_i}\left(\sigma(e_{ij}^l) \odot V^l h_j^l\right)\right)\right), \tag*{(13)}
eijl+1=eijl+ACT⁡(BN⁡(Pleijl+Qlhil+Rlhjl)).(14)e_{ij}^{l+1} = e_{ij}^l + \operatorname{ACT}\left(\operatorname{BN}\left(P^l e_{ij}^l + Q^l h_i^l + R^l h_j^l\right)\right). \tag*{(14)}

Here, UlU^l, VlV^l, PlP^l, QlQ^l, Rl∈Rd×dR^l \in\mathbb{R}^{d \times d} are learnable parameters of the GNN layers; SiLU [16] is used as the activation function for all intermediate layers; BN denotes batch normalization; σ\sigma is the sigmoid function [19]; ⊙\odot is the Hadamard product; and A\mathcal{A} denotes mean pooling over neighbors.

The denoised forward policy η(G∗,θ)\eta(\mathcal{G}^{*}, \theta) is computed using a multi-layer perceptron (MLP) applied to the final-layer GNN embeddings, followed by a sigmoid activation to normalize outputs. The source flow Z(G;θ)Z(\mathcal{G}; \theta) is computed from the final-layer edge embedding ede^d as follows:

Z(G;θ)=M⋅ReLU⁡(J⋅ed+b)+f,(15)Z(\mathcal{G}; \theta) = M \cdot\operatorname{ReLU}(J \cdot e^d + b) + f, \tag*{(15)}

where MM, JJ, bb, and ff are learnable parameters, and ReLU is the activation function.

Analysis of the Learning Target under the Noise Schedule

We describe the implemented signal construction, then derive the population target at each noise level, analyze the two endpoints, and bound its distance from reward-proportional sampling.

Setup and well-posedness

Fix an instance graph G\mathcal{G}. A trajectory τ\tau is a complete construction sequence with reward R(τ)>0R(\tau) > 0, and ∣τ∣|\tau| denotes its number of edges. For TSP, ∣τ∣=n|\tau| = n for every tour. For CVRP, ∣τ∣=n+K(τ)|\tau| = n + K(\tau), where K(τ)K(\tau) is the number of routes.

Edge signal. The edge reward Rˉ(e)\bar{R}(e) is the average reward of sampled trajectories containing edge ee. After z-score normalization, the clean signal is x0[e]=Φ(R^(e))∈(0,1)x_0[e] = \Phi(\widehat{R}(e)) \in(0, 1) (Eq. (5)).

Corruption. At noise level tt (Eq. (6)),

xt[e]=αˉt x0[e]+1−αˉt ϵ[e],ϵ[e]∼N(0,1),αˉt=∏k=1t(1−βk),(16)x_t[e] = \sqrt{\bar{\alpha}_t}\,x_0[e] + \sqrt{1-\bar{\alpha}_t}\,\epsilon[e], \qquad\epsilon[e] \sim\mathcal{N}(0,1), \qquad\bar{\alpha}_t = \prod_{k=1}^{t}(1-\beta_k), \tag*{(16)}

where the noise is sampled independently across edges.

Clamping. Because xt[e]x_t[e] may fall outside [0,1][0,1], we use

x~t[e]=max⁡(clamp⁡(xt[e],0,1),δ)∈[δ,1],δ=10−10.(17)\widetilde{x}_t[e] = \max\left(\operatorname{clamp}(x_t[e],0,1),\delta\right) \in[\delta,1], \qquad\delta= 10^{-10}. \tag*{(17)}

Backward-side trajectory weight. The backward term used in TB is

Wt(τ)=∏e∈τx~t[e]∈[δ∣τ∣,1].(18)W_t(\tau) = \prod_{e \in\tau} \widetilde{x}_t[e] \in[\delta^{|\tau|},1]. \tag*{(18)}

The factors x~t[e]\widetilde{x}_t[e] are used directly rather than normalized over parent states. Thus, WtW_t is a positive trajectory weight rather than a normalized backward transition kernel. The clamping guarantees Wt>0W_t > 0.

Objective. The TB loss for a trajectory is

Lt(τ;θ)=(log⁡Z(G;θ)+log⁡PF(τ;θ)−log⁡R(τ)−log⁡Wt(τ))2(19)L_t(\tau;\theta)=\left(\log Z(\mathcal{G};\theta)+\log P_F(\tau;\theta)-\log R(\tau)-\log W_t(\tau)\right)^2 \tag*{(19)}

Since Wt>0W_t>0 and log⁡Wt\log W_t is bounded, the loss is well defined. Equivalently, this is TB with the trajectory reward R~t(τ)=R(τ)Wt(τ)\widetilde{R}_t(\tau)=R(\tau)W_t(\tau).

Assumption 1 (Population setting). The signal x0x_0 is fixed, trajectories are sampled from a distribution with full support, and optimization is over all strictly positive trajectory distributions PFP_F together with the normalizer Z>0Z>0.

Exact target at every noise level

Lemma 1 (Bias–variance decomposition). For every trajectory τ\tau and noise level tt,

Eϵ[Lt(τ;θ)]=(log⁡Z(G;θ)+log⁡PF(τ;θ)−log⁡R(τ)−μt(τ))2+σt2(τ),(20)\mathbb{E}_{\epsilon}\left[L_t(\tau;\theta)\right]=\left(\log Z(\mathcal{G};\theta)+\log P_F(\tau;\theta)-\log R(\tau)-\mu_t(\tau)\right)^2+\sigma_t^2(\tau), \tag*{(20)}

where

μt(τ)=Eϵ[log⁡Wt(τ)]=∑e∈τht(x0[e]),(21)\mu_t(\tau)=\mathbb{E}_{\epsilon}\left[\log W_t(\tau)\right]=\sum_{e\in\tau}h_t(x_0[e]), \tag*{(21)}

with

ht(u)=Eϵ∼N(0,1)[log⁡max⁡(clamp⁡(αˉtu+1−αˉtϵ,0,1),δ)],(22)h_t(u)=\mathbb{E}_{\epsilon\sim\mathcal{N}(0,1)}\left[\log\max\left(\operatorname{clamp}\left(\sqrt{\bar{\alpha}_t}u+\sqrt{1-\bar{\alpha}_t}\epsilon,0,1\right),\delta\right)\right], \tag*{(22)}

and σt2(τ)=Var⁡ϵ[log⁡Wt(τ)]\sigma_t^2(\tau)=\operatorname{Var}_{\epsilon}[\log W_t(\tau)], which does not depend on θ\theta.

Proof. Using E[(a−X)2]=(a−E[X])2+Var⁡(X)\mathbb{E}[(a-X)^2]=(a-\mathbb{E}[X])^2+\operatorname{Var}(X), set

a=log⁡Z+log⁡PF(τ),X=log⁡R(τ)+log⁡Wt(τ).a=\log Z+\log P_F(\tau),\qquad X=\log R(\tau)+\log W_t(\tau).

For fixed τ\tau, R(τ)R(\tau) is deterministic, while log⁡Wt(τ)∈[∣τ∣log⁡δ,0]\log W_t(\tau)\in[|\tau|\log\delta,0]. The result follows from log⁡Wt(τ)=∑e∈τlog⁡x~t[e]\log W_t(\tau)=\sum_{e\in\tau}\log\widetilde{x}_t[e] and linearity of expectation. □\square

Proposition 1 (Exact target). Under Assumption 1, the expected TB loss at noise level tt has the unique population minimizer

PFt(τ)=R(τ)eμt(τ)Zt,Zt=∑τ′R(τ′)eμt(τ′).(23)P_F^t(\tau)=\frac{R(\tau)e^{\mu_t(\tau)}}{Z_t},\qquad Z_t=\sum_{\tau'}R(\tau')e^{\mu_t(\tau')}. \tag*{(23)}

Proof. By Lemma 1, the θ\theta-dependent term is minimized when

ZPF(τ)=R(τ)eμt(τ)ZP_F(\tau)=R(\tau)e^{\mu_t(\tau)}

for every trajectory. Full support requires this equality for all τ\tau. Summing over trajectories gives Z=ZtZ=Z_t, yielding (23). □\square

Remark 1. Proposition 1 is exact. The injected noise affects the optimum through Eϵ[log⁡Wt]\mathbb{E}_{\epsilon}[\log W_t], while its variance contributes only the θ\theta-independent term σt2\sigma_t^2. The result is independent of the trajectory sampling distribution as long as it has full support, including on-policy sampling. When x0x_0 changes during training, the proposition describes the population target associated with the current x0x_0 and noise level. It does not imply convergence of the parameterized training dynamics.

Low-noise endpoint: exploitation

At αˉt=1\bar{\alpha}_t=1,

x~0[e]=max⁡(x0[e],δ),h0(u)=log⁡max⁡(u,δ).\widetilde{x}_0[e]=\max(x_0[e],\delta),\qquad h_0(u)=\log\max(u,\delta).

Define

W0(τ)=∏e∈τmax⁡(x0[e],δ).W_0(\tau)=\prod_{e\in\tau}\max(x_0[e],\delta).

When x0[e]≥δx_0[e]\ge\delta along τ\tau, this reduces to ∏e∈τx0[e]\prod_{e\in\tau}x_0[e]. Proposition 1 then gives

PF0(τ)∝R(τ)W0(τ).(24)P_F^0(\tau)\propto R(\tau)W_0(\tau). \tag*{(24)}

Assumption 2 (Edge decomposability). There exists a constant c>0c > 0 such that

∏e∈τx0[e]=cR(τ)\prod_{e \in\tau} x_0[e] = cR(\tau)

for every trajectory τ\tau.

Proposition 2 (Low-noise endpoint). (a) Under Assumption 2 and x0[e]≥δx_0[e] \ge\delta,

PF0(τ)∝R(τ)2.P_F^0(\tau) \propto R(\tau)^2.

(b) Without Assumption 2, let πR(τ)∝R(τ)\pi_R(\tau) \propto R(\tau). Then

EPF0[R]−EπR[R]=Cov⁡πR(R,W0)EπR[W0].(25)\mathbb{E}_{P_F^0}[R] - \mathbb{E}_{\pi_R}[R] = \frac{\operatorname{Cov}_{\pi_R}(R,W_0)}{\mathbb{E}_{\pi_R}[W_0]}. \tag*{(25)}

Proof. For (a), substitute W0(τ)=cR(τ)W_0(\tau) = cR(\tau) into (24). For (b),

PF0(τ)=πR(τ)W0(τ)EπR[W0].P_F^0(\tau) = \frac{\pi_R(\tau)W_0(\tau)}{\mathbb{E}_{\pi_R}[W_0]}.

Therefore,

EPF0[R]=EπR[RW0]EπR[W0],\mathbb{E}_{P_F^0}[R] = \frac{\mathbb{E}_{\pi_R}[RW_0]}{\mathbb{E}_{\pi_R}[W_0]},

which gives (25).

Our CDF-based construction of x0x_0 does not satisfy Assumption 2 exactly, so the R2R^2 form is a special case rather than a general property. (25) requires no such assumption: the low-noise target has higher expected reward than reward-proportional sampling whenever Cov⁡πR(R,W0)>0\operatorname{Cov}_{\pi_R}(R,W_0) > 0. This is precisely the behavior encouraged by constructing x0x_0 from edge-reward statistics.

High-noise endpoint: exploration

Proposition 3 (High-noise endpoint). At αˉt=0\bar{\alpha}_t = 0,

μT(τ)=cT∣τ∣,\mu_T(\tau) = c_T|\tau|,

where

cT=Eϵ[log⁡max⁡(clamp⁡(ϵ,0,1),δ)].c_T = \mathbb{E}_{\epsilon}\left[\log\max(\operatorname{clamp}(\epsilon,0,1),\delta)\right].

Hence,

PFT(τ)∝R(τ)P_F^T(\tau) \propto R(\tau)

for TSP, while for CVRP,

PFT(τ)∝R(τ)ecTK(τ).P_F^T(\tau) \propto R(\tau)e^{c_TK(\tau)}.

Proof. At αˉt=0\bar{\alpha}_t = 0, x~T[e]\widetilde{x}_T[e] depends only on ϵ[e]\epsilon[e] and is independent of x0[e]x_0[e]. Thus hT(u)=cTh_T(u) = c_T for all uu, giving μT(τ)=cT∣τ∣\mu_T(\tau) = c_T|\tau|.

For TSP, every tour contains nn edges, so ecTne^{c_Tn} is absorbed into the normalizer. For CVRP, ∣τ∣=n+K(τ)|\tau| = n + K(\tau); after absorbing ecTne^{c_Tn}, the remaining factor is ecTK(τ)e^{c_TK(\tau)}.

Remark 2 (CVRP). For the implemented value δ=10−10\delta= 10^{-10}, numerical integration gives cT≈−11.9c_T \approx-11.9. The CVRP endpoint is therefore reward-proportional among solutions with the same number of routes, while favoring fewer routes across groups with different K(τ)K(\tau).

On the evaluated samples (n=500n = 500 and n=1000n = 1000, 32 instances each), route count and cost are positively correlated on every instance, with mean correlations of +0.53+0.53 and +0.36+0.36, respectively. This does not imply that fewer routes are always preferable or that near-optimal solutions always use the minimum number of routes. Therefore, the unconditional reward-proportional endpoint is exact for TSP only; for CVRP, the exploration benefit is evaluated empirically.

Rate between the endpoints

Lemma 2 (Monotonicity and Lipschitz constant of hth_t). Let αˉt<1\bar{\alpha}_t < 1. For 0≤u≤v≤10 \le u \le v \le1,

0≤ht(v)−ht(u)≤Kt(v−u),Kt≤αˉtlog⁡(1/δ)2π(1−αˉt).(26)0 \le h_t(v) - h_t(u) \le K_t(v-u), \qquad K_t \le\frac{\sqrt{\bar{\alpha}_t}\log(1/\delta)}{\sqrt{2\pi}(1-\bar{\alpha}_t)}. \tag*{(26)}

Proof. Let st=1−αˉts_t = \sqrt{1-\bar{\alpha}_t} and

ℓ(z)=log⁡max⁡(clamp⁡(z,0,1),δ).\ell(z) = \log\max(\operatorname{clamp}(z,0,1),\delta).

Then

ht(u)=Eε[ℓ(αˉtu+stε)].h_t(u) = \mathbb{E}_{\varepsilon}\left[\ell\left(\sqrt{\bar{\alpha}_t}u+s_t\varepsilon\right)\right].

Since ℓ\ell is nondecreasing, ht(v)≥ht(u)h_t(v) \ge h_t(u). Moreover, ℓ′(z)=1/z\ell'(z) = 1/z on (δ,1)(\delta,1) and 0 elsewhere. Therefore,

ht′(u)=αˉt∫δ11z1stφ(z−αˉtust) dz≤αˉtlog⁡(1/δ)st2π,(27)h_t'(u) = \sqrt{\bar{\alpha}_t}\int_{\delta}^{1}\frac{1}{z}\frac{1}{s_t}\varphi\left(\frac{z-\sqrt{\bar{\alpha}_t}u}{s_t}\right)\,dz \le\frac{\sqrt{\bar{\alpha}_t}\log(1/\delta)}{s_t\sqrt{2\pi}}, \tag*{(27)}

where φ\varphi is the standard normal density and φ≤1/2π\varphi\le1/\sqrt{2\pi}.

For δ=10−10\delta= 10^{-10}, log⁡(1/δ)≈23.0\log(1/\delta) \approx23.0, so the constant is explicit.

Theorem 1 (Distance to reward-proportional sampling, TSP). For TSP with nn nodes and αˉt<1\bar{\alpha}_t < 1, let PFtP_F^t be the target in Proposition 1 and πR(τ)∝R(τ)\pi_R(\tau) \propto R(\tau). Then

KL⁡(PFt∥πR)≤nKt≤nαˉtlog⁡(1/δ)2π(1−αˉt)⟶αˉt→00.(28)\operatorname{KL}(P_F^t \mathbin\Vert\pi_R) \le nK_t \le\frac{n\sqrt{\bar{\alpha}_t}\log(1/\delta)}{\sqrt{2\pi}(1-\bar{\alpha}_t)} \underset{\bar{\alpha}_t\to0}{\longrightarrow} 0. \tag*{(28)}

Proof. Let

g(τ)=log⁡PFt(τ)πR(τ)=μt(τ)−log⁡ZtZR,ZR=∑τR(τ).g(\tau) = \log\frac{P_F^t(\tau)}{\pi_R(\tau)} = \mu_t(\tau) - \log\frac{Z_t}{Z_R}, \qquad Z_R = \sum_{\tau}R(\tau).

Each TSP tour contains nn edges. By Lemma 2, each term ht(x0[e])h_t(x_0[e]) varies over an interval of length at most KtK_t. Hence, μt(τ)\mu_t(\tau) varies by at most nKtnK_t, and so does g(τ)g(\tau).

Because both distributions are normalized, EπR[eg]=1\mathbb{E}_{\pi_R}[e^g] = 1, which implies inf⁡τg≤0≤sup⁡τg\inf_{\tau} g \le0 \le\sup_{\tau}g. Therefore,

KL⁡(PFt∥πR)=EPFt[g]≤sup⁡τg≤nKt.\operatorname{KL}(P_F^t \mathbin\Vert\pi_R) = \mathbb{E}_{P_F^t}[g] \le\sup_{\tau}g \le nK_t.

Signal correlation. Let σ02\sigma_0^2 denote the variance of x0[e]x_0[e] over edges. Since ε\varepsilon is independent of x0x_0,

Cov⁡(xt,x0)=αˉtσ02,\operatorname{Cov}(x_t,x_0) = \sqrt{\bar{\alpha}_t}\sigma_0^2,

and

Var⁡(xt)=αˉtσ02+1−αˉt.\operatorname{Var}(x_t) = \bar{\alpha}_t\sigma_0^2 + 1-\bar{\alpha}_t.

Thus,

ρ(t)=αˉtσ02αˉtσ02+1−αˉt,(29)\rho(t) = \sqrt{\frac{\bar{\alpha}_t\sigma_0^2}{\bar{\alpha}_t\sigma_0^2+1-\bar{\alpha}_t}}, \tag*{(29)}

which decreases monotonically from 1 to 0.

As αˉt→0\bar{\alpha}_t \to0, ρ(t)=Θ(αˉt)\rho(t) = \Theta(\sqrt{\bar{\alpha}_t}), so (28) vanishes at rate O(nρ(t))O(n\rho(t)). The dependence on nn also shows that the bound is mainly informative late in the schedule, when αˉt≪1/n\sqrt{\bar{\alpha}_t} \ll1/n. Since αˉt\bar{\alpha}_t decreases with tt, the bound tightens throughout training. The edge-dependent reward signal is gradually weakened, and the TSP target converges to reward-proportional sampling at the endpoint. For CVRP, the same argument applies among trajectories with the same number of routes.

Trajectories and solutions

PFP_F is defined over trajectories rather than solutions. For TSP, each tour has the same trajectory multiplicity—between 1 and 2n2n, depending on the convention for starting node and direction. This common factor cancels, so reward proportionality over trajectories also holds over solutions.

For CVRP, the number of trajectories representing a solution can depend on its route structure. This introduces the same qualification as the factor ecTK(τ)e^{cT_K(\tau)} in Remark 2; the issue disappears when comparing solutions with the same route structure.

More Experiment Detail

GSA Comparison Results

We validate the behavior that the best outcomes of larger-scale instances often appear at earlier training stages. We evaluate the model on datasets of varying sizes (200, 500, and 1000 nodes), each containing 128 test cases. The model is trained on 100-node instances and evaluated using checkpoints saved at different training epochs, with each epoch comprising 20 training steps. The results are presented in Figure 2. As the instance size increases from 200 to 500 and then to 1000 nodes, the performance peak occurs progressively earlier during training. Moreover, the model’s performance degrades significantly after reaching its peak, especially on larger-scale instances.

Figure 2. The original performance of DEG test on different scale instance. Gap (%) is computed relative to LKH, and lower values indicate better results.

After using GSA, as illustrated in Figure 3, GSA successfully constrains the optimal inference checkpoints across different instance sizes into a consistent interval. Moreover, as training progresses, the model shows a steadily improving performance at later checkpoints—unlike the original decoder, which tends to degrade after early peaks. In addition, GSA achieves overall better performance compared to the baseline setup without GSA. These results indicate that GSA mitigates spatial pattern overfitting to the training instance size and enables the model to derive consistent results across varying instance scales.

Figure 3. The performance of GSA-based DEG test on different scale instance. Gap (%) is computed relative to LKH, and lower values indicate better results.

TSP comparison on Diffusion-Based Solver with Two-Opt

We compare DEG with existing diffusion-based models, all enhanced with Two-Opt post-processing, and the results are summarized in Table 6. Our method, DEG, achieves an objective value reduction of 2.42%, 2.27%, and 2.74% on 500-, 1000-, 3000-node instance over DIFUSCO. Compared to Fast-T2T, DEG yields improvements of 0.88%, 1.66%, and 4.17% on the same instance sizes. Furthermore, DEG outperforms DEITSP by 0.80%, 2.04% on 500-, 1000-, 3000-node instances. Notably, DEG is capable of scaling to larger problem sizes, specifically 5,000, 8,000 and 10,000 nodes, whereas other diffusion-based models fail to run due to memory limitations.

TSP and CVRP comparison in small-scale problems

To evaluate the performance of DEG on small-scale problems, we additionally conduct experiments on TSP and CVRP instances of 100 and 200 nodes. The comparisons include both diffusion-based and GFlowNet-based baselines; for CVRP, only GFlowNet-based baselines are reported because diffusion-based solvers do not directly apply to this setting. The results, summarized in Table 7, show that DEG consistently surpasses all diffusion-based and GFlowNet-based methods on TSP200, CVRP100, and CVRP200, and achieves competitive or superior performance on TSP100. These findings demonstrate that DEG also maintains strong optimization capability on problems of relatively small scales.

Multiple Scale training

We conducted additional experiments where DEG is trained on multiple node sizes. Specifically, for both TSP and CVRP, we trained models on instances of size 100, 200, 500, and 1000, and evaluated them on larger test sets with 500, 1000, 3000, 5000, 8000, and 10000 nodes. For each training scale, we report results with and without GSA rescaling.

The results provided in Table 8 and Table 9 show that DEG maintains strong performance even without GSA, while GSA further strengthens generalization on very large instances. These findings confirm that the scalability of DEG is not dependent on training exclusively at the 100-node scale, and that the model possesses substantial inherent scale robustness.

500500100010003000300050005000800080001000010000
Obj.Gap(%)Obj.Gap(%)Obj.Gap(%)Obj.Gap(%)Obj.Gap(%)Obj.Gap(%)
100(w/o GSA)18.5412.0226.7415.5648.4520.1964.9725.33––––
200(w/o GSA)18.4411.4226.5014.5247.5918.0664.1623.77––––
500(w/o GSA)18.059.0626.4214.1747.1917.0761.5518.73––––
1000(w/o GSA)18.4111.2425.8711.8046.3214.9163.1421.80––––
100(w/ GSA)18.4711.6026.4614.3547.8218.6363.6422.5783.1326.1694.6724.94
200(w/ GSA)18.3310.7626.3413.8346.9116.3762.1619.9182.1924.7491.0920.20
500(w/ GSA)18.089.2425.9712.2346.0514.2461.1117.8878.1618.6287.4415.39
1000(w/ GSA)18.2810.4525.8711.8045.0914.8662.3120.2079.0619.9989.5818.21

Table 8. Training on different scales for TSP and testing without and with GSA. Obj. denotes the total route length, and Gap (%) is computed relative to LKH. For both metrics, lower is better. “–” indicates that the model was unable to produce a result for a given instance either within the 90-minute time limit or due to GPU memory constraints.

500500100010003000300050005000800080001000010000
Obj.Gap(%)Obj.Gap(%)Obj.Gap(%)Obj.Gap(%)Obj.Gap(%)Obj.Gap(%)
100 (w/o GSA)69.7610.48129.678.49362.11-4.77596.43-7.24907.65–1125.04–
200 (w/o GSA)67.757.30127.706.84362.43-4.69580.73-9.68987.01–1094.82–
500 (w/o GSA)66.765.73124.704.34360.80-5.12577.24-10.22894.98–1072.27–
1000(w/o GSA)69.6810.36123.133.02360.42-5.21568.73-11.54885.18–1060.53–
100 (w/ GSA)70.8612.23132.6510.74368.99-2.96––––––
200 (w/ GSA)68.368.37129.508.35368.85-3.00––––––
500 (w/ GSA)66.765.73125.655.13367.13-3.45––––––
1000(w/ GSA)70.5411.72123.133.02366.19-3.70––––––

Table 9. Training on different scales for CVRP and testing without and with GSA. Obj. denotes the total route length, and Gap (%) is computed relative to LKH. For both metrics, lower values indicate better results. “–” indicates that the model was unable to produce a result for a given instance either within the 90-minute time limit or due to GPU memory constraints.

Diversity Test

As shown in Table 10, we evaluate diversity on both TSP and CVRP by comparing the trajectories generated by (i) a reinforcement-learning baseline, (ii) a vanilla GFlowNet implementation (the backbone of our method), and (iii) our proposed DEG model. The diversity metric [46] is defined as the average number of edges in one trajectory that do not appear in another, a standard measure of route-level diversity in VRP. In this experiment, all settings are kept identical across models, except for the training paradigm. The results show that DEG consistently achieves higher diversity than standard GFlowNets, demonstrating that our diffusion-enhanced design effectively enriches the exploration space.

TSP100500100030005000
RL17.6096.07217.20819.341516.64
GFlowNet20.36126.95294.301074.531895.23
DEG21.79128.97302.631145.792082.36
CVRP100500100030005000
RL16.57181.36400.711210.162372.48
GFlowNet19.33212.27443.731526.562705.91
DEG20.54217.02471.681648.822909.12

Table 10. Diversity comparison on TSP and CVRP, higher values indicate better results.

Learning Efficiency

We conducted additional experiments on a fixed problem scale and distribution to assess learning efficiency under controlled settings. Specifically, we used 10,000 uniformly sampled TSP and CVRP instances with size n=200n = 200 and trained all models with identical configurations, differing only in the training paradigm (RL, standard GFlowNet, PO [45], and our DEG). The trained models were then evaluated on TSP/CVRP test instances at n=200n = 200, n=500n = 500, and n=1000n = 1000. The results, reported in Appendix Table 11, show that DEG exhibits strong optimization performance and superior learning efficiency compared to these baselines under matched training conditions.

Applicability to Other Combinatorial Optimization Problems

To further assess the generalization ability of our proposed DEG beyond routing problems, we extended our experiments to additional combinatorial optimization domains. Specifically, we considered: (1) SMTWTP (Single-Machine Total Weighted Tardiness Problem), a classical single-machine scheduling problem where the objective is to minimize the total weighted tardiness of jobs processed on one machine. (2) BPP (Bin Packing Problem), a packing optimization problem that aims to minimize the number of bins required to accommodate items of varying sizes under capacity constraints, thereby improving space utilization. In Appendix Table 12, regarding SMTWTP, the instance sizes (100, 200, and 500) correspond to the number of jobs, with Obj. denoting total weighted tardiness. Regarding BPP, the instance sizes (120, 250, and 500) correspond to the number of items, with Obj. (%) denoting space utilization rate, i.e., the proportion of total bin capacity effectively used by the packed items. As suggested by those results, the proposed DEG model outperforms both DeepACO [61] and GFACS [27] on these tasks, demonstrating its potential as a general neural combinatorial optimization framework beyond routing.

TSP2005001000
Obj.Gap(%)Obj.Gap(%)Obj.Gap(%)
RL12.1214.1219.2816.5027.8220.22
GFlowNet12.0813.7519.0214.9227.2917.93
PO11.9712.7118.9314.3827.1117.16
DEG11.9112.1518.7913.5326.8015.82
CVRP2005001000
Obj.Gap(%)Obj.Gap(%)Obj.Gap(%)
RL32.9417.4872.5014.82133.4111.62
GFlowNet32.0314.2371.4913.22132.4710.84
PO32.1314.5971.7713.67133.3911.60
DEG31.9013.7770.1511.10131.239.80

Table 11. Comparison of training efficiency on TSP and CVRP. Obj. denotes the total route length, and Gap (%) is computed relative to LKH. For both metrics, lower values indicate better results.

Detailed Introduction of GFlowNet

The Generative Flow Network (GFlowNet) is probabilistic generative model that treats the process of sampling from a target distribution as a sequential decision-making problem [4, 5]. Formally, a GFlowNet operates on a fully-observed, deterministic Markov Decision Process (MDP) with a set of states S\mathcal{S}, a set of actions A⊆S×S\mathcal{A} \subseteq\mathcal{S} \times\mathcal{S}, and a designated initial state s0s_0. Certain states are terminal and have no outgoing actions; we denote the set of terminal states by X\mathcal{X}. Each terminal state x∈Xx \in\mathcal{X} is reachable from s0s_0 through at least one (not necessarily unique) sequence of actions.

A complete trajectory is defined as τ=(s0→s1→⋯→sn)\tau= (s_0 \to s_1 \to\cdots\to s_n), where sn∈Xs_n \in\mathcal{X} and every transition satisfies (si,si+1)∈A(s_i, s_{i+1}) \in\mathcal{A}. A forward policy PF(s′∣s)P_F(s' \mid s) defines the probability distribution over next states from ss. It induces a distribution over trajectories:

PF(τ)=PF(s0→s1→⋯→sn)=∏i=0n−1PF(si+1∣si).P_F(\tau) = P_F(s_0 \to s_1 \to\cdots\to s_n) = \prod_{i=0}^{n-1} P_F(s_{i+1} \mid s_i).

Each terminal state x∈Xx \in\mathcal{X} is associated with a reward R(x)>0R(x) > 0, interpreted as an unnormalized probability mass. The learning objective of a GFlowNet is to produce a policy PFP_F whose induced marginal distribution over terminal states satisfies

PF(x)∝R(x).P_F(x) \propto R(x).

In other words, a GFlowNet learns to sample terminal objects with probability proportional to their reward.

Trajectory Balance (TB). The trajectory balance objective [39] introduces a scalar parameter ZθZ_\theta (an estimate of the partition function) and a backward policy PBP_B. For a complete trajectory τ=(s0→⋯→sn=x)\tau= (s_0 \to\cdots\to s_n = x), the TB loss is

ℓTB(τ;θ)=(log⁡Zθ∏i=0n−1PF(si+1∣si;θ)R(x)∏i=0n−1PB(si∣si+1;θ))2.\ell_{\mathrm{TB}}(\tau;\theta) = \left(\log\frac{Z_\theta\prod_{i=0}^{n-1} P_F(s_{i+1} \mid s_i;\theta)}{R(x) \prod_{i=0}^{n-1} P_B(s_i \mid s_{i+1};\theta)}\right)^2.

If the TB loss is driven to zero for all trajectories, the forward policy satisfies the desired reward-proportional condition. In practice, GFlowNets predict the log-probabilities of both forward and backward transitions, as well as the log-flow F(s)F(s) and the log-partition constant log⁡Z\log Z.

Training and Exploration. TB losses depend on transitions or full trajectories, but do not prescribe how trajectories should be chosen. A common approach is on-policy training, where trajectories are sampled based on the current forward policy PFP_F (which assigns probabilities to edges) and backward policy PBP_B (which determines either exploration or exploitation during training), and the TB objective is minimized through gradient descent.

SMTWTP100200500
Obj.↓\downarrowTime(s)Obj.↓\downarrowTime(s)Obj.↓\downarrowTime(s)
ACO361.220.821608.261.7011015.392.84
DeepACO223.360.93905.191.811567.203.56
GFACS40.671.04119.322.25559.313.68
DEG37.700.14103.130.34510.670.98
BPP120250500
Obj.↑\uparrowTime(s)Obj.↑\uparrowTime(s)Obj.↑\uparrowTime(s)
ACO90.652.9590.365.8590.1710.00
DeepACO93.462.3793.105.5093.0810.75
GFACS94.682.3894.035.5693.6510.77
DEG96.940.2796.300.5895.371.38

Table 12. Results on SMTWTP and BPP benchmarks. For SMTWTP, Obj. denotes total weighted tardiness (lower is better); for BPP, Obj. denotes space utilization rate (higher is better). Gap (%) is computed relative to LKH, where lower values indicate better performance.

Conditional GFlowNets. In many applications, including combinatorial optimization, the reward and admissible actions depend on an input instance. Conditional GFlowNets extend the formulation so that PFP_F and PBP_B are conditioned on input features, enabling generalization to unseen instances and supporting tasks where solutions correspond to variable-sized or structured objects.

Broad Impact and Safeguards.

Diffusion-enhanced GFlowNet for vehicle routing problems has the potential to improve the efficiency of logistics and transportation systems, reducing operational costs, fuel consumption, and environmental impact. However, applying such approaches in real-world settings requires careful testing and validation. To support reliable use, we emphasize thorough evaluation across diverse scenarios, clearly document model assumptions and limitations, and recommend combining learning-based methods with classical optimization or constraint-checking mechanisms when appropriate. Domain-specific validation is strongly encouraged to ensure responsible deployment.

References

  1. [1]Florian Arnold, Michel Gendreau, and Kenneth Sörensen. Efficiently solving very large-scale routing problems. Computers & operations research, 107:32–42, 2019.DOI
  2. [2]Barrie M Baker and MA1951066 Ayechew. A genetic algorithm for the vehicle routing problem. Computers & Operations Research, 30(5):787–800, 2003.DOI
  3. [3]John E Bell and Patrick R McMullen. Ant colony optimization techniques for the vehicle routing problem. Advanced engineering informatics, 18(1):41–48, 2004.DOI
  4. [4]Emmanuel Bengio, Moksh Jain, Maksym Korablyov, Doina Precup, and Yoshua Bengio. Flow network based generative models for non-iterative diverse candidate generation. Advances in Neural Information Processing Systems, 34:27381–27394, 2021.arxiv.org/abs/2106.04399
  5. [5]Yoshua Bengio, Salem Lahlou, Tristan Deleu, Edward J Hu, Mo Tiwari, and Emmanuel Bengio. Gflownet foundations. Journal of Machine Learning Research, 24(210):1–55, 2023.
  6. [6]DD Bochtis and Claus G Sørensen. The vehicle routing problem in field logistics part i. Biosystems engineering, 104(4):447–457, 2009.DOI
  7. [7]DD Bochtis and Claus G Sørensen. The vehicle routing problem in field logistics: Part ii. Biosystems engineering, 105(2):180–188, 2010.DOI
  8. [8]Olli Bräysy and Michel Gendreau. Genetic algorithms for the vehicle routing problem with time windows. Arpakannus,(1), pages 33–38, 2001.
  9. [9]Xavier Bresson and Thomas Laurent. The transformer network for the traveling salesman problem. arXiv preprint arXiv:2103.03012, 2021.arxiv.org/abs/2103.03012
  10. [10]Francesco Carrabs, Raffaele Cerulli, and Anna Sciomachen. An exact approach for the grocery delivery problem in urban areas. Soft Computing, 21:2439–2450, 2017.DOI
  11. [11]Diego Cattaruzza, Nabil Absi, Dominique Feillet, and Jesús González-Feliu. Vehicle routing problems for city logistics. EURO Journal on Transportation and Logistics, 6(1):51–79, 2017.
  12. [12]Yihang Chen and Lukas Mauch. Order-preserving gflownets. In The Twelfth International Conference on Learning Representations.
  13. [13]Wen-Chyuan Chiang and Robert A Russell. Simulated annealing metaheuristics for the vehicle routing problem with time windows. Annals of Operations Research, 63:3–27, 1996.DOI
  14. [14]Goran Ćirović, Dragan Pamučar, and Darko Božanić. Green logistic vehicle routing problem: Routing light delivery vehicles in urban areas using a neuro-fuzzy model. Expert Systems with Applications, 41(9):4245–4258, 2014.DOI
  15. [15]Prafulla Dhariwal and Alexander Nichol. Diffusion models beat gans on image synthesis. Advances in neural information processing systems, 34:8780–8794, 2021.
  16. [16]Stefan Elfwing, Eiji Uchibe, and Kenji Doya. Sigmoid-weighted linear units for neural network function approximation in reinforcement learning. Neural networks, 107:3–11, 2018.DOI
  17. [17]Sotiris P Gavialis, Grigorios D Konstantakopoulos, and Ilias P Tatsiopoulos. Vehicle routing problem for urban freight transportation: A review of the recent literature. In Operational Research in the Digital Era–ICT Challenges: 6th International Symposium and 28th National Conference on Operational Research, Thessaloniki, Greece, June 2017, pages 89–104. Springer, 2019.
  18. [18]Alexandros Graikos, Nikolay Malkin, Nebojsa Jojic, and Dimitris Samaras. Diffusion models as plug-and-play priors. Advances in Neural Information Processing Systems, 35:14715–14728, 2022.DOI
  19. [19]Jun Han and Claudio Moraga. The influence of the sigmoid function parameters on the speed of backpropagation learning. In International workshop on artificial neural networks, pages 195–201. Springer, 1995.DOI
  20. [20]Keld Helsgaun. An effective implementation of the lin–kernighan traveling salesman heuristic. European journal of operational research, 126(1):106–130, 2000.
  21. [21]Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. Advances in neural information processing systems, 33:6840–6851, 2020.arxiv.org/abs/2006.11239
  22. [22]Yu-Hsiang Hsiao, Mu-Chen Chen, Kuan-Yu Lu, and Cheng-Lin Chin. Last-mile distribution planning for fruit-and-vegetable cold chains. The International Journal of Logistics Management, 29(3):862–886, 2018.DOI
  23. [23]Rongjie Huang, Jiawei Huang, Dongchao Yang, Yi Ren, Luping Liu, Mingze Li, Zhenhui Ye, Jinglin Liu, Xiang Yin, and Zhou Zhao. Make-an-audio: Text-to-audio generation with prompt-enhanced diffusion models. In International Conference on Machine Learning, pages 13916–13932. PMLR, 2023.arxiv.org/abs/2301.12661
  24. [24]Ziwei Huang, Jianan Zhou, Zhiguang Cao, and Yixin Xu. Rethinking light decoder-based solvers for vehicle routing problems. In International Conference on Learning Representations (ICLR), 2025.arxiv.org/abs/2503.00753
  25. [25]Zarif Ikram, Ling Pan, and Dianbo Liu. Evolution guided generative flow networks. In ICLR 2024 Workshop on Generative and Experimental Perspectives for Biomolecular Design.arxiv.org/abs/2402.02186
  26. [26]Moksh Jain, Emmanuel Bengio, Alex Hernandez-Garcia, Jarrid Rector-Brooks, Bonaventure FP Dossou, Chanakya Ajit Ekbote, Jie Fu, Tianyu Zhang, Michael Kilgour, Dinghuai Zhang, et al. Biological sequence design with flownets. In International Conference on Machine Learning, pages 9786–9801. PMLR, 2022.arxiv.org/abs/2203.04115
  27. [27]Minsu Kim, Sanghyeok Choi, Hyeonah Kim, Jiwoo Son, Jinkyoо Park, and Yoshua Bengio. Ant colony sampling with flownets for combinatorial optimization. In The 28th International Conference on Artificial Intelligence and Statistics, 2025.arxiv.org/abs/2403.07041
  28. [28]Zhifeng Kong, Wei Ping, Jiajі Huang, Kexin Zhao, and Bryan Catanzaro. Diffwave: A versatile diffusion model for audio synthesis. In International Conference on Learning Representations.
  29. [29]Grigorios D Konstantakopoulos, Sotiris P Gayialis, and Evripidis P Kechagias. Vehicle routing problem and related algorithms for logistics distribution: A literature review and classification. Operational research, 22(3):2033–2062, 2022.
  30. [30]Wouter Kool, Herke van Hoof, and Max Welling. Attention, learn to solve routing problems! In International Conference on Learning Representations, 2019.arxiv.org/abs/1803.08475
  31. [31]Yiyo Kuo. Using simulated annealing to minimize fuel consumption for the time-dependent vehicle routing problem. Computers & Industrial Engineering, 59(1):157–165, 2010.DOI
  32. [32]Yeong-Dae Kwon, Jin-ho Choo, Byoungjin Kim, Iljoо Yoon, Youngjune Gwon, and Seungjai Min. Pomo: Policy optimization with multiple optima for reinforcement learning. Advances in Neural Information Processing Systems, 33:21188–21198, 2020.
  33. [33]Kaijun Leng and Shanghong Li. Distribution path optimization for intelligent logistics vehicles of urban rail transportation using vrp optimization model. IEEE Transactions on Intelligent Transportation Systems, 23(2):1661–1669, 2021.DOI
  34. [34]Yang Li, Jinpei Guo, Runzhong Wang, and Junchi Yan. T2t: From distribution learning in training to gradient search in testing for combinatorial optimization. Advances in Neural Information Processing Systems, 36:50020–50040, 2023.DOI
  35. [35]Yang Li, Jinpei Guo, Runzhong Wang, Hongyuan Zha, and Junchi Yan. Fast t2t: Optimization consistency speeds up diffusion-based training-to-testing solving for combinatorial optimization. Advances in Neural Information Processing Systems, 37:30179–30206, 2024.arxiv.org/abs/2502.02941
  36. [36]Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In International Conference on Learning Representations.
  37. [37]Ilya Loshchilov and Frank Hutter. Sgdr: Stochastic gradient descent with warm restarts. In International Conference on Learning Representations, 2022.
  38. [38]Fu Luo, Xi Lin, Fei Liu, Qingfu Zhang, and Zhenkun Wang. Neural combinatorial optimization with heavy decoder: Toward large scale generalization. Advances in Neural Information Processing Systems, 36:8845–8864, 2023.arxiv.org/abs/2310.07985
  39. [39]Nikolay Malkin, Moksh Jain, Emmanuel Bengio, Chen Sun, and Yoshua Bengio. Trajectory balance: Improved credit assignment in flownets. Advances in Neural Information Processing Systems, 35:5955–5967, 2022.DOI
  40. [40]Mazin Abed Mohammed, Mohd Khanapi Abd Ghani, Raed Ibraheem Hamed, Salama A Mostafa, Mohd Sharifuddin Ahmad, and Dheyaa Ahmed Ibrahim. Solving vehicle routing problem by using improved genetic algorithm for optimal solution. Journal of computational science, 21:255–262, 2017.DOI
  41. [41]Roberto Montemanni, Luca Maria Gambardella, Andrea Emilio Rizzoli, and Alberto V Donati. Ant colony system for a dynamic vehicle routing problem. Journal of combinatorial optimization, 10:327–343, 2005.DOI
  42. [42]Douglas C Montgomery and George C Runger. Applied statistics and probability for engineers. John wiley & sons, 2010.
  43. [43]Andrei Cristian Nica, Moksh Jain, Emmanuel Bengio, Cheng-Hao Liu, Maksym Korablyov, Michael M Bronstein, and Yoshua Bengio. Evaluating generalization in flownets for molecule design. In ICLR2022 Machine Learning for Drug Discovery, 2022.
  44. [44]Ibrahim Hassan Osman. Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem. Annals of operations research, 41:421–451, 1993.DOI
  45. [45]Mingjun Pan, Guanquan Lin, You-Wei Luo, Bin Zhu, Zhien Dai, Lijun Sun, and Chun Yuan. Preference optimization for combinatorial optimization problems. In Forty-second International Conference on Machine Learning, 2025.arxiv.org/abs/2505.08735
  46. [46]Christian Prins. Two memetic algorithms for heterogeneous fleet vehicle routing problems. Engineering Applications of Artificial Intelligence, 22(6):916–928, 2009.DOI
  47. [47]Gerhard Reinelt. Tsplib—a traveling salesman problem library. ORSA journal on computing, 3(4):376–384, 1991.DOI
  48. [48]Andrea Emilio Rizzoli, Roberto Montemanni, Enzo Lucibello, and Luca Maria Gambardella. Ant colony optimization for real-world vehicle routing problems: from theory to applications. Swarm Intelligence, 1:135–151, 2007.
  49. [49]Robin Rombach, Andreas Blattmann, Dominik Lorenz, Patrick Esser, and Björn Ommer. High-resolution image synthesis with latent diffusion models. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 10684–10695, 2022.arxiv.org/abs/2112.10752
  50. [50]Sheldon M Ross. Introduction to probability models. Academic press, 2014.
  51. [51]Arne Schneuing, Charles Harris, Yuanqi Du, Kieran Didi, Arian Jamash, Ilia Igashov, Weitao Du, Carla Gomes, Tom L Blundell, Pietro Liò, et al. Structure-based drug design with equivariant diffusion models. Nature Computational Science, 4(12):899–909, 2024.DOI
  52. [52]Jascha Sohl-Dickstein, Eric Weiss, Niru Maheswaranathan, and Surya Ganguli. Deep unsupervised learning using nonequilibrium thermodynamics. In International conference on machine learning, pages 2256–2265. pmlr, 2015.
  53. [53]Hartej Soin, Tapas Tripura, and Souvik Chakraborty. Generative flow induced neural architecture search: Towards discovering optimal architecture in wavelet neural operator. CoRR, 2024.arxiv.org/abs/2405.06910
  54. [54]Zhiqing Sun and Yiming Yang. Difusco: Graph-based diffusion solvers for combinatorial optimization. Advances in neural information processing systems, 36:3706–3731, 2023.arxiv.org/abs/2302.08224
  55. [55]Amalia Utamima and Arif Djunaidy. Agricultural routing planning: A narrative review of literature. Procedia Computer Science, 197:693–700, 2022.DOI
  56. [56]Mingzhao Wang, You Zhou, Zhiguang Cao, Yubin Xiao, Xuan Wu, Wei Pang, Yuan Jiang, Hui Yang, Peng Zhao, and Yuanshu Li. An efficient diffusion-based non-autoregressive solver for traveling salesman problem. In Proceedings of the 31th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2025.arxiv.org/abs/2501.13767
  57. [57]Daqing Wu, Jiyu Li, Jiye Cui, and Dong Hu. Research on the time-dependent vehicle routing problem for fresh agricultural products based on customer value. Agriculture, 13(3):681, 2023.DOI
  58. [58]Dan Xie, Zhi-Wei Wang, Zhen-Yi Gu, Wan-Yue Diao, Fang-Yu Tao, Chang Liu, Hai-Zhu Sun, Xing-Long Wu, Jia-Wei Wang, and Jing-Ping Zhang. Polymeric molecular design towards horizontal zn electrodeposits at constrained 2d zn2+ diffusion: dendrite-free zn anode for long-life and high-rate aqueous zinc metal battery. Advanced Functional Materials, 32(32):2204066, 2022.
  59. [59]Liang Xin, Wen Song, Zhiguang Cao, and Jie Zhang. Neurolkh: Combining deep learning model with lin-kernighan-helsg aun heuristic for solving the traveling salesman problem. Advances in Neural Information Processing Systems, 34:7472–7483, 2021.
  60. [60]Qi Yao, Shenjun Zhu, and Yanhui Li. Green vehicle-routing problem of fresh agricultural products considering carbon emission. International Journal of Environmental Research and Public Health, 19(14):8675, 2022.DOI
  61. [61]Haoran Ye, Jiarui Wang, Zhiguang Cao, Helan Liang, and Yong Li. Deepaco: Neural-enhanced ant systems for combinatorial optimization. Advances in neural information processing systems, 36:43706–43728, 2023.arxiv.org/abs/2309.14032
  62. [62]Hang Yi, Ziwei Huang, Yining Ma, and Zhiguang Cao. Radar: Learning to route with asymmetry-aware distance representations. In International Conference on Learning Representations (ICLR), 2026.arxiv.org/abs/2603.03388
  63. [63]David W Zhang, Corrado Rainone, Markus Peschl, and Roberto Bondesan. Robust scheduling with gflownets. In The Eleventh International Conference on Learning Representations.
  64. [64]Dinghuai Zhang, Ricky TQ Chen, Cheng-Hao Liu, Aaron Courville, and Yoshua Bengio. Diffusion generative flow samplers: Improving learning signals through partial trajectory optimization. In The Twelfth International Conference on Learning Representations.
  65. [65]Dinghuai Zhang, Hanjun Dai, Nikolay Malkin, Aaron C Courville, Yoshua Bengio, and Ling Pan. Let the flows tell: Solving graph combinatorial problems with gflownets. Advances in neural information processing systems, 36:11952–11969, 2023.
  66. [66]Ni Zhang and Zhiguang Cao. Hybrid-balance gflownet for solving vehicle routing problems. Advances in Neural Information Processing Systems, 2025.arxiv.org/abs/2510.04792
  67. [67]Ni Zhang, Zhiguang Cao, Jianan Zhou, Cong Zhang, and Yew-Soon Ong. An agentic framework with LLMs for solving complex vehicle routing problems. In International Conference on Learning Representations (ICLR), 2026.arxiv.org/abs/2510.16701
  68. [68]Ni Zhang, Jingfeng Yang, Zhiguang Cao, and Xu Chi. Adversarial generative flow network for solving vehicle routing problems. In The Thirteenth International Conference on Learning Representations, 2025.arxiv.org/abs/2503.01931
  69. [69]Yiheng Zhu, Jialu Wu, Chaowen Hu, Jiahuan Yan, Tingjun Hou, Jian Wu, et al. Sample-efficient multi-objective molecular optimization with gflownets. Advances in Neural Information Processing Systems, 36:79667–79684, 2023.arxiv.org/abs/2302.04040

Paper details

vlnc:W_w99de6ub
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 1

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents