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

doi:10.11896/jsjkx.210800271

摘要/Abstract

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

关键词: 分层学习, 社会学习, 差分进化, 粒子群优化算法, 车辆路径问题

Abstract: 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.

Key words: Hierarchical learning, Social learning, Differential evolution, Particle swarm optimization algorithm, Capacitated vehicle routing problem

中图分类号:

TP301

陈莹, 黄佩萱, 陈锦萍, 王祖怡, 沈映珊, 樊小毛. 基于分层学习和差分进化的混合PSO算法求解车辆路径问题[J]. 计算机科学, 2022, 49(11A): 210800271-7. https://doi.org/10.11896/jsjkx.210800271

CHEN Ying, HUANG Pei-xuan, CHEN Jin-ping, WANG Zu-yi, SHEN Ying-shan, FAN Xiao-mao. Hybrid Particle Swarm Optimization Algorithm Based on Hierarchical Learning and Different Evolution for Solving Capacitated Vehicle Routing Problem[J]. Computer Science, 2022, 49(11A): 210800271-7. https://doi.org/10.11896/jsjkx.210800271

参考文献

[1]DANTZIG G B,RAMSER J H.The truck dispatching problem[J].Management Science,1959,6(1):80-91.
[2]YANG G,CAI Y.A review of hybrid particle swarm optimization algorithms for vehicle routing problems and its variants [J].Automation and Information Engineering,2021,42(2):7-13.
[3]LENSTRA J K,KAN A.Complexity of vehicle routing andscheduling problems[J].Networks,2010,11(2):221-227.
[4]LHAN L.An Improved Simulated Annealing Algorithm withCrossover Operator for Capacitated Vehicle Routing Problem[J].Swarm and Evolutionary Computation,2021:doi:10.1016/J.SWEVO.2021.100911.
[5]KRICHEN S,SBAI I,LIMAM O.An effective genetic algorithmfor solving the capacitated vehicle routing problem with two-dimensional loading constraint[J].International Journal of Computational Intelligence Studies,2020,9(1/2):85-106.
[6]SONG L,YUN D.An improved differential evolution algorithmwith local search for capacitated vehicle routing problem[C]//2018 Tenth International Conference on Advanced Computational Intelligence(ICACI ).2018.
[7]KOHLER M,VELLASCO M,TANSCHEIT R.PSO+:A new particle swarm optimization algorithm for constrained problems[J].Applied Soft Computing,2019,85(5):437-442.
[8]YU W W,XIE C W.A multi-strategy hybrid particle swarm op-timization algorithm[J].Computer Science,2018,45(S1):133-136.
[9]CHENG R,JIN Y.A social learning particle swarm optimization algorithm for scalable optimization[J].Information Sciences An International Journal,2015,291(5):43-60.
[10]LI J,LUO Y K,LI B,et al.Differential hybrid particle swarm optimization algorithm based on different-dimensional mutation[J].Computer Science,2018,45(5):208-214.
[11]GE H,SUN L,TAN G,et al.Cooperative Hierarchical PSO With Two Stage Variable Interaction Reconstruction for Large Scale Optimization[J].IEEE Transactions on Cybernetics,2017,47(9):2809-2823.
[12]YUAN X,JIANG S.Improved particle swarm optimization algorithm based on hierarchical autonomous learning[J].Computer Applications,2019,39(1):148-153.
[13]KENNEDY J,EBERHART R.Particle Swarm Optimization[C]//Icnn95-international Conference on Neural Networks.IEEE,2002.
[14]WU G.Research on path planning based on particle swarm algorithm[D].Qinhuangdao:Yanshan University,2016.
[15]WU B.Research and application of particle swarm optimization algorithm for vehicle routing problem[D].Hangzhou:Zhejiang University of Technology,2008.
[16]STORN R,PRICE K.Differential Evolution-A Simple and Efficient Heuristic for global Optimization over Continuous Spaces[J].Journal of Global Optimization,1997,11(4):341-359.
[17]ANONYMOUS.Discrete differential evolution algorithm forsolving problems [J].Computer and Digital Engineering,2017,45(337):58-64.
[18]SHEN J.Application Research of Hybrid Discrete Differential Evolution Algorithm in Green Logistics Vehicle Path Planning[D].Taiyuan:Taiyuan University of Science and Technology,2020.
[19]AKHAND M,PEYA Z J,MURASEK.Capacitated vehicle routing problem solving using adaptive sweep and velocity tentative PSO[J].International Journal of Advanced Computer Science and Applications,2017,8(12):288-295.
[20]ZHANG X N,FAN H M.Hybrid decentralized search algorithm for vehicle routing problem with capacity constraints [J].Control and Decision Making,2015,30(11):1937-1944.
[21]AKPINAR S.Hybrid large neighbourhood search algorithm for capacitated vehicle routing problem[J].Expert Systems with Applications,2016,61:28-38.

相关文章 15

