Problemas de ruteo de vehículos

Mostrar todas las versiones(3)

El Problema del Repartidor, PR, consiste en encontrar un camino que recorra un conjunto de clientes, comenzando en un punto dado, minimizando la suma de los tiempos de espera de estos clientes. Este es un problema de optimización simple y natural, que puede ser encontrado en diversas situaciones de...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autor principal: Zabala, Paula
Otros Autores: Lucena, Abilio
Formato: Tesis doctoral publishedVersion
Lenguaje:Español
Publicado: Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales 2006
Acceso en línea:https://hdl.handle.net/20.500.12110/tesis_n3987_Zabala
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id tesis:tesis_n3987_Zabala
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
description El Problema del Repartidor, PR, consiste en encontrar un camino que recorra un conjunto de clientes, comenzando en un punto dado, minimizando la suma de los tiempos de espera de estos clientes. Este es un problema de optimización simple y natural, que puede ser encontrado en diversas situaciones de la vida real, dentro de la industria y en el sector de servicios. La gran cantidad de aplicaciones hacen que este problema no sóolo tenga interés teórico, sino también, una gran importancia práctica. PR pertenece a la clase de problemas NP-Difícil. Para estos problemas no se conoce un algoritmo que encuentre la solución en tiempo polinomial. La mayor parte de la literatura sobre el PR está dedicada al desarrollo de algoritmos aproximados y heurísticas y son pocos los algoritmos exactos propuestos. Como muchos de los problemas de Optimización Combinatoria, PR puede ser modelado mediante formulaciones de programación lineal entera o entera mixta. Los algoritmos Branch-and-Cut son la herramienta más efectiva que se conoce para resolver un modelo de programación lineal entera. Especialmente las implementaciones basadas en combinatoria poliedral han permitido incrementar el tamaño de las instancias resueltas. El objetivo de esta tesis es abordar la resolución del Problema del Repartidor utilizando modelos de programación lineal entera binaria. Con este fin, proponemos una nueva formulación para modelar este problema. Realizamos un estudio poliedral de la cápsula convexa de las soluciones factibles, encontrando varias familias de desigualdades válidas que, bajo ciertas condiciones, demostramos que definen facetas del poliedro. Es la primera vez que se realiza un estudio poliedral asociado al Problema del Repartidor. En base a estas familias de desigualdades válidas, desarrollamos e implementamos un algoritmo Branch-and-Cut.
author2 Lucena, Abilio
author_facet Lucena, Abilio
Zabala, Paula
format Tesis doctoral
Tesis doctoral
publishedVersion
author Zabala, Paula
spellingShingle Zabala, Paula
Problemas de ruteo de vehículos
author_sort Zabala, Paula
title Problemas de ruteo de vehículos
title_short Problemas de ruteo de vehículos
title_full Problemas de ruteo de vehículos
title_fullStr Problemas de ruteo de vehículos
title_full_unstemmed Problemas de ruteo de vehículos
title_sort problemas de ruteo de vehículos
publisher Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales
publishDate 2006
url https://hdl.handle.net/20.500.12110/tesis_n3987_Zabala
work_keys_str_mv AT zabalapaula problemasderuteodevehiculos
_version_ 1782022910459772928
spelling tesis:tesis_n3987_Zabala2023-10-02T19:55:03Z Problemas de ruteo de vehículos Zabala, Paula Lucena, Abilio Méndez-Díaz, Isabel El Problema del Repartidor, PR, consiste en encontrar un camino que recorra un conjunto de clientes, comenzando en un punto dado, minimizando la suma de los tiempos de espera de estos clientes. Este es un problema de optimización simple y natural, que puede ser encontrado en diversas situaciones de la vida real, dentro de la industria y en el sector de servicios. La gran cantidad de aplicaciones hacen que este problema no sóolo tenga interés teórico, sino también, una gran importancia práctica. PR pertenece a la clase de problemas NP-Difícil. Para estos problemas no se conoce un algoritmo que encuentre la solución en tiempo polinomial. La mayor parte de la literatura sobre el PR está dedicada al desarrollo de algoritmos aproximados y heurísticas y son pocos los algoritmos exactos propuestos. Como muchos de los problemas de Optimización Combinatoria, PR puede ser modelado mediante formulaciones de programación lineal entera o entera mixta. Los algoritmos Branch-and-Cut son la herramienta más efectiva que se conoce para resolver un modelo de programación lineal entera. Especialmente las implementaciones basadas en combinatoria poliedral han permitido incrementar el tamaño de las instancias resueltas. El objetivo de esta tesis es abordar la resolución del Problema del Repartidor utilizando modelos de programación lineal entera binaria. Con este fin, proponemos una nueva formulación para modelar este problema. Realizamos un estudio poliedral de la cápsula convexa de las soluciones factibles, encontrando varias familias de desigualdades válidas que, bajo ciertas condiciones, demostramos que definen facetas del poliedro. Es la primera vez que se realiza un estudio poliedral asociado al Problema del Repartidor. En base a estas familias de desigualdades válidas, desarrollamos e implementamos un algoritmo Branch-and-Cut. The Traveling Deliveryman Problem, PR, is a generalization of the Minimum Cost Hamiltonian Path Problem where the starting vertex of the path, i.e. a depot vertex, is fixed in advance and the cost associated with a Hamiltonian path equals the sum of the costs for the layers of paths (along the Hamiltonian path) going from the depot vertex to each of the remaining vertices. Applications of DMP frequently arise in delivery situations where some kind of fairness criteria (for the visiting of clients) must be enforced. PR is known to be NP-hard for arbitrary graphs. The practical importance of the problem makes neccesary to devise algorithms capable of solving, in acceptable computational times, medium to moderate instances arising in real-world applications. A lot of work has been spent in an attempt to develop efficient algorithms for the problem, mainly by using approximation algorithms and heuristic techniques to deal with large instances. Relatively few methods for solving the problem exactly can be found in the literature. Like most optimization problems on graphs, PR can be formulated as a linear integer programming problem. LP-based Branch-and-Cut algorithms are currently the most successfull tool to deal with these models computationally. However, the amount of research effort spent in attempts to solve PR by this method is not comparable with that devoted to other problems, like TSP or maximum stable set. In this thesis, we present a new integer programming formulation. We develop a polyhedral study of the polytope associated with the proposed model in order to derive families of facet-defining inequalities. Branch-and-Cut implementations that take advantage of the particular structure of the problem under consideration have proved to be the most successfull. In this sense, the use of cutting planes arising from a polyhedral study of the feasible solution set allowed many instances of hard combinatorial optimization problems to be solved to proven optimality for the first time. We develop a Branch-and-Cut algorithm based on our theoretical polyhedral results. We also take into account many others factors like preprocessing, search and branching strategies, lower and upper bounds and streghthening of the LP-relaxation. Fil: Zabala, Paula. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales 2006 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_n3987_Zabala

Ejemplares similares