Abstract: In the paper，after analyzing genetic algorithm’s limit in detail，it forms a hybrid genetic algorithm to solve vehicle routing problem，which consists of genetic algorithm and tabu search algorithm．The key of the hybrid genetic algorithm is inserting tabu search algorithm into mutation operation and solution determination of genetic algorithm ．It can avoid genetic algorithm’s “premature”convergence effectively．Then it solves the same example with genetic algorithm and the hybrid genetic algorithm，and compares their solutions．The results indicate that the hybrid genetic algorithm has better convergence rate，and its solution is much closer to optimal solution．

Key words: vehicle routing problem, premature, hybrid genetic algorithm, convergence

摘要： 在详细分析遗传算法的局限性的基础上，构造了一种基于遗传算法和禁忌搜索算法相结合的、用于求解车辆路径问题的混合遗传算法。这种混合遗传算法主要是将禁忌搜索算法嵌入到遗传算法中的变异操作与最优解判定之间，可以有效地避免遗传算法易出现“早熟”收敛的问题。然后，分别用混合遗传算法和遗传算法对同一实例进行求解，并对求解结果进行对比分析。结果表明该混合遗传算法的求解结果比遗传算法收敛速度快，更加接近最优解。

关键词: 车辆路径问题, 早熟, 混合遗传算法, 收敛