Tesis > Documento


Ver el documento (formato PDF)   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
URL:
     
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.

* A este resumen le pueden faltar caracteres especiales. Consulte la versión completa en el documento en formato PDF

Registro:
Título : Metaheurísticas híbridas aplicadas al problema de ruteo de arcos capacitados     =    Hybrid metaheuristics for the capacitated arc routing problem
Autor : Martínez, Cristian Alejandro
Director : Loiseau, Irene
Resende, Mauricio G.C.
Consejero : Loiseau, Irene
Jurados : Chih Lin, Min  ; Salete Buriol, Luciana  ; Cancela Bosi, Héctor
Año : 2011
Editor : Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires
Filiación : Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales
Universidad Nacional de Salta
Grado obtenido : Doctor de la Universidad de Buenos Aires en el área de Ciencias de la Computación
Ubicación : Preservación - http://digital.bl.fcen.uba.ar/gsdl-282/cgi-bin/library.cgi?a=d&c=tesis&d=Tesis_4979_Martinez
Idioma : Español
Area Temática : Computación / Metaheuristica
Palabras claves : BRKGA; GRASP; HBMO; METAHEURISTICAS; PROBLEMA DE RUTEO DE ARCOS CAPACITADOS; RUTEO DE VEHICULOS; SCATTER SEARCH; TABU SEARCH; VNS; BRKGA; CAPACITATED ARC ROUTING PROBLEM; GRASP; HBMO; METAHEURISTICS; SCATTER SEARCH; TABU SEARCH; VEHICLE ROUTING; VNS
URL al Documento : 
URL al Registro : 
hola chau _gs.DocumentHeader_ chau2 _documentheader_ chau3
Estadísticas:
     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