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

Thibaut Vidal

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