14 Finding Your VRP Flavor
A Taxonomy for Navigating the VRP Literature
VRP classification, taxonomy, problem-solving, optimization literature, solution selection, systematic approach
“If I have seen further, it is by standing on the shoulders of giants.” — Sir Isaac Newton
The VRP literature has exploded over the past 70 years, with thousands of papers proposing new variants, algorithms, and applications. Without a systematic way to classify and diagnose our specific routing problem, we risk getting lost in this vast sea of research, misapplying solutions, and wasting valuable time.
In professional settings, we operate under constant pressure to deliver value quickly. Starting from scratch might be intellectually satisfying, but it is rarely the most efficient path. The Vehicle Routing Problem literature represents decades of accumulated knowledge. By accurately classifying our problem within an established taxonomy, we can immediately access relevant case studies, proven algorithms, and implementation strategies. The alternative—treating every routing problem as entirely novel—wastes valuable time reinventing solutions that already exist.
14.1 The Birth of Vehicle Routing
The vehicle routing problem was first formulated by Dantzig and Ramser (1959) in their seminal paper “The Truck Dispatching Problem,” which addressed the optimization of gasoline delivery routes to service stations.
This paper introduced what we now call the basic VRP and proposed the first algorithmic solution using linear programming. Since then, the VRP has become a cornerstone of logistics research, inspiring thousands of papers and numerous real-world applications.
14.2 From Basic VRP to Real-World Complexity
While the classic VRP considers a simple scenario—a single depot, homogeneous vehicles, and known customer demands—real-world routing problems are rarely this straightforward. The number of requirements and constraints in practical applications is so vast that the term “Rich VRP” was coined to capture this complexity (Lahyani, Khemakhem, and Semet 2015).
Instead of creating ever-longer acronyms to capture every characteristic (e.g., HMD-TWPDS-VRP for heterogeneous fleet, multi-depot, with time windows, pickup and delivery, stochastic demand, and dynamic information), the concept of a Rich VRP acknowledges that real-world routing problems often involve many simultaneous characteristics that go beyond the simplified assumptions of basic VRP variants.
A Rich VRP consists of multiple, simultaneous constraints and objectives that reflect real operational conditions that go beyond the vanilla VRP assumptions (see Figure 14.1).
14.3 A Systematic Classification Framework
Given this complexity, how can we systematically classify and diagnose routing problems? Eksioglu, Vural, and Reisman (2009) developed a comprehensive taxonomy that classifies VRP variants across five major dimensions. This framework (see Figure 14.2) provides a structured approach to problem identification and enables practitioners to quickly locate relevant research and solution methods.
Hover over any node in the tree below to see detailed descriptions of each VRP characteristic. The taxonomy branches from left to right: main dimensions → subcategories → specific attributes.
14.4 Understanding the Five Dimensions
The taxonomy visualization above organizes VRP characteristics into five major dimensions. Each dimension addresses a different aspect of the routing problem, from research methodology to data quality. By systematically classifying your problem across these dimensions, you can identify relevant literature and solution approaches.
1. Type of Study
This dimension categorizes research approaches: theoretical contributions, applied methods (exact algorithms, heuristics, simulation, real-time solutions), implementation documentation, and literature reviews. For practitioners, this dimension helps identify whether to prioritize theoretical optimality or practical implementability.
2. Scenario Characteristics
These features describe the problem instance itself: Are customer locations known in advance or do they arrive dynamically? Can deliveries be split across multiple vehicles? Are service times deterministic or uncertain? Must strict time windows be satisfied? These characteristics fundamentally shape solution complexity and appropriate methodologies.
3. Physical Characteristics
This dimension captures the tangible constraints of the routing environment: network structure (directed vs. undirected), customer positioning (node-based vs. arc-based), geographic distribution patterns, depot configuration, fleet composition, and capacity limitations. This dimension reveals how urban last-mile delivery differs fundamentally from rural service routing.
4. Information Characteristics
In an increasingly connected world, information dynamics have become critical. Is all information known upfront (static) or does it evolve over time (dynamic)? Is data deterministic, stochastic, or only revealed in real-time? Is information processing centralized or distributed? These factors determine whether classical optimization or dynamic, adaptive approaches are required.
5. Data Characteristics
Finally, this dimension addresses the empirical foundation: Is the problem studied using real-world data, synthetic benchmarks, or both? This matters for validation and practical applicability of proposed solutions.
14.5 Conclusion
Don’t reinvent the wheel.
The VRP taxonomy provides a systematic framework for diagnosing routing problems and identifying relevant research and solution approaches. By accurately classifying your problem across these five dimensions, you can quickly access proven algorithms, case studies, benchmarks, and implementation strategies that align with your requirements.
KISS (Keep It Simple,
Stupidto Start) 2
If you are new to VRP, start with the simplest variant that captures your core problem characteristics and iterate from there. The taxonomy helps you understand which assumptions and constraints are most critical, allowing you to build complexity incrementally while leveraging existing knowledge.
14.6 References
Image by Geoffrey De Smet.↩︎
The KISS principle was originally coined by the U.S. Navy in 1960 and stands for “Keep It Simple, Stupid.” It emphasizes the importance of simplicity in design and problem-solving, advocating for straightforward solutions that avoid unnecessary complexity.↩︎