Biblioteca Digital | FCEN-UBA

Biblioteca Digital ¿Por qué?
Objetivos
Impactos
Estadísticas
Documentos
Presentaciones
Notas
Autores y derechos
¿Por qué depositar?
¿Cómo depositar?
Autorización
Depositar y publicar
Editoriales
Publicar mi tesis Formulario Tesis Posgrado
Formulario Tesis Grado
Normativa
Res. CD 2053/05
Res. CD 2533/09
Res. CD 0272/13
Res. CD 2793/15

Colecciones Tesis Doctorales
Fotografías
Publicaciones
Archivo
Libros
Reportes Técnicos

Tesis > TEMA

Computación [ 80 tesis ]

Optimización Combinatoria [ 3 tesis ]

Zabala, Paula. "Problemas de ruteo de vehículos" (2006) Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires

pdf

Resumen Registro Cita

Resumen:
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.

Abstract:
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.

Miranda Bront, Juan José. "Enfoques de programación entera para el Problema del Viajante de Comercio con costos en función del tiempo" (2012) Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires

pdf

Resumen Registro Cita

Resumen:
El Problema del Viajante de Comercio Dependiente del Tiempo (PVCDT) es una generalización del clásico Problema del Viajante de Comercio (PVC) en el cual se busca un circuito de costo mínimo que recorra todos los clientes, donde los tiempos (o costos) de viaje entre ellos no son constantes y pueden variar dependiendo de diversos factores. Una de las motivaciones para considerar la dependencia del tiempo es que nos permite tener una mejor aproximación a muchas aplicaciones de la vida real, dentro de la industria y en el sector de servicios. En la literatura relacionada, existen distintas versiones del PVCDT que consideran que las variaciones se producen por diversos motivos y sobre distintos parámetros. Algunas de ellas estipulan que las variaciones se producen sobre los tiempos (y/o costos) de viaje mientras que otras asumen que las variaciones se producen sobre la velocidad de viaje. Más aún, para el primer caso, una variante asume que el tiempo de viaje depende de la posición del arco en el circuito mientras que otra asume que depende del instante en el que se comienza a atravesar el arco. Al igual que el PVC, el PVCDT pertence a la clase NP-Difícil y por lo tanto no se conoce un algoritmo que encuentre una solución en tiempo polinomial. En esta tesis abordamos dos de las variantes antes mencionadas mediante la formulación de modelos de Programación Lineal Entera. Para cada formulación, realizamos un estudio teórico enfocado en derivar familias de desigualdades válidas que exploten las características particulares del problema. En particular, para una de las variantes, demostramos que varias de ellas definen facetas del poliedro. Desde el punto de vista práctico, para las variantes consideradas desarrollamos algoritmos exactos de tipo Branch and Cut que incorporan estas familias de desigualdades válidas y los evaluamos considerando instancias propuestas en la literatura, obteniendo buenos resultados que muestran que ambos enfoques son factibles para ser utilizados en la práctica.

Abstract:
The Time Dependent Travelling Salesman Problem (TDTSP) is a generalization of the well known Travelling Salesman Problem (TSP) in which we look for a minimum cost tour that visits each client exactly once where the travel times (or costs) among them are not assumed to be constant and may vary depending on many different factors. The motivation to consider the time dependence factor is that it enables to have better approximations to many problems from practice, mainly from the industry and the service sector. In the related literature there are different versions of the TDTSP that consider that variations occur for different reasons and over distinct parameters. For example, some of them consider that variations affect travel times (and/or costs) while others assume that variations influence travel speeds. Moreover, in the first case, one version assumes that the travel time depends on the position of the arc in the tour while another one assumes that it depends on the particular starting instant for travelling the arc. As well as the TSP, the TDTSP belongs to the class NP-Hard and therefore it is not known an algorithm that solves it in polynomial time. In this thesis we approach two of the versions mentioned above by means of Integer Linear Programming formulations. For each formulation, we perform a theoretical study focused on deriving families of valid inequalities that exploit the particular characteristics of the problem. In particular, for one of the variants, we prove that some of them are facet defining. From a practical standpoint, for the versions considered we develop exact Branch and Cut algorithms that incorporate these families of valid inequalities and we evaluate them on instances from the related literature, obtaining good computational results that show that both approaches are feasible to be used in practice.

