Combinatorial neighborhood topology particle swarm optimization algorithm for the vehicle routing problem

Summarization: One of the main problems in the application of a Particle Swarm Optimization in combinatorial optimization problems, especially in routing type problems like the Traveling Salesman Problem, the Vehicle Routing Problem, etc., is the fact that the basic equation of the Particle Swarm Optimization algorithm is suitable for continuous optimization problems and the transformation of this equation in the discrete space may cause loose of information and may simultaneously need a large number of iterations and the addition of a powerful local search algorithm in order to find an optimum solution. In this paper, we propose a different way to calculate the position of each particle which will not lead to any loose of information and will speed up the whole procedure. This was achieved by replacing the equation of positions with a novel procedure that includes a Path Relinking Strategy and a different correspondence of the velocities with the path that will follow each particle. The algorithm is used for the solution of the Capacitated Vehicle Routing Problem and is tested in the two classic set of benchmark instances from the literature with very good results.Παρουσιάστηκε στο: The 13th European Conference on Evolutionary Computation in Combinatorial Optimizatio