Experimental analysis of heuristics for the bottleneck traveling salesman problem

Experimental analysis of heuristics for the bottleneck traveling salesman problem

0.00 Avg rating0 Votes
Article ID: iaor20123916
Volume: 18
Issue: 3
Start Page Number: 473
End Page Number: 503
Publication Date: Jun 2012
Journal: Journal of Heuristics
Authors: , ,
Keywords: heuristics
Abstract:

In this paper we develop efficient heuristic algorithms to solve the bottleneck traveling salesman problem (BTSP). Results of extensive computational experiments are reported. Our heuristics produced optimal solutions for all the test problems considered from TSPLIB, JM‐instances, National TSP instances, and VLSI TSP instances in very reasonable running time. We also conducted experiments with specially constructed ‘hard’ instances of the BTSP that produced optimal solutions for all but seven problems. Some fast construction heuristics are also discussed. Our algorithms could easily be modified to solve related problems such as the maximum scatter TSP and testing hamiltonicity of a graph.

Reviews

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