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

Improved Tabu Search Algorithm for Solving CVRP Problem

作　　者：李佳慧 姜志侠[1] LI Jia-hui;JIANG Zhi-xia(School of Science,Changchun University of Science and Technology,Changchun 130022)

机构地区：[1]长春理工大学理学院,长春130022

出　　处：《长春理工大学学报（自然科学版）》2021年第2期124-128,共5页Journal of Changchun University of Science and Technology(Natural Science Edition)

基　　金：国家自然科学基金资助项目(51378076)。

摘　　要：改进了禁忌搜索算法,用于解决带有容量限制的车辆路径问题(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.

关 键 词：车辆路径问题 容量限制 禁忌搜索算法 I&D搜索策略 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]