Resumen

En este trabajo se propone el uso del método heurístico de Sistema de Hormigas para resolver el problema del Camino Elemental de Costo Mínimo con Restricción de Capacidad, que es un subproblema de validación ("pricing") a resolver en cada una de las iteraciones de algunos esquemas de generación de columnas utilizados para el problema de ruta de vehículos, para la identificación de nuevas rutas factibles.

Con el fin de resolver este problema se definieron las funciones de aplicación de feromona así como la visibilidad y procesos ambientales para encontrar caminos que sean soluciones de buena calidad.

Los resultados de la implementación de la meta heurística propuesta en este trabajo nos muestran que se encuentran soluciones factibles de calidad con un esfuerzo computacional razonable, sobre todo en las instancias en las que la capacidad es más bien laxa. Además, el esfuerzo computacional tiene un comportamiento aparentemente lineal en comparación con el comportamiento exponencial del algoritmo de programación dinámica con acotamiento bidireccional. Siendo atractivo el utilizar la implementación del Sistema de Hormigas a fin de reducir el tiempo de resolución del problema y hacer más eficiente el proceso iterativo del algoritmo de generación de columnas para la búsqueda de rutas factibles.

Esta tesis sólo puede ser consultada por miembros de la Comunidad Universitaria. (ir al índice de contenido)

Cuanalo Gómez, M. A. 2006. Implementación de la meta heurística de sistema de hormigas para el problema del camino elemental de costo mínimo con restricción de recursos. Tesis Licenciatura. Ingeniería Industrial con área de manufactura. Departamento de Ingeniería Industrial y Mecánica, Escuela de Ingeniería y Ciencias, Universidad de las Américas Puebla. Mayo. Derechos Reservados © 2006.