Título: Mejoras algorítmicas al problema de minimización de la duración de rutas
Director: Francisco Soulignac
Jurados: Gonzalo Lera Romero y Agustín Pecorari

RESUMEN
En este trabajo estudiamos el problema de minimización de duración de
rutas (MTDP), una variante del problema del viajante de comercio en la
que un vehículo desea visitar a todos los clientes de un conjunto una
única vez. Los clientes tienen ventanas de tiempo asignadas a cada
uno. El vehículo puede llegar antes de la apertura de un cliente y
esperar, pero si se llega después del final de una de estas ventanas,
la ruta realizada se considera inválida. El objetivo de este problema
es minimizar el tiempo de viaje incluyendo la espera. Esto lo
diferencia de otra variante conocida como problema de viajante de
comercio con ventanas de tiempo con objetivo travel time. En dicha
variante se quiere minimizar la suma de los tiempos de viaje entre
clientes, asumiendo salida del vehículo en el instante inicial. La
diferencia entre ambos problemas es significativa considerando que en
el MTDP el instante de salida pasa a ser otra variable.

Para resolver este problema proponemos un algoritmo exacto iterativo
que alterna entre generar columnas y prohibir rutas que no sean
elementales. Más específicamente, usamos técnicas de generación de
columnas con relajación ng, y un algoritmo de pricing que busca rutas
de costo mínimo mediante backtracking con búsqueda bidireccional y
reglas de dominación. También agregamos la técnica de variable fixing
para eliminar rutas subóptimas. Estos aportes resultan significativos
puesto que obtenemos resultados mejores que los observados en el
estado del arte. Para probar el algoritmo se utilizó un conjunto de
720 instancias, de las cuales 360 se consideran de dificultad. Se
compararon los resultados obtenidos contra los del estado del arte. Se
lograron resolver 25 nuevas instancias y se mejoraron los tiempos de
353 instancias difíciles.