Particle swarm optimization and two solution representations for solving the capacitated vehicle routing problem

This paper presents two solution representations and the corresponding decoding methods for solving the capacitated vehicle routing problem (CVRP) using particle swarm optimization (PSO). The first solution representation (SR-1) is a (n+2m)-dimensional particle for CVRP with n customers and m vehicles. The decoding method for this representation starts with the transformation of particle into a priority list of customer to enter route and a priority matrix of vehicle to serve each customer. The vehicle routes are then constructed based on the customer priority list and vehicle priority matrix. The second representation (SR-2) is a 3m-dimensional particle. The decoding method for this representation starts with the transformation of particle into the vehicle orientation points and the vehicle coverage radius. The vehicle routes are constructed based on these points and radius. The proposed representations are applied using GLNPSO, a PSO algorithm with multiple social learning structures, and tested using some benchmark problems. The computational result shows that representation SR-2 is better than representation SR-1 and also competitive with other methods for solving CVRP. (C) 2008 Elsevier Ltd. All rights reserved.