Improved genetic algorithm for vehicle routing problem with time window
Weiguo Fang · Computer Engineering and Applications Journal · 2010
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.