# CaDA: Cross-Problem Routing Solver with Constraint-Aware Dual-Attention

arXiv: https://arxiv.org/abs/2412.00346 · HTML: https://mlsanity.com/paper/2412.00346/

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 77 references that are in the map.
- First posted on arXiv 30 Nov 2024.

## Builds on (most cited first, 30 of 33)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023)
- [PaLM: Scaling Language Modeling with Pathways](https://mlsanity.com/paper/2204.02311/) (2022)
- [Outrageously Large Neural Networks: The Sparsely-Gated Mixture-of-Experts Layer](https://mlsanity.com/paper/1701.06538/) (2017)
- [Longformer: The Long-Document Transformer](https://mlsanity.com/paper/2004.05150/) (2020)
- [Decoupled Weight Decay Regularization](https://mlsanity.com/paper/1711.05101/) (2017)
- [GLU Variants Improve Transformer](https://mlsanity.com/paper/2002.05202/) (2020)
- [Generating Long Sequences with Sparse Transformers](https://mlsanity.com/paper/1904.10509/) (2019)
- [Root Mean Square Layer Normalization](https://mlsanity.com/paper/1910.07467/) (2019)
- [Language Modeling with Gated Convolutional Networks](https://mlsanity.com/paper/1612.08083/) (2016)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [A Comprehensive Overview of Large Language Models](https://mlsanity.com/paper/2307.06435/) (2023)
- [Enhancing the Locality and Breaking the Memory Bottleneck of Transformer on Time Series Forecasting](https://mlsanity.com/paper/1907.00235/) (2019)
- [POMO: Policy Optimization with Multiple Optima for Reinforcement Learning](https://mlsanity.com/paper/2010.16011/) (2020)
- [Reinforcement Learning for Solving the Vehicle Routing Problem](https://mlsanity.com/paper/1802.04240/) (2018)
- [SegNeXt: Rethinking Convolutional Attention Design for Semantic Segmentation](https://mlsanity.com/paper/2209.08575/) (2022)
- [Adaptive Input Representations for Neural Language Modeling](https://mlsanity.com/paper/1809.10853/) (2018)
- [High-Resolution Representations for Labeling Pixels and Regions](https://mlsanity.com/paper/1904.04514/) (2019)
- [Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimization](https://mlsanity.com/paper/2205.13209/) (2022)
- [Star-Transformer](https://mlsanity.com/paper/1902.09113/) (2019)
- [MVMoE: Multi-Task Vehicle Routing Solver with Mixture-of-Experts](https://mlsanity.com/paper/2405.01029/) (2024)
- [Towards Omni-generalizable Neural Methods for Vehicle Routing Problems](https://mlsanity.com/paper/2305.19587/) (2023)
- [Explicit Sparse Transformer: Concentrated Attention Through Explicit Selection](https://mlsanity.com/paper/1912.11637/) (2019)
- [Learning Generalizable Models for Vehicle Routing Problems via Knowledge Distillation](https://mlsanity.com/paper/2210.07686/) (2022)
- [RouteFinder: Towards Foundation Models for Vehicle Routing Problems](https://mlsanity.com/paper/2406.15007/) (2024)
- [Generalization of Neural Combinatorial Solvers Through the Lens of Adversarial Robustness](https://mlsanity.com/paper/2110.10942/) (2021)
- [ETC: Encoding Long and Structured Inputs in Transformers](https://mlsanity.com/paper/2004.08483/) (2020)
- [Learning Classifiers with Fenchel-Young Losses: Generalized Entropies, Margins, and Algorithms](https://mlsanity.com/paper/1805.09717/) (2018)
- [Learn to Design the Heuristics for Vehicle Routing Problem](https://mlsanity.com/paper/2002.08539/) (2020)

## Built on by (most cited first, 24 of 24)

- [ARS: Automatic Routing Solver with Large Language Models](https://mlsanity.com/paper/2502.15359/) (2025)
- [MTL-KD: Multi-Task Learning Via Knowledge Distillation for Generalizable Neural Vehicle Routing Solver](https://mlsanity.com/paper/2506.02935/) (2025)
- [Improving Generalization of Neural Combinatorial Optimization for Vehicle Routing Problems via Test-Time Projection Learning](https://mlsanity.com/paper/2506.02392/) (2025)
- [Learning to Insert for Constructive Neural Vehicle Routing Solver](https://mlsanity.com/paper/2505.13904/) (2025)
- [Rethinking Neural Combinatorial Optimization for Vehicle Routing Problems with Different Constraint Tightness Degrees](https://mlsanity.com/paper/2505.24627/) (2025)
- [URS: A Unified Neural Routing Solver for Cross-Problem Zero-Shot Generalization](https://mlsanity.com/paper/2509.23413/) (2025)
- [Multi-Task Vehicle Routing Solver via Mixture of Specialized Experts under State-Decomposable MDP](https://mlsanity.com/paper/2510.21453/) (2025)
- [Survey on Neural Routing Solvers](https://mlsanity.com/paper/2602.21761/) (2026)
- [LMask: Learn to Solve Constrained Routing Problems with Lazy Masking](https://mlsanity.com/paper/2505.17938/) (2025)
- [Efficient Neural Combinatorial Optimization Solver for the Min-max Heterogeneous Capacitated Vehicle Routing Problem](https://mlsanity.com/paper/2507.21386/) (2025)
- [Chain-of-Context Learning: Dynamic Constraint Understanding for Multi-Task VRPs](https://mlsanity.com/paper/2603.01667/) (2026)
- [SPACE: Unifying Symmetric and Asymmetric Routing Problems for Generalist Neural Solver](https://mlsanity.com/paper/2605.24484/) (2026)
- [USPR: Learning a Unified Solver for Profiled Routing](https://mlsanity.com/paper/2505.05119/) (2025)
- [Aligning LLMs with Graph Neural Solvers for Combinatorial Optimization](https://mlsanity.com/paper/2603.27169/) (2026)
- [Automated Large-scale CVRP Solver Design via LLM-assisted Flexible MCTS](https://mlsanity.com/paper/2605.03339/) (2026)
- [Rethinking Constraint Awareness for Efficient State Embedding of Neural Routing Solver](https://mlsanity.com/paper/2605.10122/) (2026)
- [ARC: Leveraging Compositional Representations for Cross-Problem Learning on VRPs](https://mlsanity.com/paper/2512.18633/) (2025)
- [Enhancing Cross-Problem Vehicle Routing via Federated Learning](https://mlsanity.com/paper/2604.10652/) (2026)
- [FiLMMeD: Feature-wise Linear Modulation for Cross-Problem Multi-Depot Vehicle Routing](https://mlsanity.com/paper/2604.28102/) (2026)
- [WeCon: An Efficient Weight-Conditioned Neural Solver for Multi-Objective Combinatorial Optimization Problems](https://mlsanity.com/paper/2605.22876/) (2026)
- [LaT: LLM-as-Trainer for Multi-Task Vehicle Routing Solvers](https://mlsanity.com/paper/2607.17708/) (2026)
- [Improving Cross-Problem Vehicle Routing with Locally Augmented Preferences and Representation Disentanglement](https://mlsanity.com/paper/2608.24859/) (2026)
- [GeoPAR: Large-Scale Multi-Agent Combinatorial Optimization with Geometry-Guided Parallel Autoregressive Learning](https://mlsanity.com/paper/2609.00577/) (2026)
- [EDISCO: Equivariant DIScrete Diffusion for Euclidean Combinatorial Optimization](https://mlsanity.com/paper/2610.04953/) (2026)

## Abstract (arXiv)

Vehicle Routing Problems (VRPs) are significant Combinatorial Optimization (CO) problems holding substantial practical importance. Recently, Neural Combinatorial Optimization (NCO), which involves training deep learning models on extensive data to learn vehicle routing heuristics, has emerged as a promising approach due to its efficiency and the reduced need for manual algorithm design. However, applying NCO across diverse real-world scenarios with various constraints necessitates cross-problem capabilities. Current NCO methods typically employ a unified model lacking a constraint-specific structure, thereby restricting their cross-problem performance. Current multi-task methods for VRPs typically employ a constraint-unaware model, limiting their cross-problem performance. Furthermore, they rely solely on global connectivity, which fails to focus on key nodes and leads to inefficient representation learning. This paper introduces a Constraint-Aware Dual-Attention Model (CaDA), designed to address these limitations. CaDA incorporates a constraint prompt that efficiently represents different problem variants. Additionally, it features a dual-attention mechanism with a global branch for capturing broader graph-wide information and a sparse branch that selectively focuses on the most relevant nodes. We comprehensively evaluate our model on 16 different VRPs and compare its performance against existing cross-problem VRP solvers. CaDA achieves state-of-the-art results across all the VRPs. Our ablation study further confirms that each component of CaDA contributes positively to its cross-problem learning performance.