计算机工程与应用 ›› 2012, Vol. 48 ›› Issue (7): 26-29.

• 博士论坛 • 上一篇    下一篇

带时间窗车辆路径问题的文化基因算法

王 君,李 波   

  1. 天津大学 管理与经济学部,天津 300072
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2012-03-01 发布日期:2012-03-01

Memetic algorithm for vehicle routing problem with time windows

WANG Jun, LI Bo   

  1. College of Management and Economics, Tianjin University, Tianjin 300072, China
  • Received:1900-01-01 Revised:1900-01-01 Online:2012-03-01 Published:2012-03-01

摘要: 针对物流配送中带时间窗的车辆路径问题(Vehicle Routing Problem with Time Windows,VRPTW),建立了数学模型,并设计了求解VRPTW的文化基因算法。种群搜索采用遗传算法的进化模式,局部搜索采用禁忌搜索机制,并结合可行邻域结构避免对不可行解的搜索,以提高搜索效率。与单纯的遗传算法和禁忌搜索算法进行对比实验,表明该算法是求解VRPTW的一种有效方法。

Abstract: The Vehicle Routing Problem with Time Windows(VRPTW) is addressed in this paper. A mathematical model is designed and a memetic algorithm is proposed for VRPTW. The pattern of population search is genetic algorithm and the local search used tabu. The feasible neighborhoods are integrated into the algorithm to avoid the search for infeasible solutions, thus it improves search efficiency. Compared with the pure genetic algorithm and the tabu search, computational experiments on Solomon benchmarks show the effectiveness of the proposed memetic algorithm for VRPTW.