Technical note: Split algorithm in O(n) for the capacitated vehicle routing problem

Thibaut Vidal

Abstract

The Split algorithm is a critical component in many high-performing metaheuristics for the Vehicle Routing Problem (VRP), responsible for optimally partitioning a giant tour into individual vehicle routes. Traditionally implemented as a shortest-path problem on a Directed Acyclic Graph (DAG) with $O(nB)$ complexity, this sub-routine can become a bottleneck for large-scale instances. This paper introduces a linear-time $O(n)$ Split algorithm that exploits the mathematical structure of route costs. Empirical results demonstrate speedups of up to 400x for hard capacity constraints and over 7,000x for soft constraints on instances with up to 71,000 customers.

Introduction

Vehicle Routing Problems (VRP) are fundamental to logistics optimization. A widely successful strategy for solving VRP variants is the "route-first, cluster-second" approach. In this framework, a metaheuristic first generates a "giant tour"—a single permutation of all customers without depot visits. A specialized algorithm, known as Split, then determines the optimal locations to insert depot visits to form feasible routes that satisfy vehicle capacity and other constraints.

Visualization of the Split problem: a giant tour of 12 customers is partitioned into optimal routes starting and ending at the depot (node 0).

As shown in Figure 1, the Split algorithm transforms a sequence of nodes into a set of routes. While the classic implementation by Prins (2004) is effective, its $O(nB)$ complexity (where $n$ is the number of customers and $B$ is the average number of feasible routes per starting point) limits its scalability for modern, large-scale logistics problems.

The Linear Split Algorithm

The core innovation of this work lies in moving beyond the standard shortest-path approach by exploiting the specific mathematical structure of the costs in the Split graph.

Cost Structure and the Monge Property

The cost of a route in the Split graph is not arbitrary; it is the sum of the distance from the depot to the first customer, the distances between consecutive customers in the sequence, and the distance from the last customer back to the depot. The author identifies that the cost difference between two potential "cut points" (predecessors) remains constant for all future customers, provided the route remains feasible. This property is related to the Monge property, which allows for more efficient search strategies.

Illustration of the cost functions $g_i(x)$ used in the linear Split algorithm to identify nondominated predecessors.

Implementation via Deque

Leveraging these properties, the proposed algorithm uses a double-ended queue (deque) to maintain a set of "nondominated" predecessors. As the algorithm scans the giant tour, it can prune the search space in $O(1)$ amortized time. If a predecessor $A$ is cheaper than predecessor $B$ and has a lower cumulative load, $B$ can never become a better choice than $A$ for any future node and is discarded. This reduces the overall complexity to $O(n)$.

The algorithm is further generalized to handle:

  • Limited Fleets: Restricting the solution to exactly $m$ vehicles with $O(nm)$ complexity.
  • Soft Capacity Constraints: Allowing vehicle overloads for a penalty while maintaining $O(n)$ complexity.

Experimental Evaluation

The algorithm was evaluated on 105 benchmark instances ranging from 29 to 71,009 nodes, with various vehicle capacities.

Key Results

  • Efficiency: For standard hard capacity constraints, the linear algorithm is up to 400 times faster than the traditional Bellman-based version on large instances. On the largest 71k-node instance, the optimal partition is found in just 3.06 ms.
  • Soft Constraints: The performance gain is even more pronounced for soft constraints, reaching a speedup of 7,187x. This is because the linear approach does not rely on capacity-based pruning, which is ineffective when every route is technically "feasible" via a penalty.
  • Scalability: The linear Split algorithm becomes the superior choice as soon as average route lengths exceed four customers.

Conclusion

By reducing the complexity of the Split sub-routine to $O(n)$, this technical note removes a significant computational barrier in VRP metaheuristics. This optimization enables the solution of much larger real-world problems and provides a foundation for extending similar techniques to more complex VRP variants, such as those involving heterogeneous fleets or location-routing decisions.

Summary updated

Abstract

Highlights • We propose a simple O ( n ) Split algorithm for the capacitated vehicle routing problem. • This algorithm aims to partition a “giant tour” solution into separate routes. • Split is implemented as the resolution of a shortest path, with additional dominance rules. • The method is extended to consider limited fleets and soft capacity constraints. 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 et al. [18], 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 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 G . In this paper, 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 capacitated vehicle routing problem}},
  journal = {Comput. Oper. Res.},
  year = {2016},
  doi = {10.1016/j.cor.2015.11.012},
}
Figure