An Incremental Tabu Search Heuristic for the Generalized Vehicle Routing Problem with Time Windows

This paper describes an incremental neighbourhood tabu search heuristic for the generalized vehicle routing problem with time windows. The purpose of this work is to offer a general tool that can be successfully applied to a wide variety of specific problems. The algorithm builds upon a previously developed tabu search heuristic by replacing its neighbourhood structure. The new neighbourhood is exponential in size, but the proposed evaluation procedure has polynomial complexity. Computational results are presented and demonstrate the effectiveness of the approach.