A Survey on the Vehicle Routing Problem and Its Variants

Kumar, Suresh Nanda; Panneerselvam, Ramasamy · 2012 · OpenAlex-citations

DOI: 10.4236/iim.2012.43010

archive: archived pipeline: cataloged verified

Get this paper ↗ (DOI — opens at the source; we link to it, we don't host it)

Summary

This paper presents a comprehensive literature review of the Vehicle Routing Problem (VRP) and its primary variants, specifically the Capacitated Vehicle Routing Problem (CVRP) and the Vehicle Routing Problem with Time Windows (VRPTW). The authors address the challenge of designing optimal routes for vehicle fleets to service customers under constraints such as vehicle capacity, time windows, and service demands. Because the VRP is classified as an NP-hard combinatorial optimization problem, exact optimization methods are often computationally prohibitive for large, real-world datasets. Consequently, the paper surveys the evolution of solution methodologies, focusing on the shift from exact algorithms to heuristic and meta-heuristic approaches that provide high-quality, near-optimal solutions within acceptable time limits. The review categorizes solution methods into exact algorithms, heuristics, meta-heuristics, and hybrid approaches. Exact methods discussed include branch-and-bound, branch-and-cut, and branch-and-price algorithms, as well as set partitioning formulations. The authors note that while these methods guarantee optimality, they are generally limited to small problem instances, typically involving fewer than 50 to 100 orders. For larger instances, the paper details heuristic methods, such as construction heuristics (e.g., cluster-first, route-second) and improvement heuristics (e.g., neighborhood search, ejection chains). Significant attention is given to meta-heuristics, including Tabu Search, Genetic Algorithms, Ant Colony Optimization, Simulated Annealing, and Evolutionary Algorithms. The text also covers dynamic variants, such as the Dynamic VRP (DVRP), where orders arrive in real-time, and specific constraints like soft time windows or limited fleet sizes. Key findings highlight the effectiveness of hybrid and meta-heuristic strategies in solving complex VRP variants. For instance, Genetic Algorithms are frequently hybridized with greedy heuristics or local searches to improve solution quality for VRPTW. Ant Colony Optimization is noted for its ability to handle dynamic routing and time-dependent travel times. The review also identifies advanced techniques like Large Neighbourhood Search and cooperative parallel meta-heuristics, which utilize solution warehouses to manage asynchronous search threads. The authors emphasize that modern research prioritizes approximate algorithms capable of handling large vehicle fleets and complex constraints, such as two-dimensional loading or multi-depot scenarios, where exact methods fail. The significance of this survey lies in its systematic classification of VRP solution techniques, providing a roadmap for researchers and practitioners in logistics and supply chain management. By documenting the limitations of exact methods and the advancements in heuristic and meta-heuristic approaches, the paper underscores the importance of computational efficiency in operational planning. It highlights that while exact methods remain valuable for small-scale problems, the field has largely moved toward sophisticated meta-heuristics and hybrid models to address the scalability and complexity of real-world distribution networks. This overview serves as a foundational reference for understanding the state-of-the-art in vehicle routing optimization as of 2012.

Provenance

The full processing record for this entry. Every stage of this paper's journey through the pipeline is logged — what ran, with which tool and model, how many attempts it took, and when it last completed.

Summary generated by qwen3.6-27b-prismaquant on 2026-06-26; verification: verified.

Topics

Ranked by relevance to this paper. Hover a topic for its definition.

• exposure measurement