  Vehicle Routing Problems (VRPs) in real-world applications often come with
various constraints, therefore bring additional computational challenges to
exact solution methods or heuristic search approaches. The recent idea to learn
heuristic move patterns from sample data has become increasingly promising to
reduce solution developing costs. However, using learning-based approaches to
address more types of constrained VRP remains a challenge. The difficulty lies
in controlling for constraint violations while searching for optimal solutions.
To overcome this challenge, we propose a Reinforcement Learning based method to
solve soft-constrained VRPs by incorporating the Lagrangian relaxation
technique and using constrained policy optimization. We apply the method on
three common types of VRPs, the Travelling Salesman Problem with Time Windows
(TSPTW), the Capacitated VRP (CVRP) and the Capacitated VRP with Time Windows
(CVRPTW), to show the generalizability of the proposed method. After comparing
to existing RL-based methods and open-source heuristic solvers, we demonstrate
its competitive performance in finding solutions with a good balance in travel
distance, constraint violations and inference speed.
