Abstract: The capacitated vehicle routing problem (CVRP) involves distributing (identical) items from a depot to a set of demand locations, using a single capacitated vehicle. We study a generalization of this problem to the setting of multiple vehicles having non-uniform speeds (that we call Heterogenous CVRP), and present a constant-factor approximation algorithm. The technical heart of our result lies in achieving a constant approximation to the following TSP variant (called Heterogenous TSP). Given a metric denoting distances between vertices, a depot $r$ containing $k$ vehicles with possibly different speeds, the goal is to find a tour for each vehicle (starting and ending at $r$), so that every vertex is covered in some tour and the maximum completion time is minimized. This problem is precisely Heterogenous CVRP when vehicles are uncapacitated. The presence of non-uniform speeds introduces difficulties for employing standard tour-splitting techniques. In order to get a better understanding of this technique in our context, we appeal to ideas from the 2-approximation for scheduling in parallel machine of Lenstra et al.. This motivates the introduction of a new approximate MST construction called Level-Prim, which is related to Light Approximate Shortest-path Trees. The last component of our algorithm involves partitioning the Level-Prim tree and matching the resulting parts to vehicles. This decomposition is more subtle than usual since now we need to enforce correlation between the size of the parts and their distances to the depot.
Introduction
The classic Capacitated Vehicle Routing Problem (CVRP) is a fundamental challenge in logistics: how can a fleet deliver items to various locations while minimizing total distance, given fixed carrying capacities? In real-world scenarios, fleets are often heterogeneous, comprising vehicles with vastly different speeds—such as a mix of bicycles, scooters, and vans. This paper addresses the Heterogeneous CVRP (HetCVRP), where the objective is to minimize the makespan, or the time the last vehicle returns to the depot.
Standard "tour-splitting" techniques, which divide a single long route into segments for multiple vehicles, fail in the heterogeneous setting. A vehicle's speed dictates not just how much it can carry, but how far it can travel from the depot within a time limit. Prior to this work, solutions for HetCVRP only offered logarithmic ($O(\log n)$) approximation ratios.
Methodology: From TSP to CVRP
The authors first solve a simplified version without capacity constraints, termed Heterogeneous TSP (HetTSP), using three primary technical pillars:
- Level-Prim Trees: A novel variation of Prim’s algorithm that groups vertices into "levels" based on their distance from the depot (using powers of two). It ensures all nodes in a closer level are connected before moving to the next, creating a "level-monotonic" tree structure.
- Assignable Tree Decomposition: The algorithm identifies subtrees that are "assignable"—meaning they are small enough and close enough to the depot to be handled by specific vehicles in the fleet.
- Scheduling Theory Integration: To match vehicles to these subtrees, the authors adapt the Lenstra-Shmoys-Tardos algorithm for scheduling on unrelated parallel machines, converting a fractional assignment of work into a concrete routing plan.
Finally, the full HetCVRP is reduced to HetTSP by modifying the distance metric to account for the multiple trips required when a vehicle reaches its capacity limit.
Key Insights: The Need for Structured Trees
A critical realization in this work is that in heterogeneous routing, the size of a task and its distance from the depot must be strictly correlated. A slow vehicle can only handle a small task if it is very close to the depot; a fast vehicle is required for larger tasks or those further away.
While standard tools like Minimum Spanning Trees (MST) or Light Approximate Shortest-path Trees (LAST) balance total edge weight and distance from a root, they lack the specific structure required for this problem. Specifically, they can produce "dangling" nodes that are far away in the tree structure but physically close to the depot, complicating the assignment process.
Level-Prim is specifically designed to prevent these structural issues, ensuring that the decomposition into subtrees remains assignable to a fleet with varying speeds.
Results and Theoretical Impact
The paper establishes the first constant-factor approximation for both HetCVRP and HetTSP. Specifically, they derive a $(4\alpha + 2\beta)$-approximation (where $\alpha=6$ and $\beta=40$). Although these constants are theoretically large, they represent a breakthrough by providing a bound that does not grow with the number of delivery locations ($n$).
Additionally, the authors bound the "preemption gap"—the efficiency difference between a strategy allowing items to be transferred between vehicles versus one where a single vehicle handles an item from start to finish.
Limitations and Future Work
Despite its theoretical significance, the current framework has limitations:
- Single Depot: The algorithm assumes all vehicles start and end at one central location. Multi-depot scenarios would require new methods for defining levels.
- Uniform Capacities: The model assumes all vehicles have the same capacity ($Q$), even if their speeds differ. In practice, faster vehicles often have larger capacities.
- Constant Optimization: Future research may focus on tightening the approximation constants to make the algorithm more practical for real-world implementation.
Summary updated