Modelos y algoritmos basados en programación lineal entera para problemas de ruteo de vehículos

Mostrar todas las versiones(3)

En esta tesis se abordan variantes de uno de los problemas más importantes en el área del transporte, conocido como el Problema de Ruteo de Vehículos (VRP), a través de métodos basados en Programación Lineal Entera (ILP). El VRP consiste en determinar un conjunto de rutas de costo mínimo para una fl...

Descripción completa

Detalles Bibliográficos
Autor principal: Montero, Agustín Ismael
Otros Autores: Méndez-Díaz, Isabel
Formato: Tesis doctoral publishedVersion
Lenguaje:Español
Publicado: Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales 2022
Materias:
OPTIMIZACION COMBINATORIA
PROBLEMAS DE RUTEO DE VEHICULOS
PICKUP-AND-DELIVERY
DEPENDENCIA DEL TIEMPO
FECHAS DE DISPONIBILIDAD
PROGRAMACION LINEAL ENTERA
BRANCH-AND-CUT
COMBINATORIAL OPTIMIZATION
VEHICLE ROUTING PROBLEMS
TIME DEPENDENCY
RELEASE DATES
INTEGER LINEAR PROGRAMMING
Acceso en línea:https://hdl.handle.net/20.500.12110/tesis_n7045_Montero
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id tesis:tesis_n7045_Montero
record_format dspace
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
language Español
orig_language_str_mv spa
topic OPTIMIZACION COMBINATORIA
PROBLEMAS DE RUTEO DE VEHICULOS
PICKUP-AND-DELIVERY
DEPENDENCIA DEL TIEMPO
FECHAS DE DISPONIBILIDAD
PROGRAMACION LINEAL ENTERA
BRANCH-AND-CUT
COMBINATORIAL OPTIMIZATION
VEHICLE ROUTING PROBLEMS
PICKUP-AND-DELIVERY
TIME DEPENDENCY
RELEASE DATES
INTEGER LINEAR PROGRAMMING
BRANCH-AND-CUT
spellingShingle OPTIMIZACION COMBINATORIA
PROBLEMAS DE RUTEO DE VEHICULOS
PICKUP-AND-DELIVERY
DEPENDENCIA DEL TIEMPO
FECHAS DE DISPONIBILIDAD
PROGRAMACION LINEAL ENTERA
BRANCH-AND-CUT
COMBINATORIAL OPTIMIZATION
VEHICLE ROUTING PROBLEMS
PICKUP-AND-DELIVERY
TIME DEPENDENCY
RELEASE DATES
INTEGER LINEAR PROGRAMMING
BRANCH-AND-CUT
Montero, Agustín Ismael
Modelos y algoritmos basados en programación lineal entera para problemas de ruteo de vehículos
topic_facet OPTIMIZACION COMBINATORIA
PROBLEMAS DE RUTEO DE VEHICULOS
PICKUP-AND-DELIVERY
DEPENDENCIA DEL TIEMPO
FECHAS DE DISPONIBILIDAD
PROGRAMACION LINEAL ENTERA
BRANCH-AND-CUT
COMBINATORIAL OPTIMIZATION
VEHICLE ROUTING PROBLEMS
PICKUP-AND-DELIVERY
TIME DEPENDENCY
RELEASE DATES
INTEGER LINEAR PROGRAMMING
BRANCH-AND-CUT
description En esta tesis se abordan variantes de uno de los problemas más importantes en el área del transporte, conocido como el Problema de Ruteo de Vehículos (VRP), a través de métodos basados en Programación Lineal Entera (ILP). El VRP consiste en determinar un conjunto de rutas de costo mínimo para una flota de vehículos que deben visitar exactamente una vez a determinados clientes, comenzando y finalizando sus recorridos en un único depósito, y satisfaciendo una restricción de capacidad. La primera variante abordada es el VRP con Pickups and Deliveries (VRPPD), en la cual se consideran precedencias 1-a-1 entre los clientes. La investigación se centra en estudiar la factibilidad de utilizar modelos basados en ILP heurísticamente, como parte de un algoritmo de búsqueda local, para explorar espacios de búsqueda grandes a fin de mejorar soluciones de una calidad media o alta. Se obtienen muy buenos resultados, mostrando que el desarrollo tiene potencial para ser utilizado en la práctica. La segunda variante contempla una generalización de la versión mono-vehículo del VRP sin capacidades, conocida como Problema del Viajante de Comercio (TSP). En esta versión denominada TDTSPTW se incluyen ventanas de tiempo y se incorpora variabilidad en los tiempos de viaje entre dos clientes que permite capturar la congestión y su potencial impacto en la práctica. Se desarrolla un algoritmo exacto siguiendo un esquema Branch-and-Cut, que es evaluado en instancias de prueba. A nuestro saber y entender, esta fue una de las primeras comparaciones exhaustivas de enfoques exactos para el TDTSPTW, donde resultados obtenidos mejoraron los de la literatura. Finalmente, la tercera variante estudiada se denomina TSP-rd e incorpora fechas de disponibilidad para modelar el tiempo en el que cada uno de los productos llegan al depósito. Se dispone de un único vehículo que puede realizar múltiples rutas y que en todo momento debe decidir si conviene esperar a que lleguen más productos al depósito, o si es mejor comenzar el recorrido para entregar aquellos que ya están disponibles. El objetivo es minimizar el tiempo de finalización. Se propone un nuevo algoritmo basado en ILP que demuestra ser mejor que el estado del arte. Adicionalmente, se adapta el modelo a otras variantes de TSP-rd y se explora el comportamiento en nuevas instancias de prueba. Hasta donde sabemos, es el mejor modelo exacto para el problema.
author2 Méndez-Díaz, Isabel
author_facet Méndez-Díaz, Isabel
Montero, Agustín Ismael
format Tesis doctoral
Tesis doctoral
publishedVersion
author Montero, Agustín Ismael
author_sort Montero, Agustín Ismael
title Modelos y algoritmos basados en programación lineal entera para problemas de ruteo de vehículos
title_short Modelos y algoritmos basados en programación lineal entera para problemas de ruteo de vehículos
title_full Modelos y algoritmos basados en programación lineal entera para problemas de ruteo de vehículos
title_fullStr Modelos y algoritmos basados en programación lineal entera para problemas de ruteo de vehículos
title_full_unstemmed Modelos y algoritmos basados en programación lineal entera para problemas de ruteo de vehículos
title_sort modelos y algoritmos basados en programación lineal entera para problemas de ruteo de vehículos
publisher Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales
publishDate 2022
url https://hdl.handle.net/20.500.12110/tesis_n7045_Montero
work_keys_str_mv AT monteroagustinismael modelosyalgoritmosbasadosenprogramacionlinealenteraparaproblemasderuteodevehiculos
AT monteroagustinismael enhancedintegerlinearprogrammingtechniquesforvehicleroutingproblems
_version_ 1831982472490909696
spelling tesis:tesis_n7045_Montero2025-03-31T21:50:42Z Modelos y algoritmos basados en programación lineal entera para problemas de ruteo de vehículos Enhanced integer linear programming techniques for vehicle routing problems Montero, Agustín Ismael Méndez-Díaz, Isabel Miranda-Bront, Juan José OPTIMIZACION COMBINATORIA PROBLEMAS DE RUTEO DE VEHICULOS PICKUP-AND-DELIVERY DEPENDENCIA DEL TIEMPO FECHAS DE DISPONIBILIDAD PROGRAMACION LINEAL ENTERA BRANCH-AND-CUT COMBINATORIAL OPTIMIZATION VEHICLE ROUTING PROBLEMS PICKUP-AND-DELIVERY TIME DEPENDENCY RELEASE DATES INTEGER LINEAR PROGRAMMING BRANCH-AND-CUT En esta tesis se abordan variantes de uno de los problemas más importantes en el área del transporte, conocido como el Problema de Ruteo de Vehículos (VRP), a través de métodos basados en Programación Lineal Entera (ILP). El VRP consiste en determinar un conjunto de rutas de costo mínimo para una flota de vehículos que deben visitar exactamente una vez a determinados clientes, comenzando y finalizando sus recorridos en un único depósito, y satisfaciendo una restricción de capacidad. La primera variante abordada es el VRP con Pickups and Deliveries (VRPPD), en la cual se consideran precedencias 1-a-1 entre los clientes. La investigación se centra en estudiar la factibilidad de utilizar modelos basados en ILP heurísticamente, como parte de un algoritmo de búsqueda local, para explorar espacios de búsqueda grandes a fin de mejorar soluciones de una calidad media o alta. Se obtienen muy buenos resultados, mostrando que el desarrollo tiene potencial para ser utilizado en la práctica. La segunda variante contempla una generalización de la versión mono-vehículo del VRP sin capacidades, conocida como Problema del Viajante de Comercio (TSP). En esta versión denominada TDTSPTW se incluyen ventanas de tiempo y se incorpora variabilidad en los tiempos de viaje entre dos clientes que permite capturar la congestión y su potencial impacto en la práctica. Se desarrolla un algoritmo exacto siguiendo un esquema Branch-and-Cut, que es evaluado en instancias de prueba. A nuestro saber y entender, esta fue una de las primeras comparaciones exhaustivas de enfoques exactos para el TDTSPTW, donde resultados obtenidos mejoraron los de la literatura. Finalmente, la tercera variante estudiada se denomina TSP-rd e incorpora fechas de disponibilidad para modelar el tiempo en el que cada uno de los productos llegan al depósito. Se dispone de un único vehículo que puede realizar múltiples rutas y que en todo momento debe decidir si conviene esperar a que lleguen más productos al depósito, o si es mejor comenzar el recorrido para entregar aquellos que ya están disponibles. El objetivo es minimizar el tiempo de finalización. Se propone un nuevo algoritmo basado en ILP que demuestra ser mejor que el estado del arte. Adicionalmente, se adapta el modelo a otras variantes de TSP-rd y se explora el comportamiento en nuevas instancias de prueba. Hasta donde sabemos, es el mejor modelo exacto para el problema. In this thesis, we address different variants of one of the most important problems in transportation research, known as the Vehicle Routing Problem (VRP), through methods based on Integer Linear Programming (ILP). The VRP consists of determining a set of minimum cost routes for a fleet of vehicles that must visit certain customers exactly once, starting and ending in a single depot, and satisfying a capacity constraint. The first variant considered is the VRP with Pickups and Deliveries (VRPPD), in which 1-to-1 precedences among customers are considered. The approach evaluates the feasibility of using ILPs heuristically within a local search algorithm. Based on extensive computational experiments, we show that the algorithm is capable of improving good quality solutions and has potentital to be used in practice. The second variant tackles a generalization of the well known Traveling Salesman Problem (TSP), that can be seen as a special case of the VRP with a single vehicle having infinite capacity. In this version, called TDTSPTW, time windows are included and variability in travel-times between every two clients is incorporated, which allows congestion and its potential impact in practice to be captured. We develop an exact algorithm following a Branch-and-Cut scheme, which is evaluated in benchmark instances. To the best of our knowledge, this is one of the first comprehensive exact approach comparisons for the TDTSPTW, and the obtained results improved those reported in the literature by the time the algorithm was presented. Finally, the third variant considers also a generalization of the TSP, where a single vehicle is allowed to perform multiple trips during the day. The distinctive constraints are that the requests incorporate the so-called release dates, that model the time at which they arrive to the depot. This problem is known as the TSP-rd, and the key decision is whether to wait for more requests to arrive at the depot, or whether to depart to deliver those that are already available. The objective is to minimize total completion-time. We propose a new ILP formulation for the classical version of the TSP-rd, which is later extended to further variants considering relevant practical constraints. Through extensive computational experiments, we show that the proposed approach improves the state of the art. As far as we know, this is the best exact model for the problem. Fil: Montero, Agustín Ismael. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales 2022-03-18 info:eu-repo/semantics/doctoralThesis info:ar-repo/semantics/tesis doctoral info:eu-repo/semantics/publishedVersion application/pdf spa info:eu-repo/semantics/openAccess https://creativecommons.org/licenses/by-nc-sa/2.5/ar https://hdl.handle.net/20.500.12110/tesis_n7045_Montero

Ejemplares similares