BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Departamento de Computación - ECPv6.15.18//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:Departamento de Computación
X-ORIGINAL-URL:https://www.dc.uba.ar
X-WR-CALDESC:Eventos para Departamento de Computación
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:America/Sao_Paulo
BEGIN:STANDARD
TZOFFSETFROM:-0300
TZOFFSETTO:-0300
TZNAME:-03
DTSTART:20250101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=America/Sao_Paulo:20260618T140000
DTEND;TZID=America/Sao_Paulo:20260618T150000
DTSTAMP:20260618T125922
CREATED:20260612T141604Z
LAST-MODIFIED:20260612T141604Z
UID:10668-1781791200-1781794800@www.dc.uba.ar
SUMMARY:Defensa Tesis Licenciatura Pablo Zaid
DESCRIPTION:Título: Mejoras algorítmicas al problema de minimización de la duración de rutas\nDirector: Francisco Soulignac\nJurados: Gonzalo Lera Romero y Agustín Pecorari \nRESUMEN\nEn este trabajo estudiamos el problema de minimización de duración de\nrutas (MTDP)\, una variante del problema del viajante de comercio en la\nque un vehículo desea visitar a todos los clientes de un conjunto una\núnica vez. Los clientes tienen ventanas de tiempo asignadas a cada\nuno. El vehículo puede llegar antes de la apertura de un cliente y\nesperar\, pero si se llega después del final de una de estas ventanas\,\nla ruta realizada se considera inválida. El objetivo de este problema\nes minimizar el tiempo de viaje incluyendo la espera. Esto lo\ndiferencia de otra variante conocida como problema de viajante de\ncomercio con ventanas de tiempo con objetivo travel time. En dicha\nvariante se quiere minimizar la suma de los tiempos de viaje entre\nclientes\, asumiendo salida del vehículo en el instante inicial. La\ndiferencia entre ambos problemas es significativa considerando que en\nel MTDP el instante de salida pasa a ser otra variable. \nPara resolver este problema proponemos un algoritmo exacto iterativo\nque alterna entre generar columnas y prohibir rutas que no sean\nelementales. Más específicamente\, usamos técnicas de generación de\ncolumnas con relajación ng\, y un algoritmo de pricing que busca rutas\nde costo mínimo mediante backtracking con búsqueda bidireccional y\nreglas de dominación. También agregamos la técnica de variable fixing\npara eliminar rutas subóptimas. Estos aportes resultan significativos\npuesto que obtenemos resultados mejores que los observados en el\nestado del arte. Para probar el algoritmo se utilizó un conjunto de\n720 instancias\, de las cuales 360 se consideran de dificultad. Se\ncompararon los resultados obtenidos contra los del estado del arte. Se\nlograron resolver 25 nuevas instancias y se mejoraron los tiempos de\n353 instancias difíciles.
URL:https://www.dc.uba.ar/event/defensa-tesis-licenciatura-pablo-zaid/
LOCATION:Sala 1604
CATEGORIES:Agenda
END:VEVENT
END:VCALENDAR