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

Vista sencilla de ítem
dc.contributor.advisorBravo Bastidas, Juan José
dc.contributor.advisorOrejuela Cabrera, Juan Pablo
dc.contributor.authorOsorio Catañeda, César David
dc.date.accessioned2021-08-17T16:11:38Z
dc.date.available2021-08-17T16:11:38Z
dc.date.issued2021
dc.description.abstractEl 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.spa
dc.description.degreelevelMaestríaspa
dc.description.degreenameMAGISTER EN INGENIERÍA ÉNFASIS INGENIERÍA INDUSTRIALspa
dc.format.extent1 recurso en línea (80 páginas)spa
dc.format.mimetypeapplication/pdfspa
dc.identifier.urihttps://hdl.handle.net/10893/21143
dc.language.isospaspa
dc.publisherUniversidad del Vallespa
dc.publisher.facultyFACULTAD DE INGENIERÍAspa
dc.publisher.placeColombiaspa
dc.publisher.programMAESTRÍA EN INGENIERÍA-ÉNFASIS INGENIERÍA INDUSTRIALspa
dc.rights.accessrightsinfo:eu-repo/semantics/openAccessspa
dc.subject.ddcAlgoritmos genéticos
dc.subject.ddcRed de Petri
dc.subject.ddcAutomatización
dc.subject.ddcOptimización combinatoria
dc.subject.ddcProgramación lineal entera
dc.subject.ddcVendedores ambulantes
dc.subject.ddcLogística industrial
dc.titleIntegración de algoritmos genéticos y redes de Petri como propuesta metodológica para la solución del time-dependent traveling Salesm problem.spa
dc.typeTrabajo de grado - Pregradospa
dc.type.coarhttp://purl.org/coar/resource_type/c_7a1fspa
dc.type.contentTextspa
dc.type.driverinfo:eu-repo/semantics/bachelorThesisspa
dc.type.redcolhttps://purl.org/redcol/resource_type/TPspa
dc.type.versioninfo:eu-repo/semantics/publishedVersionspa
dspace.entity.typePublication
oaire.accessrightshttp://purl.org/coar/access_right/c_abf2spa
oaire.versionhttp://purl.org/coar/version/c_970fb48d4fbd8a85spa
Archivos
Bloque original
Mostrando 1 - 1 de 1
Miniatura
Nombre:
Integración-Algoritmos-Genéticos-Osorio-Cesar-7716-O83i.pdf
Tamaño:
2.01 MB
Formato:
Adobe Portable Document Format
Descripción:
Descargar
Bloque de licencias
Mostrando 1 - 1 de 1
No hay miniatura disponible
Nombre:
license.txt
Tamaño:
14.48 KB
Formato:
Item-specific license agreed upon to submission
Descripción:
Descargar
Colecciones
Maestría en Ingeniería - Énfasis en Ingeniería Industrial