Abstract: The vehicle routing problem with time windows(VRPTW) cannot be solved effectively by using the existing genetic algorithm, a new stochastic approach called the genetic simulated annealing algorithm (GSAG) is proposed to solve vehicle routing problems and the solution is then compared with that from simulated algorithm. Making full of preventing into local minimization in simulated annealing, GSAG avoids effectively the common defects of early convergence. Results from case studies show that the proposed algorithm has better convergence property and find the optimal or near-optimal solution effectively as well as time and quickly convergence property. So, it is an efficient method for vehicle routing problem.

Key words: vehicle routing problem with time window, genetic algorithm, simulated annealing

摘要： 为了克服现有遗传算法不能有效求解时间窗车辆路径问题的缺陷，提出了一种由遗传算法结合模拟退火算法的混合算法求解该问题，并与遗传算法进行了比较。该算法利用了模拟退火算法具有较强的局部搜索能力的特性，有效地克服了传统遗传算法的“早熟收敛”问题。实验结果表明，该算法具有计算效率高、收敛速度快和求解质量优的特点，是解决车辆路径问题的有效方法。

关键词: 有时间窗的车辆路径问题, 遗传算法, 模拟退火算法