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

作     者：陈莹 黄佩萱 陈锦萍 王祖怡 沈映珊 樊小毛 CHEN Ying;HUANG Pei-xuan;CHEN Jin-ping;WANG Zu-yi;SHEN Ying-shan;FAN Xiao-mao

作者机构：华南师范大学计算机学院广州510631 

出 版 物：《计算机科学》 (Computer Science)

年 卷 期：2022年第49卷第S2期

页      面：188-194页

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 081104[工学-模式识别与智能系统] 08[工学] 082303[工学-交通运输规划与管理] 0835[工学-软件工程] 082302[工学-交通信息工程及控制] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 0823[工学-交通运输工程] 

基　　金：国家重点研发计划(2018YFB1800705) 

主　　题：分层学习 社会学习 差分进化 粒子群优化算法 车辆路径问题 

摘      要：车辆路径问题旨在求解每辆车的服务路线,使其在完成配送任务的情况下行驶距离之和最短,是运筹学中经典的组合优化问题,属于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的求解性能优于其他对比算法。