El problema del agente viajero: un algoritmo determinístico usando búsqueda tabú

Se implementa un algoritmo correspondiente al método Búsqueda Tabú, llamado EraDeterminístico, experimentado con el algoritmo básico que explora el espacio de búsqueda e incorporando la diversificación como estrategia para explorar nuevas regiones. El algoritmo se desarrolla en el ambiente de progr...

Descripción completa

Detalles Bibliográficos
Autores principales:	López, Erasmo, Salas, Oscar, Murillo, Álex
Formato:	Online
Idioma:	spa
Publicado:	Universidad de Costa Rica, Centro de Investigación en Matemática Pura y Aplicada (CIMPA) 2014
Acceso en línea:	https://revistas.ucr.ac.cr/index.php/matematica/article/view/14142

id	RMTA14142
record_format	ojs
spelling	RMTA141422022-01-28T16:32:29Z The traveling salesman problem: a deterministic algorithm using tabu search El problema del agente viajero: un algoritmo determinístico usando búsqueda tabú López, Erasmo Salas, Oscar Murillo, Álex tabu search deterministic algorithm frequencies matrix diversification permutation traveling salesman problem búsqueda tabú algoritmo determinístico matriz de frecuencias diversificación problema del agente viajero We implement an algorithm corresponding to the Taboo Search method, called EraDeterministic, experimenting with the basic algorithm that ex- plores the search space and incorporating the diversification as strategy to explore new regions. The algorithm is developed in the programming environment Visual Basic 6.0 and the implementation is aimed at finding close solutions to the optimum of the problem NP−complete of the Sym- metric Traveling Salesman (STS). To test the functionality, the model is compared with some instances of the Travel Salesman Problem Library (TSPLIB), some random instances and applied to three real-life situations. Finally, we present a section with comments and conclusions, that guide us on possible future developments that demonstrate the benefits and the efficiency of the implementation. Se implementa un algoritmo correspondiente al método Búsqueda Tabú, llamado EraDeterminístico, experimentado con el algoritmo básico que explora el espacio de búsqueda e incorporando la diversificación como estrategia para explorar nuevas regiones. El algoritmo se desarrolla en el ambiente de programación Visual Basic 6.0 y la implementación se orienta a encontrar soluciones cercanas a la óptima del problema NP−Completo del Agente Viajero Simétrico (AVS). Para probar la funcionalidad, el modelo se compara con algunas instancias de la Travel Salesman Problem Library (TSPLIB), algunas instancias aleatorias y se aplica a tres situaciones reales. Finalmente, se presenta una sección donde se exponen recomendaciones y conclusiones, las cuales orientan posibles desarrollos futuros de ésta teoría y donde se pone en evidencian las bondades y la eficiencia de la implementación. Universidad de Costa Rica, Centro de Investigación en Matemática Pura y Aplicada (CIMPA) 2014-04-03 info:eu-repo/semantics/article info:eu-repo/semantics/publishedVersion Article application/pdf https://revistas.ucr.ac.cr/index.php/matematica/article/view/14142 10.15517/rmta.v21i1.14142 Revista de Matemática: Teoría y Aplicaciones; Vol. 21 No. 1 (2014): Revista de Matemática: Teoría y Aplicaciones; 127-144 Revista de Matemática: Teoría y Aplicaciones; Vol. 21 Núm. 1 (2014): Revista de Matemática, Teoría y Aplicaciones; 127-144 Revista de Matemática; Vol. 21 N.º 1 (2014): Revista de Matemática, Teoría y Aplicaciones; 127-144 2215-3373 1409-2433 spa https://revistas.ucr.ac.cr/index.php/matematica/article/view/14142/13458 Derechos de autor 2014 Revista de Matemática: Teoría y Aplicaciones
institution	Universidad de Costa Rica
collection	Revista de Matemática: Teoría y Aplicaciones
language	spa
format	Online
author	López, Erasmo Salas, Oscar Murillo, Álex
spellingShingle	López, Erasmo Salas, Oscar Murillo, Álex El problema del agente viajero: un algoritmo determinístico usando búsqueda tabú
author_facet	López, Erasmo Salas, Oscar Murillo, Álex
author_sort	López, Erasmo
description	Se implementa un algoritmo correspondiente al método Búsqueda Tabú, llamado EraDeterminístico, experimentado con el algoritmo básico que explora el espacio de búsqueda e incorporando la diversificación como estrategia para explorar nuevas regiones. El algoritmo se desarrolla en el ambiente de programación Visual Basic 6.0 y la implementación se orienta a encontrar soluciones cercanas a la óptima del problema NP−Completo del Agente Viajero Simétrico (AVS). Para probar la funcionalidad, el modelo se compara con algunas instancias de la Travel Salesman Problem Library (TSPLIB), algunas instancias aleatorias y se aplica a tres situaciones reales. Finalmente, se presenta una sección donde se exponen recomendaciones y conclusiones, las cuales orientan posibles desarrollos futuros de ésta teoría y donde se pone en evidencian las bondades y la eficiencia de la implementación.
title	El problema del agente viajero: un algoritmo determinístico usando búsqueda tabú
title_short	El problema del agente viajero: un algoritmo determinístico usando búsqueda tabú
title_full	El problema del agente viajero: un algoritmo determinístico usando búsqueda tabú
title_fullStr	El problema del agente viajero: un algoritmo determinístico usando búsqueda tabú
title_full_unstemmed	El problema del agente viajero: un algoritmo determinístico usando búsqueda tabú
title_sort	el problema del agente viajero: un algoritmo determinístico usando búsqueda tabú
title_alt	The traveling salesman problem: a deterministic algorithm using tabu search
publisher	Universidad de Costa Rica, Centro de Investigación en Matemática Pura y Aplicada (CIMPA)
publishDate	2014
url	https://revistas.ucr.ac.cr/index.php/matematica/article/view/14142
work_keys_str_mv	AT lopezerasmo thetravelingsalesmanproblemadeterministicalgorithmusingtabusearch AT salasoscar thetravelingsalesmanproblemadeterministicalgorithmusingtabusearch AT murilloalex thetravelingsalesmanproblemadeterministicalgorithmusingtabusearch AT lopezerasmo elproblemadelagenteviajerounalgoritmodeterministicousandobusquedatabu AT salasoscar elproblemadelagenteviajerounalgoritmodeterministicousandobusquedatabu AT murilloalex elproblemadelagenteviajerounalgoritmodeterministicousandobusquedatabu AT lopezerasmo travelingsalesmanproblemadeterministicalgorithmusingtabusearch AT salasoscar travelingsalesmanproblemadeterministicalgorithmusingtabusearch AT murilloalex travelingsalesmanproblemadeterministicalgorithmusingtabusearch
_version_	1811744079082422272

El problema del agente viajero: un algoritmo determinístico usando búsqueda tabú

Ejemplares similares