mlsanityData to 7 Oct 2026

Learning to Handle Complex Constraints for Vehicle Routing Problems

arXiv 2410.21066 ↗First posted 28 Oct 2024cs.AI cs.LGcited by 29

Not on the map. Why?

Abstract (arXiv)

Vehicle Routing Problems (VRPs) can model many real-world scenarios and often involve complex constraints. While recent neural methods excel in constructing solutions based on feasibility masking, they struggle with handling complex constraints, especially when obtaining the masking itself is NP-hard. In this paper, we propose a novel Proactive Infeasibility Prevention (PIP) framework to advance the capabilities of neural methods towards more complex VRPs. Our PIP integrates the Lagrangian multiplier as a basis to enhance constraint awareness and introduces preventative infeasibility masking to proactively steer the solution construction process. Moreover, we present PIP-D, which employs an auxiliary decoder and two adaptive strategies to learn and predict these tailored masks, potentially enhancing performance while significantly reducing computational costs during training. To verify our PIP designs, we conduct extensive experiments on the highly challenging Traveling Salesman Problem with Time Window (TSPTW), and TSP with Draft Limit (TSPDL) variants under different constraint hardness levels. Notably, our PIP is generic to boost many neural methods, and exhibits both a significant reduction in infeasible rate and a substantial improvement in solution quality.

Key facts. Cited by 29 papers in the map (data through 7 Oct 2026). Builds on 55 of its 77 references that are in the map. First posted on arXiv 28 Oct 2024.

Builds on

55 of 77 references.

References · 55

  1. 2015Pointer Networkscited by 882
  2. 2023Large Language Models as Optimizerscited by 830
  3. 2018Attention, Learn to Solve Routing Problems!cited by 646
  4. 2018Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizoncited by 612
  5. 2016Neural Combinatorial Optimization with Reinforcement Learningcited by 600
  6. 2020POMO: Policy Optimization with Multiple Optima for Reinforcement Learningcited by 341
  7. 2018Reinforcement Learning for Solving the Vehicle Routing Problemcited by 327
  8. 2019An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problemcited by 265
  9. 2024Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Modelcited by 258
  10. 2023DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimizationcited by 216
  11. 2018Learning to Perform Local Rewriting for Combinatorial Optimizationcited by 183
  12. 2019Learning Improvement Heuristics for Solving Routing Problemscited by 162
38 more
  1. 2020Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instancescited by 161
  2. 2023Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalizationcited by 140
  3. 2022DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problemscited by 127
  4. 2023Large Language Models as Evolutionary Optimizerscited by 122
  5. 2022Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimizationcited by 118
  6. 2019Neural Large Neighborhood Search for the Capacitated Vehicle Routing Problemcited by 117
  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. 2021NeuroLKH: Combining Deep Learning Model with Lin-Kernighan-Helsgaun Heuristic for Solving the Traveling Salesman Problemcited by 102
  10. 2020Learning 2-opt Heuristics for the Traveling Salesman Problem via Deep Reinforcement Learningcited by 100
  11. 2020Multi-Decoder Attention Model with Embedding Glimpse for Solving Vehicle Routing Problemscited by 100
  12. 2021Efficient Active Search for Combinatorial Optimization Problemscited by 99
  13. 2021Deep Policy Dynamic Programming for Vehicle Routing Problemscited by 94
  14. 2021Matrix Encoding Networks for Neural Combinatorial Optimizationcited by 89
  15. 2022Simulation-guided Beam Search for Neural Combinatorial Optimizationcited by 84
  16. 2023GLOP: Learning Global Partition and Local Construction for Solving Large-scale Routing Problems in Real-timecited by 82
  17. 2023Learning to Search Feasible and Infeasible Regions of Routing Problems with Flexible Neural k-Optcited by 81
  18. 2019Combinatorial Optimization by Graph Pointer Networks and Hierarchical Reinforcement Learningcited by 78
  19. 2023DeepACO: Neural-enhanced Ant Systems for Combinatorial Optimizationcited by 77
  20. 2023RL4CO: an Extensive Reinforcement Learning for Combinatorial Optimization Benchmarkcited by 70
  21. 2024MVMoE: Multi-Task Vehicle Routing Solver with Mixture-of-Expertscited by 69
  22. 2023Towards Omni-generalizable Neural Methods for Vehicle Routing Problemscited by 68
  23. 2020Combining Reinforcement Learning and Constraint Programming for Combinatorial Optimizationcited by 63
  24. 2022Learning Generalizable Models for Vehicle Routing Problems via Knowledge Distillationcited by 61
  25. 2022Winner Takes It All: Training Performant RL Populations for Combinatorial Optimizationcited by 57
  26. 2023Unsupervised Learning for Solving the Travelling Salesman Problemcited by 57
  27. 2024Ant Colony Sampling with GFlowNets for Combinatorial Optimizationcited by 53
  28. 2023Pointerformer: Deep Reinforced Multi-Pointer Transformer for the Traveling Salesman Problemcited by 49
  29. 2023H-TSP: Hierarchically Solving the Large-Scale Travelling Salesman Problemcited by 43
  30. 2023Combinatorial Optimization with Policy Adaptation using Latent Space Searchcited by 41
  31. 2020Online 3D Bin Packing with Constrained Deep Reinforcement Learningcited by 35
  32. 2021Generalization of Neural Combinatorial Solvers Through the Lens of Adversarial Robustnesscited by 35
  33. 2024PolyNet: Learning Diverse Solution Strategies for Neural Combinatorial Optimizationcited by 35
  34. 2021Deep Reinforcement Learning for Solving the Heterogeneous Capacitated Vehicle Routing Problemcited by 31
  35. 2020Learning to Solve Vehicle Routing Problems with Time Windows through Joint Attentioncited by 29
  36. 2022Efficient Neural Neighborhood Search for Pickup and Delivery Problemscited by 29
  37. 2024Self-Improved Learning for Scalable Neural Combinatorial Optimizationcited by 29
  38. 2022Learning to Solve Travelling Salesman Problem with Hardness-adaptive Curriculumcited by 27

