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 ]

Metaheuristica [ 2 tesis ]

Martínez, Cristian Alejandro. "Metaheurísticas híbridas aplicadas al problema de ruteo de arcos capacitados" (2011) Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires

pdf

Resumen Registro Cita

Resumen:
El Problema de Ruteo de Arcos Capacitados (CARP) es un problema de optimización combinatoria que consiste en satisfacer demandas de servicios/productos sobre determi- nadas calles de una red vial mediante una flota homogénea de vehículos, minimizando el costo total de recorrido involucrado. Ha sido aplicado a casos reales como recolección de residuos, mantenimiento de calles, lectura de medidores eléctricos, entre otros. CARP es un problema de optimización combinatoria de tipo NP-Hard. A tal efecto, en la literatura se han propuesto algoritmos exactos y heurísticas. Los primeros, basados en su mayoría en las técnicas Branch and Bound y Cutting Plane, obtienen soluciones óptimas sobre instancias de datos de tamaño reducido. Los segundos, en general, alcanzan soluciones cercanas a las óptimas y a bajo costo computacional. El objetivo de esta tesis es el desarrollo de algoritmos heurísticos que contengan ca- racterísticas salientes de metaheurísticas tales como Honey Bee Mating Optimization (HBMO), Biased Random Key Genetic Algorithm (BRKGA), Greedy Randomized Adaptive Search Procedure (GRASP), Variable Neighborhood Search (VNS), entre otras. Los resultados computacionales obtenidos por los algoritmos propuestos usando diferentes instancias de la literatura, muestran que los mismos son competitivos y robustos.

Abstract:
The Capacitated Arc Routing Problem (CARP) consists in determining a set of vehicle trips minimizing total travel cost, so that each demand over certain streets of a road network be served. Our motivation to deal with this problem is related to its application in real world cases such as street sweeping, urban waste collection and electric meter, reading just to mention a few. Since its first formulation, several exact and approximative methods for this NP-Hard problem have been proposed. The former, generally based on Branch and Bound and Cutting Plane methods, reach optimal solutions in small data instances. The latter, obtain near optimal solutions using low CPU ffort. The objective of this work consists in proposing hybrid heuristic algorithms that inclu- de most important features from metaheuristics such as Honey Bee Mating Optimization (HBMO), Biased Random Key Genetic Algorithm (BRKGA), Greedy Randomized Adaptive Search Procedure (GRASP), Variable Neighborhood Search (VNS), among others. The algorithms were tested with several well-known instances from the literature. The results obtained were competitive in terms of objective function value and required computational time.

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