Hybrid particle swarm optimization algorithm for solving the clustered vehicle routing problem

Abstract

This paper considers a variant of the classical capacitated vehicle routing problem called clustered vehicle routing problem (CluVRP). In CluVRP, customers are grouped into different clusters. A vehicle visiting a cluster cannot leave the cluster until all customers in the same cluster have been served. Each cluster and customer have to be served only once. A new hybrid metaheuristic, combining the particle swarm optimization (PSO) and variable neighborhood search (VNS) for the specific problem, is proposed to solve the CluVRP. In the hybrid PSO, the basic PSO principle ensures the solution diversity and VNS ensures solution intensity to bring the solution to the local optima. Extensive computational experiments have been performed on numerous benchmark instances with various sizes obtained from the CluVRP literature to evaluate the performance of the proposed hybrid PSO. The obtained results of the proposed algorithm are compared with the results found in the literature to validate the effectiveness of the proposed hybrid PSO. The proposed algorithm is proven to be superior to the state-of-the-art algorithms on the CluVRP. The proposed algorithm obtains 138 new best-known solutions among the 293 benchmark instances.