Fast local searches for the vehicle routing problem with time windows

The purpose of this paper is to present new deterministic local searches for solving the vehicle routing problem with time windows. The proposed algorithms are based on a new three-phase approach. In the first phase an initial solution is created with one of the two proposed route construction heuristics. In the second phase a special local search operator based on ejection chains is used to reduce the number of routes. Finally, in the third phase well-known Or-opt exchanges are used to minimize the total distance of the routes. The findings of computational experiments indicate that the proposed methods are competitive with the best approaches proposed earlier in the literature in terms of solution quality, while being much faster. Moreover, the proposed algorithms may easily be used to create initial solutions for a wide variety of vehicle routing algorithms.