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

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

0.00 Avg rating0 Votes
Article ID: iaor19992660
Country: Netherlands
Volume: 104
Issue: 1
Start Page Number: 113
End Page Number: 128
Publication Date: Jan 1998
Journal: European Journal of Operational Research
Authors: ,
Keywords: heuristics
Abstract:

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 à 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.

Reviews

Required fields are marked *. Your email address will not be published.