mlsanityData to 14 Oct 2026

Neural Deconstruction Search for Vehicle Routing Problems

arXiv 2501.03715 ↗First posted 7 Jan 2025cs.AI cs.LGcited by 15

Not on the map. Why?

Abstract (arXiv)

Autoregressive construction approaches generate solutions to vehicle routing problems in a step-by-step fashion, leading to high-quality solutions that are nearing the performance achieved by handcrafted operations research techniques. In this work, we challenge the conventional paradigm of sequential solution construction and introduce an iterative search framework where solutions are instead deconstructed by a neural policy. Throughout the search, the neural policy collaborates with a simple greedy insertion algorithm to rebuild the deconstructed solutions. Our approach matches or surpasses the performance of state-of-the-art operations research methods across three challenging vehicle routing problems of various problem sizes.

Key facts. Cited by 15 papers in the map (data through 14 Oct 2026). Builds on 36 of its 52 references that are in the map. First posted on arXiv 7 Jan 2025.

Builds on

36 of 52 references.

References · 36

  1. 2017Attention Is All You Needcited by 60,361
  2. 2014Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translationcited by 4,057
  3. 2015Pointer Networkscited by 895
  4. 2018Attention, Learn to Solve Routing Problems!cited by 656
  5. 2016Neural Combinatorial Optimization with Reinforcement Learningcited by 608
  6. 2020POMO: Policy Optimization with Multiple Optima for Reinforcement Learningcited by 348
  7. 2018Reinforcement Learning for Solving the Vehicle Routing Problemcited by 333
  8. 2019An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problemcited by 269
  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
24 more
  1. 2020Hybrid Genetic Search for the CVRP: Open-Source Implementation and SWAP* Neighborhoodcited by 125
  2. 2022Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimizationcited by 119
  3. 2019Neural Large Neighborhood Search for the Capacitated Vehicle Routing Problemcited by 117
  4. 2021Learning to Delegate for Large-scale Vehicle Routingcited by 109
  5. 2021Learning to Iteratively Solve Routing Problems with Dual-Aspect Collaborative Transformercited by 108
  6. 2020Learning 2-opt Heuristics for the Traveling Salesman Problem via Deep Reinforcement Learningcited by 100
  7. 2021Efficient Active Search for Combinatorial Optimization Problemscited by 100
  8. 2021Deep Policy Dynamic Programming for Vehicle Routing Problemscited by 94
  9. 2021Learning Collaborative Policies to Solve NP-hard Routing Problemscited by 86
  10. 2023GLOP: Learning Global Partition and Local Construction for Solving Large-scale Routing Problems in Real-timecited by 85
  11. 2022Simulation-guided Beam Search for Neural Combinatorial Optimizationcited by 84
  12. 2023Learning to Search Feasible and Infeasible Regions of Routing Problems with Flexible Neural k-Optcited by 81
  13. 2023DeepACO: Neural-enhanced Ant Systems for Combinatorial Optimizationcited by 78
  14. 2023RL4CO: an Extensive Reinforcement Learning for Combinatorial Optimization Benchmarkcited by 71
  15. 2022Winner Takes It All: Training Performant RL Populations for Combinatorial Optimizationcited by 58
  16. 2023Unsupervised Learning for Solving the Travelling Salesman Problemcited by 58
  17. 2024RouteFinder: Towards Foundation Models for Vehicle Routing Problemscited by 55
  18. 2024Ant Colony Sampling with GFlowNets for Combinatorial Optimizationcited by 53
  19. 2023PyVRP: a high-performance VRP solver packagecited by 52
  20. 2024UDC: A Unified Neural Divide-and-Conquer Framework for Large-Scale Combinatorial Optimization Problemscited by 47
  21. 2024PolyNet: Learning Diverse Solution Strategies for Neural Combinatorial Optimizationcited by 35
  22. 2020Learning to Solve Vehicle Routing Problems with Time Windows through Joint Attentioncited by 29
  23. 2023Too Big, so Fail? -- Enabling Neural Construction Methods to Solve Large-Scale Routing Problemscited by 6
  24. 2024An efficient implementation of parallel simulated annealing algorithm in GPUscited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 8; 2026: 7.

15 papers.

Sort:

By area:

  1. 2025MTL-KD: Multi-Task Learning Via Knowledge Distillation for Generalizable Neural Vehicle Routing Solvercited by 13
  2. 2025RRNCO: Towards Real-World Routing with Neural Combinatorial Optimizationcited by 11
  3. 2025Learning to Insert for Constructive Neural Vehicle Routing Solvercited by 10
  4. 2025VRPAgent: LLM-Driven Discovery of Heuristic Operators for Vehicle Routing Problemscited by 7
  5. 2025Learning to Segment for Vehicle Routing Problemscited by 5
  6. 2026Survey on Neural Routing Solverscited by 4
  7. 2025USPR: Learning a Unified Solver for Profiled Routingcited by 1
  8. 2025Recurrent State Encoders for Efficient Neural Combinatorial Optimizationcited by 1
  9. 2026Large Neighborhood Search meets Iterative Neural Constraint Heuristicscited by 1
  10. 2026Learning with Foresight: Enhancing Neural Routing Policy via Multi-Node Lookahead Predictioncited by 1
  11. 2025GAMA: A Neural Neighborhood Search Method with Graph-aware Multi-modal Attention for Vehicle Routing Problemcited by 0
  12. 2026Learning to Solve Orienteering Problem with Time Windows and Variable Profitscited by 0
3 more
  1. 2026Rethinking Positional Encoding for Neural Vehicle Routingcited by 0
  2. 2026JAMPR+/L2D: scalable neural heuristic for constrained vehicle routing problems in dynamic environmentcited by 0
  3. 2026SPO: Discovering Adaptive Large Neighborhood Search Operators via Stackelberg Program Optimizationcited by 0