Particle Swarm Optimization Algorithm with Real Number Encoding for Vehicle Routing Problem

摘要

Vehicle routing problem (VRP) is a NP-hard problem, many heuristic algorithms, for example Genetic algorithm, Ant Colony optimization is applied for this problem. Particle swarm optimization (PSO) is an evolutionary computation technique. The research on discrete combinatorial optimization problem based on PSO needs extensive and intensive. A real number encoding method of PSO and a decoding rule based on loading capacity are proposed to resolve VRP. An efficient adjusting strategy aiming at illegal solution after decoding is proposed. Nearest Neighbor algorithm and Or-Opt are utilized to optimize solution through adjusting within routes and among routes. Ten benchmark problem instances were tested and validated that the algorithm is better than integer encoding PSO and genetic algorithm ground on these experiments data.