Registro:
| Documento: | Tesis de Grado |
| Título: | Un enfoque exacto para el problema de camino mínimo elemental con restricciones de recursos y tiempos de viaje variables |
| Título alternativo: | An exact approach the time-dependent elemenary shortest path problem with resource constrants |
| Autor: | Lera Romero, Gonzalo |
| Editor: | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales |
| Publicación en la web: | 2023-09-12 |
| Fecha de defensa: | 2021-10-27 |
| Fecha en portada: | 2017 |
| Grado Obtenido: | Grado |
| Título Obtenido: | Licenciado en Ciencias de la Computación |
| Director: | Miranda Bront, Juan José |
| Idioma: | Español |
| Palabras clave: | PROGRAMACION LINEAL ENTERA; RUTEO DE VEHICULOS; TRAFICO Y CONGESTION; OPTIMIZACION COMBINATORIAINTEGER LINEAL PROGRAMMING; VEHICLE ROUTING PROBLEM; CONGESTION; COMBINATORIAL OPTIMIZATION |
| Formato: | PDF |
| Handle: |
http://hdl.handle.net/20.500.12110/seminario_nCOM000471_LeraRomero |
| PDF: | https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000471_LeraRomero.pdf |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/seminario/document/seminario_nCOM000471_LeraRomero |
| Ubicación: | Dep.COM 000471 |
| 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. (2017). Un enfoque exacto para el problema de camino mínimo elemental con restricciones de recursos y tiempos de viaje variables. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de http://hdl.handle.net/20.500.12110/seminario_nCOM000471_LeraRomero |
Resumen:
La congestión en las grandes ciudades y en áreas sobrepobladas es uno de los mayores desafíos en la logística urbana, y hoy en día se ha convertido en uno de los inconvenientes principales en el planeamiento urbano y la denominada distribución de la última milla debido a su impacto económico, social y ambiental. La mayor parte de la investigación dedicada a los Problemas de Ruteo de Vehículos (VRP, por su sigla en inglés) considera que el tiempo de viaje entre dos sitios cualesquiera es constante a lo largo del horizonte de planeamiento. En los últimos años, ha habido una tendencia a enriquecer estos modelos mediante la incorporación de funciones de tiempo de viaje más complejas que capturen el efecto de la congestión, conocidos como VRP Dependientes del Tiempo (TDVRP, ver Gendreau et al. [11])). La incorporación explícita de la congestión a nivel táctico es un aspecto fundamental de los Sistemas de Soporte a la Decisión (DSS) modernos a fin de obtener planificaciones y recorridos que sean representativos de las operaciones habituales (Huang et al. [15]). Sin embargo, los algoritmos presentes actualmente en la literatura requieren mejoras, como se muestra en Dabia et al. [6] y Montero et al. [26], para poder transformarse en herramientas automatizadas que puedan ser utilizadas en la práctica. Los enfoques exactos generales para las variantes monovehículo suelen basarse en modelos de Programación Lineal Entera (PLEM) y algoritmos Branch&Cut (B&C), como puede verse en los trabajos de Cordeau et al. [5] para el Problema del Viajante de Comercio Dependiente del Tiempo (TDTSP) y Arigliano et al. [3] para el TDTSP-TW, es decir, el TDTSP con ventanas de tiempo. Los algoritmos exactos para problemas multivehículos suelen recurrir a modelos de PLEM combinados con técnicas de descomposición, dando lugar a los denominados algoritmos Branch&Price (B&P). Uno de los ingredientes principales de estos algoritmos radica en la resolución del subproblema de generación de columnas, que puede ser formulado como un problema de Camino Mínimo Elemental Dependiente del Tiempo con Restricciones de Recursos y Beneficios (TD-PESPPRC). Dabia et al. [6] siguen este enfoque y proponen un algoritmo B&P para el TDVRP con Ventanas de Tiempo (TDVRP-TW), que es luego adaptado por Sun et al. [29] para considerar también restricciones de precedencia. En ambos artículos, en sus problemas correspondientes es abordado mediante algoritmos de labeling y Programación Dinámica (DP). La generación de columnas aparece como un problema difícil y desafiante computacionalmente, especialmente cuando no se posee un recurso limitante (por ejemplo, la capacidad o las ventanas de tiempo) que permita reducir de forma significativa el espacio de búsqueda. En esta tesis abordamos el TD-PESPPRC con restricciones de capacidad pero, a diferencia de los enfoques anteriores, no consideramos la presencia de ventanas de tiempo en los clientes. Desde el punto de vista práctico, con esta configuración los algoritmos de labeling propuestos previamente encuentran fuertes limitaciones dado que el espacio de búsqueda se vuelve muy grande, dando lugar también a la construcción de rutas con muchos clientes como parte de las soluciones al problema. Luego, la importancia de estudiar esta variante tiene dos razones principales. La primera de ellas es que las versiones mono-vehículo, como el TDTSP y el TDTSP-TW, pueden ser fácilmente adaptadas introduciendo pequeñas modificaciones al modelo. En segundo lugar, la obtención de un algoritmo eficiente para el TD-PESPPRC abriría la posibilidad a integrarlo en los esquemas B&P en los casos donde los enfoques tradicionales no son satisfactorios. Con esto en mente, proponemos un modelo PLEM mejorado basado en el propuesto por Sun et al. [29]. Realizamos un estudio teórico enfocado en derivar nuestras familias de desigualdades válidas que exploten la estructura particular introducida por la red subyacente dependiente del tiempo, y que permita mejorar la calidad de las cotas inferiores provistas por la relajación lineal del modelo. Estas familias son embebidas en un algoritmo de tipo Branch&Cut, que es evaluado experimentalmente en función del tiempo de cómputo requerido y la calidad de las cotas provistas. Los resultados son muy prometedores y muestran que el algoritmo es capaz de resolver instancias de 25 vértices consistentemente dentro de los límites establecidos, que los resultados teóricos pueden ser extendidos a otras variantes de problemas dependientes del tiempo y que el enfoque en su totalidad tiene potencial de ser aplicado en la práctica.
Abstract:
Congestion in large cities and populated areas is one of the major challenges in urban logistics, becoming one of the key issues in city planning and last-mile logistics due to its economic, social and environmental impact. Most of the research devoted to the Vehicle Routing Problem (VRP) considers that travel times between any two locations are fixed along the time horizon. In the last few years, there has been a trend to enrich these models by incorporating more complex travel time functions to capture the effect of congestion, known as Time-Dependent VRPs (TDVRP, see, e.g., Gendreau et al. [11], for an updated survey). Incorporating the congestion explicitly at a tactical level is a key aspect of modern Decision Support Systems (DSS) in order to obtain distribution plans that are representative of the real-life operations (Huang et al. [15]). However, state-of-the-art algorithms require further developments, as shown in Dabia et al. [6] and Montero et al. [26], in order to derive them into automated tools that can be implemented in practice. Standard exact approaches for single-vehicle problems are generally addressed by means of Integer Linear Programming (ILP) and Branch&Cut (B&C) algorithms, as shown in Cordeau et al. [5] for the Time Dependent Traveling Salesman Problem (TDTSP) and by Arigliano et al. [3] for the TDTSP with Time Windows (TDTSP-TW). Exact approaches for multi-vehicle variants generally resort to ILP combined with decomposition techniques, resulting in Branch&Price (B&P) algorithms. One of the key ingredients of the latter rely on the pricing problem within the column generation algorithm, which can be formulated as a Time-Dependent Elementary Shortest Path Problem with Resource Constraints and Profits (TD-PESPPRC). Dabia et al. [6] follow this approach and propose a B&P algorithm for the capacitated TDVRP with time windows (TDVRP-TW), which is later adapted by Sun et al. [29] to further consider the TD-PESPPRC with precedence constraints. In both papers, the corresponding problem is tackled by labeling and Dynamic Programming (DP) algorithms. The pricing step appears as a very difficult and challenging problem that requires further developments, specially under the absence of a limiting resource (for instance, time windows) that may allow to reduce the search space. In this thesis, we tackle the TD-PESPPRC with capacity constraints but, opposed to the previously mentioned cases, we do not consider time windows. From a practical standpoint, under these settings the standard labeling algorithms from previous approaches find some limitations since the search space becomes too large to explore, giving place to constructing large routes as part of the overall solution. Therefore, the importance of studying this variant has two main reasons. Firstly, single-vehicle variants, such as the TDTSP and the TDTSP-TW, are easily recovered with some minor modifications to the formulation. Secondly, an efficient algorithm for the TD-PESPPRC could be integrated within a B&P scheme where the standard approaches are not satisfactory. For this purpose, we propose an enhanced ILP formulation based on the one proposed in Sun et al. [29]. We perform a theoretical study focused on deriving three new families of valid inequalities that exploit the particular structure introduced by the time-dependent underlying network aiming to improve the quality of the lower bounds provided by the LP relaxation. These families are embedded in a Branch&Cut algorithm, which is experimentally evaluated in terms of computing times and quality of the lower bounds. The results are very promising, showing that our algorithm is able to solve consistently instances with 25 vertices in reasonable computing times, that the results can be extended to other time-dependent problems and that the overall approach has potential to be applied in practice.
Citación:
---------- APA ----------
Lera Romero, Gonzalo. (2017). Un enfoque exacto para el problema de camino mínimo elemental con restricciones de recursos y tiempos de viaje variables. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/seminario_nCOM000471_LeraRomero
---------- CHICAGO ----------
Lera Romero, Gonzalo. "Un enfoque exacto para el problema de camino mínimo elemental con restricciones de recursos y tiempos de viaje variables". Tesis de Grado, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2017.https://hdl.handle.net/20.500.12110/seminario_nCOM000471_LeraRomero
Estadísticas:
Descargas mensuales
Total de descargas desde :
https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000471_LeraRomero.pdf
Distrubución geográfica
