Technical Note: Split Algorithm in O(n) for the Vehicle Routing Problem

Thibaut Vidal

This technical note by Thibaut Vidal introduces a significant algorithmic optimization for the Capacitated Vehicle Routing Problem (CVRP), a cornerstone of logistics and supply chain management. By identifying a specific property in the underlying graph structure of the problem, the author reduces the complexity of a critical sub-routine from $O(nB)$ to a linear $O(n)$.

TL;DR

The paper presents a linear-time $O(n)$ "Split" algorithm for the CVRP, replacing the traditional $O(nB)$ Bellman-based approach. By exploiting a "stronger-than-Monge" property in the route cost structure, the new method achieves speedups of up to 400x on large-scale instances, removing a major computational bottleneck in modern routing metaheuristics.

What Problem Does This Paper Address?

In modern Vehicle Routing Problem (VRP) solvers, particularly hybrid genetic algorithms, a popular strategy is "route-first, cluster-second." Instead of managing complex route structures directly, the algorithm evolves a "giant tour"—a simple permutation of all customers. A decoder called the Split algorithm then optimally partitions this giant tour into individual routes by inserting depot visits.

While conceptually elegant, the Split algorithm is called tens of thousands of times during a single metaheuristic run. Traditionally, it is solved as a shortest-path problem in a Directed Acyclic Graph (DAG) using Bellman’s algorithm. For large problems with many customers per route, this $O(nB)$ complexity (where $B$ is the average number of feasible routes starting at a customer) becomes a massive computational bottleneck.

Methods

The author moves beyond the standard Bellman-based approach by identifying a specific cost structure property.

The "Stronger Property"

The core innovation lies in Property (2) identified in the paper. The author notes that for any two possible starting points for a route in the giant tour ($i_1$ and $i_2$), the difference in cost to reach any subsequent customer $j$ is constant, provided the route is feasible.

Figure 2: Numerical example – The functions gi(x) are displayed for i ∈{1, . . . , 6}. Note that the function g0(x) does not appear (takes an infinite value) since (0, 7) /∈A.

The Linear Split Algorithm

Leveraging this property, the author proposes a labeling algorithm that uses a double-ended queue (deque) to maintain a set of "non-dominated" predecessors.

  • Pruning: As the algorithm iterates through customers, it uses a dominates(i, j) function to quickly discard predecessors that can never lead to an optimal path.
  • Complexity: Because each node is added to and removed from the deque at most once, the total complexity is strictly $O(n)$.

Extensions

The paper doesn't stop at the basic CVRP. It extends the $O(n)$ logic to:

  1. Limited Fleets: By iterating the algorithm $m$ times, achieving $O(nm)$ complexity.
  2. Soft Capacity Constraints: Allowing routes to exceed capacity for a linear penalty. Surprisingly, the algorithm remains $O(n)$ in this case, whereas the traditional Bellman approach's complexity explodes to $O(n^2)$ because it can no longer prune based on feasibility.

Datasets

The algorithm was evaluated on 105 benchmark instances derived from:

  • TSPLib: A standard library for Traveling Salesman Problem instances.
  • World TSP: Large-scale instances representing real-world country maps.
  • Instance Scale: Customer counts ($n$) ranged from 29 to 71,009, with vehicle capacities adjusted to produce between 4 and 4,000 deliveries per route.

Key Insights and Ideas

  • Beyond Monge: While it was known that the Split graph satisfies the "Monge property" (allowing for some linear-time shortest path algorithms), those methods are notoriously complex to implement. Vidal shows that the VRP Split graph has an even stronger property that allows for a much simpler deque-based linear algorithm.
  • Dominance is Global: Because the marginal cost of choosing one predecessor over another is constant across all feasible end-points, a predecessor that is "beaten" once is beaten for good. This allows for aggressive, one-pass pruning.
  • Soft Constraints Advantage: The linear Split is most dominant when constraints are "soft." In these scenarios, the traditional algorithm must explore every possible arc in the graph, while the linear Split maintains its efficiency.

Key Results

The practical performance gains are dramatic:

  • Speedups: For standard hard-capacity constraints, speedup factors ranged from 0.8 to 400. The largest gains were seen in instances with many deliveries per route (e.g., courier services or refuse collection).
  • Absolute Time: For the largest instance ($n \approx 71,000$), the Bellman-based algorithm took roughly 1 second per call. The linear Split algorithm completed the same task in under 3 milliseconds.
  • Soft Constraints: Speedup factors reached as high as 7,187 for the largest instances when capacity constraints were relaxed.
Extracted figure from page 5 of Technical Note: Split Algorithm in O(n) for the Vehicle Routing Problem

Limitations and Future Work

  • Fleet Size Bottleneck: While $O(nm)$ is an improvement for limited fleets, it can still be slow if the number of vehicles ($m$) is very large. The author suggests exploring Lagrangian relaxation to handle fleet limits more efficiently.
  • Generalization: A key question for future research is identifying which other VRP variants (e.g., those with time windows or heterogeneous fleets) possess the necessary "resource extension function" properties to support similar linear-time decoders.
  • Local Search Integration: The author notes that while Split is no longer the bottleneck, the local search (LS) phase now is. Future work should focus on improving LS efficiency to match these new decoding speeds.

Summary updated

Abstract

The Split algorithm is an essential building block of route-first cluster-second heuristics and modern genetic algorithms for vehicle routing problems. The algorithm is used to partition a solution, represented as a giant tour without occurrences of the depot, into separate routes with minimum cost. As highlighted by the recent survey of [Prins, Lacomme and Prodhon, Transport Res. C (40), 179-200], no less than 70 recent articles use this technique. In the vehicle routing literature, Split is usually assimilated to the search for a shortest path in a directed acyclic graph $\mathcal{G}$ and solved in $O(nB)$ using Bellman's algorithm, where $n$ is the number of delivery points and $B$ is the average number of feasible routes that start with a given customer in the giant tour. Some linear-time algorithms are also known for this problem as a consequence of a Monge property of $\mathcal{G}$. In this article, we highlight a stronger property of this graph, leading to a simple alternative algorithm in $O(n)$. Experimentally, we observe that the approach is faster than the classical Split for problem instances of practical size. We also extend the method to deal with a limited fleet and soft capacity constraints.
BibTeX
@article{vidal2016technical,
  author = {Thibaut Vidal},
  title = {{Technical Note: Split Algorithm in O(n) for the Vehicle Routing Problem}},
  journal = {Comput. Oper. Res.},
  year = {2016},
  doi = {10.1016/j.cor.2015.11.012},
}
Figure