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

• We propose a simple O(n)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.

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 GG and solved in O(nB)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 GG. In this paper, we highlight a stronger property of this graph, leading to a simple alternative algorithm in O(n)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.