Hybrid-Balance GFlowNet for Solving Vehicle Routing Problems

We sincerely thank the reviewer for the thoughtful and encouraging feedback. We greatly appreciate the kind comment of the conceptual motivation, the theoretical contribution of Detailed Balance in VRP, and the thoroughness of our experimental design across diverse solvers and problem scales. Below, we respond to the concerns you raised.

W1 Q1: Weight 𝜆

We sincerely thank the reviewer for this insightful comment and for pointing out the potential ambiguity in our use of the term "adaptive". Our original intention was to emphasize the unified and structurally integration of TB and DB within a consistent probabilistic framework. We appreciate the reviewer’s suggestion and will revise the manuscript accordingly to clarify this point and avoid any possible misunderstanding.

We also appreciate the reviewer’s concern regarding a weighted combination (i.e., 𝐿_{HB} = 𝐿_{TB}+ 𝜆⋅𝐿_{DB}). In response, we have conducted additional experiments to assess the sensitivity of our method to different values of 𝜆, which are gathered in Tables B1–B4 below. The results include adaptive weights (i.e., 𝜆: 0.5->0, 1->0, 2->0 and so on) and fixed weights (i.e., 𝜆: 0.5->0.5, 1->1, 2->2). We find that, for HBG-AGFN, a fixed 1:1 weight between TB and DB consistently yields the best performance. Similarly, for HBG-GFACS, this ratio offers the most favorable trade-off between performance with and without local search.

Table B1. Weights Analysis of HBG-AGFN on CVRP

"𝜆: 0.5→0" refers to changing the TB:DB loss weight ratio from 1:0.5 to 1:0 during training, with the TB weight fixed at 1. The interpretation for other entries follows analogously. The term "origin" denotes the original hyperparameter setting used in our main experiments.

Table B2. Weights Analysis of HBG-AGFN on TSP

Table B3. Weights Analysis of HBG-GFACS on CVRP

Table B4. Weights Analysis of HBG-GFACS on TSP

W2: Improvement on 1000 Node CVRP Instances

We sincerely thank the reviewer for raising the concern. While the improvement on CVRP1000 under AGFN may appear modest (~1.6%) in absolute terms, we would like to note that this result is obtained on the challenging large-scale instance involving 1000 nodes, where even small percentage gains are non-trivial due to the high combinatorial complexity of the problem. More importantly, we observe consistent improvements across a wide range of problem sizes, solver backbones (AGFN and GFACS), and problem types (CVRP and TSP). We believe this consistency highlights the robustness and broad applicability of our proposed approach.

W3: Re-tuning

We sincerely thank the reviewer for this valuable suggestion. The reviewer is absolutely right that the introduction of a new loss component (𝐿_{DB}) could potentially alter the optimization landscape, and that the original hyperparameter settings used in AGFN and GFACS may not be optimal for the proposed HBG variants.

Our initial motivation for adopting the same configurations was to ensure a fair comparison under consistent settings. However, inspired by the reviewer’s insightful comment, we have conducted additional experiments in which we re-tuned key hyperparameters for the HBG models, including the sparsity parameter, learning rate, and optimizer settings. The updated results (Table A1, C, D) will be incorporated into the Appendix of the revised version.

As the sparsity parameter results shown in Table A1, the original sparsity setting yields the best performance for both HBG-GFACS and HBG-AGFN. Regarding the learning rate comparisons in Table C, for HBG-GFACS, the original value of $5×10^{−4}$ performs best without local search, while a value of $1×10^{−3}$ achieves the best results when local search is enabled. For HBG-AGFN, a learning rate of $1×10^{−4}$ shows superior performance on the 200- and 500-node instances, whereas the original value performs best on the 1000-node instances. As for the optimizer comparison in Table D, the original AdamW setting provides the best performance in most cases. An exception is observed on the 500- and 1000-node instance with local search, where Adam slightly outperforms AdamW for HBG-GFACS.

Table A1. Comparison of Various Sparse Parameter k on CVRP

HBG-GFACS_2 refers to the HBG-GFACS model evaluated with k=|V|/2; the interpretation is analogous for the other entries. The term "origin" denotes the original hyperparameter setting used in our main experiments.

Table C. Comparison of Various Learning Rate on CVRP

HBG-GFACS_$5×10^{-3}$ refers to the HBG-GFACS model evaluated with learning rate of $5×10^{-3}$; the interpretation is analogous for the other entries.

Table D. Comparison of Various Optimizer on CVRP

