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

Improved genetic algorithm for solving capacitated vehicle routing problem

作　　者：徐伟华[1] 邱龙龙 张根瑞 魏传祥 XU Wei-hua;QIU Long-long;ZHANG Gen-rui;WEI Chuan-xiang(College of Transportation Engineering,Kunming University of Science and Technology,Kunming 650000,China)

机构地区：[1]昆明理工大学交通工程学院,云南昆明650000

出　　处：《计算机工程与设计》2024年第3期785-792,共8页Computer Engineering and Design

基　　金：国家自然科学基金项目(71961012)。

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

关 键 词：遗传算法 车辆路径问题 贪婪策略 交叉算子 最近邻搜索 局部优化 精英选择 

分 类 号：TP391.9[自动化与计算机技术—计算机应用技术]