基于分层学习和差分进化的混合PSO算法求解车辆路径问题

Hybrid Particle Swarm Optimization Algorithm Based on Hierarchical Learning and Different Evolution for Solving Capacitated Vehicle Routing Problem

车辆路径问题旨在求解每辆车的服务路线,使其在完成配送任务的情况下行驶距离之和最短,是运筹学中经典的组合优化问题,属于NP难问题,且具有较高的理论意义与实际应用价值。针对该问题,提出了一种基于分层学习和差分进化的混合粒子群优化算法(Hybrid Particle Swarm Optimization Algorithm Based on Hierarchical Learning and Different Evolution,DEHSLPSO)。DE-HSLPSO中引入了分层学习策略,以适应度值和迭代次数为依据将种群粒子动态划分为3层,在前两层粒子的进化过程中引入了社会学习机制,而第三层粒子进行差分进化,通过变异和交叉有效地增加粒子的多样性,从而开拓空间,有利于跳出局部最优。通过在经典的CVRP数据集上进行仿真实验,来探究DE-HSLPSO各部分对整体性能的影响,实验证明分层策略与差分进化均可提升算法的整体性能。另外,在7个基本算例上对DE-HSLPSO与其他优化算法进行了测试,综合时间与最优解进行对比,结果表明DE-HSLPSO的求解性能优于其他对比算法。

The purpose of the vehicle routing problem(VRP)is to search the service route of each vehicle,so as to minimize the sum of driving distances in the case of completing all of the distribution tasks.CVRP,a classical combinatorial optimization problem in operations research,belongs to NP-hard problem and has high theoretical significance and practical value.In order to solve this problem,a hybrid particle swarm optimization algorithm based on hierarchical learning and different evolution(DE-HSLPSO)is proposed.First,the hierarchical learning strategy is introduced and the population particles are divided into three layers according to their fitness values and number of iterations.Secondly,the social learning mechanism is introduced in the evolution of the first two layers of particles,while particles in the third layer carry out differential evolution which effectively increases the diversity of particles,thus expanding the space and jumping out of local optimal.Simulation experiment whose examples are taken from the classical CVRP data sets explores the impact of each part of DE-HSLPSO on the overall performance.It is found that both hierarchical strategy and differential evolution can improve the overall performance of the algorithm.In addition,DE-HSLPSO and other algorithms are tested on seven benchmark examples.With comprehensive comparison of time and optimal solution,the result shows that the solution performance of DE-HSLPSO is better than that of other algorithms.