多车场车辆路径问题的改进粒子群算法  

Study on multi-depots vehicle routing problem based on improved particle swarm optimization

作　　者：王铁君[1] 邬开俊[2] 

机构地区：[1]西北民族大学数学与计算机科学学院,兰州730030 [2]兰州交通大学电子与信息工程学院,兰州730070

出　　处：《计算机工程与应用》2013年第2期5-8,共4页Computer Engineering and Applications

基　　金：国家社科基金项目(No.12CGL004);甘肃省教育厅科研项目(No.1118B-03);西北民族大学中央高校基本业务费专项资金项目(No.ZYZ2011080)

摘　　要：多车场车辆路径问题是一类实用性很高的NP难解问题。针对标准粒子群算法易早熟、收敛速度慢的缺陷,提出了一种新的改进算法,该算法采用协同进化思想,同时在搜索陷入局部最优的情况下引入了模式搜索方法。针对多车场车辆路径问题构造了一种新的粒子编码方法,建立了相应的数学模型,并介绍了该算法的详细实现过程。仿真结果通过和遗传算法和标准粒子群算法比较,表明该算法具有更好的寻优速度和寻优效率,从而证明了提出的算法用于优化多车场车辆路径问题是可行和有效的。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 opti- mum. In this paper, a kind of new particles coding method is constructed and the solution algorithm is developed. The simula- tion 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.

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]