改进混合萤火虫算法求解 CVRP-《计算机技术与发展》

文章信息/Info

作者:: 白雪媛¹ ; 张磊¹ ; 李琳¹ ; 武文喆²; 1. 沈阳航空航天大学理学院,辽宁沈阳 110136;
2. 沈阳航空航天大学电子信息工程学院,辽宁沈阳 110136

Author(s):: BAI Xue-yuan1 ; ZHANG Lei1 ; LI Lin1 ; WU Wen-zhe2; 1. School of Science,Shenyang Aerospace University,Shenyang 110136,China;
2. School of Electronic Information Engineering,Shenyang Aerospace University,Shenyang 110136,China

Keywords:: capacitated vehicle routing problem; improved hybrid firefly algorithm; K-Means clustering; local search operator; crossoverand mutation operators

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

Abstract:: 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 thefirefly 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 improvethe ability of the algorithm to jump out of the local optimum. In this paper,94 instances of small-scale and medium-scale data sets areselected for simulation experiments. For 79 instances,the solution obtained by KM-HFA was significantly superior over the hybrid fireflyalgorithm and CC-CVRP,and the total distance of vehicles driving obtained by KM- HFA is smaller. When KM- HFA calculating 5groups 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 solutionthan the best-known solution without increasing the number of delivery routes. When KM-HFA calculating the instances P-n22-k8 andP-n23-k8,under the premise that the number of routes is increased by one more than the best-known solution,a solution with a smallertotal distance of vehicles is found. Simulation experimental results show that the KM-HFA has good stability and effectiveness.