Metaheuristic and Reinforcement Learning Techniques for Solving the Vehicle Routing Problem: A Literature Review

The Vehicle Routing Problem remains a pivotal challenge in combinatorial optimization, where the objective is to determine optimal routes for a fleet of vehicles serving geographically distributed customers under specific constraints. Over decades, a diverse spectrum of solution methodologies—spanning exact algorithms, heuristics, metaheuristics, and, more recently, machine learning—has emerged. This review critically examines the intersection of metaheuristics and reinforcement learning (RL), with a focus on hybrid frameworks that exploit their complementary advantages. While existing literature has predominantly explored the role of metaheuristics in fine-tuning RL parameters, the inverse—using RL to enhance metaheuristic search adaptivity, and real-time decision-making—remains markedly underexplored. This paper presents a bidirectional analysis of their integration: (1) how metaheuristics enhance RL-based solutions and (2) how reinforcement learning improves the efficiency and adaptability of metaheuristics. A systematic review of 279 relevant studies reveals that only 13.2% (37 papers) explicitly integrate both techniques, highlighting a critical research opportunity. We propose a classification framework that categorizes these hybrid approaches into three distinct types, analyzing their underlying principles, methodologies, and contributions. Furthermore, we discuss key challenges and future research avenues, offering insights into emerging trends and the potential of this combination to advance VRP optimization.