mlsanityData to 14 Oct 2026

Reinforcement Learning with Combinatorial Actions: An Application to Vehicle Routing

arXiv 2010.12001 ↗First posted 22 Oct 2020cs.LG cs.AI math.OCcited by 61

Not on the map. Why?

Abstract (arXiv)

Value-function-based methods have long played an important role in reinforcement learning. However, finding the best next action given a value function of arbitrary complexity is nontrivial when the action space is too large for enumeration. We develop a framework for value-function-based deep reinforcement learning with a combinatorial action space, in which the action selection problem is explicitly formulated as a mixed-integer optimization problem. As a motivating example, we present an application of this framework to the capacitated vehicle routing problem (CVRP), a combinatorial optimization problem in which a set of locations must be covered by a single vehicle with limited capacity. On each instance, we model an action as the construction of a single route, and consider a deterministic policy which is improved through a simple policy iteration algorithm. Our approach is competitive with other reinforcement learning methods and achieves an average gap of 1.7% with state-of-the-art OR methods on standard library instances of medium size.

Key facts. Cited by 61 papers in the map (data through 14 Oct 2026). First posted on arXiv 22 Oct 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 12; 2022: 8; 2023: 16; 2024: 8; 2025: 8; 2026: 9.

61 papers.

Sort:

By area:

  1. 2021Deep Policy Dynamic Programming for Vehicle Routing Problemscited by 94
  2. 2022Simulation-guided Beam Search for Neural Combinatorial Optimizationcited by 84
  3. 2023Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNetscited by 40
  4. 2023When Deep Learning Meets Polyhedral Theory: A Surveycited by 39
  5. 2021Reinforcement Learning for Ridesharing: An Extended Surveycited by 35
  6. 2022Unsupervised Learning for Combinatorial Optimization with Principled Objective Relaxationcited by 32
  7. 2021An Overview and Experimental Study of Learning-based Optimization Algorithms for Vehicle Routing Problemcited by 22
  8. 2022A Deep Reinforcement Learning Framework For Column Generationcited by 22
  9. 2023Unsupervised Learning for Combinatorial Optimization Needs Meta-Learningcited by 20
  10. 2021Scaling Up Exact Neural Network Compression by ReLU Stabilitycited by 19
  11. 2022Learning to Solve Vehicle Routing Problems: A Surveycited by 16
  12. 2024Optimization Over Trained Neural Networks: Taking a Relaxing Walkcited by 10
38 more
  1. 2024Offline-Boosted Actor-Critic: Adaptively Blending Optimal Historical Behaviors in Deep Off-Policy RLcited by 10
  2. 2025Learning to Insert for Constructive Neural Vehicle Routing Solvercited by 10
  3. 2021Modeling Design and Control Problems Involving Neural Network Surrogatescited by 9
  4. 2025A Forget-and-Grow Strategy for Deep Reinforcement Learning Scaling in Continuous Controlcited by 9
  5. 2021Smart Feasibility Pump: Reinforcement Learning for (Mixed) Integer Programmingcited by 8
  6. 2023Getting Away with More Network Pruning: From Sparsity to Geometry and Linear Regionscited by 8
  7. 2022Overcoming the Long Horizon Barrier for Sample-Efficient Reinforcement Learning with Latent Low-Rank Structurecited by 7
  8. 2024Tackling Prevalent Conditions in Unsupervised Combinatorial Optimization: Cardinality, Minimum, Covering, and Morecited by 7
  9. 2021Fast Approximate Solutions using Reinforcement Learning for Dynamic Capacitated Vehicle Routing with Time Windowscited by 6
  10. 2021Deep Policy Iteration with Integer Programming for Inventory Managementcited by 6
  11. 2023Efficient Planning in Combinatorial Action Spaces with Applications to Cooperative Multi-Agent Reinforcement Learningcited by 6
  12. 2023Computational Tradeoffs of Optimization-Based Bound Tightening in ReLU Networkscited by 6
  13. 2023Assessment of Reinforcement Learning Algorithms for Nuclear Power Plant Fuel Optimizationcited by 5
  14. 2023Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methodscited by 5
  15. 2024Stochastic Q-learning for Large Discrete Action Spacescited by 5
  16. 2024A Behavior-Aware Approach for Deep Reinforcement Learning in Non-stationary Environments without Known Change Pointscited by 5
  17. 2025Reinforcement learning with combinatorial actions for coupled restless banditscited by 5
  18. 2024Offline Hierarchical Reinforcement Learning via Inverse Optimizationcited by 4
  19. 2021Deep Reinforcement Learning for Demand Driven Services in Logistics and Transportation Systems: A Surveycited by 3
  20. 2022The First AI4TSP Competition: Learning to Solve Stochastic Routing Problemscited by 3
  21. 2022Cost Effective MLaaS Federation: A Combinatorial Reinforcement Learning Approachcited by 3
  22. 2024BraVE: Offline Reinforcement Learning for Discrete Combinatorial Action Spacescited by 3
  23. 2026Combinatorial Optimization Augmented Machine Learningcited by 3
  24. 2021Where the Action is: Let's make Reinforcement Learning for Stochastic Dynamic Vehicle Routing Problems work!cited by 2
  25. 2022Solving the capacitated vehicle routing problem with timing windows using rollouts and MAX-SATcited by 2
  26. 2024Multi-Agent Reinforcement Learning for Joint Police Patrol and Dispatchcited by 2
  27. 2025Unrealized Expectations: Comparing AI Methods vs Classical Algorithms for Maximum Independent Setcited by 2
  28. 2021RP-DQN: An application of Q-Learning to Vehicle Routing Problemscited by 1
  29. 2023Diverse Policy Optimization for Structured Action Spacecited by 1
  30. 2023Surge Routing: Event-informed Multiagent Reinforcement Learning for Autonomous Ridesharecited by 1
  31. 2023Threshold-aware Learning to Generate Feasible Solutions for Mixed Integer Programscited by 1
  32. 2023Solving the Quadratic Assignment Problem using Deep Reinforcement Learningcited by 1
  33. 2025Conformal Mixed-Integer Constraint Learning with Feasibility Guaranteescited by 1
  34. 2025Attacks and Defenses Against LLM Fingerprintingcited by 1
  35. 2026Latent Spherical Flow Policy for Reinforcement Learning with Combinatorial Actionscited by 1
  36. 2026Efficient Decoder Scaling Strategy for Neural Routing Solverscited by 1
  37. 2026Baseline-Free Policy Optimization for Neural Combinatorial Optimizationcited by 1
  38. 2021A study of first-passage time minimization via Q-learning in heated gridworldscited by 0

50 most cited of 61 All 61 (JSON)