Registro:
| Documento: | Tesis de Grado |
| Título: | Un enfoque de programación lineal entera para el problema de ruteo de vehículos con subentregas de alcance limitado |
| Autor: | Skakovsky, Luciana |
| Editor: | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales |
| Fecha de defensa: | 2025-08-11 |
| Fecha en portada: | 2025 |
| Grado Obtenido: | Grado |
| Título Obtenido: | Licenciado en Ciencias de la Computación |
| Departamento Docente: | Departamento de Computación |
| Director: | Méndez Díaz, Isabel; Zabala, Paula Lorena |
| Jurado: | Curcio, Brian Luis; Factorovich, Pablo Matías |
| Idioma: | Español |
| Palabras clave: | OPTIMIZACION COMBINATORIA; PROGRAMACION LINEAL ENTERA; RUTEO DE VEHICULOSCOMBINATORIAL OPTIMIZATION; LINEAR INTEGER PROGRAMMING; VEHICLE ROUTING PROBLEM |
| Formato: | PDF |
| Handle: |
https://hdl.handle.net/20.500.12110/seminario_nCOM000849_Skakovsky |
| PDF: | https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000849_Skakovsky.pdf |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/seminario/document/seminario_nCOM000849_Skakovsky |
| Ubicación: | COM 000849 |
| 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. Skakovsky, Luciana. (2025). Un enfoque de programación lineal entera para el problema de ruteo de vehículos con subentregas de alcance limitado. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/seminario_nCOM000849_Skakovsky |
Resumen:
El Problema de Ruteo de Vehículos (VRP) es una familia de problemas de Optimización Combinatoria donde el objetivo es planificar la distribución ́de bienes mediante vehículos desde uno o mas depósitos para satisfacer las demandas de clientes. Este problema presenta muchas variantes, principalmente basadas en restricciones operativas que dependen del escenario de aplicación que se esté tratando. Si bien en la versión clásica todas las demandas son satisfechas por los vehículos que parten desde los depósitos y visitan a cada cliente, en los últimos a nos se ha comenzado a considerar la interacción entre diferentes tipos de transporte con el objetivo de mejorar la eficiencia logística. En la variante que trata este trabajo, se considera la interacción entre un camión principal y vehículos auxiliares. El camión principal sale del depósito con la carga correspondiente a todos los pedidos. Al visitar a un cliente, ademas de satisfacer el pedido correspondiente, puede entregar los pedidos de algunos clientes a un vehículo auxiliar que realizar ́a la distribución de los mismos. El vehículo auxiliar tiene la restricción de que el recorrido para entregar los pedidos asignados no puede tener un costo mayor a determinado valor, asumiendo que comienza en la parada donde recibió los pedidos y debe retornar al mismo lugar. El problema entonces consiste en determinar la ruta del vehículo principal, saliendo y retornando al deposito y qué entregas deriva a vehículos auxiliares, con el objetivo de minimizar costos. En este trabajo se propone un modelo de programación lineal entera para el problema, y se analiza la performance de un algoritmo branch-and-cut basado en dicho modelo, utilizando instancias generadas a partir de parámetros específicos. Además, se desarrollan heurísticas para acelerar la obtención de soluciones factibles iniciales, así como planos de corte diseñados para mejorar la eficiencia del proceso de ramificación. Se propone ademas una metaheurística GRASP cuya performance es evaluada.
Abstract:
The Vehicle Routing Problem (VRP) is a family of Combinatorial Optimization problems whose objective is to plan the distribution of goods from one or more depots to satisfy customer demands. This problem has many variants, mainly based on operational constraints that depend on the specific application scenario. While in the classical version all demands are fulfilled by vehicles that depart from the depots and visit each customer, in recent years the interaction between different types of transportation has begun to be considered, aiming to improve logistical efficiency. In the variant addressed in this work, the interaction between a main truck and auxiliary vehicles is considered. The main truck departs from the depot carrying the total load for all orders. When visiting a customer, besides delivering the corresponding order, it can also hand over some orders to an auxiliary vehicle, which will handle their distribution. The auxiliary vehicle is restricted in that its delivery route for the assigned orders cannot exceed a given cost, assuming it starts from the handover point and must return to the same location. The problem then consists of determining the route of the main vehicle, departing from and returning to the depot, and deciding which deliveries are delegated to auxiliary vehicles, with the objective of minimizing costs. In this work, an integer linear programming model is proposed for the problem, and the performance of a branch-and-cut algorithm based on this model is analyzed, using instances generated from specific parameters. Additionally, heuristics are developed to speed up the generation of initial feasible solutions, as well as cutting planes designed to improve the efficiency of the branching process. A GRASP metaheuristic is also proposed and its performance is evaluated.
Citación:
---------- APA ----------
Skakovsky, Luciana. (2025). Un enfoque de programación lineal entera para el problema de ruteo de vehículos con subentregas de alcance limitado. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/seminario_nCOM000849_Skakovsky
---------- CHICAGO ----------
Skakovsky, Luciana. "Un enfoque de programación lineal entera para el problema de ruteo de vehículos con subentregas de alcance limitado". Tesis de Grado, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2025.https://hdl.handle.net/20.500.12110/seminario_nCOM000849_Skakovsky
Estadísticas:
Descargas mensuales
Total de descargas desde :
https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000849_Skakovsky.pdf
Distrubución geográfica
