A Heuristic for the Vehicle Routing Problem with Time Windows

In this paper we propose a heuristic algorithm to solve the Vehicle Routing Problem with Time Windows. Its framework is a smart combination of three simple procedures: the classical k-opt exchanges improve the solution, an ad hoc procedure reduces the number of vehicles and a second objective function drives the search out of local optima. No parameter tuning is required and no random choice is made: these are the distinguishing features with respect to the recent literature. The algorithm has been tested on benchmark problems which prove it to be more effective than comparable algorithms.