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

arXiv: https://arxiv.org/abs/2504.02383 · HTML: https://mlsanity.com/paper/2504.02383/

## Key facts

- Cited by 1 papers 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.

## Placed in

- Deep reinforcement learning methods / [RL for games and combinatorial optimization](https://mlsanity.com/deeprl/rl-for-games-and-combinatorial-optimization/)

## Builds on (most cited first, 16 of 16)

- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [POMO: Policy Optimization with Multiple Optima for Reinforcement Learning](https://mlsanity.com/paper/2010.16011/) (2020)
- [Reinforcement Learning for Solving the Vehicle Routing Problem](https://mlsanity.com/paper/1802.04240/) (2018)
- [Reinforcement Learning for Combinatorial Optimization: A Survey](https://mlsanity.com/paper/2003.03600/) (2020)
- [Neural Large Neighborhood Search for the Capacitated Vehicle Routing Problem](https://mlsanity.com/paper/1911.09539/) (2019)
- [Learning 2-opt Heuristics for the Traveling Salesman Problem via Deep Reinforcement Learning](https://mlsanity.com/paper/2004.01608/) (2020)
- [A Deep Reinforcement Learning Framework For Column Generation](https://mlsanity.com/paper/2206.02568/) (2022)
- [Reasoning About Beliefs and Actions Under Computational Resource Constraints](https://mlsanity.com/paper/1304.2759/) (2013)
- [Guidelines for the Computational Testing of Machine Learning approaches to Vehicle Routing Problems](https://mlsanity.com/paper/2109.13983/) (2021)
- [Learning to Solve Vehicle Routing Problems: A Survey](https://mlsanity.com/paper/2205.02453/) (2022)
- [Machine-learning-based arc selection for constrained shortest path problems in column generation](https://mlsanity.com/paper/2201.02535/) (2022)
- [Approximate Models and Robust Decisions](https://mlsanity.com/paper/1402.6118/) (2014)
- [Enhancing Column Generation by Reinforcement Learning-Based Hyper-Heuristic for Vehicle Routing and Scheduling Problems](https://mlsanity.com/paper/2310.09686/) (2023)

## Built on by (most cited first, 1 of 1)

- [Graph Reduction with Unsupervised Learning in Column Generation: A Routing Application](https://mlsanity.com/paper/2504.08401/) (2025)

## 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.