Large multiple neighborhood search for the clustered vehicle-routing problem

The clustered vehicle-routing problem is a variant of the classical capacitated vehicle-routing problem in which customers are partitioned into clusters, and it is assumed that each cluster must have been served completely before the next cluster is served. This decomposes the problem into three subproblems, i.e., the assignment of clusters to routes, the routing inside each cluster, and the sequencing of the clusters in the routes. The second task requires the solution of several Hamiltonian path problems, one for each possibility to route through the cluster. We pre-compute the Hamiltonian paths for every pair of customers of each cluster. We present a large multiple neighborhood search which makes use of multiple cluster destroy and repair operators and a variable-neighborhood descent (VND) for post-optimization. The VND is based on classical neighborhoods such as relocate, 2-opt, and swap all working on the cluster level and a generalization of the Balas–Simonetti neighborhood modifying simultaneously the intra-cluster routings and the sequence of clusters in a route. Computational results with our new approach compare favorably to existing approaches from the literature.