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

2025/04/03 by Abdo Abouelrous, Laurens Bliek, Abouelrous, Abdo +7
Engineering · #Assembly Line Balancing Optimization #FOS: Computer and information sciences #Machine Learning (cs.LG) #Traffic control and management #Transportation and Mobility Innovations

paper · pdf · doi:10.48550/arxiv.2504.02383

openalex publication_date 2025/04/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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 within 9% in significantly shorter running times, up to over 300 times faster for instances with 100 customers.

Related

• Reinforcement Learning to Solve NP-hard Problems: an Application to the CVRP
• Reinforcement Learning for Solving the Vehicle Routing Problem
• Enhancing Column Generation by Reinforcement Learning-Based Hyper-Heuristic for Vehicle Routing and Scheduling Problems
• Machine-learning-based arc selection for constrained shortest path problems in column generation
• Graph Reduction with Unsupervised Learning in Column Generation: A Routing Application