HBG-GFACS_SGD refers to the HBG-GFACS model evaluated with SGD optimizer; the interpretation is analogous for the other entries.

Q2: Reward Function

We sincerely thank the reviewer for this thoughtful question. The use of reward relative to the batch average in Equation 9 is a common practice in the VRP literature, particularly in learning-based methods like POMO, AGFN, and GFACS. The key motivation behind this choice is to mitigate the effect of node distance discrepancies across different instances, thereby promoting training stability.

For example, different instances often exhibit varying step-wise reward magnitudes due to differences in route length, customer density, or total demand. As a result, the average reward per decision step can differ between instances. If we directly use these raw per-step rewards to compute energy values, instances with smaller average step-wise rewards would inherently yield more favorable energy values, even for suboptimal decisions. In contrast, instances with larger average per-step rewards might assign worse energy values even to relatively good decisions within that instance. This imbalance can distort the learning signal, causing the model to undervalue high-quality decisions in instances with larger average per-step rewards, while overvaluing mediocre decisions in smaller ones.

By using reward values relative to the batch average, we normalize this effect and encourage the model to compare solutions fairly within the context of each instance. This stabilizes training and helps the model focus on learning to generate relatively good solutions across diverse instances, instead of simply favoring small step-wise rewards in absolute terms.

We sincerely thank the reviewer for the thoughtful and encouraging feedback. We truly appreciate your kind comment of our theoretical contributions, including the formalization of DB in VRP and the unified integration of TB and DB. We're also grateful for your positive comments on the clarity of our design and analysis, as well as the empirical improvements and careful ablation studies.

Below, we provide detailed responses to the questions and suggestions you kindly raised.

W1: DB Motivation and Term Explanation

We sincerely thank the reviewer for raising this important question. The necessity of incorporating local optimization signals arises from a core limitation of relying solely on global feedback. Trajectory Balance (TB), while effective in guiding overall optimization, assigns credit based on the full trajectory. This can misrepresent the contribution of locally good decisions when the overall solution is not good.

To illustrate this concretely, consider a long vehicle routing trajectory constructed incrementally as A → B → C → D → E → ... → U → V → W → X → Y → Z. Assume the overall route has a high cost (bad performance) due to early suboptimal choices like traversing a high-cost edge from C to D. However, the later segment (e.g., U to Z) may be well-structured and efficient. Under TB, the reward signal derived from the final cost is spread across the entire trajectory. As a result, good transitions like W → X → Y may receive low or misleading credit as the overall result is not good, hindering the model from reinforcing these useful local patterns.

In contrast, Detailed Balance (DB) operates at a step-wise level, comparing local alternatives directly. For example, at node W, DB can determine that choosing X instead of alternative choices like Z leads to better outcomes, which is independent of early errors. This enables the model to recognize and reinforce high-quality decisions even within imperfect global solutions.

Importantly, adding DB does not bias the model away from global optimization—rather, it complements TB by supplying more granular learning signals. As validated in our ablation study (Section 3.2, Table 3), the hybrid use of TB and DB consistently improves performance over using either objective alone.

Moreover, the term “fine-grained local structure” refers to the localized reward relationships between a given state and its immediate successor, which captures beneficial sub-patterns within a trajectory, such as short, efficient sub-routes or cost-effective transitions. These local structures often contribute meaningfully to overall solution quality but may be overlooked or undervalued when using a purely trajectory-level objective like TB. By introducing DB, the model gains the capability to identify and reinforce these fine-grained decisions during training. While the concept of “fine-grained local structure” is implicitely mentioned in Lines 40–41 of the paper, we will revise the text to make it more explicit and accessible.

Motivated by your insightful suggestion, we will incorporate this example and discussion into the main paper to better clarify the motivation behind our hybrid design.

W2: Depot-Guided Inference

The reviewer is correct on this point, the Depot-Guided Inference strategy is specifically tailored for depot-centric problems such as CVRP. While we briefly acknowledged this in Lines 54–58, 66–67, and 233–236 of the manuscript, we appreciate the opportunity to clarify further. In practice, a large number of VRP variants including capacitated VRP, multi-depot VRP, and VRP with time windows, are inherently structured around depots. Therefore, despite its limited applicability to non-depot problems like TSP, we believe the proposed strategy remains broadly relevant and useful for a wide range of real-world routing scenarios. And the results in Table 5 shows that even in the depot-free scenatios like TSP, our overall hybrid balance framework without Depot-Guided Inference can still improve the performance.

W3: Constrains of GFlowNet Solvers

