基于自适应大邻域搜索的遗传算法求解VRPTW研究

Genetic Algorithm for Vehicle Routing Problems with Time Windows Based on Adaptive Large Neighborhood Search

针对传统遗传算法在求解带时间窗的车辆路径问题(vehicle routing problems with time window,VRPTW)上存在的易陷入局部最优及求解质量不高等问题,本文主要对基于自适应大邻域搜索的遗传算法求解带时间窗车辆路径问题进行研究。通过将自适应大邻域搜索算法与遗传算法相结合,称为ALNS-GA设计了3个移除算子和2个重插算子,以提高遗传算法的局部搜索能力,并优化了初始种群生成策略。同时,为了验证算法的有效性,分别对比了传统遗传算法和基于大规模邻域搜索的遗传算法(LNS-GA、LNS*-GA),并选取Solomon数据库上VRPTW测试算例,在Matlab R2016b上进行实验验证。实验结果表明,当终止条件为迭代100次时,ALNS-GA的求解质量高于传统遗传算法,大部分案例中,ALNS-GA所求的最好值优于LNS-GA和LNS*-GA,且ALNS-GA平均用时均小于LNS-GA和LNS*-GA,特别是当顾客规模为100时,ALNS-GA的平均用时更少,虽然小部分案例的平均值略高于LNS-GA和LNS*-GA,但从整体上看,ALNS-GA的寻优速度和质量均优于LNS-GA和LNS*-GA,说明经过改进后,遗传算法的局部搜索能力明显提高,可以有效改善遗传算法在带时间窗车辆路径问题上的应用。该研究具有一定的创新。

To address the problems of traditional genetic algorithms in solving vehicle routing problems with time window(VRPTW),which are easy to fall into local optimum and the solution quality is not high,this paper focuses on the genetic algorithm based on adaptive large neighborhood search to solve vehicle routing problems with time window.By combining the adaptive large neighborhood search algorithm with the genetic algorithm,three removal operators and two reinsertion operators are designed as ALNS-GA to improve the local search capability of the genetic algorithm,and the initial population generation strategy is optimized.Meanwhile,to verify the effectiveness of the algorithm,traditional genetic algorithms and genetic algorithms based on large-scale neighborhood search(LNS-GA,LNS*-GA)are compared respectively,and VRPTW test cases on Solomon database are selected for experimental verification on Matlab R2016b.The experimental results show that the solution quality of ALNS-GA is higher than that of traditional genetic algorithms when the termination conditions are both 100 iterations,and the best values found by ALNS-GA are better than those of LNS-GA and LNS*-GA in most cases,and the average time taken by ALNS-GA is smaller than that of LNS-GA and LNS*-GA in all cases.Especially when the customer size is 100,the average time taken by ALNS-GA takes less time on average,and although the average value of a small number of cases is slightly higher than that of LNS-GA and LNS*-GA,on the whole,the speed and quality of ALNS-GA is better than that of LNS-GA and LNS*-GA in the search for the best performance,which indicates that after improvement,the local search ability of genetic algorithm is significantly improved,and it can effectively improve the application of genetic algorithm on vehicle path problems with time windows.The study has some innovations.