交通运输系统工程与信息

交通运输系统工程与信息 ›› 2006, Vol. 6 ›› Issue (6): 49-52 .

• 系统工程理论与方法 • 上一篇    下一篇

基于混合遗传算法的车辆路径问题

卫绍元，王冬梅   

  1. 辽宁工学院 汽车与交通工程学院，锦州121001
  • 收稿日期:2006-08-21 修回日期:1900-01-01 出版日期:2006-12-20 发布日期:2006-12-20

Research in Vehicle Routing Problem Based on Hybrid Genetic Algorithm

WEI Shao-yuan，WANG Dung-mei   

  1. College of Automobile and Transportation Engineering, Liaoning Institute of Technology，Jinzhou 121001，China
  • Received:2006-08-21 Revised:1900-01-01 Online:2006-12-20 Published:2006-12-20

PDF

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

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

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