Reinforcement learning for solving the pricing problem in column generation for routing

In this paper, we address the problem of Column Generation (CG) for routing problems 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 that 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 series of experiments comparing our approach with a Dynamic Programming (DP)-based heuristic for solving the PP, we demonstrate that the proposed method obtains solutions for the linear relaxation up to a reasonable objective gap and significantly faster than the DP-based heuristic for the PP. • We directly solve the pricing problem in column generation using a reinforcement learning agent in an end-to-end fashion. • We provide guidelines on generating duals training data for the pricing problem. • We consider C-VRPTW as a case study and compare our model with a renowned Dynamic Programming baseline. • Results showcase our model’s ability to solve the root node of C-VRPTW in shorter time with objective values in a reasonable gap. • We test our model’s generalization to larger instances and instances of an unseen distribution.