Application of Reinforcement Learning for Optimizing the Capacitated Vehicle Routing Problem

Abstract

This study proposes a reinforcement learning (RL) framework for solving the deterministic single-depot Capacitated Vehicle Routing Problem (CVRP). The Capacitated Vehicle Routing Problem is formulated as a Markov Decision Process and a REINFORCE agent with a linear-softmax policy, incorporating Clarke-Wright savings features, is trained as a proof-of-concept prior to future deep architectures such as Deep Q-Network and Proximal Policy Optimization. The proposed agent is trained and evaluated on three reproducible synthetic benchmark datasets comprising 20, 50, and 100 customers, and its performance is compared with two conventional construction methods, namely Nearest Neighbor and Clarke-Wright Savings. The results show that the learned policy consistently converges to a stable routing strategy and outperforms the Nearest Neighbor heuristic on the medium- and large-scale instances, reducing total travel distance by 8.3% and 10.0% respectively, while remaining within 13.8-20.8% of the Clarke-Wright benchmark across all scenarios. Inference is completed within milliseconds once training is finished, indicating that the learned policy can be reused across new routing instances without restarting the optimization process. These findings demonstrate that reinforcement learning is a promising and scalable alternative to conventional heuristic and metaheuristic approaches for capacitated routing problems, particularly in dynamic logistics environments that require rapid and adaptive decision making.