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

  1. Almiñana Alemany, Marcos
Supervised by:
  1. Jesús T. Pastor Ciurana Director

Defence university: Universitat de València

Year of defence: 1994

Committee:
  1. Marco A. López Cerdá Chair
  2. Ramón Álvarez Valdés Secretary
  3. Miguel Ángel Goberna Torrent Committee member
  4. Laureano Fernando Escudero Bueno Committee member
  5. Ángel Corberán Salvador Committee member

Type: Thesis

Teseo: 44198 DIALNET

Abstract

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.