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

Improved Hybrid Firefly Algorithm for Solving CVRP

作　　者：白雪媛 张磊 李琳 武文喆 BAI Xue-yuan;ZHANG Lei;LI Lin;WU Wen-zhe(School of Science,Shenyang Aerospace University,Shenyang 110136,China;School of Electronic Information Engineering,Shenyang Aerospace University,Shenyang 110136,China)

机构地区：[1]沈阳航空航天大学理学院,辽宁沈阳110136 [2]沈阳航空航天大学电子信息工程学院,辽宁沈阳110136

出　　处：《计算机技术与发展》2023年第12期207-214,共8页Computer Technology and Development

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

摘　　要：提出一种改进混合萤火虫算法(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具有较好的稳定性和有效性。An improved hybrid firefly algorithm(KM-HFA)is proposed to solve the capacitated vehicle routing problem.It uses K-Means clustering to classify the customers set first,and then constructs the initial solutions,which starts the optimization process of the firefly with a better initial solution,reducing the calculation of the algorithm.In the firefly algorithm,partial matching crossover operator,2H-opt exchange operator,local search operator and mutation operators are introduced to accelerate the convergence speed and improve the ability of the algorithm to jump out of the local optimum.In this paper,94 instances of small-scale and medium-scale data sets are selected for simulation experiments.For 79 instances,the solution obtained by KM-HFA was significantly superior over the hybrid firefly algorithm and CC-CVRP,and the total distance of vehicles driving obtained by KM-HFA is smaller.When KM-HFA calculating 5 groups of small-scale instances:A-n33-k6,A-n37-k6,P-n16-k8,P-n19-k2 and P-n20-k2,KM-HFA gets a better delivery solution than the best-known solution without increasing the number of delivery routes.When KM-HFA calculating the instances P-n22-k8 and P-n23-k8,under the premise that the number of routes is increased by one more than the best-known solution,a solution with a smaller total distance of vehicles is found.Simulation experimental results show that the KM-HFA has good stability and effectiveness.

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

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程] U116.2[自动化与计算机技术—控制科学与工程]