Technical Note: Split algorithm in O(n) for the capacitated vehicle routing problem
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.
split algorithm vehicle routing problem large neighborhood search cluster-first route-second heuristic