As acknowledged by the reviewer, the performance of our framework could indeed be constrained by the quality of the underlying GFlowNet solvers. This limitation is explicitly noted in the Conclusion (Lines 316–317) of our manuscript. However, our method is designed to be general and has demonstrated its ability to enhance different types of GFlowNet-based backbones, such as GFACS (which learns to search) and AGFN (which learns to construct). We believe it remain applicable for improving future stronger GFlowNet backbone as well.

We sincerely thank the reviewer for the thoughtful and constructive feedback. We are grateful for the reviewer’s kind comments on the technical soundness of our methodology, the clarity and thoroughness of our presentation, the performance improvements shown in Table 1 over strong baselines such as AGFN and GFACS, and the usefulness of our ablation studies in analyzing the effects of balancing strategies and individual components.

Below, we provide detailed responses to the questions and concerns raised.

W1: DB Motivation

To provide a concrete illustration, consider a long vehicle routing trajectory constructed incrementally as A → B → C → D → E → ... → U → V → W → X → Y → Z.

Assume this complete route yields a high total cost (bad performance), primarily due to suboptimal decisions made in the early stages, such as traversing a high-cost edge from node C to node D. In contrast, the latter portion of the tour (e.g., from node U to Z) may follow a more cost-effective and well-structured pattern.

Under Trajectory Balance (TB), the final reward is determined by the overall trajectory cost, and is proportionally assigned to all transitions. Consequently, even high-quality local transitions, such as W → X → Y, may receive weak or misleading training signals simply because they are embedded in a globally suboptimal trajectory. This would hinder the model's ability to learn and reinforce desirable local patterns.

On the other hand, Detailed Balance (DB) operates at a step-wise granularity, evaluating the expected outcomes of individual transitions. For instance, at node W, DB can assess whether transitioning to X leads to better outcomes compared to alternative choices like Z, regardless of earlier suboptimal steps. This localized and reward-sensitive feedback enables the model to more accurately learn local quality from global performance, and promotes stronger learning signals for valuable decisions even within imperfect trajectories.

This example illustrates a core limitation of Trajectory Balance (TB) in long-horizon combinatorial tasks like VRP: when the overall trajectory is suboptimal, TB lacks the ability to identify and preserve well-structured local segments within it. As a result, valuable local patterns may be overlooked or penalized. By incorporating Detailed Balance (DB) into the training objective, we address this limitation by providing fine-grained, step-level singal that helps isolate and reinforce high-quality local decisions, even when the global trajectory doesn't show good performance.

We sincerely thank the reviewer for raising this important point. Motivated by your suggestion, we will include this example and discussion in the revised paper to better illustrate the motivation behind integrating TB and DB. Furthermore, as shown in Section 3.2 and Table 3, our ablation study confirms that combining TB with DB (i.e., Hybrid Balance) consistently leads to improved performance, validating the complementary strengths of Hybrid Balance objectives.

W2: Related Work

We fully acknowledge the reviewer’s concern regarding the placement of the Related Work section in the Appendix. In the original submission, this decision was made due to strict space constraints, i.e., we prioritized providing a thorough and transparent explanation of our methodology, which we felt was critical for understanding the technical contributions. However, we are open to the suggestion and sincerely thank the reviewer for raising this point, i.e., having the Related Work in the main body could greatly benefit readers, especially those less familiar with the research area.

W3: Equation

We sincerely thank the reviewer for this helpful comment. We hadn’t realized that the explanation of the energy term appears nearly two pages after its introduction in Equation 2, and we truly appreciate the reviewer for pointing this out. In the revised version, we will move the explanation closer to Equation 2 to improve clarity and make the flow of the methodology easier to follow.

Regarding the second point about whether the energy can be negative, we appreciate the opportunity to clarify this. Yes, this is indeed intended behavior. As is common in VRP literature such as POMO, GFACS, and AGFN, the energy is defined relative to a baseline (e.g., average reward) and can take negative values. Moreover, the energy in Equation 9 appears in the denominator of the loss function (Equation 2), and a negative energy results in a smaller exponentiated value in the denominator, which leads to a higher loss, which penalizes relatively poor trajectories. We will clarify this behavior of the energy term more explicitly in the revised manuscript.

W4: Contribution and Extention

We thank the reviewer for the thoughtful comment. To the best of our knowledge, this work is the first to introduce the DB objective into vehicle routing problem (VRP), and the first to integrate TB and DB objectives within a unified GFlowNet framework. Achieving this integration is non-trivial, as it requires reconciling two fundamentally different types of training signals: global trajectory-level feedback from TB and localized stepwise credit assignment from DB. At the same time, it is necessary to ensure that the forward and backward dynamics remain consistent throughout training. This carefully unified design allows our method to effectively leverage both global and local learning signals, leading to improved training stability and performance across various VRP settings. To achieve this integration:

