Título: Algoritmos exactos para el problema de ruteo de vehéculos con ventanas de tiempo sobre road networks
Directores: Gonzalo Lera-Romero y Juan José Miranda Bront
Jurados: Francisco Soulignac e Ivo Koch

Resumen:
En este trabajo estudiamos el problema de ruteo de vehículos con ventanas de tiempo y capacidad sobre grafos road-network. Estos grafos proponen una representación más directa de la red de calles y caminos subyacente que permite modelar ciertos fenómenos de la realidad más fielmente, en contraposición a la representación típica de grafos completos usualmente empleada para estos problemas. Desarrollamos un algoritmo Branch & Price donde resolvemos la generación de columnas mediante algoritmos de Labeling, de los cuales implementamos distintas variantes y heurísticas. También proponemos e implementamos un nuevo esquema de branching y lo comparamos con el encontrado en la literatura, obteniendo muy buenos resultados mediante una extensa experimentación computacional.