An iterative insertion algorithm and a hybrid meta heuristic for the traveling salesman problem with time windows

This paper presents a heuristic algorithm for the traveling salesman problem with time windows (TSPTW). An iterative insertion algorithm as a constructive search heuristic and a hybrid meta heuristic combining simulated annealing and tabu search with the randomized selection of 2-interchange and a simple move operator as an improving search heuristic are proposed. Computational tests performed on 400 benchmark problem instances show that the proposed algorithm generates optimal or near-optimal solutions in most cases. New best known heuristic values for many benchmark problem sets were obtained using the proposed approach.