Study on VRPTW based on Improved Particle Swarm Optimization

Abstract

Vehicle routing problem with time windows (VRPTW) is a typical non-deterministic polynomial hard (NP-hard) optimization problem. In order to overcome PSO’s slow astringe and premature convergence, an improved particle swarm optimization (IPSO) is put forward. In the algorithm, it uses the population entropy to makes a quantitative description about the diversity of the population, and adaptively adjusts the cellular structure according to the change of population entropy to have an effective balance between the local exploitation and the global exploration, thus enhance the performance of the algorithm. In the paper, the algorithm was applied to solve VRPTW, the mathematical model was established and the detailed implementation process of the algorithm was introduced. The simulation results show that the algorithm has better optimization capability than PSO.

DOI : http://dx.doi.org/10.11591/telkomnika.v12i6.5395