A Hybrid Search based on Genetic Algorithms and Tabu Search for Vehicle Routing

B.M. Ombuki (Canada), M. Nakamura and M. Osamu (Japan)


genetic algorithms, tabu search, meta-heuristic, Vehicle routing problem, combinatorial optimization


We present a hybrid search technique based on meta heuristics for approximately solving the vehicle routing problem with time windows (VRPTW). The approach is two phased; a global customer clustering phase based on genetic algorithms (GAs) and a post-optimization local search technique based on tabu search (TS). We also devise a new crossover operator for the VRPTW and compare its performance with two well-known crossover operators for VRPTW and related problems. Computational experi ments show that the GA is effective in setting the number of vehicles to be used while the tabu search is better suited for reducing the total number of distance traveled by the vehicles. Through our simulations, we conclude that the hybrid search technique is more suitable for the multi-objective optimization for the VRPTW than applying either the GA or tabu search independently.

Important Links:

Go Back