A threshold accepting heuristic with intense local search for the solution of special instances of the traveling salesman problem

In real life scheduling, variations of the standard traveling salesman problem are very often encountered. The aim of this work is to present a new heuristic method for solving three such special instances with a common approach. The proposed algorithm uses a variant of the threshold accepting method, enhanced with intense local search, while the candidate solutions are produced through an insertion heuristic scheme. The main characteristic of the algorithm is that it does not require modifications and parameter tuning in order to cope with the three different problems. Computational results on a variety of real life and artificial problems are presented at the end of this work and prove the efficiency and the ascendancy of the proposed method over other algorithms found in the literature. (c) 2005 Elsevier B.V. All rights reserved.