mlsanityData to 14 Oct 2026

Reinforcement Learning for Solving the Pricing Problem in Column Generation: Applications to Vehicle Routing

arXiv 2504.02383 ↗First posted 3 Apr 2025cs.LGcited by 1

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

Abstract (arXiv)

In this paper, we address the problem of Column Generation (CG) using Reinforcement Learning (RL). Specifically, we use a RL model based on the attention-mechanism architecture to find the columns with most negative reduced cost in the Pricing Problem (PP). Unlike previous Machine Learning (ML) applications for CG, our model deploys an end-to-end mechanism as it independently solves the pricing problem without the help of any heuristic. We consider a variant of Vehicle Routing Problem (VRP) as a case study for our method. Through a set of experiments where our method is compared against a Dynamic Programming (DP)-based heuristic for solving the PP, we show that our method solves the linear relaxation up to a reasonable objective gap in significantly shorter running times.

Key facts. Cited by 1 paper 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 16 of its 45 references that are in the map. First posted on arXiv 3 Apr 2025.

Builds on

16 of 45 references.

References · 16

  1. 2017Graph Attention Networkscited by 8,923
  2. 2018Attention, Learn to Solve Routing Problems!cited by 656
  3. 2018Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizoncited by 623
  4. 2017Learning Combinatorial Optimization Algorithms over Graphscited by 561
  5. 2020POMO: Policy Optimization with Multiple Optima for Reinforcement Learningcited by 348
  6. 2018Reinforcement Learning for Solving the Vehicle Routing Problemcited by 333
  7. 2020Reinforcement Learning for Combinatorial Optimization: A Surveycited by 236
  8. 2019Neural Large Neighborhood Search for the Capacitated Vehicle Routing Problemcited by 117
  9. 2020Learning 2-opt Heuristics for the Traveling Salesman Problem via Deep Reinforcement Learningcited by 100
  10. 2022A Deep Reinforcement Learning Framework For Column Generationcited by 22
  11. 2013Reasoning About Beliefs and Actions Under Computational Resource Constraintscited by 18
  12. 2021Guidelines for the Computational Testing of Machine Learning approaches to Vehicle Routing Problemscited by 16
4 more
  1. 2022Learning to Solve Vehicle Routing Problems: A Surveycited by 16
  2. 2022Machine-learning-based arc selection for constrained shortest path problems in column generationcited by 13
  3. 2014Approximate Models and Robust Decisionscited by 10
  4. 2023Enhancing Column Generation by Reinforcement Learning-Based Hyper-Heuristic for Vehicle Routing and Scheduling Problemscited by 5

Built on by

Cited by year

Citing papers per year: 2025: 1.

1 paper.

  1. 2025Graph Reduction with Unsupervised Learning in Column Generation: A Routing Applicationcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2024Reinforcement Learning for Solving Stochastic Vehicle Routing Problem with Time Windows
  2. 2026A Curriculum-Based Deep Reinforcement Learning Framework for the Electric Vehicle Routing Problem
  3. 2025Accelerating Vehicle Routing via AI-Initialized Genetic Algorithms
  4. 2026Demand Acceptance using Reinforcement Learning for Dynamic Vehicle Routing Problem with Emission Quota
  5. 2026Vehicle-as-Prompt: A Unified Deep Reinforcement Learning Framework for Heterogeneous Fleet Vehicle Routing Problem
  6. 2026A Deep Reinforcement Learning Algorithm for the Vehicle Routing Problem with Stochastic Demands and Outsourcing
  7. 2024Deep Reinforcement Learning for Multi-Truck Vehicle Routing Problems with Multi-Leg Demand Routes
  8. 2026Vehicle routing problem using deep reinforcement learning - A case study about truck planning in the industry