Negrotto, Daniel. "Algoritmos para el problema de localización y ruteo de vehículos con capacidades y premios" (2015-09-24) Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires

pdf

Resumen Registro Cita

Resumen:
El problema de Localización y Ruteo de Vehículos con Capacidades (CLRP) es la combinación de dos problemas muy estudiados del área de la Investigación Operativa: el problema de localización de depósitos con capacidades (CFLP) y el problema de ruteo de vehículos con múltiples depósitos (MDVRP). Dado un conjunto de posibles localizaciones se busca determinar cuáles utilizar para satisfacer las demandas de un conjunto de clientes y programar las rutas que los visitan. Se busca minimizar los costos de apertura de depósitos, de utilización de vehículos y de ruteo satisfaciendo restricciones de capacidad tanto en los vehículos como en los depósitos. En este trabajo se presenta una nueva versión del problema denominada Localización y Ruteo de Vehículos con Capacidades y Premios (PC-CLRP) que busca generalizar el problema CLRP permitiendo la posibilidad de que los clientes sean o no visitados. Los clientes atendidos otorgan un beneficio y la maximización de la suma de los beneficios forma parte del objetivo del nuevo problema. Se proponen en este trabajo algoritmos para el problema PC-CLRP. En primer lugar se introduce un algoritmo metaheurístico para resolverlo basado en el método de optimización por Colonia de Hormigas. Se implementa una metaheurística de 3 colonias de hormigas que colaboran construyendo las distintas etapas de una solución PC-CLRP: localización, clusterizado y ruteo. Posteriormente, se presentan modelos de programación lineal entera basadas en modelos de flujo de 2 índices y 3 índices. Se analizan distintas familias de desigualdades válidas utilizadas para CLRP y se proponen nuevas versiones de las mismas para el problema PC-CLRP. Además, se definen nuevas desigualdades válidas y cortes de optimalidad junto a sus correspondientes algoritmos de separación. Por último, se implementa un algoritmo Branch&Cut utilizando uno de los modelos de programación lineal entera propuestos. Se reportan los resultados obtenidos por ambos algoritmos para el problema PC-CLRP sobre un conjunto de instancias especialmente dise~nadas para el nuevo problema. Se compara además los resultados frente a los reportados en otros trabajos sobre el problema CLRP obteniendo resultados competitivos. Palabras claves: problema de localización y ruteo de vehículos, programación lineal entera, branch and cut, colonia de hormigas, optimización combinatoria, recolección de premios.

Abstract:
The Capacitated Location Routing Problem (CLRP) is the combination of two well studied problems in Operations Research: Capacitated Facility Location Problem (CFLP) and Multiple Depots Vehicles Routing Problem (MDVRP). Given a set of available locations, the aim is to find a subset of depots to satisfy customer demands and to determine the routes to visit the customers. The objective is to minimize the cost of the opened depots, the fixed cost of the vehicles in use and the cost of the routes satisfying vehicle and depot capacity constraints. In this work we present a new version of the problem named Prize-Collecting Capacitated Location Routing Problem (PC-CLRP). This problem is a generalization of CLRP where customers have not the requirement to be visited. A customer gives a benefit if it is considered as part of the proposed solution. The maximization of this benefits is a new objective for this problem. We proposed an algorithmic approach to solving PC-CLRP. First, we introduce a new meta-heuristic algorithm based on the Ant Colony Optimization algorithm. Our ant algorithm optimizes the 3 levels of decision: location, clustering and routing. Next, we present new models based on two-index and three-index ow integer linear programming formulations. Known valid inequalities for CLRP are analyzed and adapted for PC-CLRP. This is complemented with the development of new valid inequalities and optimality cuts and their corresponding separation algorithms. Finally, we implement a Branch&Cut algorithm based on one of the proposed models. Computational results are reported for both implemented algorithms on a new set of instances specially designed for the new problem. Additionally, we compare it with recent work for CLRP on instances from the literature obtaining competitive results. Keywords: location routing problem, integer linear programming, branch and cut, ant colony, combinatorial optimization, prize-collecting

http://digital.bl.fcen.uba.ar

Biblioteca Central Dr. Luis Federico Leloir - Facultad de Ciencias Exactas y Naturales - Universidad de Buenos Aires
Intendente Güiraldes 2160 - Ciudad Universitaria - Pabellón II - C1428EGA - Tel. (54 11) 4789-9293 int 34