Research map / Image generation / GANs
Adversarial Generative Flow Network 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 AGFN, a GFlowNet-based constructive VRP solver trained adversarially with a discriminator that scores solutions against local-search-improved ones, plus a hybrid sampling/greedy decoding scheme, evaluated on CVRP and TSP up to 1,000 nodes (and up to 10,000 for CVRP).
Problem
Neural construction-based solvers for vehicle routing (CVRP, TSP) rely on Transformers that scale poorly to large instances and produce low-diversity solutions.
Approach
Replace the Transformer with a sparse-graph GNN GFlowNet generator trained with a trajectory balance loss whose reward is modulated by a discriminator score; the discriminator is trained to separate generator routes from local-search-improved routes, and inference uses a hybrid of sampling and greedy node selection.
Key results
- On CVRP-1000 synthetic, AGFN-100 reaches 133.97 objective vs POMO(*8) 192.79 and GANCO 145.40, at 0.72 s per instance.
- On TSPLib, AGFN-100 gap 27.36% vs POMO(*8) 50.02% and GFACS 102.01%, with 0.04 s time.
- AGFN is slightly worse than POMO(*8) and GANCO on 200-node CVRP and TSP (e.g., CVRP-200 gap 8.41% vs POMO(*8) 1.20%... with AGFN-100 trained on 100 nodes).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Train on 100-node instances rather than using POMO(*8) | AGFN-100 vs POMO(*8) · Synthetic CVRP, 200 nodes | Obj.: 7.13% | Hurt |
| Use AGFN-100 rather than GANCO | AGFN-100 · Synthetic CVRP, 500 nodes | Obj.: 0.29% | Helped |
| Use AGFN-100 rather than GANCO | AGFN-100 · Synthetic CVRP, 1,000 nodes | Obj.: 7.86% | Helped |
| Use AGFN-100 rather than GANCO | AGFN-100 · Synthetic TSP, 500 nodes | Obj.: 1.47% | Helped |
| Use AGFN-100 rather than GANCO | AGFN-100 · Synthetic TSP, 1,000 nodes | Obj.: 9.49% | Helped |
| Use hybrid decoding instead of pure sampling or greedy decoding (ablation) | AGFN · CVRP and TSP, varying sizes | Gap (%) | Helped |
| Set hybrid-decoding sampling probability to 0.05 rather than 0.01 (ablation) | AGFN · Synthetic CVRP, 200 nodes | Obj.: 31.555902 -> 31.260145 | Helped |
| Set hybrid-decoding sampling probability to 0.05 rather than 0.01 (ablation) | AGFN · Synthetic TSP, 200 nodes | Obj.: 11.873071 -> 11.847540 | Helped |
| Replace the discriminator's local search with LKH (ablation) | AGFN · CVRP, 200 nodes | average objective value | No clear effect |
| Remove adversarial training from AGFN (ablation) | AGFN · CVRP, 200 nodes | average objective value | Hurt |
Surprising findings
- AGFN-100 trained on 100 nodes achieves better objective than LKH-3(100) on 1000-node CVRP-type comparisons only at larger scales, and is worse on 200-node instances.
Limitations
- Slightly weaker than POMO(*8) and GANCO on 200-node instances, attributed to generator diversity/quality limits.
- Generalization from 100-node training to 200-node instances is limited.
- Evaluated only on CVRP and TSP; comparison against broader robust neural solvers on larger instances is left for future work.
Experimental setup
Datasets: synthetic CVRP instances synthetic TSP instances CVRPLib TSPLib
Benchmarks: synthetic CVRP 200/500/1000 synthetic TSP 200/500/1000 CVRPLib TSPLib synthetic CVRP 2000-10000
Metrics: objective (total travel distance) gap (%) time per instance (s)
Baselines: LKH-3 POMO NeuOpt GANCO ACO GFACS
Builds on: GFlowNet trajectory balance GFACS POMO GANCO NeuroLKH
Closest papers by meaning
- MVMoE: Multi-Task Vehicle Routing Solver with Mixture-of-Experts (ICML 2024 · similarity 0.87)
- SPACE: Unifying Symmetric and Asymmetric Routing Problems for Generalist Neural Solver (NeurIPS 2026 · similarity 0.86)
- Flow Factorization for Efficient Generative Flow Networks (AAAI 2025 · similarity 0.86)
- Improving Generalization of Neural Combinatorial Optimization for Vehicle Routing Problems via Test-Time Projection Learning (NeurIPS 2025 · similarity 0.86)
- Collaboration! Towards Robust Neural Methods for Routing Problems (NeurIPS 2024 · similarity 0.86)
- Pre-Training and Fine-Tuning Generative Flow Networks (ICLR 2024 · similarity 0.86)
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.