Title :
Research in capacitated vehicle routing problem based on modified hybrid particle swarm optimization
Author :
Wang, Zhengchu ; Li, Jun ; Zhou, Muxun ; Fan, Jian
Author_Institution :
Sch. of Mech. Eng., Taizhou Coll., Taizhou, China
Abstract :
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.
Keywords :
combinatorial mathematics; computational complexity; particle swarm optimisation; stochastic programming; transportation; vehicles; NP hard problem; capacitated vehicle routing problem; combination optimization problem; computational complexity; discrete optimization problem; diversity-measure; modified hybrid particle swarm optimization; stochastic property; Chaos; Computational complexity; Genetic algorithms; Large-scale systems; NP-hard problem; Optimization methods; Particle swarm optimization; Routing; Stochastic processes; Vehicles; optimization; particle swarm optimization; swarm intelligence; vehicle routing problem;
Conference_Titel :
Intelligent Computing and Intelligent Systems, 2009. ICIS 2009. IEEE International Conference on
Conference_Location :
Shanghai
Print_ISBN :
978-1-4244-4754-1
Electronic_ISBN :
978-1-4244-4738-1
DOI :
10.1109/ICICISYS.2009.5358182