Geodesy

Constraint programming

Routing (electronic design automation)

Metaheuristic

Algorithm

Benchmark (surveying)

Stochastic programming

Vehicle routing problem

Local search (optimization)

Particle swarm optimization

Computer science

Mathematical optimization

Computer network

Cluster (spacecraft)

Mathematics

Geography

Hybrid algorithm (constraint satisfaction)

Variable neighborhood search

Constraint logic programming

Programming language

Applied Soft Computing

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.

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