MINIMIZING ENERGY USAGE FOR CAPACITATED VEHICLE ROUTING PROBLEM USING POLICY GRADIENT (RL) AND COMPARING SOLUTIONS WITH GUROBI

Abstract

The Vehicle Routing Problem (VRP) is a well-known optimization challenge with practical applications in various areas, including delivery route optimization, transportation logistics, and mobile resource allocation. This work specifically focuses on the capacitated vehicle routing problem (CVRP), where each customer has a demand that must be met by vehicles with capacity constraints. The goal is to minimize the total cost or distance traveled by vehicles while ensuring that each customer’s demand is satisfied and vehicles stay within their capacity limits. Traditional methods for solving CVRP typically use heuristics and mathematical programming techniques. However, these approaches can struggle with large-scale instances and dynamic environments. In recent years, reinforcement learning (RL) has emerged as a promising solution for complex optimization problems. In this study, we use RL techniques to address the CVRP. Our approach harnesses the power of deep RL algorithms, specifically combining deep neural networks and actor-critic methods, to learn effective policies for route planning and optimization. By framing the CVRP as a Markov Decision Process, we develop an RL agent that learns to make sequential decisions regarding vehicle movements and load allocations. We evaluate our proposed RL framework on a set of benchmark VRP instances, comparing its performance against the state-of-the-art solver Gurobi. The experimental results demonstrate that our approach achieves competitive solution quality and computational efficiency, especially in larger problems. Additionally, we explore the robustness and generalization capability of the learned policies by assessing their performance on unseen problem instances and assessing the performance of RL(trained for larger problems) on smaller problem instances. Overall, our work underscores the potential of reinforcement learning as a promising methodology for solving the Vehicle Routing Problem. Through the integration of deep RL algorithms and problem-specific insights, we illustrate that RL can provide efficient and effective solutions to this challenging optimization problem, opening avenues for further advancements in the field of transportation logistics and route planning.