An empirical study of a new metaheuristic for the traveling salesman problem

We present a deceptively simple, yet empirically powerful metaheuristic, called jump search, for solving traveling salesman problems that has been found to be more effective than tabu search on both random and benchmark test problems from the literature. While the underlying philosophy of jump search — applying local search from different starting points — has been discussed in the literature previously (using random starting points), the use of construction-based heuristic solutions has heretofore not been considered. Extensive empirical analysis shows the method to be surprisingly effective vis a vis a randomized strategy and in comparison with tabu search. The approach is quite robust and suggests that a systematic search among neighborhoods of good, not random, solutions provides distinct advantages. This suggests that further research be focused on better construction heuristics and hybrid schemes that incorporate jump search in, for example, tabu search.