带时间窗车辆路径问题的混沌粒子群优化算法  

A Chaos Particle Swarm Optimization Algorithm of Vehicle Routing Problem with Time Windows

作　　者：杨庆[1] 陈强[1] 李珍珍[1] 

机构地区：[1]上海工程技术大学,上海201620

出　　处：《计算机技术与发展》2015年第8期119-122,127,共5页Computer Technology and Development

基　　金：上海市教育创新项目理科重点项目(12ZZ182)

摘　　要：车辆路径问题属于完全NP问题,也是运筹学中的热点问题。虽然目前有很多人进行研究,但搜索效率和达优率较低,而且计算所得平均费用偏高。鉴于此,基于基本PSO算法容易陷入局部最优,而混沌具有随机性、遍历性及规律性等特点,文中很好地将混沌优化算法与粒子优化算法相结合,提出了一种混沌粒子群优化算法,应用于带时间窗的车辆路径问题(VRPTW)。通过仿真实验,将混沌粒子群算法与粒子群算法、遗传算法等多种算法进行比较。结果显示,混沌粒子群算法运算速度快、鲁棒性好且能获得高质量的解,是求解带时间窗的车辆路径问题的一种简单有效的算法。The vehicle routing problem is a NIP complete problem and is also a hot topic in the operational research field. Many people do research on it,but searching efficiency and the rate of success are low and the cost is high. In view of this,based on basic PSO algorithm is easy to fall into local optimum, and chaos has many characteristics such as randomicity, ergodicity and regularity,combined the particle optimization algorithm with chaos optimization algorithm in this paper, a chaos particle swarm optimization algorithm is proposed, and applied to the Vehicle Routing Problem with Time Windows （VRPTW）. Through simulation experiments,the chaotic Particle Swarm Opti- mization （PSO） algorithm and PSO algorithm,genetic algorithm and other algorithms are compared. The experimental results show that the chaotic particle swarm optimization arithmetic with fast speed and good robustness, can obtain high quality of the solution, which is a simple and effective algorithm to solve the vehicle routing problem with time windows.

关 键 词：混沌 粒子群 车辆问题 混沌粒子群优化算法 

分 类 号：TP202.7[自动化与计算机技术—检测技术与自动化装置]