mlsanityData to 14 Oct 2026

Rethinking Light Decoder-based Solvers for Vehicle Routing Problems

arXiv 2503.00753 ↗First posted 2 Mar 2025cs.AI cs.LGcited by 37

On the map: Deep reinforcement learning methods → RL for games and combinatorial optimization

Abstract (arXiv)

Light decoder-based solvers have gained popularity for solving vehicle routing problems (VRPs) due to their efficiency and ease of integration with reinforcement learning algorithms. However, they often struggle with generalization to larger problem instances or different VRP variants. This paper revisits light decoder-based approaches, analyzing the implications of their reliance on static embeddings and the inherent challenges that arise. Specifically, we demonstrate that in the light decoder paradigm, the encoder is implicitly tasked with capturing information for all potential decision scenarios during solution construction within a single set of embeddings, resulting in high information density. Furthermore, our empirical analysis reveals that the overly simplistic decoder struggles to effectively utilize this dense information, particularly as task complexity increases, which limits generalization to out-of-distribution (OOD) settings. Building on these insights, we show that enhancing the decoder capacity, with a simple addition of identity mapping and a feed-forward layer, can considerably alleviate the generalization issue. Experimentally, our method significantly enhances the OOD generalization of light decoder-based approaches on large-scale instances and complex VRP variants, narrowing the gap with the heavy decoder paradigm. Our code is available at: https://github.com/ziweileonhuang/reld-nco.

Key facts. Cited by 37 papers in the map (data through 14 Oct 2026). Placed in RL for games and combinatorial optimization, one of 15 directions in Deep reinforcement learning methods. Builds on 61 of its 76 references that are in the map. First posted on arXiv 2 Mar 2025.

Builds on

61 of 76 references.

Closest ancestors · 3

Same direction, newest first

  1. 2024Self-Improvement for Neural Combinatorial Optimization: Sample without Replacement, but Improvement22 Mar
  2. 2024PolyNet: Learning Diverse Solution Strategies for Neural Combinatorial Optimization21 Feb
  3. 2024INViT: A Generalizable Routing Problem Solver with Invariant Nested View Transformer4 Feb

Other references · 58

  1. 2015Deep Residual Learning for Image Recognitioncited by 52,096
  2. 2020Language Models are Few-Shot Learnerscited by 32,419
  3. 2023Llama 2: Open Foundation and Fine-Tuned Chat Modelscited by 13,028
  4. 2020A Simple Framework for Contrastive Learning of Visual Representationscited by 12,049
  5. 2019Momentum Contrast for Unsupervised Visual Representation Learningcited by 7,513
  6. 2023GQA: Training Generalized Multi-Query Transformer Models from Multi-Head Checkpointscited by 1,346
  7. 2015Pointer Networkscited by 895
  8. 2019Fast Transformer Decoding: One Write-Head is All You Needcited by 717
  9. 2021Do Vision Transformers See Like Convolutional Neural Networks?cited by 675
  10. 2018Attention, Learn to Solve Routing Problems!cited by 656
  11. 2020On the Bottleneck of Graph Neural Networks and its Practical Implicationscited by 631
  12. 2018Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizoncited by 623