50 most cited of 55 All 55 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 15; 2026: 14.

29 papers.

Sort:

By area:

  1. 2025Rethinking Light Decoder-based Solvers for Vehicle Routing Problemscited by 36
  2. 2025BOPO: Neural Combinatorial Optimization via Best-anchored and Objective-guided Preference Optimizationcited by 14
  3. 2025Learning to Insert for Constructive Neural Vehicle Routing Solvercited by 10
  4. 2026Constructing Industrial-Scale Optimization Modeling Benchmarkcited by 10
  5. 2025Generalizable Heuristic Generation Through LLMs with Meta-Optimizationcited by 7
  6. 2025Rethinking Neural Combinatorial Optimization for Vehicle Routing Problems with Different Constraint Tightness Degreescited by 7
  7. 2025Preference-Driven Multi-Objective Combinatorial Optimization with Conditional Computationcited by 6
  8. 2025An Agentic Framework with LLMs for Solving Complex Vehicle Routing Problemscited by 5
  9. 2026Survey on Neural Routing Solverscited by 4
  10. 2025Learning Constraints-Based Adaptive Hypergraph Neural Networks for Solving Vehicle Routing Problemscited by 3
  11. 2025LMask: Learn to Solve Constrained Routing Problems with Lazy Maskingcited by 3
  12. 2025TuneNSearch: a hybrid transfer learning and local search approach for solving vehicle routing problemscited by 2
17 more
  1. 2025Beyond Simple Graphs: Neural Multi-Objective Routing on Multigraphscited by 2
  2. 2025Lifelong Learner: Discovering Versatile Neural Solvers for Vehicle Routing Problemscited by 2
  3. 2026Towards Efficient Constraint Handling in Neural Solvers for Routing Problemscited by 2
  4. 2025USPR: Learning a Unified Solver for Profiled Routingcited by 1
  5. 2025Learning to Optimize Capacity Planning in Semiconductor Manufacturingcited by 1
  6. 2026Efficient Decoder Scaling Strategy for Neural Routing Solverscited by 1
  7. 2025GAMA: A Neural Neighborhood Search Method with Graph-aware Multi-modal Attention for Vehicle Routing Problemcited by 0
  8. 2026EGAM: Extended Graph Attention Model for Solving Routing Problemscited by 0
  9. 2026Learning to Solve Orienteering Problem with Time Windows and Variable Profitscited by 0
  10. 2026Offline Decision Transformers for Neural Combinatorial Optimization: Surpassing Heuristics on the Traveling Salesman Problemcited by 0
  11. 2026The Traveling Thief Problem with Time Windows: Benchmarks and Heuristicscited by 0
  12. 2026Enhancing Cross-Problem Vehicle Routing via Federated Learningcited by 0
  13. 2026Two-Stage Learned Decomposition for Scalable Routing on Multigraphscited by 0
  14. 2026LINC: Decoupling Local Consequence Scoring from Hidden Matching in Constructive Neural Routingcited by 0
  15. 2026A Unified Knowledge Embedded Reinforcement Learning-based Framework for Generalized Capacitated Vehicle Routing Problemscited by 0
  16. 2026Optimizing Nursing Care Taxi Dispatch Leveraging Integer Linear Programming Solvers and Machine Learningcited by 0
  17. 2026Position: Certified Correctness in Neural Constraint Reasoning Requires Symbolic Integrationcited by 0