基于改进的蜣螂优化算法的动态路径优化问题  

Dynamic Path Optimization Problem Based on Improved Dung Beetle Optimization Algorithm

作　　者：王群 刘艳秋[1] WANG Qun;LIU Yanqiu(School of Science,Shenyang University of Technology,Shenyang 110870,Liaoning Province)

机构地区：[1]沈阳工业大学理学院,辽宁沈阳110870

出　　处：《沈阳工程学院学报(自然科学版)》2025年第1期78-83,共6页Journal of Shenyang Institute of Engineering:Natural Science

摘　　要：为了使车辆配送更具有现实性,贴合实际情况,解决资源浪费问题,建立以最小化总成本为目标的动态车辆路径模型(DVRP),并将其分解为求解多个静态VRP问题以解决动态性问题,同时提出了一种新型的改进的蜣螂优化算法(DBO)。在生成初始种群时,使用Kmeans聚类提升初始种群的质量,并对原本的DBO的4个子种群所执行的算子进行替代。在滚球阶段采用新的滚球策略更新,模拟繁殖产生新解,并引入了2-opt算子和relocate算子改进算法,进一步提升算法的搜索性能。最后结合数据集,运用Matlab分析算法性能。结果表明:所提算法与经典求解DVRP的算法相比,解的质量有了明显提升。A Dynamic Vehicle Routing Problem(DVRP)with the goal of minimizing total cost is established to make vehicle delivery more realisticand decreasing resource waste.The DVRP is decomposed into solving multiple static VRP problems to solve dynamic problems,and a new improved dung beetle optimization algorithm has been proposed.When generating the initial population,K-means clustering is used to improve the quality of the initial population,and the operators executed by the four subpopulations of the original Dung Beetle Optimizer(DBO)algorithm are replaced.In the rolling stage,a new rolling strategy is adopted to update and simulate reproduction to generate new solutions.The 2-opt operator and relocate operator are introduced to improve the algorithm and further enhance its search performance.Combined with the dataset,the results obtained by analyzing the algorithm performance with Matlabshow that the algorithm proposed in this article has significantly improved the quality of solutions compared to classical algorithms for solving DVRP.

关 键 词：动态车辆路径问题 K-MEANS聚类 蜣螂优化算法 2-opt算子 relocate算子 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]