几种改进PSO算法在带时间窗车辆路径问题中的比较与分析

The Comparison and Analysis of Several Improved PSO Algorithms in Solving the Vehicle Routing Problem with Time Window

车辆路径问题属于完全NP问题,也是运筹学中的热点问题。虽然目前有很多人进行研究,但搜索效率和达优率较低,而且计算所得平均费用偏高。鉴于此,本文分别用二阶振荡PSO、随机惯性权重PSO、带自变异算子PSO、模拟退火PSO求解带时间窗车辆路径问题。通过仿真实验给出了这四种改进PSO算法在求解该问题时的不同;同时,与文献[1]中的遗传算法、标准PSO算法求解该问题进行了比较并得出结论:本文中用到的四种改进PSO算法都能更有效地降低成本,缩短运行时间,提高达优率,而且随机惯性权重PSO表现尤为突出。

The Vehicle Routing Problem is a NP complete problem and is also a hot topic in the operational research field. Many people do research on it, but searching effiency and the rate of success are low and the cost is high. In view of this,the paper adopts the second-order oscillating particle swarm optimization, particle swarm optimization-randomly varying inertia weight,particle swarm optimization mutation operator, and simulated annealing particle swarm optimization to solve the vehicle routing problem with time window. We list the differences when solving the problem through simulation experiments and compare the four algorithms with the genetic algorithm, standard particle swarm optimization used in literature[14]. We can conclude that all the four algorithms used in this article can decrease the cost, shorten the running time, and improve the rate of success effectively,and particle swarm optimization-randomly varying inertia weight is the best.