Título: Estructura de datos para acelerar la búsqueda de subconjuntos en el labeling para TSP Time-Dependent
Director: Francisco Soulignac
Jurados: Min Chih Lin y Gonzalo Lera Romero

RESUMEN
El problema del viajante de comercio con ventanas de tiempo y dependencia temporal (TDTSPTW) es una versión del TSP donde los tiempos de viaje varían a lo largo del horizonte de planificación para simular los efectos de la congestión. Este problema tiene aplicaciones directas a la planificación de entregas directo al consumidor en grandes ciudades, donde la congestión de tránsito es un aspecto predominante. En esta tesis, analizamos una solución exacta con programación dinámica del estado del arte para este problema y proponemos una mejora en su tiempo de ejecución basada en una nueva estructura de datos. La ventaja de esta estructura de datos es que permite buscar eficientemente elementos indexados por conjuntos, cuando se busca aquellos índices contenidos por un conjunto de búsqueda. Se realizaron experimentos computacionales para determinar su rendimiento y se logró demostrar la efectividad de la mejora.