自适应混合蚁群算法求解带容量约束车辆路径问题

Adaptive Hybrid Ant Colony Optimization for Capacitated Vehicle Routing Problem

针对带容量约束车辆路径问题(capacitated vehicle routing problem,CVRP),提出了一种自适应混合蚁群算法.由蚁群算法生成子回路,为增强跳出局部最优能力,在蚁群算法的状态转移规则和信息素更新规则中引入了自适应机制.基于子回路组合,由遗传算法构造近似解,根据问题编码特性设计了适应度函数和遗传算子,提高了构造效率,并采用Clark和Wright节约算法将近似解修复成可行解.采用扫描法和2-opt局部优化方法提高可行解的质量.标准算例的实验结果表明,该算法在求解CVRP问题上具有良好的寻优精度和寻优效率.灵敏度分析结果表明蚂蚁数量对算法性能具有显著影响.

To solve the capacitated vehicle routing problem(CVRP),an adaptive hybrid ant colony optimization algorithm is proposed.A number of subroutes are obtained using ant colony optimization,and in order to enhance the ability to avoid falling into local optima,adaptive mechanisms are introduced to the rules of pheromone updating and state transferring respectively in ant colony optimization.Based on subroute combining,approximate solutions are constructed using genetic algorithm.According to the characteristics of the encoding scheme,the fitness function and genetic operators are designed to improve construction efficiency.Clarke and Wright savings algorithm is adopted to feasibilize the approximate solutions.Sweep algorithm and 2-opt local search are conducted to enhance the quality of feasible solutions.The experimental results based on standard examples show that the algorithm has good optimization accuracy and efficiency in solving the capacitated vehicle routing problem.Sensitivity analysis results show that the ant quantity has a significant impact on algorithm performance.