A two-level variable neighbourhood search for the Euclidean clustered vehicle routing problem

In this paper, a metaheuristic approach is presented to solve the Clustered Vehicle Routing Problem (CluVRP). The CluVRP, in which customers are grouped into predefi?ned clusters, can be seen as a generalisation of the classical Capacitated Vehicle Routing Problem (CVRP). When serving all these customers with a given fl?eet of vehicles it should be ensured that clients belonging to the same cluster are served by one vehicle, sequentially in the same path (CluVRP with hard cluster constraints). In a second phase, these constraints will be relaxed as we will de?ne the CluVRP with so? cluster constraints. Th?e proposed metaheuristic approach tries to fi?nd the optimal solution for both problems by combining two variable neighbourhood search algorithms, exploring the distribution area at two different levels. ?The algorithm is tested on di?erent benchmark instances from the literature with up to 484 nodes, obtaining high quality solutions.