Abstract: Multi-Depots Vehicle Routing Problem（MDVRP） is a kind of NP combination problem which possesses important practical value. In order to overcome PSO’s premature and slow convergence, a new improved algorithm is put forward, it adopts co-evolutionary thought and at the same time pattern search method is introduced while the search falling into local optimum. In this paper, a kind of new particles coding method is constructed and the solution algorithm is developed. The simulation results show that the algorithm has better optimal speed and optimal efficiency than GA and PSO, so it proves the algorithm used to optimize MDVRP is feasible and effective.

Key words: vehicle routing problem, multi-depots, pattern search, Particle Swarm Optimization（PSO）, co-evolutionary

摘要： 多车场车辆路径问题是一类实用性很高的NP难解问题。针对标准粒子群算法易早熟、收敛速度慢的缺陷，提出了一种新的改进算法，该算法采用协同进化思想，同时在搜索陷入局部最优的情况下引入了模式搜索方法。针对多车场车辆路径问题构造了一种新的粒子编码方法，建立了相应的数学模型，并介绍了该算法的详细实现过程。仿真结果通过和遗传算法和标准粒子群算法比较，表明该算法具有更好的寻优速度和寻优效率，从而证明了提出的算法用于优化多车场车辆路径问题是可行和有效的。

关键词: 车辆路径问题, 多车场, 模式搜索, 粒子群优化, 协同进化