Título: Un algoritmo exacto para TDTSPD-D, el problema del viajante de comercio con dron dependiente del tiempo
Director: Francisco Soulignac
Jurados: Isabel Méndez Díaz y Federico Pousa

RESUMEN
El rápido crecimiento de las plataformas de e-commerce motiva a resolver eficientemente la etapa final de la logística, conocida como
última milla. Estos problemas pueden modelarse como problemas de ruteo de vehículos (VRP) que consisten en atender de manera óptima un
conjunto de clientes utilizando una flota de camiones. Una estrategia interesante para resolver este problema dentro de ciudades es
considerar utilizar drones para distribuir paquetes, dado que no están limitados a la red vial. En este trabajo proponemos un algoritmo
exacto para el problema de viajante de comercio con dron dependiente del tiempo (TDTSP-D), una variante de VRP donde, en vez de una flota
de camiones contamos con un dron y un camión para atender a los clientes, y donde el tiempo de viaje del camión en vez de ser una
constante, es una función que depende del momento de partida.
Describimos dicho algoritmo, que está basado en un branch-and-price para TSP-D, y explicamos los cambios que fueron necesarios aplicar
para poder lidiar con dependencia en el tiempo. Contamos diversas mejoras que realizamos sobre nuestro algoritmo inicial, aprovechando
las particularidades del nuevo problema. Realizamos también una comparativa de la solución TDTSP-D contrastándola con la solución
TSP-D, notando qué propiedades dejan de valer y provocan que el problema se torne más complejo, y midiendo el impacto que tiene la
dependencia en el tiempo sobre la calidad de las soluciones y la cantidad de instancias que son capaces de resolver los algoritmos.