Keywords
deterministic algorithm
frequencies matrix
diversification
permutation
traveling salesman problem
búsqueda tabú
algoritmo determinístico
matriz de frecuencias
diversificación
problema del agente viajero
How to Cite
Abstract
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.
References
Baez, A. (2009) “Problema del agente viajero usando búsqueda tabú”. Proyecto Final, Programación Cientifica, Universidad Autónoma de Nuevo León, Monterrey. Disponible en: http://es.scribd.com/doc/41965624/Busqueda-Tabu-Problema-delagente-viajero-Angels-Baez-Olvera, consultado el 09-Ago-2012, 11:30 a.m.
Barros, H.J. (2005) “Optimización de ruteo de vehículos empleando búsqueda tabú”. Memos de Investigación, Ingeniería Civil y Ambiental, Universidad de los Andes, Bogotá.
De los Cobos, S.; Goddard, J.; Gutiérrez, M.; Martínez, A. (2010) Búsqueda y Exploración Estocástica. Universidad Autónoma Metropolitana, México D.F.
Franco, J.; Toro, E.; Gallego, R. (2008) “Problema de asignación óptima de los salones resuelto con búsqueda tabú”, Revista Ingeniería & Desarrollo 24: 149–175.
Glover, F.; Melián, B. (2003) “Búsqueda tabú”, Revista Iberoamericana de Inteligencia Artificial 19: 29–48.
López, C.A.; Mendoza, J.A.; Cuartas, E. (2008) “Algoritmo para la exploración de todos los valores posibles en el problema del agente viajero (TSP)”, Scientia et Technica 14(39): 399–403.
López, E. (2011) El Agente Viajero: Un Algoritmo Determinístico. Tesis de Licenciatura en Matemática, Universidad Nacional, Heredia, Costa Rica.
Reinelt, G. (2004) “TSPLIB, Travelling salesman problem”, Universität Heidelberg, en: http://www.iwr.uni- heidelberg.de/groups/comopt/software/TSPLIB95.
Soto, D.; Soto, W.; Pinzón, Y. (2008) “ Una metaheurística híbrida aplicada a un problema de planificación de rutas”. Revista Avances en Sistemas e Informática 5(3): 135–145.