38 more
  1. 2016Neural Combinatorial Optimization with Reinforcement Learningcited by 608
  2. 2021MetaFormer Is Actually What You Need for Visioncited by 524
  3. 2020POMO: Policy Optimization with Multiple Optima for Reinforcement Learningcited by 348
  4. 2018Reinforcement Learning for Solving the Vehicle Routing Problemcited by 333
  5. 2019An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problemcited by 269
  6. 2021Combinatorial optimization and reasoning with graph neural networkscited by 268
  7. 2020ReZero is All You Need: Fast Convergence at Large Depthcited by 264
  8. 2023DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimizationcited by 221
  9. 2018Learning to Perform Local Rewriting for Combinatorial Optimizationcited by 185
  10. 2019Learning Improvement Heuristics for Solving Routing Problemscited by 164
  11. 2020Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instancescited by 162
  12. 2023Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalizationcited by 142
  13. 2020Learning to Dispatch for Job Shop Scheduling via Deep Reinforcement Learningcited by 140
  14. 2022DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problemscited by 129
  15. 2020Hybrid Genetic Search for the CVRP: Open-Source Implementation and SWAP* Neighborhoodcited by 125
  16. 2022Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimizationcited by 119
  17. 2021Learning to Delegate for Large-scale Vehicle Routingcited by 109
  18. 2021Learning to Iteratively Solve Routing Problems with Dual-Aspect Collaborative Transformercited by 108
  19. 2021NeuroLKH: Combining Deep Learning Model with Lin-Kernighan-Helsgaun Heuristic for Solving the Traveling Salesman Problemcited by 103
  20. 2020Learning 2-opt Heuristics for the Traveling Salesman Problem via Deep Reinforcement Learningcited by 100
  21. 2020Multi-Decoder Attention Model with Embedding Glimpse for Solving Vehicle Routing Problemscited by 100
  22. 2021Matrix Encoding Networks for Neural Combinatorial Optimizationcited by 91
  23. 2023GLOP: Learning Global Partition and Local Construction for Solving Large-scale Routing Problems in Real-timecited by 85
  24. 2023BQ-NCO: Bisimulation Quotienting for Efficient Neural Combinatorial Optimizationcited by 82
  25. 2023Learning to Search Feasible and Infeasible Regions of Routing Problems with Flexible Neural k-Optcited by 81
  26. 2023DeepACO: Neural-enhanced Ant Systems for Combinatorial Optimizationcited by 78
  27. 2023RL4CO: an Extensive Reinforcement Learning for Combinatorial Optimization Benchmarkcited by 71
  28. 2024MVMoE: Multi-Task Vehicle Routing Solver with Mixture-of-Expertscited by 70
  29. 2023Towards Omni-generalizable Neural Methods for Vehicle Routing Problemscited by 69
  30. 2022Learning Generalizable Models for Vehicle Routing Problems via Knowledge Distillationcited by 62
  31. 2023Towards Generalizable Neural Solvers for Vehicle Routing Problems via Ensemble with Transferrable Local Policycited by 62
  32. 2022Winner Takes It All: Training Performant RL Populations for Combinatorial Optimizationcited by 58
  33. 2023Unsupervised Learning for Solving the Travelling Salesman Problemcited by 58
  34. 2024RouteFinder: Towards Foundation Models for Vehicle Routing Problemscited by 55
  35. 2024Ant Colony Sampling with GFlowNets for Combinatorial Optimizationcited by 53
  36. 2023Pointerformer: Deep Reinforced Multi-Pointer Transformer for the Traveling Salesman Problemcited by 50
  37. 2024Multi-Task Learning for Routing Problem with Cross-Problem Zero-Shot Generalizationcited by 50
  38. 2024GOAL: A Generalist Combinatorial Optimization Agent Learnercited by 42

50 most cited of 58 All 58 (JSON)

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 17; 2026: 20.

37 papers.

Sort:

By area:

  1. 2025MTL-KD: Multi-Task Learning Via Knowledge Distillation for Generalizable Neural Vehicle Routing Solvercited by 13
  2. 2025Improving Generalization of Neural Combinatorial Optimization for Vehicle Routing Problems via Test-Time Projection Learningcited by 12
  3. 2025RRNCO: Towards Real-World Routing with Neural Combinatorial Optimizationcited by 11
  4. 2025Learning to Insert for Constructive Neural Vehicle Routing Solvercited by 10
  5. 2025Rethinking Neural Combinatorial Optimization for Vehicle Routing Problems with Different Constraint Tightness Degreescited by 8
  6. 2025URS: A Unified Neural Routing Solver for Cross-Problem Zero-Shot Generalizationcited by 8
  7. 2026RADAR: Learning to Route with Asymmetry-aware DistAnce Representationscited by 8
  8. 2025Hybrid-Balance GFlowNet for Solving Vehicle Routing Problemscited by 7
  9. 2025VRPAgent: LLM-Driven Discovery of Heuristic Operators for Vehicle Routing Problemscited by 7
  10. 2025EFormer: An Effective Edge-based Transformer for Vehicle Routing Problemscited by 5
  11. 2026Survey on Neural Routing Solverscited by 4
  12. 2025Learning Constraints-Based Adaptive Hypergraph Neural Networks for Solving Vehicle Routing Problemscited by 3
