Técnicas de optimización aplicadas a problemas de distribución bajo condiciones de tráfico variable

Lera Romero, Gonzalo

Registro:

Documento:	Tesis Doctoral
Título:	Técnicas de optimización aplicadas a problemas de distribución bajo condiciones de tráfico variable
Título alternativo:	Optimization techniques applied to distribution problems under variable traffic conditions
Autor:	Lera Romero, Gonzalo
Editor:	Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales
Fecha de defensa:	2025-09-19
Fecha en portada:	19 de septiembre de 2025
Grado Obtenido:	Doctorado
Título Obtenido:	Doctor de la Universidad de Buenos Aires en el área de Ciencias de la Computación
Departamento Docente:	Departamento de Computación
Director:	Miranda Bront, Juan José
Consejero:	Méndez Díaz, Isabel
Jurado:	Bonomo, Flavia; Novellani, Stefano; Alvarez Miranda, Eduardo
Idioma:	Español
Palabras clave:	TIME DEPENDENT; PROBLEMA DE RUTEO DE VEHICULOS; PROBLEMA DEL VIAJANTE DE COMERCIO; VEHÍCULOS ELECTRICOS; PROBLEMA DEL CAMINO MAS CORTO ELEMENTAL; BRANCH CUT AND PRICE; LABELINGTIME DEPENDENT; VEHICLE ROUTING PROBLEM; TRAVELING SALESMAN PROBLEM; ELECTRIC VEHICLES; ELEMENTARY SHORTEST PATH PROBLEM; BRANCH CUT AND PRICE; LABELING
Formato:	PDF
Handle:	https://hdl.handle.net/20.500.12110/tesis_n7879_LeraRomero
PDF:	https://bibliotecadigital.exactas.uba.ar/download/tesis/tesis_n7879_LeraRomero.pdf
Registro:	https://bibliotecadigital.exactas.uba.ar/collection/tesis/document/tesis_n7879_LeraRomero
Ubicación:	COM 007879
Derechos de Acceso:	Esta obra puede ser leída, grabada y utilizada con fines de estudio, investigación y docencia. Es necesario el reconocimiento de autoría mediante la cita correspondiente. Lera Romero, Gonzalo. (2025). Técnicas de optimización aplicadas a problemas de distribución bajo condiciones de tráfico variable. (Tesis Doctoral. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales). Recuperado de https://hdl.handle.net/20.500.12110/tesis_n7879_LeraRomero

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 N P-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.

Abstract:

Last-mile deliveries account for the final stage of the distribution process, which typically takes place near customer locations, inside large or populated cities. Traditionally, these distribution problems have been tackled in some variants of the well-known Vehicle Routing Problem (VRP) consisting of visiting a set of customers with a fleet of vehicles while minimizing the total operational cost. Developing effective algorithms for the VRP represents a challenge from a computational perspective, as it belongs to the N P-Hard complexity class. Frequently, the conditions of the transportation network in these types of scenarios vary along the day, as more congestion builds at certain hours. The Time-Dependent Vehicle Routing Problem (TDVRP) is a generalization of the classical VRP where the travel speed is not assumed to be constant throughout the planning horizon and, as a consequence, travel times vary throughout the planning horizon. In this sense, the outcome of these types of models is expected to be more accurate, with solutions closer to real-life constraints, but at the expense of more complex algorithms. In this thesis, we analyze the impact of explicitly including time dependency across a wide range of variants of the TDVRP. The first contribution addresses the Time-Dependent Traveling Salesman Problem (TDTSP), a generalization of the classical Traveling Salesman Problem (TSP). We propose a flexible Mixed Integer Linear Programming (MILP) formulation, reinforced with novel families of valid inequalities that effectively capture the temporal aspects of the problem. The second contribution presents an alternative solution method for the TDTSP based on dynamic programming. This approach achieves significant improvements in execution time and successfully solves several instances that remained open in the literature. The third contribution focuses on the Time-Dependent Electric Vehicle Routing Problem (TDEVRP), which combines time-dependent routing with operational constraints specific to electric vehicles, such as limited driving range and speed-dependent battery consumption. We develop a branch-cut-and-price (BCP) algorithm that incorporates several state-of-the-art components. Extensive computational experiments demonstrate its effectiveness and competitiveness.

Citación:

---------- APA ----------

Lera Romero, Gonzalo. (2025). Técnicas de optimización aplicadas a problemas de distribución bajo condiciones de tráfico variable. (Tesis Doctoral. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/tesis_n7879_LeraRomero

---------- CHICAGO ----------

Lera Romero, Gonzalo. "Técnicas de optimización aplicadas a problemas de distribución bajo condiciones de tráfico variable". Tesis Doctoral, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2025.https://hdl.handle.net/20.500.12110/tesis_n7879_LeraRomero

Estadísticas:

Descargas totales desde :

Navegar

Colección

Tesis Doctoral