Research map / Probabilistic and scientific modeling / Molecules and proteins
Hybrid-Balance GFlowNet for Solving Vehicle Routing Problems
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Hybrid-Balance GFlowNet (HBG), which adds a VRP-specific detailed-balance loss to trajectory-balance training and a depot-guided inference rule, applied to AGFN and GFACS on CVRP and TSP.
Problem
GFlowNet-based VRP solvers train only with trajectory balance, which optimizes global route cost but neglects local transition structure; pure detailed balance alone is insufficient for holistic VRP trajectories.
Approach
Combine TB and a VRP-specific DB loss (with a step-wise backward probability derived from depot sub-trajectory counting and a local energy term) in one objective, and sample only at the depot while acting greedily at customer nodes during inference.
Key results
- HBG-AGFN reduces CVRP1000 gap from 11.15% to 9.34% and HBG-GFACS (with local search) reduces the CVRP200 gap from 2.10% to 1.96% versus LKH.
- Replacing TB alone with hybrid balance in AGFN cuts CVRP500 gap from 12.21% to 10.53%; DB alone gives 21.26%.
- On CVRPLIB-XXL, HBG-GFACS gaps drop substantially (e.g., L1 from 119.24% to 52.25%).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add Hybrid-Balance to AGFN (ablation) | AGFN · CVRP200, CVRP500, CVRP1000 | Gap(%): 11.48 -> 10.84; 12.21 -> 10.53; 11.15 -> 9.47 | Helped |
| Add Hybrid-Balance to GFACS (ablation) | GFACS · CVRP200, CVRP500, CVRP1000 | Gap(%): 23.11 -> 21.29; 23.83 -> 21.08; 23.82 -> 19.87 | Helped |
| Add depot-guided inference after Hybrid-Balance (ablation) | HBG-AGFN · CVRP200, CVRP500, CVRP1000 | Gap(%): 10.84 -> 9.95; 10.53 -> 10.44; 9.47 -> 9.34 | Helped |
| Add depot-guided inference after Hybrid-Balance (ablation) | HBG-GFACS · CVRP200, CVRP500, CVRP1000 | Gap(%): 21.29 -> 16.48; 21.08 -> 13.53; 19.87 -> 10.61 | Helped |
| Use Detailed Balance alone instead of Trajectory Balance (ablation) | AGFN · CVRP200, CVRP500, CVRP1000 | Gap(%): 11.48 -> 22.72; 12.21 -> 21.26; 11.15 -> 18.85 | Hurt |
| Use Detailed Balance alone instead of Trajectory Balance (ablation) | GFACS · CVRP200, CVRP500, CVRP1000 | Gap(%): 23.11 -> 54.36; 23.83 -> 48.77; 23.82 -> 50.89 | Hurt |
| Sample at depot and greedily decode at customers rather than using other sampling/greedy combinations (ablation) | Depot-guided inference in AGFN and GFACS · CVRP200, CVRP500, CVRP1000 | Gap(%): DS and CG: AGFN 9.95, 10.44, 9.34; GFACS 16.48, 13.53, 10.61 | Helped |
| Add Hybrid-Balance to AGFN | AGFN · TSP200, TSP500, TSP1000 | Obj.: 11.85 -> 11.73; 19.08 -> 18.59; 27.15 -> 26.87 | Helped |
| Add Hybrid-Balance to GFACS | GFACS · TSP200, TSP500, TSP1000 | Obj.: 13.04 -> 12.68; 24.41 -> 24.19; 41.86 -> 39.90 | Helped |
| Add Hybrid-Balance to GFACS with local search | GFACS (local search) · TSP200, TSP500, TSP1000 | Obj.: 10.78 -> 10.78; 17.10 -> 17.05; 24.45 -> 24.42 | Mixed |
| Use the original fixed 1:1 TB:DB loss-weight ratio (ablation) | HBG-AGFN · CVRP and TSP, sizes 200, 500, 1000 | Gap(%) | Mixed |
| Change the sparsity parameter, learning rate, or optimizer from the original configuration (ablation) | HBG-AGFN and HBG-GFACS · CVRP200, CVRP500, CVRP1000 | Gap(%) | Mixed |
Surprising findings
- DB alone performs far worse than TB (e.g., 21–51% gaps for DB vs. 11–24% for TB), supporting the claim that DB is insufficient alone for VRPs.
Limitations
- Performance depends on the underlying GFlowNet solver (AGFN or GFACS); gains are not shown for other solvers.
- On some CVRPLIB-XXL instances HBG-AGFN is worse than AGFN (e.g., B1 109.80 vs 20.65 in the table's bolding), and gaps remain large on several large instances.
- Depot-guided inference is specialized to depot-centric problems and is not used for TSP.
Experimental setup
Datasets: synthetic CVRP instances (100-node training; 200, 500, 1000-node test) CVRPLIB-XXL
Benchmarks: CVRP200 CVRP500 CVRP1000 TSP200 TSP500 TSP1000 CVRPLIB-XXL
Metrics: objective value inference time (s) optimality gap (%)
Baselines: LKH ACO POMO POMO (*8) GANCO NeuOpt AGFN GFACS
Builds on: GFlowNet Trajectory Balance Detailed Balance AGFN GFACS
Closest papers by meaning
- GLOP: Learning Global Partition and Local Construction for Solving Large-Scale Routing Problems in Real-Time (AAAI 2024 · similarity 0.87)
- Adversarial Generative Flow Network for Solving Vehicle Routing Problems (ICLR 2025 · similarity 0.85)
- CaDA: Cross-Problem Routing Solver with Constraint-Aware Dual-Attention (ICML 2025 · similarity 0.85)
- Improving Generalization of Neural Combinatorial Optimization for Vehicle Routing Problems via Test-Time Projection Learning (NeurIPS 2025 · similarity 0.85)
- MVMoE: Multi-Task Vehicle Routing Solver with Mixture-of-Experts (ICML 2024 · similarity 0.85)
- Equity-Transformer: Solving NP-Hard Min-Max Routing Problems as Sequential Generation with Equity Context (AAAI 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.