A concise guide to existing and emerging vehicle routing problem variants

Thibaut Vidal, Gilbert Laporte, Piotr Matl

Abstract

As global supply chains face increasing pressure from urbanization and e-commerce, the classic Vehicle Routing Problem (VRP) has evolved from a simple distance-minimization exercise into a complex, multi-faceted optimization challenge. This paper provides a high-level taxonomy and critical review of the "VRP explosion," categorizing how modern research integrates human factors, environmental sustainability, and strategic business decisions into routing algorithms. By moving beyond myopic cost metrics, the study outlines a roadmap for making routing plans more executable and "optimal" in real-world logistics environments.

Introduction

The classic Vehicle Routing Problem (VRP) asks a fundamental question: What is the optimal set of routes for a fleet of vehicles to deliver goods to a specific set of customers? For decades, the answer was defined by the shortest distance or the lowest operational cost. However, in practical applications, these mathematically "optimal" solutions often fail. Drivers may reject routes they perceive as unfair, dispatchers may find overlapping routes counter-intuitive, and environmental regulations may penalize the most direct paths.

This paper, published in 2020, addresses the widening gap between theoretical models and the complex reality of modern logistics. It argues that for routing to remain relevant, it must account for a broader spectrum of objectives, ranging from driver consistency and CO2 emissions to the strategic placement of warehouses.

A Three-Pillared Taxonomy of Modern VRPs

To organize the vast landscape of VRP research, the authors propose a framework based on three distinct pillars of evolution:

1. Emerging Objectives

Research is shifting from cost-centric to value-centric metrics. This includes:

  • Profitability: Utilizing the "logistic ratio" (cost per unit delivered) rather than just total distance.
  • Service Quality: Explicitly minimizing customer inconvenience.
  • Equity: Balancing workloads across a fleet to ensure driver satisfaction.
  • Externalities: Accounting for the social and environmental costs of routing, such as safety risks and carbon emissions.

2. Integrated Problems

Routing is increasingly used as an evaluation tool for higher-level tactical decisions. This integration includes Location-Routing (determining facility placement based on delivery efficiency), Inventory-Routing (synchronizing delivery schedules with stock levels), and Fleet Composition (optimizing the mix of electric and internal combustion vehicles).

3. Refined Problems

Modern models are increasing their "resolution" to capture fine-grained operational details. This involves accounting for time-dependent road congestion, urban turn restrictions, and the integration of new delivery modes, such as drone-assisted routing.

Key Insights: Beyond Distance Minimization

The "Logistic Ratio" and Long-Term Health

Pure cost minimization can lead to myopic operational behavior. The authors highlight that optimizing the ratio of routing cost to delivered quantity over a long horizon often leads to better long-term business health than simply cutting miles in the short term.

Visual Appeal and Intuition

Interestingly, the paper identifies "visual appeal" as a valid constraint. Drivers and dispatchers are more likely to trust and execute plans that look "simple." The research discusses mathematical surrogates like "compactness" and "separation" (ensuring routes do not overlap) to create plans that are intuitive and executable.

Consistency and Human Factors

In service-heavy industries like home healthcare, "person-oriented consistency"—where the same professional visits the same patient—is often more valuable than the marginal fuel savings achieved by reassigning routes. Furthermore, the paper notes a delicate balance in modeling uncertainty; while "robust" models protect against traffic or demand spikes, they can become overly risk-averse if not carefully calibrated.

The paper tracks the shift in how these problems are solved. While exact mathematical solvers are useful for smaller problems, metaheuristics have become the dominant tool for "rich" VRPs—variants with many overlapping constraints. These algorithms offer a superior trade-off between computational speed and solution quality for large-scale applications.

Key findings from the reviewed literature include:

  • Green VRPs: Research shows that minor increases in travel time can lead to disproportionately large reductions in fuel consumption and emissions.
  • Integration Benefits: Studies consistently demonstrate that jointly optimizing location and routing can save between 5% and 15% in total costs compared to solving those problems sequentially.

Benchmarking and Future Directions

The evolution of the VRP is also reflected in how research is validated. Traditional benchmarks (e.g., Solomon or Christofides) typically focus on a few hundred delivery points. However, the authors call for a "scaling up" to benchmarks involving thousands of visits to reflect the reality of modern mega-city logistics. They also emphasize the growing importance of reproducibility, noting that top-tier journals now frequently require code submissions to maintain experimental standards.

Looking forward, the authors suggest several frontiers:

  • The Physical Internet: Moving toward collaborative, open-logistics systems rather than optimizing private, siloed fleets.
  • Stochastic Correlation: Improving models to account for the fact that random events, like traffic jams, are often highly correlated rather than independent.
  • Emerging Tech: Developing robust models for autonomous vehicles and "synchromodality," where systems switch between drones, vans, and bikes in real-time.

Conclusion

The Vehicle Routing Problem is no longer just a math puzzle about the shortest path. It has become a strategic framework for sustainable, human-centric, and integrated supply chain management. As the field moves toward more collaborative and high-resolution models, the focus remains on bridging the gap between algorithmic elegance and real-world execution.

Summary updated

Abstract

Highlights • We present an overview of existing and emerging vehicle routing problem variants. • Emerging models consider different objectives and performance metrics. • They may integrate vehicle routing evaluations with other tactical decisions. • They also aim to capture fine-grained yet essential aspects of modern supply chains. • We pinpoint current shortcomings, recent successes, and emerging challenges. Abstract Vehicle routing problems have been the focus of extensive research over the past sixty years, driven by their economic importance and their theoretical interest. The diversity of applications has motivated the study of a myriad of problem variants with different attributes. In this article, we provide a concise overview of existing and emerging problem variants. Models are typically refined along three lines: considering more relevant objectives and performance metrics, integrating vehicle routing evaluations with other tactical decisions, and capturing fine-grained yet essential aspects of modern supply chains. We organize the main problem attributes within this structured framework. We discuss recent research directions and pinpoint current shortcomings, recent successes, and emerging challenges.
BibTeX
@article{vidal2020concise,
  author = {Thibaut Vidal and Gilbert Laporte and Piotr Matl},
  title = {{A concise guide to existing and emerging vehicle routing problem variants}},
  journal = {Eur. J. Oper. Res.},
  year = {2020},
  doi = {10.1016/j.ejor.2019.10.010},
}
Figure