Nuevos heurísticos para la resolución del problema del cubrimiento total

Resum

EL OBJETIVO PRINCIPAL DE LA MEMORIA ES EL DESARROLLO DE NUEVOS ALGORITMOS HEURISTICOS QUE RESUELVAN DE MODO EFICIENTE EL PROBLEMA DEL CUBRIMIENTO TOTAL, PUESTO QUE ESTE ES UN CASO PARTICULAR DEL "SET COVERING PROBLEM" EL CAPITULO I ESTA DEDICADO AL PLANTEAMIENTO Y FORMULACION DE AMBOS PROBLEMAS. EN EL SE DEMUESTRAN TEORICAMENTE DIVERSAS PROPIEDADES DE LAS REGLAS DE REDUCCION. EN EL CAPITULO II SE ABORDA EL DESARROLLO DE DOS NUEVOS HEURISTICOS TIPO "GREEDY" CUYA EFICIENCIA ES ANALIZADA COMPARANDO SUS RESULTADOS CON LOS QUE SE OBTIENEN MEDIANTE OTROS DOS REPUTADOS HEURISTICOS (GH1 Y GH2) AL SER APLICADOS SOBRE UNA BATERIA DE PROBLEMAS GENERADOS ALEATORIAMENTE. EL CAPITULO II ESTA DEDICADO A LA CONSTRUCCION DE UN NUEVO ALGORITMO (RS), MUCHO MAS COMPLEJO QUE LOS ANTERIORES, BASADO EN UNA COMBINACION DE LAS TECNICAS LAGRANGIANAS CON LA RESOLUCION DE PROBLEMAS SUBROGADOS. A EFECTOS COMPARATIVOS SE RECURRE AL ALGORITMO DE LOPEZ Y LORENA (1992) Y AL DE VASKO Y WILSON (1986). LA EXPERIENCIA COMPUTACIONAL DEMUESTRA QUE NUESTRO ALGORITMO ES EL MAS POTENTE DE ENTRE LOS DISEÑADOS HASTA EL MOMENTO PARA LA RESOLUCION DE LOS PROBLEMAS DE LOCALIZACION CON CUBRIMIENTO TOTAL.