变邻域退火算法在CVRPTW中的研究  

VNS-annealing Algorithm for CVRPTW

作　　者：王仁民[1] 闭应洲[1,2] 刘阿宁[1] 李杰[1] 

机构地区：[1]广西师范学院计算机与信息工程学院,广西南宁530004 [2]武汉大学软件工程国家重点实验室,武汉430072

出　　处：《广西师范学院学报（自然科学版）》2012年第2期88-93,共6页Journal of Guangxi Teachers Education University(Natural Science Edition)

摘　　要：针对传统单一启发式方法解决VRP(Vehicle Routing Problem)问题解质量不高的问题,提出一种新的混合算法。该混合算法以随机近邻启发算法作为初始解,结合嵌入"退火机制"的变邻域VNS(Variable Neighbour Search)搜索算法解决车辆路径问题。实验结果表明,改进算法收敛速度较快,且解决了变邻域搜索易陷入局部最优的问题。When VRP （vehicle routing problem） is solved with the traditional single method, the qual- ity of the results is usually low, so this paper presents a novel hybrid-heuristic algorithm. Firstly, the initial solution is generated with the nearest neighbor heuristic algorithm, then it is improved with VNS- -An- nealing algorithm. Experimental results show that the hybrid algorithm can solve the VRP effectively and efficiently.

关 键 词：车辆路径问题 近邻启发式算法 退火机制 变邻域搜索算法 

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