Regresar

Estudio de Algoritmos Genéticos para la Optimización de Rutas.

Abstract:

El método utilizado para la optimización es uno de los factores que pueden influir en el tiempo de respuesta para encontrar la mejor ruta, y por tanto en su eficiencia. Este problema es todavía más acentuado en el caso de rutas que tienen redes con un gran número de nodos. Para estas redes grandes y en las que el tiempo de respuesta es importante, la utilización de algoritmos clásicos de optimización de rutas, ha quedado obsoleta debido a la alta complejidad computacional de los mismos. Es por ello que surgen nuevas alternativas a estos métodos, como la utilización de algoritmos que permitan explorar varias soluciones a la vez, con el fin de obtener mejores resultados. Un tipo de algoritmo apropiado para este tipo de problemas de optimización son los algoritmos genéticos, que reciben este nombre pues su ejecución está basada en la evolución natural descrita por Darwin en el siglo XIX. En este proyecto de investigación se ha desarrollado un demo que permite la demostración de la utilización de un algoritmo genético para la optimización de rutas, es decir encontrar la mejor ruta entre dos puntos de una red de nodos con determinadas condiciones iniciales, simulando una red vehicular. La presentación del demo es uno de los objetivos de la investigación, otro de los objetivos es aumentar el conocimiento sobre los algoritmos genéticos para la optimización en el sector de TI y sobre todo a las futuras generaciones de estudiantes de la universidad de Guayaquil. El algoritmo genético utilizado para la demostración es el Algoritmo Genético del Ciervo, propuesto por José Luis Gahete Díaz. Para las pruebas realizadas al algoritmo genético del ciervo se tomaron como muestra un grupo de compañías que se dedica al transporte de carga liviana en camionetas y camiones de la ciudad de Guayaquil.