Research in Capacitated Vehicle Routing Problem Based on Modified Hybrid Particle Swarm Optimization

摘要

Capacitated vehicle routing problem (CVRP) is an NP hard problem and it has important practical value. For large-scale problems, it is quite difficult to achieve an optimal solution with traditional optimization methods due to the high computational complexity. In this paper, it is analyzed that the insufficiency of the traditional particle swarm optimization (PSO) to the discrete and combination optimization problem; and hybrid particle swarm optimization (HPSO) is developed in this work to CVRP. Considering the large lost in swarm diversity during the evolution, diversity-measure is introduced into algorithm. Modified hybrid particle swarm optimization (MHPSO) is proposed and the detailed strategy of solving CVRP is also discussed. In order to utilize the ergodicity, stochastic property and regularity of capability of chaos, it also constructs the initial solution with chaos. The effectiveness and better performance of the proposed algorithm is demonstrated by comparing with other particle swarm optimization algorithms (PSO) and genetic algorithms (GA). Series of numerical examples show that MHPSO is a feasible and effective approach for capacitated vehicle routing problem.