A hybrid genetic – Particle Swarm Optimization Algorithm for the vehicle routing problem

作者:

Highlights:

摘要

Usually in a genetic algorithm, individual solutions do not evolve during their lifetimes: they are created, evaluated, they may be selected as parents to new solutions and they are destroyed. However, research into memetic algorithms and genetic local search has shown that performance may be improved if solutions are allowed to evolve during their own lifetimes. We propose that this solution improvement phase can be assisted by knowledge stored within the parent solutions, effectively allowing parents to teach their offspring how to improve their fitness. In this paper, the evolution of each individual of the total population, which consists of the parents and the offspring, is realized with the use of a Particle Swarm Optimizer where each of them has to improve its physical movement following the basic principles of Particle Swarm Optimization until it will obtain the requirements to be selected as a parent. Thus, the knowledge of each of the parents, especially of a very fit parent, has the possibility to be transferred to its offspring and to the offspring of the whole population, and by this way the proposed algorithm has the possibility to explore more effectively the solution space. These ideas are applied in a classic combinatorial optimization problem, the vehicle routing problem, with very good results when applied to two classic benchmark sets of instances.

论文关键词:Vehicle routing problem,Genetic algorithms,Particle Swarm Optimization

论文评审过程:Available online 5 July 2009.

论文官网地址:https://doi.org/10.1016/j.eswa.2009.06.085