Título: Técnicas de optimización aplicadas a problemas de distribución bajo condiciones de tráfico variable
Director: Juan José Miranda Bront
Consejera de estudios: Isabel Méndez-Díaz

Jurados:
Dra. Flavia Bonomo-Braberman, CONICET – Universidad de Buenos Aires, Instituto de Investigación en Ciencias de la Computación (ICC) / Universidad de Buenos Aires, Buenos Aires, Argentina
Dr. Stefano Novellani, Universitá di Pisa, Pisa, Italia.
Dr. Eduardo Alvarez-Miranda, Universidad de Talca, Talca, Chile.

Link Youtube: https://youtube.com/live/9Rvz9Qp3jiU?feature=share

Resumen:

Las entregas de última milla representan la etapa final del proceso de distribución, que suele tener lugar cerca de las ubicaciones de los clientes, dentro de ciudades grandes o pobladas. Tradicionalmente, estos problemas de distribución se han abordado en algunas variantes del conocido Problema de Ruteo de Vehículos (VRP), que consiste en visitar un conjunto de clientes con una flota de vehículos minimizando el costo operativo total. Desarrollar algoritmos efectivos para el VRP representa un desafío desde una perspectiva computacional, ya que pertenece a la clase de complejidad NP-Hard. Frecuentemente, las condiciones de la red de transporte en estos tipos de escenarios varían a lo largo del día, ya que se acumula más congestión en ciertas horas. El Problema de Ruteo de Vehículos con Tiempos de Viaje Variables (TDVRP) es una generalización del VRP clásico, donde la velocidad de viaje no se asume constante a lo largo del horizonte de planificación y, como consecuencia, los tiempos de viaje varían en función del tiempo. En este sentido, se espera que el resultado de estos tipos de modelos sea más preciso, con soluciones más cercanas a las restricciones de la vida real, pero a expensas de algoritmos más complejos. En esta tesis, analizamos el impacto de incluir explícitamente la dependencia temporal en una amplia gama de variantes del TDVRP. La primera contribución aborda el Problema del Viajante de Comercio con Tiempos de Viaje Variables (TDTSP), una generalización del clásico Problema del Viajante de Comercio (TSP). Proponemos una formulación de Programación Lineal Entera Mixta (MILP), reforzada con nuevas familias de desigualdades válidas que capturan eficazmente los aspectos temporales del problema, y que es posible de ser adaptada a diferentes variantes.

La segunda contribución presenta un método de solución alternativo para el TDTSP basado en programación dinámica. Este enfoque logra mejoras significativas en el tiempo de ejecución y resuelve con éxito varias instancias que permanecían abiertas en la literatura.

La tercera contribución, en contraste, se centra en una variante multi-vehículo, el Problema de Ruteo de Vehículos con Tiempos de Viaje Variables y Vehículos Eléctricos (TDEVRP), que combina el ruteo dependiente del tiempo con restricciones operativas específicas de vehículos eléctricos, como el alcance de conducción limitado y el consumo de batería dependiente de la velocidad. Desarrollamos un algoritmo de branch-cut-and-price (BCP) que incorpora varios componentes de última generación. Experimentos computacionales extensos demuestran su efectividad y competitividad.