  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.
