聚类蚁群混合算法求解CVRP  

Cluster ant colony hybrid algorithm for solving CVRP

作　　者：何通尧 李琳 郑学东 HE Tongyao;LI Lin;ZHENG Xuedong(College of Science,Shenyang Aerospace University,Shenyang 110136,China;College of Computer Science,Shenyang Aerospace University,Shenyang 110136,China)

机构地区：[1]沈阳航空航天大学理学院,沈阳110136 [2]沈阳航空航天大学计算机学院,沈阳110136

出　　处：《沈阳航空航天大学学报》2024年第1期90-96,共7页Journal of Shenyang Aerospace University

基　　金：国家自然科学基金(项目编号:61972266,61403260);辽宁省自然科学基金(项目编号:2020-MS-233);辽宁省兴辽英才计划项目(项目编号:XLYC2002017)。

摘　　要：针对带容量约束的车辆路径问题,提出了一种聚类蚁群混合算法,将车辆路径问题拆分成数个旅行商问题进行求解。首先,改进了蚁群算法中信息素和路径的生成方式,使其能够对车辆路径问题进行有效的拆分求解;然后通过对种群进行分级,加快了蚁群算法的收敛速度,并设置3种邻域搜索算子来避免蚁群算法陷入局部最优;最后,设计了仿真实验对算法的部分参数进行合理设计,选取50个Solomon基准算例对算法进行实验验证。实验结果表明,算法收敛速度快,稳定性较高,求解结果较好。A clustering ant colony hybrid algorithm was proposed for the vehicle routing problem with capacity constraints,which divided the vehicle routing problem into several traveling salesman prob‐lems for solution.Firstly,the generation method of pheromones and paths in the ant colony algorithm was improved to effectively split and solve the vehicle routing problem;Then,by grading the popula‐tion,the convergence speed of the ant colony algorithm was accelerated,and three neighborhood search operators were set to avoid the ant colony algorithm falling into local optima;Finally,simula‐tion experiments were designed to reasonably design some parameters of the algorithm,and 50 Solo‐mon benchmark examples were selected for experimental verification of the algorithm.The experimen‐tal results show that the algorithm proposed in this paper has fast convergence speed,high stability,and good solution results.

关 键 词：带容量约束的车辆路径问题 聚类分析 改进蚁群算法 信息素 邻域搜索 

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