改进禁忌搜索算法求解CVRP问题

Improved Tabu Search Algorithm for Solving CVRP Problem

改进了禁忌搜索算法,用于解决带有容量限制的车辆路径问题(CVRP)。该算法在标准禁忌搜索算法的基础上,采用了I&D搜索策略,给出了两种作用于局部最优解的变异算子来扩大搜索区域,并设计了一种CVRP问题的初始解的产生方式。改进后的算法克服了标准禁忌搜索算法对初始解的依赖较强的缺陷,减小了算法在搜索过程中陷入局部最优的可能,提高了算法的搜索质量与效率。

In this paper,the tabu search algorithmwasimproved to solve the Capacitated VehicleRouting Problem(CVRP).Based on the standard tabu search algorithm,the I&D search strategywasused inthisimproved algorithm.It gives two mutation operators that the local optimal solution wasacted on to expand the search area;and a method was designed for generating the initial solution of the CVRP problem.The improved algorithm overcomes the shortcomings of standard tabu search algorithms that rely heavily on the initial solution,reduces the possibility of the algorithm falling into a local optimum during the search process and improves the search quality and efficiency of the algorithm.