mlsanityData to 7 Oct 2026

Learning to Search Feasible and Infeasible Regions of Routing Problems with Flexible Neural k-Opt

arXiv 2310.18264 ↗First posted 27 Oct 2023cs.LG cs.AIcited by 81

Not on the map. Why?

Abstract (arXiv)

In this paper, we present Neural k-Opt (NeuOpt), a novel learning-to-search (L2S) solver for routing problems. It learns to perform flexible k-opt exchanges based on a tailored action factorization method and a customized recurrent dual-stream decoder. As a pioneering work to circumvent the pure feasibility masking scheme and enable the autonomous exploration of both feasible and infeasible regions, we then propose the Guided Infeasible Region Exploration (GIRE) scheme, which supplements the NeuOpt policy network with feasibility-related features and leverages reward shaping to steer reinforcement learning more effectively. Additionally, we equip NeuOpt with Dynamic Data Augmentation (D2A) for more diverse searches during inference. Extensive experiments on the Traveling Salesman Problem (TSP) and Capacitated Vehicle Routing Problem (CVRP) demonstrate that our NeuOpt not only significantly outstrips existing (masking-based) L2S solvers, but also showcases superiority over the learning-to-construct (L2C) and learning-to-predict (L2P) solvers. Notably, we offer fresh perspectives on how neural solvers can handle VRP constraints. Our code is available: https://github.com/yining043/NeuOpt.

Key facts. Cited by 81 papers in the map (data through 7 Oct 2026). Builds on 40 of its 60 references that are in the map. First posted on arXiv 27 Oct 2023.

Builds on

40 of 60 references.

References · 40

  1. 2015Deep Unsupervised Learning using Nonequilibrium Thermodynamicscited by 7,005
  2. 2014Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translationcited by 4,016
  3. 2016HyperNetworkscited by 1,003
  4. 2015Pointer Networkscited by 882
  5. 2022Recipe for a General, Powerful, Scalable Graph Transformercited by 702
  6. 2018Attention, Learn to Solve Routing Problems!cited by 646
  7. 2016Neural Combinatorial Optimization with Reinforcement Learningcited by 600
  8. 2017Learning Combinatorial Optimization Algorithms over Graphscited by 557
  9. 2020POMO: Policy Optimization with Multiple Optima for Reinforcement Learningcited by 341
  10. 2018Reinforcement Learning for Solving the Vehicle Routing Problemcited by 327
  11. 2019An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problemcited by 265
  12. 2023DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimizationcited by 216
28 more
  1. 2018Learning to Perform Local Rewriting for Combinatorial Optimizationcited by 183
  2. 2019Learning Improvement Heuristics for Solving Routing Problemscited by 162
  3. 2020Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instancescited by 161
  4. 2022DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problemscited by 127
  5. 2020Hybrid Genetic Search for the CVRP: Open-Source Implementation and SWAP* Neighborhoodcited by 122
  6. 2022Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimizationcited by 118
  7. 2021Learning to Delegate for Large-scale Vehicle Routingcited by 108
  8. 2021Learning to Iteratively Solve Routing Problems with Dual-Aspect Collaborative Transformercited by 108
  9. 2020Learning 2-opt Heuristics for the Traveling Salesman Problem via Deep Reinforcement Learningcited by 100
  10. 2020Multi-Decoder Attention Model with Embedding Glimpse for Solving Vehicle Routing Problemscited by 100
  11. 2021Efficient Active Search for Combinatorial Optimization Problemscited by 99
  12. 2021Deep Policy Dynamic Programming for Vehicle Routing Problemscited by 94
  13. 2021Learning Collaborative Policies to Solve NP-hard Routing Problemscited by 86
  14. 2021Sparse is Enough in Scaling Transformerscited by 86
  15. 2022Simulation-guided Beam Search for Neural Combinatorial Optimizationcited by 84
  16. 2021Graph Neural Network Guided Local Search for the Traveling Salesperson Problemcited by 70
  17. 2023Towards Omni-generalizable Neural Methods for Vehicle Routing Problemscited by 68
  18. 2022Learning Generalizable Models for Vehicle Routing Problems via Knowledge Distillationcited by 61
  19. 2022Penalized Proximal Policy Optimization for Safe Reinforcement Learningcited by 60
  20. 2022Pareto Set Learning for Neural Multi-objective Combinatorial Optimizationcited by 56
  21. 2023Pointerformer: Deep Reinforced Multi-Pointer Transformer for the Traveling Salesman Problemcited by 49
  22. 2023H-TSP: Hierarchically Solving the Large-Scale Travelling Salesman Problemcited by 43
  23. 2020Learning to Solve Combinatorial Optimization Problems on Real-World Graphs in Linear Timecited by 39
  24. 2020Online 3D Bin Packing with Constrained Deep Reinforcement Learningcited by 35
  25. 2021Heterogeneous Attentions for Solving Pickup and Delivery Problem via Deep Reinforcement Learningcited by 35
  26. 2021Deep Reinforcement Learning for Solving the Heterogeneous Capacitated Vehicle Routing Problemcited by 31
  27. 2022Efficient Neural Neighborhood Search for Pickup and Delivery Problemscited by 29
  28. 2022Model-based Safe Deep Reinforcement Learning via a Constrained Proximal Policy Optimization Algorithmcited by 27

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 1; 2024: 19; 2025: 37; 2026: 24.

81 papers.

Sort:

