In classical vehicle routing problems (VRP), vehicles are treated as interchangeable commodities. This homogeneous fleet assumption simplifies the combinatorial search space: if every truck has the exact same capacity, speed, and fuel constraint, a solver only needs to decide which customer to visit next, not which vehicle is capable of making the trip.
However, real-world logistics operate on mixed fleets. As Jingwen Li et al. point out, assuming identical vehicles prevents solvers from capturing real-world logistics where specifications vary widely. When optimization models ignore these differences, they produce schedules that are mathematically optimal on paper but operationally unfeasible or highly inefficient in practice.
The Dimensions of Heterogeneity
To understand why the homogeneous assumption fails, we must look at how fleet diversity shatters the mathematical symmetries relied upon by traditional solvers. Heterogeneity manifests across several distinct physical and operational dimensions:
1. Capacity and Space Asymmetry
In public transit and paratransit, vehicles have highly diverse internal configurations. Amutheezan Sivagnanam et al. note that ignoring uniform passenger capacity constraints can lead to assigning standard buses to high-demand lines that strictly require articulated vehicles. Furthermore, in specialized transit, Sophie Pavia et al. demonstrate that capacity tracking must dynamically account for physical reconfigurations, such as the varying space required for wheelchairs versus ambulatory riders.
2. Kinematics and Speed
Traditional models assume uniform travel times across a network. However, Inge Li Gørtz et al. show that when a fleet contains vehicles with non-uniform speeds, standard tour-splitting techniques break down. Routes must be optimized based on the specific speed capabilities of each vehicle to minimize the arrival time of the last returning unit.
3. Energy, Range, and Fuel Constraints
The transition to electric vehicles (EVs) introduces highly non-linear constraints. John Lygeros et al. emphasize that assuming identical battery capacities ignores how diverse battery constraints influence individual driver strategies and collective charging queues. Furthermore, as shown by Justin Luke et al., optimization frameworks must jointly co-design infrastructure and routing to handle heterogeneous fleets with varying battery capacities, charging speeds, and energy efficiencies.
Why Homogeneous Solvers Fail: The Intuition
In a homogeneous fleet, the cost function is symmetric with respect to vehicle assignment. Swapping the entire route of Vehicle A with Vehicle B changes nothing.
In a heterogeneous fleet, this symmetry is completely shattered. A route that is highly efficient for a small electric van might be physically impossible for a heavy diesel truck due to urban low-emission zones, or impossible for a larger vehicle due to tight urban turns, as discussed by U. Breunig et al..
Homogeneous Fleet (Symmetric Costs):
[Vehicle A: Cap 10] ---> Route 1 (Cost: $50)
[Vehicle B: Cap 10] ---> Route 2 (Cost: $40)
*Swapping routes preserves total cost ($90)*
Heterogeneous Fleet (Asymmetric Costs):
[EV Van: Cap 5] ---> Route 1 (Cost: $30)
[Diesel Truck: Cap 20] -> Route 2 (Cost: $70)
*Swapping routes is impossible or drastically changes costs*
When we force a homogeneous assumption onto a heterogeneous reality, the solver lacks the vocabulary to make trade-offs between vehicle capabilities. For instance, it cannot decide whether to send a faster, low-capacity vehicle or a slower, high-capacity vehicle to a distant cluster of customers.
Algorithmic Strategies for Breaking the Homogeneity Assumption
To handle the exploded search space of heterogeneous routing, researchers have shifted from rigid linear programming to adaptive, learning-based architectures and hybrid heuristics.
Dual-Decoder Attention Mechanisms
To solve the simultaneous problem of choosing which vehicle and which node to visit, Jingwen Li et al. designed a deep reinforcement learning framework utilizing a specialized dual-decoder attention mechanism. Instead of treating vehicles as interchangeable, the first decoder selects an appropriate vehicle based on its current state (remaining capacity, location, speed), and the second decoder selects the next customer node. This allows the neural network to evaluate vehicle-to-node compatibility dynamically at each step.
Graph Neural Networks and Space Pruning
In complex joint scheduling problems, Jiawei Lu et al. combined traditional Column Generation with Graph Neural Networks (GNNs). The GNN is trained to prune the massive search space of potential routes by filtering out paths that are structurally incompatible with specific vehicle capacities or specialized equipment before the heavy mathematical optimization begins.
The Linear-Time Partitioning Challenge
Even exact algorithmic subroutines face hurdles when homogeneity is discarded. Thibaut Vidal notes that while linear-time partitioning methods (like the Split algorithm) drastically accelerate homogeneous VRP solvers, adapting these techniques to handle heterogeneous fleets or multiple trips per vehicle remains a significant algorithmic challenge because the underlying shortest-path subproblems lose their simple structural properties.
Key Foundational Work
Transport Logistics Planning with Service-Level Constraints (2004) — contributed 1 concept elements to this direction.
Transport Scheduling with Service-Level Constraints - Complexity and Algorithms (2004) — contributed 1 concept elements to this direction.