• Leveraging the hybrid structure of VRP whose solution is comprised of multi-node and single-node sub-tours, we derive a general recurrence formulation (Eq. 4) for counting trajectory orders. This formulation serves as the mathematical foundation for integrating TB and DB in a consistent manner.
• From this recurrence, we analytically derive a set of twelve equations (Eq. 13–24 in Appendix), which lead to the expressions for the backward probability of TB (Eq. 6) and DB (Eq. 7) within a consistent framework.
• We also define forward probability composition (Eq. 3), where DB serves as the building block for TB, maintaining coherence throughout trajectory construction.
• To unify flow representations, we compute DB flow from state embeddings and TB flow from final trajectories, interpreting DB flow as an intermediate form of TB flow.
• Finally, based on hybrid balance, we derive an important structural property: only the depot node has multiple feasible predecessors, while customer nodes have unique ones. This motivates our Depot-Guided Inference, a targeted module that strengthens backward modeling and trajectory quality.

Regarding the potential for generalization to other combinatorial optimization (CO) problems, we agree that our approach holds strong promise beyond VRP. In fact, many existing neural methods in the CO literature such as AGFN, begin with a focus on VRP, precisely because VRP presents a particularly challenging testbed due to its complex structure and rich constraints. Successfully addressing VRP often serves as a strong indication of a method’s scalability and robustness. Building on this foundation, we plan to extend our GED framework to other CO problems such as the Maximum Independent Set (MIS), the Knapsack Problem (KP) and Graph Coloring, which generally involve simpler or fewer constraints compared to VRP. Given the modularity of our framework and its basis in general GFlowNet principles, we are confident in its adaptability and effectiveness across a broader class of combinatorial optimization tasks.

We sincerely thank the reviewer for the insightful feedback, particularly kind comments of our well-motivated, depot-aware design and effective experimental validation.

W1 W2: Theoretical Contribution: the Consistency of DB and Overall GFlowNet Framework

While TB and DB have been individually explored in prior work, our work presents the first attempt to unify them within one consistent theoretical framework, which is non-trivial and challenging.

Specifically, the DB objective has never been applied to VRP before, and no prior work has explored the combination of TB and DB in GFlowNets. Formulating the DB objective in the VRP setting and achieving a coherent integration with the TB objective requires reconciling two fundamentally different types of training signals and carefully designing forward and backward dynamics that remain consistent throughout the training process.

Backward Probability. Leveraging the hybrid structure of VRP whose solution is comprised of multi-node and single-node sub-tours, we derive a general recurrence formulation of trajectory orders’ count (Eq. (4)). And this formulation serves as the foundation for unifying TB and DB under a consistent probabilistic framework. From this unifying recurrence, we analytically derive a set of twelve equations (Eq. (13)–(24)) in the Appendix, leading to the trajectory-level backward probability of TB (Eq. (6)) and step-wise backward probability of DB (Eq. (7)). These two backward formulations are inherently consistent, as they are both derived from the same recurrence relation in Eq. (4).

Forward Probability. We define the relationship between the step-wise (DB) and trajectory-level (TB) forward probabilities in Eq. (3), where the step-wise forward probability serves as the building block of the trajectory-level forward probability. This formulation ensures that the two are mathematically consistent within the unified framework.

Flow. We further clarify the definition of flow under joint training: the DB flow is computed from the embedding of the current state's node, while the TB flow is computed from the embedding of the final trajectory's nodes. In essence, the DB flow can be seen as an intermediate form of the TB flow, capturing the flow dynamics at each decision step. This perspective reinforces consistency of our unified GFlowNet framework.

Moreover, motivated by the structure of the hybrid balance, we derive an important structural property: only the depot node retains multiple feasible predecessors during reverse sampling. This insight leads us to design the Depot-Guided Inference, which plays a key role in guiding trajectories generation.

Placing most of derivations in the Appendix may have made our theoretical contribution less clear. To improve clarity, we will move the key parts to the main text in the revised version.

Overall, we believe our framework provides a novel and principled theoretical foundation for combining TB and DB objectives in GFlowNets in a consistent manner, particularly adapted to complex routing problems, and opens up new possibilities for general-purpose generative models in structured combinatorial domains.

