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

VNS-annealing Algorithm for CVRPTW

针对传统单一启发式方法解决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.