Estudio del Espacio de Soluciones del Problema del Cajero Viajante

Pedro Gardel (1), Osvaldo Gómez (1), Benjamín Barán (1)

e-mails: pgardel@cnc.una.py, ogomez@cnc.una.py, bbaran@cnc.una.py

(1) Universidad Nacional de Asunción - Centro Nacional de Computación, San Lorenzo Paraguay

Abstract

The present paper studies the space of solutions of the Traveling Salesman Problem (TSP). Due to the enormous size of the solutions space of the studied problems, it has been decided to take samples with the objective of having a general vision of the problem structure. For this purpose, two policies were used to obtain the samples, one already used in previous studies and the other designed by the authors. For this study, 20 instances of the TSP have been taken from the TSPLIB. The analysis of the results was coherent with the conjecture of a globally convex structure of the TSP’s solutions space. That is, a space that has characteristics of "Great Valley" as it was suggested by Boese and experimentally proved in the present work.

Resumen/Resumo

El presente trabajo estudia el espacio de soluciones del Traveling Salesman Problem (TSP). Debido al enorme tamaño del espacio de soluciones de los problemas estudiados, se ha decidido tomar muestras de los mismos con el objetivo de tener una visión general de su estructura. Para este fin, se utilizaron dos políticas en la obtención de las muestras, una basada en estudios anteriores y otra aquí propuesta por los autores. Se han tomado veinte instancias del TSP de la TSPLIB. El análisis de los resultados obtenidos es congruente en todos los casos con la conjetura de un espacio de soluciones globalmente convexo del TSP. Esto es, un espacio con características de ``Gran Valle" como fuera sugerido por Boese, y verificado experimentalmente en el presente trabajo.

Keywords:Traveling Salesman Problem, Optimización local, Espacio globalmente convexo

Palabras Clave/Palavras Chave: Traveling Salesman Problem, Local Optimization, Globally Convex Space

BibTex

@INPROCEEDINGS{gardel04:249,
                  AUTHOR       = {Pedro Gardel and Osvaldo Gómez and Benjamín Barán},
                  TITLE        = {Estudio del Espacio de Soluciones del Problema del Cajero Viajante},
                  BOOKTITLE    = {30ma Conferencia Latinoamericana de Informática (CLEI2004)},
                  YEAR         = {2004},
                  editor       = {Mauricio Solar and David Fernández-Baca and Ernesto Cuadros-Vargas},
                  pages        = {745--756},
                  address      = {},
                  month        = Sep,
                  organization = {Sociedad Peruana de Computación},
                  note         = {ISBN 9972-9876-2-0},
                  file         = {http://clei2004.spc.org.pe/es/html/pdfs/249.pdf}
}

PDF de este artículo
PDF de CLEI2004 (incluye todos los artículos)
Página principal CLEI 2004
Generado por Sociedad Peruana de Computación