Metaheurísticas híbridas aplicadas al problema de ruteo de arcos capacitados

Mostrar todas las versiones(3)

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

Descripción completa

Guardado en:

Detalles Bibliográficos
Autor principal:	Martínez, Cristian Alejandro
Otros Autores:	Loiseau, Irene
Formato:	Tesis doctoral publishedVersion
Lenguaje:	Español
Publicado:	Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales 2011
Materias:	BRKGA GRASP HBMO METAHEURISTICAS PROBLEMA DE RUTEO DE ARCOS CAPACITADOS RUTEO DE VEHICULOS SCATTER SEARCH TABU SEARCH VNS CAPACITATED ARC ROUTING PROBLEM METAHEURISTICS VEHICLE ROUTING
Acceso en línea:	https://hdl.handle.net/20.500.12110/tesis_n4979_Martinez http://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesis&d=tesis_n4979_Martinez_oai
Aporte de:	Repositorio Digital de la Universidad de Buenos Aires (UBA) de Universidad de Buenos Aires

id	I28-R145-tesis_n4979_Martinez_oai
record_format	dspace
spelling	I28-R145-tesis_n4979_Martinez_oai2023-04-26 Loiseau, Irene Resende, Mauricio G. C. Martínez, Cristian Alejandro 2011 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. 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. Fil: Martínez, Cristian Alejandro. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. application/pdf https://hdl.handle.net/20.500.12110/tesis_n4979_Martinez spa Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales info:eu-repo/semantics/openAccess https://creativecommons.org/licenses/by-nc-sa/2.5/ar 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 Metaheurísticas híbridas aplicadas al problema de ruteo de arcos capacitados Hybrid metaheuristics for the capacitated arc routing problem info:eu-repo/semantics/doctoralThesis info:ar-repo/semantics/tesis doctoral info:eu-repo/semantics/publishedVersion http://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesis&d=tesis_n4979_Martinez_oai
institution	Universidad de Buenos Aires
institution_str	I-28
repository_str	R-145
collection	Repositorio Digital de la Universidad de Buenos Aires (UBA)
language	Español
orig_language_str_mv	spa
topic	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
spellingShingle	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 Martínez, Cristian Alejandro Metaheurísticas híbridas aplicadas al problema de ruteo de arcos capacitados
topic_facet	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
description	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.
author2	Loiseau, Irene
author_facet	Loiseau, Irene Martínez, Cristian Alejandro
format	Tesis doctoral Tesis doctoral publishedVersion
author	Martínez, Cristian Alejandro
author_sort	Martínez, Cristian Alejandro
title	Metaheurísticas híbridas aplicadas al problema de ruteo de arcos capacitados
title_short	Metaheurísticas híbridas aplicadas al problema de ruteo de arcos capacitados
title_full	Metaheurísticas híbridas aplicadas al problema de ruteo de arcos capacitados
title_fullStr	Metaheurísticas híbridas aplicadas al problema de ruteo de arcos capacitados
title_full_unstemmed	Metaheurísticas híbridas aplicadas al problema de ruteo de arcos capacitados
title_sort	metaheurísticas híbridas aplicadas al problema de ruteo de arcos capacitados
publisher	Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales
publishDate	2011
url	https://hdl.handle.net/20.500.12110/tesis_n4979_Martinez http://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesis&d=tesis_n4979_Martinez_oai
work_keys_str_mv	AT martinezcristianalejandro metaheuristicashibridasaplicadasalproblemaderuteodearcoscapacitados AT martinezcristianalejandro hybridmetaheuristicsforthecapacitatedarcroutingproblem
_version_	1766015724430557184

Metaheurísticas híbridas aplicadas al problema de ruteo de arcos capacitados

Ejemplares similares