[1]	杨浩雄, 高晶, 邵恩露. 考虑一单多品的外卖订单配送时间的带时间窗的车辆路径问题 Vehicle Routing Problem with Time Window of Takeaway Food ConsideringOne-order-multi-product Order Delivery 计算机科学, 2022, 49(6A): 191-198. https://doi.org/10.11896/jsjkx.210400005
[2]	刘宝宝, 杨菁菁, 陶露, 王贺应. 基于DE-LSTM模型的教育统计数据预测研究 Study on Prediction of Educational Statistical Data Based on DE-LSTM Model 计算机科学, 2022, 49(6A): 261-266. https://doi.org/10.11896/jsjkx.220300120
[3]	刘漳辉, 郑鸿强, 张建山, 陈哲毅. 多无人机使能移动边缘计算系统中的计算卸载与部署优化 Computation Offloading and Deployment Optimization in Multi-UAV-Enabled Mobile Edge Computing Systems 计算机科学, 2022, 49(6A): 619-627. https://doi.org/10.11896/jsjkx.210600165
[4]	岑健铭, 封全喜, 张丽丽, 佟锐超. 基于DE-lightGBM模型的上市公司高送转预测实证研究 Empirical Study on the Forecast of Large Stock Dividends of Listed Companies Based on DE-lightGBM 计算机科学, 2022, 49(11A): 211000017-7. https://doi.org/10.11896/jsjkx.211000017
[5]	杨浩, 闫巧. 基于差分进化算法的字符对抗验证码生成方法 Adversarial Character CAPTCHA Generation Method Based on Differential Evolution Algorithm 计算机科学, 2022, 49(11A): 211100074-5. https://doi.org/10.11896/jsjkx.211100074
[6]	高际航, 张艳. 基于FWA-PSO-MSVM的船舶区域配电电力系统故障诊断 Fault Diagnosis of Shipboard Zonal Distribution Power System Based on FWA-PSO-MSVM 计算机科学, 2022, 49(11A): 210800209-5. https://doi.org/10.11896/jsjkx.210800209
[7]	屈立成, 吕娇, 屈艺华, 王海飞. 基于模糊神经网络的运动目标智能分配定位算法 Intelligent Assignment and Positioning Algorithm of Moving Target Based on Fuzzy Neural Network 计算机科学, 2021, 48(8): 246-252. https://doi.org/10.11896/jsjkx.200600050
[8]	俞家珊, 吴雷. 双领导者樽海鞘群算法 Two Types of Leaders Salp Swarm Algorithm 计算机科学, 2021, 48(4): 254-260. https://doi.org/10.11896/jsjkx.200600181
[9]	张志强, 鲁晓锋, 隋连升, 李军怀. 集成随机惯性权重和差分变异操作的樽海鞘群算法 Salp Swarm Algorithm with Random Inertia Weight and Differential Mutation Operator 计算机科学, 2020, 47(8): 297-301. https://doi.org/10.11896/jsjkx.190700063
[10]	侯改, 何朗, 黄樟灿, 王占占, 谈庆. 基于差分进化的金字塔演化策略求解一维下料问题 Pyramid Evolution Strategy Based on Differential Evolution for Solving One-dimensional Cutting Stock Problem 计算机科学, 2020, 47(7): 166-170. https://doi.org/10.11896/jsjkx.190500014
[11]	宋岩, 胡瑢华, 郭福民, 袁新亮, 熊睿洋. 基于sEMG的改进SVM+BP肌力预测分层算法 Improved SVM+BP Algorithm for Muscle Force Prediction Based on sEMG 计算机科学, 2020, 47(6A): 75-78. https://doi.org/10.11896/JsJkx.190900143
[12]	李章维,王柳静. 基于群体分布的自适应差分进化算法 Population Distribution-based Self-adaptive Differential Evolution Algorithm 计算机科学, 2020, 47(2): 180-185. https://doi.org/10.11896/jsjkx.181202356
[13]	郑波, 马昕. 基于双变异粒子群优化算法优化的支持向量机及其在民航发动机损伤类型识别中的应用 Application on Damage Types Recognition in Civil Aeroengine Based on SVM Optimized by DMPSO 计算机科学, 2020, 47(11A): 132-138. https://doi.org/10.11896/jsjkx.200600101
[14]	王瑄, 毛莺池, 谢在鹏, 黄倩. 基于差分进化的推断任务卸载策略 Inference Task Offloading Strategy Based on Differential Evolution 计算机科学, 2020, 47(10): 256-262. https://doi.org/10.11896/jsjkx.190800159
[15]	董明刚,刘宝,敬超. 模糊自适应排序变异多目标差分进化算法 Multi-objective Differential Evolution Algorithm with Fuzzy Adaptive Ranking-based Mutation 计算机科学, 2019, 46(7): 224-232. https://doi.org/10.11896/j.issn.1002-137X.2019.07.034

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed