Source-linked AI summary
A concise guide to existing and emerging vehicle routing problem variants
Thibaut Vidal, Gilbert Laporte, Piotr Matl
TL;DR
Vehicle routing research must address a widening range of objectives, decisions, and supply-chain details beyond traditional route-cost minimization. This article synthesizes existing and emerging variants in a structured framework, finding that integrated, application-specific models create both practical relevance and unresolved complexity. It also identifies limits in model design, scenario generation, and experimental standards.
Problem
Traditional cost-focused VRP models do not capture all relevant practical criteria, while modern applications require links to strategic and tactical decisions and more detailed supply-chain representations.
Method
The article provides a concise, theme-based review organized around richer objectives and metrics, integrated business decisions, and fine-grained supply-chain aspects.
Results
The review organizes major VRP attributes and discusses research directions, current shortcomings, recent successes, and emerging challenges across these three lines.
Takeaways & Limitations
Vehicle routing research increasingly evaluates broader business decisions and must balance sophisticated models and data requirements with operational simplicity.
Takeaways & Limitations
The review is not exhaustive, and exact location-routing methods face challenges from enumerating many candidate facility subsets.
Abstract
from arXiv · showhide
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.
1 Introduction
Vehicle routing research has expanded because VRPs combine substantial economic importance with theoretical richness and increasingly diverse applications. This review organizes the field around emerging objectives, integration with strategic and tactical decisions, and evolving application needs.
- Motivation: VRPs have attracted six decades of intensive research because efficient routes offer transportation companies competitive advantages while providing rich combinatorial-optimization testbeds.Their structure generalizes the traveling salesman problem and supports research in optimization and heuristics.
- Research evolution: Since the early 2000s, VRP research has rapidly broadened beyond traditional attributes such as time windows, multiple depots, multiple periods, and heterogeneous fleets.The expansion reflects the diversity of application settings.
- Research evolution: Routing algorithms increasingly evaluate strategic and tactical decisions involving facility location, fleet sizing, production, and inventory management.Routing is therefore used not only to construct daily routes but also to assess higher-level plans.
- Review scope: The article offers a concise, theme-based review of problem attributes, applications, research directions, shortcomings, successes, and emerging challenges rather than exhaustive variant-by-variant coverage.It directs readers seeking detailed coverage of specific variants to established books and surveys.
- Review framework: The review classifies VRP extensions into richer objectives and metrics, integration with other business decisions, and finer-grained aspects of modern supply chains.Sections 2–4 discuss these classifications, followed by challenges and conclusions.
2 Emerging Objectives – Measuring as a Step Toward Optimizing
The review argues that routing models should measure more than cost because practical solutions also depend on profitability, service, equity, reliability, and externalities. It surveys these criteria while highlighting modeling risks, including poorly designed equity objectives and the mismatch between cost and emissions.
- Motivation: Cost optimization alone can produce routing solutions that are impractical, motivating additional objectives or constraints for application-relevant performance criteria.The review groups these criteria into profitability, service quality, equity, consistency, simplicity, reliability, and externalities.
- Profitability: Profitability objectives include routing cost, performance ratios, delivered quantity, customer-selection profits, and outsourcing decisions.The logistic ratio can reduce myopic behavior in inventory-routing settings, while profit variants maximize collected prizes minus routing costs.
- Service quality: Service-oriented VRPs replace or supplement total cost with arrival times, inconvenience measures, or minimum on-time-delivery levels.Examples include cumulative objectives for relief operations, ride-time criteria for passenger services, and service-level constraints for 3PL providers.
- Equity: Equity criteria address fair distributions of workload, resources, responsibilities, and benefits among internal or external stakeholders.Workload balance can support plan acceptance, employee morale, reduced overtime, and fewer resource bottlenecks.
- Equity: Non-monotonic equity functions such as workload range or standard deviation can perversely increase every route’s workload to satisfy an ill-posed objective.The review specifically warns that equity metrics must be modeled carefully for optimization.
- Externalities: Green VRPs model emissions because minimizing distance or time does not necessarily minimize fuel consumption or emissions, despite correlation between these quantities.Emission models may depend on load, time, fleet heterogeneity, and modal choice.
3 Integrated Problems – Routing as an Evaluation Tool
Routing models increasingly serve as evaluation tools for strategic and tactical decisions, linking operational routes with districting, facility location, fleet composition, inventory, and production. The review describes approximation, regression, scenario-based, and integrated optimization approaches, along with their computational and modeling challenges.
- Integrated decision-making: Routing evaluations help assess higher-level decisions such as districting, facility location, fleet composition, inventory, and production management.These decisions operate over longer horizons, whereas routing decisions are fundamentally operational and may change dynamically.
- Evaluation methods: Continuous approximation estimates routing costs geometrically, while regression models and fast stochastic or scenario-based algorithms provide alternative evaluation tools.Approximation formulas separate line-haul distance from routing costs within districts.
- Routing and districting: Districting applications must account for within-district routing costs while maintaining equity among routes assigned to different districts.Districts may also require contiguity, size, compactness, balance, homogeneity, fairness, and robustness constraints.
- Routing and facility location: Location-routing research evaluates facility decisions jointly with vehicle routes using continuous approximations, geometric catchment areas, Monte Carlo scenarios, or deterministic routing scenarios.Monte Carlo methods can create difficult scenario-generation and optimization problems, encouraging the use of canonical location-routing models.
- Routing and facility location: Exact algorithms for canonical location-routing problems face difficulty from enumerating many candidate facility subsets, whereas metaheuristics currently produce good solutions for large-scale instances.The canonical model is most relevant when delivery routes remain fixed for long periods or both decisions are operational.
- Fleet decisions: Fleet composition models address vehicle renewal, market changes, leasing, vehicle heterogeneity, alternative fuels, emissions restrictions, and crowdsourced delivery systems.The fleet size and mix VRP assumes unlimited vehicles of each type, whereas the heterogeneous fixed fleet VRP imposes maximum limits.
- Inventory and production management: Inventory-routing problems jointly optimize vehicle routes, delivery schedules, and quantities in vendor-managed inventory systems.Applications include maritime transport, perishables, and repositioning shared bikes or cars.
4 Refined Problems – Precise and Applicable Plans
Vehicle routing models increasingly capture fine-grained transportation, vehicle, driver, and customer-request attributes that affect feasibility and solution quality. These refinements create substantial modeling and methodological challenges, including synchronization, time dependence, loading feasibility, and regulatory compliance.
- Specificities of the Transportation Network: Fine-grained transportation-network attributes such as emissions, safety, tolls, turn restrictions, and congestion can require multiple paths and time-dependent routing models.Routing methods may need joint optimization of visit sequences and paths, while accurate travel-time queries on large networks remain challenging.
- Specificities of the Transportation Network: Two-echelon routing jointly optimizes routes at two levels while handling time constraints and synchronization between vehicles, facilities, and customers.Such structures are used in e-retail and city logistics, including transfers through cross-docking facilities or peripheral urban transfer points.
- Specificities of the Transportation Network: Turn restrictions, intersection delays, tolls, and limited parking materially affect urban logistics, yet parking considerations remain largely unrepresented in vehicle routing models.Turns and intersection delays are estimated to represent 30% of total urban transit time.
- Specificities of Drivers and Vehicles: Vehicle and driver refinements include heterogeneous fleets, alternative delivery modes, working-hours regulations, and coordinated rest or recharging decisions.Hours-of-service rules impose daily and weekly rest requirements and limits on driving and working time, making compliance difficult even for fixed visit sequences.
- Specificities of Customer Requests: Loading constraints must represent geometry, fragility, orientation, equilibrium, axle weights, and specialized truck configurations because feasibility checking can be NP-hard even for a fixed route.Trailer parking and retrieval can also create two-echelon variants.
5 Challenges and Prospects
Vehicle routing research has produced many successful applications but must continue adapting to differentiated, synchronized flows and emerging technologies. Key prospects include scalable, general algorithms, meaningful problem variants, and stronger reproducibility and benchmarking standards.
- Emerging applications: Future applications will increasingly differentiate, synchronize, and optimize multiple flows involving products, customers, and vehicles.The paper connects this challenge to technologies and business models such as autonomous vehicles, crowdsourced deliveries, and the physical Internet.
- Methodology: Developing heuristics and mathematical-programming algorithms that are simple, efficient, and general across many VRP variants remains crucial.Recent progress has relied on problem-structure analysis and decision-set decompositions, but further scaling is needed.
- Research standards: Research should prioritize VRP variants with genuine methodological or practical interest rather than arbitrary combinations of attributes.The paper identifies reproducibility, benchmarking, over-tuning, coding protocols, and hardware differences as unresolved concerns.