自适应遗传灰狼优化算法求解带容量约束的车辆路径问题

带容量约束的车辆路径问题是NP难的组合优化问题，精确算法无法在合理的时间内得到有效的解.本文提出了一种采用灰狼空间整数编码和先路由后分组解决方案生成策略的自适应遗传灰狼优化算法用于求解带容量约束的车辆路径问题.该算法提出了移动平均自适应灰狼更新策略和灰狼基因遗传策略提高全局收敛能力，同时提出带3-opt的劣势点启发邻域搜索策略来增强算法的全局和局部搜索能力.实验结果表明：所提出算法具有较高的计算精度和较强的寻优能力，有较高的鲁棒性，通过与自适应扫描和速度推测粒子群优化算法、K均值聚类和灰狼优化混合算法、大邻域搜索和蚁群优化混合算法、基于精英选择的多种群人工蜂群算法、基于集覆盖的扩展节省算法、混合变邻域生物共栖搜索算法等6个算法对比证明了算法的有效性.

Adaptive Genetic Grey Wolf Optimizer Algorithm for Capacitated Vehicle Routing Problem

Capacitated vehicle routing problem (CVRP) is an NP-hard combinatorial optimization problem.Many CVRP instances cannot be solved by the exact algorithms in a reasonable time.This paper presents an adaptive genetic grey wolf optimizer algorithm (AGGWOA),which implements grey wolf space integer coding and route-first cluster-second solution generation strategy,to solve the capacitated vehicle routing problem.The AGGWOA proposes the adaptive update strategy on moving average and grey wolf genetic operation that improve the global convergence of the algorithm.To enhance the global search ability and the local search ability of the algorithm,the AGGWOA proposes the inferior-node heuristic neighborhood search strategy,which implements the 3-opt local search operation.The experimental results indicate that the algorithm proposed has superior computational accuracy,effective optimization ability and high robustness.The effectiveness of the algorithm proposed is proved by comparing AGGWOA with 6 other algorithms including adaptive sweep plus velocity tentative PSO(Adaptive Sweep + VTPSO),K-means clustering GWO(K-GWO),hybrid large neighbourhood search algorithm with ant colony optimization(LNS-ACO),elitism-based multiple colonies artificial bee colony(EBMC-ABC),set-covering-based extended savings algorithm(SC-ESA),hybrid variable neighborhood symbiotic organisms search(HVNSOS).