改进差分进化算法求解带容量约束车辆路径问题  

Improved differential evolution algorithm for capacitated vehicle routing problem

作　　者：冉敏 潘大志[1,2] Ran Min;Pan Dazhi(School of Mathematics and Information,China West Normal University,Nanchong 637009,China;Institute of Computing Method and Application Software,China West Normal University,Nanchong 637009,China)

机构地区：[1]西华师范大学数学与信息学院,南充637009 [2]西华师范大学计算方法与应用研究所,南充637009

出　　处：《现代计算机》2024年第15期10-17,56,共9页Modern Computer

基　　金：国家自然科学基金项目(11871059);四川省教育厅自然科学基金项目(18ZA0469)。

摘　　要：针对带容量约束车辆路径问题(CVRP),提出了一种改进差分进化算法(IDE)。首先,在变异、交叉操作过程中提出一种新的扰动策略,同时设计两类不同的邻域搜索算子,加快算法收敛速度;其次,设计一种多样性保护策略,以防止算法后期种群单一化;最后,基于个体、整体收敛性设计两种惩罚因子,对不可行解作出有效的惩罚。通过对三组CVRP问题实例进行仿真实验分析,并将求解结果与其他算法相比较,验证了所提算法的有效性。Aiming at the vehicle routing problem with capacity,an improved differential evolution algorithm(IDE)was proposed.Firstly,a new perturbation strategy is proposed for mutation and cross operation,and two kinds of neighborhood operators are designed to accelerate the convergence of the algorithm.Secondly,a diversity protection strategy is designed to prevent population uniformity in the later stage of the algorithm.Finally,two penalty factors are designed based on individual and global convergence to effectively punish infeasible solutions.The effectiveness of the proposed algorithm is verified by the simulation experiments of three CVRP problem examples,and the results are compared with other algorithms.

关 键 词：车辆路径问题 扰动策略 多样性保护机制 自适应罚函数 差分进化算法 

分 类 号：U492.22[交通运输工程—交通运输规划与管理] TP18[交通运输工程—道路与铁道工程]