聚类蚁群混合算法求解CVRP
Cluster ant colony hybrid algorithm for solving CVRP
何通尧 1李琳 1郑学东2
作者信息
- 1. 沈阳航空航天大学理学院,沈阳 110136
- 2. 沈阳航空航天大学计算机学院,沈阳 110136
- 折叠
摘要
针对带容量约束的车辆路径问题,提出了一种聚类蚁群混合算法,将车辆路径问题拆分成数个旅行商问题进行求解.首先,改进了蚁群算法中信息素和路径的生成方式,使其能够对车辆路径问题进行有效的拆分求解;然后通过对种群进行分级,加快了蚁群算法的收敛速度,并设置3种邻域搜索算子来避免蚁群算法陷入局部最优;最后,设计了仿真实验对算法的部分参数进行合理设计,选取50个Solomon基准算例对算法进行实验验证.实验结果表明,算法收敛速度快,稳定性较高,求解结果较好.
Abstract
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.
关键词
带容量约束的车辆路径问题/聚类分析/改进蚁群算法/信息素/邻域搜索Key words
vehicle routing problem with capacity constraints/cluster analysis/improved ant colony algorithm/pheromone/neighborhood search引用本文复制引用
基金项目
国家自然科学基金(61972266)
国家自然科学基金(61403260)
辽宁省自然科学基金(2020-MS-233)
辽宁省兴辽英才计划项目(XLYC2002017)
出版年
2024
国家科技期刊平台
NSTL
万方数据