Research map / Graph learning / Graph algorithms and clustering
CaDA: Cross-Problem Routing Solver with Constraint-Aware Dual-Attention
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 CaDA, a cross-problem neural VRP solver with a constraint prompt and a dual-attention encoder (global softmax branch plus Top-k sparse branch), trained with RL on 16 VRP variants.
Problem
Cross-problem neural combinatorial optimization for vehicle routing: existing multi-task VRP solvers are unaware of which constraints are active and use only global attention, which attends to irrelevant nodes.
Approach
Encode the active constraint set as a multi-hot vector turned into a prompt concatenated to node embeddings, and pair a global softmax attention branch with a Top-k sparse attention branch that keeps only the most relevant node connections, fusing the two branches at each layer.
Key results
- On VRP50 and VRP100 across 16 VRPs, CaDA surpasses the second-best neural solver by 0.26% and 0.32% respectively, ranking first among neural solvers on all VRP50 variants and 13 of 16 VRP100 variants.
- Ablation on VRP50: average gap 1.714% for CaDA versus 1.926% without the prompt and 1.795% without the sparse branch.
- On CVRPLib (101 instances), CaDA_25 x32 achieves average gap 3.32% versus 5.49% for RF-TE, the best prior neural baseline listed.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add the constraint prompt (ablation) | CaDA · 16 VRPs, VRP50 average | gap: 1.926% -> 1.714% | Helped |
| add Top-k sparse attention (ablation) | CaDA · 16 VRPs, VRP50 average | gap: 1.795% -> 1.714% | Helped |
| set Top-k to 25 instead of 10 (ablation) | CaDA · 16 VRPs, VRP50 average | gap: 4.61% -> 4.17% | Helped |
| set Top-k to 50 instead of 25 (ablation) | CaDA · 16 VRPs, VRP50 average | gap: 4.17% -> 4.79% | Hurt |
| set Top-k to 75 instead of 25 (ablation) | CaDA · 16 VRPs, VRP50 average | gap: 4.17% -> 4.88% | Hurt |
| set Top-k to 100 instead of 25 (ablation) | CaDA · 16 VRPs, VRP50 average | gap: 4.17% -> 5.15% | Hurt |
| use 32-prompt data augmentation | CaDA25 · CVRPLib, average | gap: 4.17% -> 3.32% | Helped |
| use CaDA25 × 32 instead of RF-TE | CVRPLib · CVRPLib, average | gap: 5.49% -> 3.32% | Helped |
Surprising findings
- Placing the constraint prompt in the sparse branch performs worse than placing it in the global branch, because the sparse masking can suppress the prompt.
Limitations
- Evaluation is limited to two scales (N=50 and N=100) and the 16 VRP variants with five constraints.
- Requires a separate model trained per scale (VRP50 and VRP100), and the sparse branch's top-k depends on N.
Experimental setup
Datasets: RouteFinder test set (1K instances per variant) CVRPLib Sets A, B, F, P, X
Benchmarks: 16 VRP variants at n=50 and n=100 (1K test instances each) CVRPLib Sets A, B, F, P, X
Metrics: objective value optimality gap running time
Baselines: PyVRP OR-Tools MTPOMO MVMoE RF-POMO RF-MoE RF-TE
Builds on: Attention Model POMO RouteFinder MTPOMO MVMoE
Closest papers by meaning
- Rethinking Neural Combinatorial Optimization for Vehicle Routing Problems with Different Constraint Tightness Degrees (NeurIPS 2025 · similarity 0.92)
- Improving Generalization of Neural Combinatorial Optimization for Vehicle Routing Problems via Test-Time Projection Learning (NeurIPS 2025 · similarity 0.92)
- Neural Solver Selection for Combinatorial Optimization (ICML 2025 · similarity 0.90)
- Learning to Insert for Constructive Neural Vehicle Routing Solver (NeurIPS 2025 · similarity 0.89)
- Neural Combinatorial Optimization for Robust Routing Problem with Uncertain Travel Times (NeurIPS 2024 · similarity 0.89)
- Multi-Task Vehicle Routing Solver via Mixture of Specialized Experts under State-Decomposable MDP (NeurIPS 2025 · similarity 0.88)
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.