Palabras clave
deterministic algorithm
frequencies matrix
diversification
permutation
traveling salesman problem
búsqueda tabú
algoritmo determinístico
matriz de frecuencias
diversificación
problema del agente viajero
Cómo citar
Resumen
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.
Citas
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.