Istituto di Scienza e Tecnologie dell'Informazione     
Codenotti B., Margara L. Efficient clustering techniques for the traveling salesman problem. In: International Symposium on Computer and Information Sciences VII. (Antalya, Turkey, 4 - 6 November 1992). Proceedings, pp. 1 - 7. Erol Gelenbe, Ugur Halici, Neşe Ylabik (eds.). Presses de l'EHEI, Université René Descartes, 1992.
This paper presents some direct and iterative heuristic methods for the Traveling Salesman Problem (TSP) based on the notion of mass density. We give a particular definition of mass density, which can be used to construct a tour for the euclidean TSP in an incremental fashion. In the iterative method, this technique is combined with the Lin-Kernighan heuristic, and this allows us to find better solutions than the ones found by using Lin-Kernighan method (1.1 % off the optimum). The direct method presented here runs in O (n∆3) time and finds solutions whose cost is 9.2% off the optimal one.
Subject Clustering

Icona documento 1) Download Document PDF

Icona documento Open access Icona documento Restricted Icona documento Private


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional