PUMA
Istituto di Scienza e Tecnologie dell'Informazione     
Codenotti B., Margara L. Heuristics for the traveling salesman problem. Internal note IEI-B4-14, 1991.
 
 
Abstract
(English)
This paper presents two heuristics for the Traveling Salesman Problem (TSP) based on a concept borrowed from physics, i.e. the "center of mass". We define a particular notion of center of mass that can be used for "special" graphs. This parameter helps us to extend, step by step, the subsolution that we are building; at the end of this procedure we obtain a solution for the TSP. The algorithms we present run in O(n^2) time and find solutions comparable to the ones obtained by other popular methods (e.g. "cheapest insertion method").
Subject


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