Introduction
Most routing software was built for fleets where every vehicle is the same. But most real fleets aren't.
Fleet managers running mixed assets — cargo vans alongside box trucks, motorcycles mixed with refrigerated units — face a routing challenge that standard VRP solvers weren't designed to handle. When the optimizer treats all vehicles as identical, the output looks clean on paper but fails in the field.
The consequences are predictable: oversized trucks dispatched on routes a van could cover, temperature-controlled assets running dry-goods runs, smaller vehicles racking up excess mileage to absorb demand that a larger vehicle should have taken.
According to ATRI's 2025 analysis, the average marginal cost of operating a truck reached $2.260 per mile in 2024, with empty miles rising to 16.7 percent of total miles traveled. In a mixed fleet, poor vehicle-to-route matching compounds these figures .
This guide breaks down HFVRP end-to-end — what it is, how solvers handle it, which variants show up in practice, and where it actually pays off.
TL;DR
- HFVRP extends classic VRP to fleets where vehicles differ in capacity, cost, speed, or cargo type — making vehicle selection itself a decision variable
- It jointly optimizes vehicle assignment and stop sequencing to minimize total fixed plus variable costs
- Key variants include Fleet Size and Mix VRP, HFVRP with Time Windows, Open HFVRP, and Multi-Depot HFVRP
- Exact solvers hit limits fast — metaheuristics and ML-augmented approaches are required at real-world scale
- If vehicle types in your fleet have similar cost and capacity profiles, standard capacitated VRP may be sufficient
What Is the Heterogeneous Fleet Vehicle Routing Problem?
HFVRP is a combinatorial optimization problem where a fleet of vehicles must serve all customers at minimum total routing cost. What makes it "heterogeneous" is that vehicles differ across at least one attribute: capacity, fixed cost per route, variable cost per kilometer, speed, or cargo compatibility — and each vehicle starts from one or more depots.
What the Problem Is Designed to Solve
The optimizer must accomplish three things at once:
- Assign each customer to exactly one vehicle
- Select the most cost-effective vehicle type for each route
- Sequence stops on each route to minimize distance or time
In classic (homogeneous) VRP, all vehicles share identical attributes, so only sequencing is optimized. In HFVRP, vehicle selection becomes a decision variable alongside sequencing — adding a combinatorial layer that makes the problem substantially harder.
The Two Foundational Sub-Types
| Sub-Type | Fleet Composition | What's Optimized |
|---|---|---|
| Fleet Size and Mix VRP (FSMVRP) | Not predetermined — quantities per vehicle type are decided by solver | Vehicle mix, assignment, and routing |
| Fixed Fleet HFVRP | Predetermined — specific vehicles already owned or contracted | Assignment and routing only |
Koc et al.'s comprehensive 2016 review of thirty years of heterogeneous vehicle routing formalizes this classification, distinguishing unlimited-availability FSMVRP from fixed-fleet variants where the available fleet is set in advance.
HFVRP sits within the broader VRP family alongside VRPTW (time windows), CVRP (capacitated), and multi-depot VRP. Real-world deployments routinely stack HFVRP with several of these constraint layers simultaneously, which is why production solvers need to handle compound constraint sets, not just one dimension at a time.
Why Fleet Heterogeneity Complicates Route Optimization
Homogeneous fleets are relatively straightforward to optimize — every vehicle shares the same cost structure, capacity, and access rules. Heterogeneous fleets don't offer that simplicity. Every customer stop requires evaluating feasibility and cost-efficiency across multiple vehicle types, and those decisions interact across all routes at once.
The Operational Cost of Getting It Wrong
Poor vehicle-to-route matching produces predictable failures:
- Large trucks dispatched on routes that only needed a cargo van, paying high fixed costs for underutilized capacity
- Refrigerated units running dry-goods deliveries, wasting specialized asset cost
- High-capacity vehicles running at 40% load while smaller vehicles are overcommitted and incurring excess mileage
- Violations of road access rules — weight limits, height restrictions, low-emission zones — because the optimizer didn't distinguish vehicle types
Why Generic VRP Solvers Fail Here
A routing system that treats all vehicles with a single profile will produce routes that look optimized but aren't. It ignores per-vehicle fixed costs (a leased refrigerated truck costs more per route than a cargo van regardless of distance), misses vehicle-specific access restrictions, and can't evaluate whether load utilization makes a large vehicle economical on a given route.
The stop sequencing may be efficient. The vehicle assignment almost certainly isn't — and that's where the real cost lives.
How HFVRP Works: Inputs, Constraints, and Optimization Logic
Required Inputs
A properly formulated HFVRP requires:
- Customer locations, demand quantities, cargo type, and site access requirements
- Per-vehicle attributes: capacity, fixed/variable costs, speed profile, and cargo compatibility
- Depot locations and operating hours (single or multi-depot)
- Active constraints: time windows, driver shift limits, road restrictions, bridge weight limits, load sequencing rules
The richer the constraint set, the more executable the output. Simplifying vehicle attributes to fit a generic solver produces cleaner math but worse real-world routes.
The Objective Function
The standard HFVRP objective minimizes:
Total Cost = Σ (Fixed costs per vehicle deployed) + Σ (Variable costs across all routes)
The balance between these components differs by vehicle type — a semi-truck has high fixed cost and low per-km cost over long distances, while a motorcycle has negligible fixed cost but limited range. That cost asymmetry is what makes vehicle selection genuinely complex — the cheapest vehicle per stop isn't always the cheapest vehicle per route.
Step 1: Define Vehicles and Constraints
Translating that objective into executable routes starts with vehicle configuration. In NextBillion.ai's Route Optimization API, planners configure per-vehicle:
- Capacity (weight, volume, item count — multi-dimensional)
- Fixed cost per route and variable cost parameters
- Vehicle mode and dimensions (truck height, width, axle load, weight)
- Cargo type and incompatible load type rules
- Maximum tasks, maximum travel cost, and shift/break parameters
The platform enforces 50+ hard and soft constraints independently per vehicle — covering truck routing restrictions, hazmat rules, multi-compartment load assignments, and time-window compliance — without forcing planners to simplify real fleet profiles to fit a generic template.
Step 2: Assign Customers to Vehicle Types and Routes
The solver groups customers into candidate routes and evaluates which vehicle type is feasible and lowest-cost for each grouping, accounting for:
- Whether vehicle capacity covers the route's total demand
- Geographic clustering to reduce unnecessary travel distance
- Cargo compatibility and site access restrictions
- Load utilization — avoiding underloaded expensive vehicles and overextended smaller ones
Step 3: Sequence and Optimize Each Route
Once vehicle-to-customer assignments are set, each route is sequenced to minimize distance or time. This step interacts directly with vehicle speed profiles and time-window constraints. Swap the vehicle on a route and the entire stop sequence may need to be rebuilt — which is why assignment and sequencing must be solved together, not in isolation. Treating them as separate steps often produces routes that look optimal on paper but violate time windows or capacity limits in practice.
Key Variants and Real-World Applications of HFVRP
The Most Operationally Relevant Variants
HFVRP with Time Windows (HFVRPTW): Each customer has a fixed delivery window the vehicle must honor. This variant dominates last-mile and food delivery scenarios. NextBillion.ai's API handles per-customer delivery windows alongside vehicle-type-specific constraints simultaneously — making it the most common real-world HFVRP configuration.
Open HFVRP: Vehicles don't return to the depot after completing routes. Common in one-way field service deployments where technicians start at home and finish at the last job site.
Multi-Depot HFVRP: Vehicles originate from different facilities and are optimized simultaneously across a shared customer set. NextBillion.ai supports this through parallel optimization within depot clusters, reducing empty miles and balancing workload across facilities.
Industry Applications
| Industry | Fleet Mix | Key Constraint Layer |
|---|---|---|
| Last-mile e-commerce | Cargo vans + motorcycles | Time windows, urban access rules |
| Waste collection | Compactor trucks + smaller vehicles for narrow streets | Multiple trips, compartments, emissions |
| Field service | Service vans with different tool loadouts | Job-type compatibility, technician skills |
| Freight distribution | Semi-trucks for trunk legs + smaller vehicles for final-mile | Cross-dock points, multi-depot, weight limits |
Academic evidence supports heterogeneous fleet modeling for solid-waste collection, where objectives include transportation cost, emissions, and fair load allocation across vehicle types — not just distance minimization.
The Fleet Size and Mix Variant
FSMVRP is the most strategically valuable variant because it answers not just "how to route" but "how many of each vehicle type to deploy." This makes it directly applicable to fleet acquisition decisions and owned-versus-contracted asset trade-offs.
NextBillion.ai's Route Optimization API supports an iterative approach for FSMVRP scenarios: planners start with an initial vehicle count and narrow down to the minimum vehicles needed to meet demand at the lowest total cost.
This is especially useful when fleet composition isn't fixed by ownership. The solver identifies the point where adding more vehicles stops reducing total cost — giving planners a clear signal for when the fleet is right-sized.
Common Algorithms Used to Solve HFVRP
Exact Methods: Theoretically Optimal, Practically Limited
Integer programming and branch-and-price methods guarantee the best solution — but computation time grows exponentially with problem size. Sahin et al.'s 2022 branch-and-price algorithm for multi-depot heterogeneous fleet VRP with time windows solved instances with up to 40 customers, 3 depots, and 2 vehicle types. Beyond that scale, exact methods become computationally impractical for production use.
Metaheuristics for Real-World Scale
| Algorithm | How It Works | HFVRP Evidence |
|---|---|---|
| Genetic Algorithm | Evolutionary search across solution space | Prins (2009) matched best-known solutions on 14 of 20 benchmark problems |
| Tabu Search | Iterative improvement with memory to avoid revisiting recent solutions | Consistently strong on FSMVRP benchmarks |
| Simulated Annealing | Probabilistic acceptance of worse solutions to escape local optima | Yu and Lin (2021) applied to HFVRP with cross-docks |
| Clarke-Wright Savings | Fast construction heuristic that merges routes when savings exceed threshold | Standard starting point; often used to seed other methods |
Adaptive iterated local search has shown strong results at scale — Maximo et al. (2022) reported outperforming state-of-the-art metaheuristics on 87% of benchmark instances with up to 360 customers.
ML-Augmented Approaches
Machine learning is now being layered on top of classical metaheuristics to improve solver performance at scale. Reinforcement learning-based hyper-heuristics — where a learned policy dynamically selects among low-level metaheuristics — have outperformed both MILP and standalone metaheuristics on large-scale benchmark instances with 200+ customers.
For most operations teams, building and maintaining this solver stack in-house isn't realistic. NextBillion.ai's route optimization API abstracts this complexity: submit a fleet configuration and stop list, and the engine returns per-route vehicle assignments, stop sequences, estimated costs, and load utilization data at each stop — no solver development required.
Misconceptions About HFVRP and When It May Not Be the Right Fit
Misconception: Any Route Optimizer Handles Heterogeneous Fleets
Many routing systems model all vehicles with a single profile. The output appears optimized but ignores per-vehicle cost differences and vehicle-specific constraints: the solver is treating a heterogeneous fleet as homogeneous.
Before assuming your tool handles HFVRP, confirm it meets both of these criteria:
- Accepts per-vehicle cost attributes (fixed cost, variable cost per km)
- Enforces vehicle-specific constraints independently for each vehicle in the same optimization run
When HFVRP Is Unnecessary Overhead
HFVRP modeling adds complexity that only pays off when vehicle heterogeneity meaningfully changes cost or feasibility. Skip it if:
- All vehicles carry the same cargo type and serve the same customer segments
- Capacity and cost differences between vehicle types are small enough to ignore
- Vehicle type is pre-assigned by territory or contract, leaving no actual selection decision for the solver
In these cases, standard capacitated VRP will solve faster and produce equally actionable results.
Signals You're Applying HFVRP by Default
- Using Fleet Size and Mix VRP logic when fleet composition is fixed by ownership (the solver is optimizing a decision that doesn't actually exist)
- Applying vehicle-type selection constraints on fleets where vehicle assignment is already determined before routing runs
- Adding constraint layers that don't correspond to real operational rules — bridge weight limits for vehicles that never approach those roads, for example
Applying HFVRP by default increases computation time without improving solution quality. Match the model to the actual decision your operation needs to make.
Frequently Asked Questions
What is the difference between homogeneous and heterogeneous fleet VRP?
In homogeneous VRP, all vehicles share identical capacity, cost, and speed attributes, so only stop sequencing is optimized. In heterogeneous fleet VRP, vehicles differ in at least one attribute, making vehicle selection itself part of the optimization problem alongside sequencing.
What are the main variants of the heterogeneous fleet vehicle routing problem?
The core variants are: Fixed Fleet HFVRP (fleet composition given, only assignment and routing optimized), Fleet Size and Mix VRP (vehicle quantities are also a decision), HFVRP with Time Windows, Open HFVRP (vehicles don't return to depot), and Multi-Depot HFVRP.
What algorithms are commonly used to solve HFVRP?
Exact methods like integer programming and branch-and-price work for small instances (tens of customers). For real-world fleet sizes, metaheuristics — genetic algorithms, tabu search, simulated annealing, and Clarke-Wright savings — are standard. Production systems increasingly layer in hybrid or ML-augmented solvers to handle larger, more constrained problems faster.
How does fleet heterogeneity affect total routing cost?
Mismatching vehicle types to routes inflates costs through underutilized large vehicles carrying unnecessary fixed costs, excess mileage from range-limited small vehicles, and a higher route count that proper consolidation would eliminate. Proper HFVRP optimization minimizes combined fixed and variable cost across the entire fleet.
Can HFVRP handle time windows and multi-depot constraints simultaneously?
Yes. Most real enterprise logistics problems require exactly this combination: HFVRPTW with multi-depot structure. Complexity rises with each additional constraint layer, which is why production systems rely on metaheuristics rather than exact solvers for these configurations.
What industries benefit most from HFVRP?
Last-mile e-commerce delivery, waste collection, field service dispatch, freight distribution, and food delivery are the primary industries. Any operation running vehicles with meaningfully different capacity, cost, or access profiles stands to benefit from HFVRP optimization.
