Particle Swarm Optimization for Split Delivery Vehicle Routing Problem

Abstract

The split delivery vehicle routing problem (SDVRP) is a variation of the capacitated vehicle routing problem in which some customers may be served by more than one vehicle. We have proposed a particle swarm optimization approach that incorporates a local search to solve the SDVRP. An integer coding method was presented, and a decoding method based on Bellman’s equation was modified for the SDVRP. A way to address the differences in the length of the velocity vector, the position vector, the personal best position vector, the local best position vector and the global best position vector was designed. Two groups of local searches for top solutions were incorporated into the algorithm, with the ability to control whether they are executed on a given solution. The algorithm was initially tested using the modified Solomon’s instances to verify the parameters used, including the local search probability, the size of the swarm, the velocity equation and the length of the vectors. Extensive computational experiments were carried out on 131 benchmark instances available in the literature. The results obtained were competitive. More precisely, equally good solutions were found in 32 instances, and improved solutions were found in 35 instances, with an average improvement of 0.02% and a maximum improvement of 1.12%.