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

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

来源：计算机技术与发展, 2023, 33(12): 207-214.

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

提出一种改进混合萤火虫算法(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具有较好的稳定性和有效性。

• 出版日期2023
• 单位沈阳航空航天大学; 电子信息工程学院