Defensa Tesis Doctorado Cristian Martínez
Detalles del evento
Cuándo
de 13:00 a 15:00
Dónde
- TITULO: "Metaheurísticas híbridas aplicadas al Problema de Ruteo de Arcos Capacitados"
- DIRECTORES: Dra. Irene Loiseau y Dr. Mauricio Resende
- JURADOS:
- Dra. Luciana Buriol, UFRGS, Brasil
- Dr. Héctor Cancela, UDELAR, Uruguay
- Dr. Min Chih Lin, FCEN, UBA
- 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 determinadas 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 que pertenece a la clase NP-Hard. 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 para instancias medianas y a bajo costo computacional.
El objetivo de esta tesis es el desarrollo de algoritmos heurísticos que contengan caracterí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.
