Experimental analysis of heuristics for the bottleneck traveling salesman problem
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.
Keywords: Traveling salesman problem, bottleneck TSP, experimental analysis, maximum scatter TSP
Category 1: Combinatorial Optimization
Category 2: Combinatorial Optimization (Other )
Citation: Reserch report, Department of Mathematics, SFU, 2010.
Entry Submitted: 01/08/2010
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|