改进混合萤火虫算法求解 CVRP

来源：计算机技术与发展杂志2023年第12期北京时间：

作者：白雪媛;张磊;李琳;武文喆

单位：1. 沈阳航空航天大学 理学院,辽宁 沈阳 110136;2. 沈阳航空航天大学 电子信息工程学院,辽宁 沈阳 110136

摘要：提出一种改进混合萤火虫算法( KM-HFA)来解决带容量约束的车辆路径问题。 该算法利用 K-Means 聚类方法将客户集先进行分类,再构建初始解,以较好的初始解开始萤火虫算法的寻优过程,减少了算法的计算量。 在萤火虫算法中引入部分匹配交叉算子,2H-opt 交换算子,局部搜索算子和变异算子,这些方法加快了算法的收敛速度,提高了萤火虫算法跳出局部最优的能力。 选取小规模及中规模数据集进行仿真实验,共 94 组标准算例。 对于 79 组实例,KM-HFA 得到的解优于对照的混合萤火虫算法和 CC-CVRP 所得的求解方案,KM-HFA 所求方案的车辆行驶总距离更小。 KM-HFA 计算了 5 组小规模实例,即 A-n33-k6,A-n37-k6,P-n16-k8,P-n19-k2 和 P-n20-k2,在不增加车辆配送路径数目的情况下,得到比经典解更好的配送方案。 对于实例 P-n22-k8 和 P-n23 -k8,文中算法在比经典解路径数增加了一条的前提下,找到了车辆行驶总距离更小的解。 仿真实验结果表明 KM-HFA 具有较好的稳定性和有效性。

关键词：带容量约束车辆路径问题;改进混合萤火虫算法;K-Means 聚类;局部搜索算子;交叉和变异算子