Metaheuristic and reinforcement learning techniques for solving the vehicle routing problem: A literature review

The vehicle routing problem (VRP) 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 such as capacity, time windows, and demand variability. Over the decades, a diverse spectrum of solution methodologies has emerged to address the NP-hard nature of this problem and its numerous real-world variants. This review critically examines the intersection of metaheuristics (MHs) and reinforcement learning (RL), with a particular focus on hybrid frameworks that exploit the complementary strengths of both paradigms: the broad exploratory power of MHs and the adaptive, experience-driven decision-making of RL. While existing literature has predominantly explored the role of metaheuristics in fine-tuning RL parameters and architectures, 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, examining (1) how metaheuristics enhance RL-based solutions and (2) how reinforcement learning improves the efficiency and adaptability of metaheuristics. Drawing on a systematic review of 279 relevant studies across seven major academic databases, we find that only 13.2% (37 papers) explicitly integrate both techniques into unified hybrid frameworks, rather than merely benchmarking one against the other. Based on this curated set of studies, we propose a novel classification framework that organizes hybrid MH-RL approaches into three distinct categories: MH-based RL/improving MHs, enhancing RL, and dynamic optimization, analyzing their underlying principles, mathematical formulations, methodologies, and contributions. Furthermore, we discuss key limitations of current methods, including high computational costs and standardization challenges, and outline future research avenues, offering insights into emerging trends and the potential of this hybridization to advance VRP optimization.