求解带容量约束车辆路径问题的改进遗传算法

Improved genetic algorithm for solving capacitated vehicle routing problem

为解决传统遗传算法求解带容量约束的车辆路径问题时收敛速度慢和局部搜索能力差的问题,对传统遗传算法提出一种改进策略。使用基于贪婪策略的启发式交叉算子加强算法接近最优解的能力,加快算法收敛速度,在变异操作中,引入最近邻搜索算子,缩小基因变异范围,使用单点局部插入算子提高算法的局部优化能力。采用精英选择和轮盘赌法结合的选择策略,保持种群多样性以加强算法的全局搜索能力。实例计算测试表明,与传统遗传算法相比,所提算法求解平均偏差降低了70.25%,求解时间减少了87.41%;与ALNS和AGGWOA算法相比,有更高的求解质量和更好的稳定性。

To solve the shortcomings of low convergence speed and poor local search ability when traditional genetic algorithm solves the vehicle routing problem with capacity constraints,an improved strategy for traditional genetic algorithm was proposed.The heuristic crossover operator based on the greedy strategy was used to enhance the ability of the algorithm to approach the optimal solution.In the mutation operation,the nearest neighbor search operator was introduced to narrow the range of gene mutation,and the single-point local insertion operator was used to improve the local optimization ability of the algorithm.A selection strategy combining elite selection and roulette method was adopted to maintain the diversity of the population and strengthen the global search ability of the algorithm.Example calculation test shows that compared with the traditional genetic algorithm,the average deviation of the solution is reduced by 70.25%,and the solution time is reduced by 87.41%.Compared with the ALNS and AGGWOA algorithms,it has higher solution quality and better stability.