Integración de algoritmos genéticos y redes de Petri como propuesta metodológica para la solución del time-dependent traveling Salesm problem.

El Time Dependent Traveling Salesman Problem (TDTSP) es una generalización del conocido problema del agente viajero (TSP por sus siglas en ingles), en el que los tiempos de viaje entre un par de nodos depende del instante de tiempo en que dicho viaje se realice. En esta tesis el problema se divide en la exploración de las secuencias de visitas a los nodos, para posteriormente determinar el tiempo de inicio óptimo de dichas rutas. En este sentido se propone un algoritmo híbrido entre algoritmos genéticos y redes de Petri con el que se busca aprovechar, por un lado el buen desempeño de los algoritmos genéticos en problemas combinatorios como el sub-problema de secuenciación de visitas, y por otro lado las ventajas de modelado de las redes de Petri para abordar el sub-problema del manejo temporal del problema. El objetivo fue entonces el diseño del algoritmo híbrido como propuesta metodológica de solución al TDTSP. Se parte de la caracterización del problema desde los elementos conceptuales introducidos por Fox en 1973, hasta formulaciones más recientes y se propone una representación matemática del problema, así como una representación en red de Petri a partir de la cual se diseña una estructura cromosómica que siempre garantice la factibilidad de todas las soluciones exploradas por el algoritmo genético. Para la fase de evaluación del algoritmo se plantean dos ramas: la primera es la optimización del tiempo de inicio a través de programación matemática, y la segunda es el uso de la lógica de simulación de la red de Petri para obtener la función de desempeño a través del control estricto de la evolución del tiempo que brinda esta herramienta. El análisis computacional mostró que la rama de la lógica de simulación de la red de Petri tiene menor costo computacional que la optimización del tiempo de inicio, lo cual se traduce en que un mayor uso de la red de Petri en la fase de evaluación del algoritmo, trae mejoras de hasta un 83% en el costo computacional, sin afectar la calidad de las soluciones. La validación en instancias resalta esa calidad de las soluciones obtenidas con el algoritmo propuesto, y la aplicación en el caso real muestra la flexibilidad de la metodología y el potencial de aplicación en diversos contextos. Estos resultados hacen prever este enfoque como promisorio para trabajos futuros.

• Autores: Osorio Catañeda, César David
• Tipo de recurso: Trabajo de grado de pregrado
• Fecha de publicación: 2021
• Institución: Universidad del Valle
• Repositorio: Repositorio Digital Univalle
• Idioma: spa
• OAI Identifier: oai:bibliotecadigital.univalle.edu.co:10893/21143
• Acceso en línea: https://hdl.handle.net/10893/21143
• Palabra clave: Algoritmos genéticos; Red de Petri; Automatización; Optimización combinatoria; Programación lineal entera; Vendedores ambulantes; Logística industrial
• Rights: openAccess
• License: http://purl.org/coar/access_right/c_abf2