A Comparative Analysis of Reinforcement Learning’s Effectiveness in Solving the Capacitated Vehicle Routing Problem Against Traditional Methods
Venkatesh Duraiarasan, DA24C021
Capacitated Vehicle Routing Problem (CVRP) is a generalization of the Traveling Salesman Problem (TSP), which is also NP-hard. While the TSP seeks the shortest route for a single salesperson to visit all cities, the CVRP extends this by adding vehicles with limited capacity that must satisfy customer demands. This addition of capacity constraints introduces further complexity.Consequently, exact methods often fail to find feasible solutions for large CVRP instances within a reasonable timeframe. While metaheuristics offer practical alternatives for larger problems, they only provide approximate solutions. Given the limitations of existing methods, this project investigates Reinforcement Learning (RL) as a potential alternative for solving CVRP and compares its performance to established methods.
The goal of this project is to conduct a comparative analysis of RL's performance and effectiveness in solving the CVRP against traditional methods which includes exact methods and metaheuristics. The specific objectives are: • To evaluate the effectiveness of RL algorithms in finding near-optimal solutions to the CVRP compared to traditional methods, as measured by solution quality and optimality gap. • To assess the computational efficiency of RL algorithms in solving CVRP instances of varying sizes and complexities, as measured by inference time and training time • To identify the strengths and limitations of RL and traditional methods in the context of CVRP