Vehicle Routing Problem
Combinatorial Optimization
State of the Art
From "XL" scale metaheuristics to Agentic AI designers. A comprehensive analysis of the vehicle routing landscape in 2024–2025.
Paradigm Shift: Hybridization
The boundary between "Learning" and "Searching" has eroded. The SOTA is no longer pure OR or pure AI, but a symbiotic fusion.
HGS (Genetic Search)
Undisputed champion for quality. Uses "Giant Tour" representation and "Catastrophe" diversity management.
Agentic AI
LLMs don't solve the route; they write the solver code. Enables "Zero-Shot" custom constraints.
Scaling to "XL" (10k Nodes)
Optimality Gap (%)While Exact methods break and NCO struggles at scale, Hybrid Genetic Search (PyVRP) maintains <1% gap even at 10,000 nodes.
The Algorithmic Core
The mechanics powering the 2025 leaderboard.
Hybrid Genetic Search
The King- ▸ Giant Tour: Ignores capacity initially to traverse search space.
- ▸ Split Algorithm: Uses shortest-path on DAG to segment tour into valid routes.
- ▸ PyVRP: The SOTA implementation bridging C++ speed with Python ease.
Neural Optimization
The Frontier- ▸ Diffusion Models: Generates entire solution structure simultaneously (non-autoregressive).
- ▸ Generalization: Uses "Multi-Expert" modules to handle varying constraint tightness.
Exact Methods (BCP)
The Proof- ▸ Neural Pricing: Uses ML to accelerate column generation.
- ▸ RouteOpt: Modular solver proving optimality for 360-400 node instances.
1. Interpreter Agent
Reads natural language: "Drivers need a 15m break every 3h."
2. Coder Agent
solver.Add(drive_time <= 180)
3. Refiner Agent
Tests synthetic cases. Debugs errors. Optimizes params.
The Agentic Shift
In 2025, we stop asking AI to "solve" the problem and start asking it to "write the solver." Frameworks like AFL can automatically generate valid code for 91.67% of custom VRP variants, democratizing access to complex optimization.
Electric Vehicle Routing
Physics dictates the algorithm. Solvers must now handle non-linear charging curves and battery degradation.
Practitioner's Guide
Offline Planning
Quality First
- Goal: Save 1-2% fleet cost
- Time: Minutes/Hours
- Tool: PyVRP
Real-Time Dispatch
Speed First
- Goal: Instant Assignment
- Time: Milliseconds
- Tool: VROOM (C++)
Enterprise Scale
Size First
- Goal: 30,000+ Nodes
- Tech: List Variables
- Tool: Hexaly
Complex Logic
Flexibility First
- Goal: Weird Constraints
- Tech: CP / Agentic AI
- Tool: OR-Tools / AFL