Q1 Q2 Q4: GNN

As our GNN architecture follows the same design as those used in AGFN and GFACS to ensures a fair comparison, we initially omitted its detailed description due to space limitation. However, as the reviewer suggested, We include the GNN specifications below and will incorporate them into the revised version of the paper.

Our model uses a custom GNN architecture designed specifically for the VRP task, which is widely used in VRP domain, and employs a custom message-passing GNN that jointly updates node and edge representations over multiple layers. At each layer 𝑙, node embedding $ℎ_𝑖^𝑙$ of the 𝑖-th node and and edge embeddings $𝑒^{𝑖𝑗}_l$ between the 𝑖-th and j-th node are updated via the following formulations:

$\mathbf{h}^{l+1}_i$ = $\mathbf{h}^l_i$ + $\mathrm{ACT}$ ( $\mathrm{BN}$ ( $\mathbf{W}^l_1$ $\mathbf{h}^l_i$ + $\mathcal{A}$ ( $\sigma$ ( $\mathbf{e}_l^{ij}$ ) $\odot$ $\mathbf{W}^l_2 \mathbf{h}^l_j) )$

$\mathbf{e}_{l+1}^{ij}$ = $\mathbf{e}_l^{ij}$ + $\mathrm{ACT}$ ( $\mathrm{BN}$ ( $\mathbf{W}^l_3$ $\mathbf{e}_l^{ij}$ + $\mathbf{W}^l_4 \mathbf{h}^l_i$ + $\mathbf{W}^l_5 \mathbf{h}^l_j$ ))

Here, $W_1^l, W_2^l, W_3^l, W_4^l$ are learnable parameters, 𝐴(⋅) is the aggregation function (mean pooling in our case), 𝜎(⋅) is the sigmoid activation that modulates attention over neighbors, and ACT denotes the SiLU activation. Graph normalization (BN) is applied at each step for stability. And the number of layers is set to 12 for HBG-GFACS and 16 for HBG-AGFN, with hidden dimensions of 32 and 64, respectively.

Q3: Sparsification Value

We follow AGFN and GFACS in setting the value of k for fair comparison: k = |V|/5 for both HBG-GFACS and HBG-AGFN on CVRP, k = |V|/10 for HBG-GFACS on TSP, and k = |V|/5 for HBG-AGFN on TSP, where ∣V∣ denotes the number of nodes in the instance. Inspired by the reviewer’s comment, we further conducted an ablation study to evaluate how different choices of k affect model performance across various problem sizes to provide a more comprehensive assessment of our model. The results are presented in Table A1 and A2 below. On CVRP, the original k setting consistently outperforms other configurations. For TSP, HBG-GFACS achieves the best performance with its original k setting. Although HBG-AGFN with the original k slightly underperforms compared to k = |V|/2 on 200-node TSP instances instances, it demonstrates superior results on the 500- and 1000-node TSP instances and CVRP instances of all scales. Overall, the results suggest that the best performance is typically achieved at the original k setting.

Table A1. Comparison of Various Sparse Parameter k on CVRP

HBG-GFACS_2 refers to the HBG-GFACS model evaluated with k=|V|/2; the interpretation is analogous for the other entries. The term "origin" denotes the original hyperparameter setting used in our main experiments.

Table A2. Comparison of Various Sparse Parameter k on TSP

Q5: Adaptive Weights

We sincerely thank the reviewer for the thoughtful suggestion regarding the use of adaptive weights in combining TB and DB losses. Motivated by this, we conducted additional experiments exploring the effect of different weighting strategies (i.e., $𝐿_{HB} = 𝐿_{TB}+ 𝜆⋅𝐿_{DB}$), including adaptive weights (i.e., 𝜆: 0.5->0, 1->0, 2->0 and so on) and fixed weights (i.e., 𝜆: 0.5->0.5, 1->1, 2->2). The results are presented in Tables B1–B4 below. The findings suggest that for HBG-AGFN, a fixed 1:1 weighting between TB and DB yields the best performance, while for HBG-GFACS, this fixed ratio also provides the best balance between performance with and without local search.

Table B1. Weights Analysis of HBG-AGFN on CVRP

"𝜆: 0.5→0" refers to changing the TB:DB loss weight ratio from 1:0.5 to 1:0 during training, with the TB weight fixed at 1. The interpretation for other entries follows analogously.

Table B2. Weights Analysis of HBG-AGFN on TSP

Table B3. Weights Analysis of HBG-GFACS on CVRP

Table B4. Weights Analysis of HBG-GFACS on TSP