Computer Engineering and Applications ›› 2010, Vol. 46 ›› Issue (32): 228-231.DOI: 10.3778/j.issn.1002-8331.2010.32.063

• 工程与应用 • Previous Articles     Next Articles

Improved genetic algorithm for vehicle routing problem with time window

ZHANG Jian-qiang,FANG Wei-guo   

  1. School of Economics and Management,Beihang University,Beijing 100191,China
  • Received:2009-03-31 Revised:2009-05-26 Online:2010-11-11 Published:2010-11-11
  • Contact: ZHANG Jian-qiang



  1. 北京航空航天大学 经济管理学院,北京 100191
  • 通讯作者: 张建强

Abstract: By incorporating Tabu Search(TS) into Genetic Algorithm(GA),an improved genetic algorithm is proposed to solve the classic Vehicle Routing Problem with Time Window(VRPTW).To improve the computational efficiency of GA,a better initial population is generated by using the Push-Forward-Insertion-Heuristics(PFIH) algorithm,and an improved inversion mutation operator is also exploited so that more parents’ excellent performance can be inherited by off-springs.A measure,Hamming distance,is introduced to evaluate individuals’ diversification within populations in GA.Once individuals’ diversification is below a given level,then the algorithm is switched to tabu search.This intends to avoid the drawback of premature in GA,and to obtain a global optimum.Finally,through a numerical example,the superiority of the proposed algorithm is demonstrated.

摘要: 将遗传算法与禁忌搜索结合起来,设计了一种改进的遗传算法求解有时间窗约束车辆路径问题。采用启发式插入算法产生较优良的遗传操作初始种群,通过改进的逆转变异算子更多继承父代的优良性能,以提高遗传算法的计算效率。引入海明距评估遗传进化中种群的多样性。当种群多样性低到一定程度时转入禁忌搜索,以避免遗传算法早熟的缺陷,最终实现全局优化。通过算例验证了该算法的优越性。

CLC Number: