多目标车辆路径问题的粒子群优化算法研究  

A Novel Particle Swarm Optimization for Multi-Objective Vehicle Routing Problem

作　　者：郭森[1] 秦贵和[1,2] 张晋东[1] 于赫[1] 卢政宇[1] 于佳欣[3] 

机构地区：[1]吉林大学计算机科学与技术学院,长春130012 [2]吉林大学符号计算与知识工程教育部重点实验室,长春130012 [3]吉林大学软件学院,长春130012

出　　处：《西安交通大学学报》2016年第9期97-104,共8页Journal of Xi'an Jiaotong University

基　　金：国家自然科学基金资助项目(51205154);吉林省科技发展计划资助项目(20140520073JH);吉林省重点科技攻关资助项目(2015020434);中央大学基础研究基金资助项目(JCKY-QKJC14)

摘　　要：针对粒子群算法(PSO)及其变种在约束多目标等复杂问题优化过程中所遇到的易陷入局部最优和收敛性问题,提出了一种基于动态学习和突变因子的粒子群算法(DSPSO)。首先,通过分析粒子群群体的学习机制,采用动态的学习策略,使粒子自适应动态调整认知成分和社会成分在迭代更新中的权重,以引导自身向最优解的方向探索,有效改善了群体的收敛速度;其次,通过引入阶梯突变因子的概念,使粒子在陷入局部最优时进行试探跳跃,阶梯突变赋予粒子突破更新步长限制的能力,使粒子在当前位置速度矢量方向上的二维空间邻域内进行试探寻优,当发现更优解时则跳出当前局部最优;最后,通过在BenchMark基准函数测试集中典型函数上的实验,证明了DSPSO的求解精度和收敛速度均优于对比算法。在多目标车辆路径问题实例优化中,解的可接受率和成功率分别为0.91和0.66,远优于对比算法中最优解的0.16和0.11,体现了所提改进算法在车辆路径问题中的优越性。Considering the problems that particle swarm optimization （PSO） algorithm and its variants are easily to fall into local optimal solutions and convergence in the optimization process of complex constrained multi-objective problem, a novel PSO based on dynamic learning strategy and mutation factor （DSPSO） is proposed. First, through analyzing the learning mechanism of particle swarm, DSPSO introduces the dynamic learning strategy, enabling particles to adaptively adjust the weights of cognitive component and social component in the iteration renewal process and guide themselves to explore in the optimal direction, hence effectively accelerating the convergence rate. Second, by introducing the ladder mutation factor, when the particles are trapped in a local optimum, they are enabled to break the limit of update-step size to make tentative jumps in the two-dimensional spatial neighborhood of the velocity vector direction.When a better solution is found, the optimal solution would be updated. Finally, experiments are conducted on the typical functions of BenchMark, and the results show that the accuracy and convergence rate of DSPSO are better than the contrast algorithms. In the multi-objective vehicle routing problem optimization, the acceptable and success rates of the DSPSO solutions are 0. 91 and 0. 66, respectively, far outperform the results of 0. 16 and 0. 11 by comparison algorithm, reflecting the superiority of DSPSO in the multi-objective vehicle routing problem.

关 键 词：车辆路径问题 多目标优化 粒子群 

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