车辆路径问题的粒子群算法研究

Particle swarm optimization for vehicle routing problem

车辆路径优化问题是一类具有重要实用价值的组合NP问题.粒子群算法(particleswarmoptimization)是一种新出现的群智能(swarmintelligence)优化方法,将其应用于车辆路径优化问题,构造车辆路径问题的粒子表达方法,建立了此问题的粒子群算法,并与遗传算法作了对比试验.结果表明,粒子群算法可以快速、有效求得车辆路径问题的优化解,是求解车辆路径问题的一个较好方案.

The vehicle routing problem (VRP) is a kind of combination NP problem which possesses important practical value. Particle swarm optimization (PSO) is a newly appeared method for swarm intelligence optimization. PSO is used in this paper to solve the VRP. This paper proposes a novel particle presentation for the vehicle routing problem, establishes an algorithm of PSO for this kind of problem, and compares PSO with GA in the same VRP experiments. Experimental results indicate that the established algorithm of PSO can quickly and effectively get optimal solution to the vehicle routing problem, which demonstrates that the algorithm is an effective method for solving the vehicle routing problem.