25 more
  1. 2025LMask: Learn to Solve Constrained Routing Problems with Lazy Maskingcited by 3
  2. 2026Towards Efficient Constraint Handling in Neural Solvers for Routing Problemscited by 3
  3. 2025Lifelong Learner: Discovering Versatile Neural Solvers for Vehicle Routing Problemscited by 2
  4. 2026Chain-of-Context Learning: Dynamic Constraint Understanding for Multi-Task VRPscited by 2
  5. 2026SPACE: Unifying Symmetric and Asymmetric Routing Problems for Generalist Neural Solvercited by 2
  6. 2025USPR: Learning a Unified Solver for Profiled Routingcited by 1
  7. 2025Recurrent State Encoders for Efficient Neural Combinatorial Optimizationcited by 1
  8. 2026Efficient Decoder Scaling Strategy for Neural Routing Solverscited by 1
  9. 2026Rethinking Constraint Awareness for Efficient State Embedding of Neural Routing Solvercited by 1
  10. 2026Learning with Foresight: Enhancing Neural Routing Policy via Multi-Node Lookahead Predictioncited by 1
  11. 2025Latent Guided Sampling for Combinatorial Optimizationcited by 0
  12. 2025GAMA: A Neural Neighborhood Search Method with Graph-aware Multi-modal Attention for Vehicle Routing Problemcited by 0
  13. 2025ARC: Leveraging Compositional Representations for Cross-Problem Learning on VRPscited by 0
  14. 2026SEAFormer: A Spatial Proximity and Edge-Aware Transformer for Real-World Vehicle Routing Problemscited by 0
  15. 2026Keep Rehearsing and Refining: Lifelong Learning Vehicle Routing under Continually Drifting Taskscited by 0
  16. 2026Enhancing Cross-Problem Vehicle Routing via Federated Learningcited by 0
  17. 2026LINC: Decoupling Local Consequence Scoring from Hidden Matching in Constructive Neural Routingcited by 0
  18. 2026Learning to Solve Compositional Geometry Routing Problemscited by 0
  19. 2026Edge-aware Decoding for Neural Asymmetric Routingcited by 0
  20. 2026LaT: LLM-as-Trainer for Multi-Task Vehicle Routing Solverscited by 0
  21. 2026Improving Cross-Problem Vehicle Routing with Locally Augmented Preferences and Representation Disentanglementcited by 0
  22. 2026Depot-Closed Multi-Component Construction for Neural Vehicle Routingcited by 0
  23. 2026Understanding Decision-Making Mechanisms in Neural Routing Solverscited by 0
  24. 2026MiLoop: Selective Memory Propagation for Neural Combinatorial Optimizationcited by 0
  25. 2026Size Generalization for Diffusion Routing Solverscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2026Two Black Boxes, One Solver: Encoder Probing and Decoder Attribution for Neural Multi-Attribute VRP under Hard-Mask and Recourse Decoders
  2. 2024DPN: Decoupling Partition and Navigation for Neural Solvers of Min-max Vehicle Routing Problems
  3. 2026Reinforcement Learning Enhanced LLM Agents for Complex Vehicle Routing Problems
  4. 2024Memory-Enhanced Neural Solvers for Routing Problems
  5. 2025SED2AM: Solving Multi-Trip Time-Dependent Vehicle Routing Problem using Deep Reinforcement Learning
  6. 2025TuneNSearch: a hybrid transfer learning and local search approach for solving vehicle routing problems
  7. 2026Beyond Solving: Prescriptive Probing for Neural Routing Solvers
  8. 2025Efficient Neural Combinatorial Optimization Solver for the Min-max Heterogeneous Capacitated Vehicle Routing Problem