A hybrid search based on genetic algorithms and Tabu search for vehicle routing

摘要

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 experiments 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.