Please use this identifier to cite or link to this item:
Type: Artigo de periódico
Title: On The Performance Of Heuristics On Finite And Infinite Fractal Instances Of The Euclidean Traveling Salesman Problem
Author: Moscato P.
Norman M.G.
Abstract: We show how, by a constructive process, we can generate arbitrarily large instances of the Traveling Salesman Problem (TSP) using standard fractals such as those of Peano, Koch, or Sierpinski. We show that optimal solutions for these TSPs can be known a priori, and thus, they provide us with new nontrivial TSP instances offering the possibility of testing heuristics well beyond the scope of testbed instances which have been solved by exact numerical methods. Furthermore, instances may be constructed with different features, for example, with different fractal dimensions. To four of these fractal TSPs we apply three standard constructive heuristics, namely Multiple Fragment, Nearest Neighbor, and Farthest Insertion from Convex-Hull, which have efficient general-purpose implementations. The ability of different algorithms to solve these different fractal TSPs gives us significant insight into the nature of TSP heuristics in a way which is complementary to approaches such as worst-case or average-case analysis. © 1998 INFORMS.
Rights: fechado
Identifier DOI: 
Date Issue: 1998
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
File Description SizeFormat 
2-s2.0-0004913699.pdf261.86 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.