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

• López, Erasmo ^[3] ; Salas, Oscar ^[1] ; Murillo, Álex ^[2]
  1. [1] Universidad Nacional de Costa Rica

     Universidad Nacional de Costa Rica

     Heredia, Costa Rica

     
  2. [2] Universidad de Costa Rica

     Universidad de Costa Rica

     Hospital, Costa Rica

     
  3. [3] Colegio Técnico Profesional de Upala (CTPU), Upala, Costa Rica.

  Mostrar afiliaciones +
• Localización: Revista de Matemática: Teoría y Aplicaciones, ISSN 2215-3373, ISSN-e 2215-3373, Vol. 21, Nº. 1, 2014, págs. 127-144
• Idioma: español
• DOI: 10.15517/rmta.v21i1.14142
• Títulos paralelos:
  • The traveling salesman problem: a deterministic algorithm using tabu search
• Enlaces
  • Texto completo (pdf)
• Resumen
  • español

    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 Li- brary (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.

  • English

    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. 

• Referencias bibliográficas
  • Baez, A. (2009) “Problema del agente viajero usando búsqueda tabú”. Proyecto Final, Programación Cientifica, Universidad Autónoma de Nuevo...
  • 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 Cobos, S.; Goddard, J.; Gutiérrez, M.; Martínez, A. (2010) Búsqueda y Exploración Estocástica. Universidad Autónoma Metropolitana,...
  • Franco, J.; Toro, E.; Gallego, R. (2008) “Problema de asignación óptima de los salones resuelto con búsqueda tabú”, Revista Ingeniería &...
  • 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...
  • López, E. (2011) El Agente Viajero: Un Algoritmo Determinístico. Tesis de Licenciatura en Matemática, Universidad Nacional, Heredia, Costa...
  • 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...