The Vehicle Routing Problem (VRP) is a mathematical problem that aims at determining the best possible routes that a number of vehicles can take to visit a number of locations and return to the depot with the least possible travel distance and time while satisfying certain constraints. In this paper, we propose a Hybrid Genetic Algorithm with Ruin and Recreate and Memetic Improvement (HGARM) as an optimization technique to tackle VRP. This hybrid method is a combination of Genetic Algorithm (GA), Ruin and Recreate Algorithm (RR), Memetic Algorithm (MA). This hybrid method is then combined with Reinforcement Learning (RL)–HGARM-RL. The primary goal of the study is to find the best path for all the available cities with constraints on distance and time. The algorithms use several techniques such as crossover, mutation, local search, and exploration–exploitation trade-off to refine the solution by generating a new population in successive iterations. In addition, integrating the hybrid approach with RL allows for the dynamic tuning of the ruin factor, a control parameter that governs the level of solution diversification. The experimental findings show that the proposed hybrid approach is indeed capable of generating good solutions for the vehicle routing problem that can be useful in practical scenarios in the area of logistics and transportation.