Research map / Adversarial robustness and security / Certified and empirical robustness
Collaboration! Towards Robust Neural Methods for 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 CNF, an ensemble-based collaborative adversarial training framework with global adversarial instances and an attention-based neural router, to make neural VRP solvers (POMO, MatNet) robust while also improving clean and OOD generalization.
Problem
Neural VRP solvers suffer severe robustness issues under crafted adversarial perturbations, and vanilla adversarial training trades off standard (clean) generalization against adversarial robustness.
Approach
Adversarially train multiple copies of a pretrained neural VRP model collaboratively: generate global adversarial instances by attacking the currently best-performing model per instance, and use an attention-based neural router trained with RL to distribute training instances to models with top-K load balancing.
Key results
- On TSP100 with 3 models, CNF achieves 0.118% uniform gap and 0.236% fixed adversarial gap, versus 0.365% and 0.390% for POMO_AT (1).
- On CVRP100, CNF (3) reaches 1.073% uniform and 0.730% fixed adversarial gap, outperforming POMO_AT (3) (1.256%, 0.767%).
- CNF (3) outperforms vanilla AT with nine models, per the conclusion, while trained with three models.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use CNF collaborative training instead of POMO_AT with three models | POMO · TSP100 Fixed Adv. (100) | optimality gap: 0.295% -> 0.236% | Helped |
| Use CNF collaborative training instead of POMO_AT with three models | POMO · CVRP100 Fixed Adv. (100) | optimality gap: 0.767% -> 0.730% | Helped |
| Use CNF collaborative training instead of POMO_AT with three models | POMO · TSP100 Uniform (100) | optimality gap: 0.255% -> 0.118% | Helped |
| Use CNF collaborative training instead of POMO_HAC with three models | POMO · CVRP100 Uniform (100) | optimality gap: 1.085% -> 1.073% | Helped |
| Use CNF collaborative training instead of POMO_DivTrain with three models | POMO · CVRP100 Fixed Adv. (100) | optimality gap: 0.754% -> 0.730% | Helped |
| Use CNF collaborative training instead of vanilla adversarial training | POMO · TSP OOD datasets | optimality gap | Helped |
| Add global adversarial attack generation alongside local attacks (ablation) | CNF · TSP100 Fixed Adv. (100) | optimality gap | Helped |
| Add the neural router for instance distribution (ablation) | CNF · TSP100 Uniform and Fixed Adv. | optimality gap | Helped |
| Increase the number of trained models (ablation) | CNF · TSP100 collaborative performance | optimality gap | Helped |
| Use M-TopK routing instead of other routing strategies (ablation) | CNF · TSP100 collaborative performance | optimality gap | Helped |
| Replace the neural router with greedy selection (ablation) | CNF · TSP100 and CVRP100 | optimality gap | Hurt |
| Use vanilla adversarial training instead of CNF | POMO · OOD generalization | optimality gap | Hurt |
Surprising findings
- Vanilla adversarial training on neural VRP solvers degrades OOD generalization on synthetic datasets, while CNF improves it.
- A larger single POMO model (3.64M parameters) with vanilla AT underperforms the three-model ensemble.
Limitations
- Increased training computational cost from training multiple models (85 hrs vs 32 hrs for POMO_AT (3) on TSP100).
- Attack budget is not constrained to imperceptible perturbations, so adversarial instances can differ substantially from clean ones.
- Evaluated mainly on POMO with one attacker; ensemble-based defense of other attack types is not thoroughly tested.
Experimental setup
Datasets: synthetic uniform TSP/CVRP instances TSPLIB CVRPLIB
Benchmarks: TSP100 uniform/adversarial test sets TSP200 CVRP100 CVRP200 TSPLIB CVRPLIB synthetic cross-distribution and cross-size TSP
Metrics: optimality gap inference time
Baselines: POMO POMO_AT POMO_HAC POMO_DivTrain POMO_TRS Concorde LKH3 HGS CNF_Greedy DIMES DeepACO
Builds on: POMO adversarial training (Madry et al.) REINFORCE Attention Model
Closest papers by meaning
- MVMoE: Multi-Task Vehicle Routing Solver with Mixture-of-Experts (ICML 2024 · similarity 0.88)
- Multi-Task Vehicle Routing Solver via Mixture of Specialized Experts under State-Decomposable MDP (NeurIPS 2025 · similarity 0.86)
- Learning to Handle Complex Constraints for Vehicle Routing Problems (NeurIPS 2024 · similarity 0.86)
- Adversarial Generative Flow Network for Solving Vehicle Routing Problems (ICLR 2025 · similarity 0.86)
- Neural Combinatorial Optimization for Robust Routing Problem with Uncertain Travel Times (NeurIPS 2024 · similarity 0.85)
- SPACE: Unifying Symmetric and Asymmetric Routing Problems for Generalist Neural Solver (NeurIPS 2026 · 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.