Tesis profesional presentada por David Palacios Somohano

Licenciatura en Ingeniería en Sistemas Computacionales. Departamento de Ingeniería en Sistemas Computacionales. Escuela de Ingeniería, Universidad de las Américas Puebla.

Jurado Calificador

Presidente: Dr. Mauricio Javier Osorio Galindo
Vocal y Director: Mtra. Carolina Yolanda Castañeda Roldán
Secretario: Dr. Solon Javier Garcés Eisele

Cholula, Puebla, México a 21 de noviembre de 2003.

Resumen

A partir de la inquietud de complementar la herramienta "Técnicas de Solución al PAV", desarrollada por el grupo Ku-Pachaloti, se desarrolló la implementación de un método de solución aproximada para la solución del Problema del Agente Viajero (PAV). El método, llamado Híbrido MST-2Opt, es una combinación del método MST-Preorden con el método 2Opt. Este método híbrido obtiene una solución aproximada para el PAV.

El híbrido parte de un grafo completo, por medio del Algoritmo de Prim se obtiene un árbol de expansión mínima. Este árbol es leido en preorden, y con esta lectura se tiene un circuito Hamiltoniano que sirve como circuito inicial para el algoritmo 2Opt. Este algoritmo busca una optimización del circuito provisto. Todo esto se realiza en tiempo polinomial. Con esto es posible conseguir un circuito, de buena aproximación, para la solución del PAV.

La evaluación del desempeño del híbrido fue realizada empíricamente. Esto se logró por medio de comparaciones contra otros métodos de solución. Se compararon tanto las soluciones como los tiempos de ejecución registrados por cada método. Con esto se logró demostrar empíricamente que el Híbrido MST-2Opt es un buen método de solución aproximada para el PAV.

Índice de contenido

Capítulo 1. Introducción (archivo pdf, 91 kb)

  • 1.1 Objetivo general
  • 1.2 Objetivos específicos

Capítulo 2. Marco Teórico (archivo pdf, 1015 kb)

  • 2.1 Grafos
  • 2.2 Árboles
  • 2.3 Algoritmo de Prim
  • 2.4 Preorden
  • 2.5 Problema del Agente Viajero
  • 2.6 Algoritmos exactos y aproximados
  • 2.7 Dos-Optimal o 2Opt
  • 2.8 PAV con la desigualdad del triángulo
  • 2.9 Híbrido MST-2Opt
  • 2.10 Interacción Humano-Computadora

Capítulo 3. Análisis y diseño del sistema (archivo pdf, 203 kb)

  • 3.1 Análisis del sistema
  • 3.2 Diseño del sistema
  • 3.3 Pruebas de defectos

Capítulo 4. Implementación del sistema (archivo pdf, 118 kb)

  • 4.1 Herramienta empleada
  • 4.2 Implementación del método
  • 4.3 Funcionamiento del sistema

Capítulo 5. Pruebas (archivo pdf, 203 kb)

  • 5.1 Generación de casos de prueba y ejecución de algoritmos
  • 5.2 Comparación de resultados obtenidos

Capítulo 6. Conclusiones (archivo pdf, 81 kb)

  • 6.1 Implementación del Híbrido MST-2Opt
  • 6.2 Evaluación del desempeño del Híbrido MST-2Opt
  • 6.3 Trabajo a futuro

Referencias (archivo pdf, 112 kb)

Apéndice A. Código fuente (archivo pdf, 66 kb)

Apéndice B. Referencia vía correo electrónico (archivo pdf, 59 kb)

Apéndice C. Formato de un archivo de entrada (archivo pdf, 93 kb)

Apéndice D. Archivo de pruebas (archivo pdf, 53 kb)

Apéndice E. Pruebas de aproximados vs exacto (archivo pdf, 53 kb)

Apéndice F. Manual de usuario (archivo pdf, 611 kb)

Palacios Somohano, D. 2003. Híbrido MST-2Opt para la Solución del Problema del Agente Viajero. Tesis Licenciatura. Ingeniería en Sistemas Computacionales. Departamento de Ingeniería en Sistemas Computacionales, Escuela de Ingeniería, Universidad de las Américas Puebla. Noviembre. Derechos Reservados © 2003.