By area:

  1. 2024ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolutioncited by 266
  2. 2023GLOP: Learning Global Partition and Local Construction for Solving Large-scale Routing Problems in Real-timecited by 82
  3. 2024MVMoE: Multi-Task Vehicle Routing Solver with Mixture-of-Expertscited by 69
  4. 2024RouteFinder: Towards Foundation Models for Vehicle Routing Problemscited by 54
  5. 2024Ant Colony Sampling with GFlowNets for Combinatorial Optimizationcited by 53
  6. 2025Rethinking Light Decoder-based Solvers for Vehicle Routing Problemscited by 36
  7. 2024PolyNet: Learning Diverse Solution Strategies for Neural Combinatorial Optimizationcited by 35
  8. 2024Learning to Handle Complex Constraints for Vehicle Routing Problemscited by 29
  9. 2024Position: Rethinking Post-Hoc Search-Based Neural Approaches for Solving Large-Scale Traveling Salesman Problemscited by 24
  10. 2024Neural Combinatorial Optimization Algorithms for Solving Vehicle Routing Problems: A Comprehensive Survey with Perspectivescited by 23
  11. 2025Neural Deconstruction Search for Vehicle Routing Problemscited by 15
  12. 2025BOPO: Neural Combinatorial Optimization via Best-anchored and Objective-guided Preference Optimizationcited by 14
38 more
  1. 2024DISCO: Efficient Diffusion Solver for Large-Scale Combinatorial Optimization Problemscited by 10
  2. 2025Adversarial Generative Flow Network for Solving Vehicle Routing Problemscited by 10
  3. 2025RRNCO: Towards Real-World Routing with Neural Combinatorial Optimizationcited by 10
  4. 2025Learning to Insert for Constructive Neural Vehicle Routing Solvercited by 10
  5. 2024Hierarchical Neural Constructive Solver for Real-world TSP Scenarioscited by 9
  6. 2024Collaboration! Towards Robust Neural Methods for Routing Problemscited by 9
  7. 2024PARCO: Parallel AutoRegressive Models for Multi-Agent Combinatorial Optimizationcited by 7
  8. 2025Learning-Guided Rolling Horizon Optimization for Long-Horizon Flexible Job-Shop Schedulingcited by 7
  9. 2025Generalizable Heuristic Generation Through LLMs with Meta-Optimizationcited by 7
  10. 2025Rethinking Neural Combinatorial Optimization for Vehicle Routing Problems with Different Constraint Tightness Degreescited by 7
  11. 2025Hybrid-Balance GFlowNet for Solving Vehicle Routing Problemscited by 7
  12. 2025Multi-Task Vehicle Routing Solver via Mixture of Specialized Experts under State-Decomposable MDPcited by 7
  13. 2026RADAR: Learning to Route with Asymmetry-aware DistAnce Representationscited by 7
  14. 2025Learning for routing: A guided review of recent developments and future directionscited by 6
  15. 2025VRPAgent: LLM-Driven Discovery of Heuristic Operators for Vehicle Routing Problemscited by 6
  16. 2024Leader Reward for POMO-Based Neural Combinatorial Optimizationcited by 5
  17. 2024Neural Solver Selection for Combinatorial Optimizationcited by 5
  18. 2025Learning to Segment for Vehicle Routing Problemscited by 5
  19. 2025An Agentic Framework with LLMs for Solving Complex Vehicle Routing Problemscited by 5
  20. 2026PathWise: Planning through World Model for Automated Heuristic Design via Self-Evolving LLMscited by 5
  21. 2024Learning Solution-Aware Transformers for Efficiently Solving Quadratic Assignment Problemcited by 4
  22. 2026Survey on Neural Routing Solverscited by 4
  23. 2024MARCO: A Memory-Augmented Reinforcement Framework for Combinatorial Optimizationcited by 3
  24. 2025Neural Graduated Assignment for Maximum Common Edge Subgraphscited by 3
  25. 2025LMask: Learn to Solve Constrained Routing Problems with Lazy Maskingcited by 3
  26. 2025Efficient Neural Combinatorial Optimization Solver for the Min-max Heterogeneous Capacitated Vehicle Routing Problemcited by 3
  27. 2025Refining Hybrid Genetic Search for CVRP via Reinforcement Learning-Finetuned LLMcited by 3
  28. 2025Probing Neural Combinatorial Optimization Modelscited by 3
  29. 2025Bridging Synthetic and Real Routing Problems via LLM-Guided Instance Generation and Progressive Adaptationcited by 3
  30. 2026TIDE: Tuning-Integrated Dynamic Evolution for LLM-Based Automated Heuristic Designcited by 3
  31. 2024Scaling Combinatorial Optimization Neural Improvement Heuristics with Online Search and Adaptationcited by 2
  32. 2025Diversity Optimization for Travelling Salesman Problem via Deep Reinforcement Learningcited by 2
  33. 2025TuneNSearch: a hybrid transfer learning and local search approach for solving vehicle routing problemscited by 2
  34. 2025Accelerating Vehicle Routing via AI-Initialized Genetic Algorithmscited by 2
  35. 2026Towards Efficient Constraint Handling in Neural Solvers for Routing Problemscited by 2
  36. 2026Chain-of-Context Learning: Dynamic Constraint Understanding for Multi-Task VRPscited by 2
  37. 2024On Size and Hardness Generalization in Unsupervised Learning for the Travelling Salesman Problemcited by 1
  38. 2024Feature-Guided Metaheuristic with Diversity Management for Solving the Capacitated Vehicle Routing Problemcited by 1

50 most cited of 81 All 81 (JSON)