关键词: 车辆路径优化问题, 模拟退火算法, 多约束耦合求解, 邻域变换

Abstract: To solve the Capacitated Vehicle Routing Problem (CVRP),an improved simulated annealing algorithm with the tempering operation was presented .Based on the characteristic analysis of route optimization under multiple constraints,the solution framework of simulated annealing operation with simple structure and independent functional modules was constructed,which could facilitate the coupling of relevant constraints and algorithms.Under the arithmetic framework,the acceptance rules for the better solution were altered,and the balance between global searching and local searching was achieved through the tempering operation.A compulsory random neighborhood transformation strategy was designed to improve the quality of new solution generation under multiple constraints.The entire algorithm was constructed by combining the initial solution method.Simulation results on classic benchmarks with different types demonstrated the effectiveness of the presented algorithm.This study of the corresponding solution framework and optimization method could provide a reference for the relevant multi-constraint coupling solution.

Key words: vehicle routing problem, simulated annealing algorithm, multi-constraint coupling solution, neighborhood search