Estudios computacionales para problemas tipo p-hub

  1. Melquíades Pérez Pérez
Supervised by:
  1. José Marcos Moreno Vega Director
  2. Francisco Almeida Rodriguez Director

Defence university: Universidad de La Laguna

Year of defence: 2009

Committee:
  1. José Andrés Moreno Pérez Chair
  2. Vicente José Blanco Pérez Secretary
  3. Vicente Liern Carrión Committee member
  4. Enrique Salvador Quintana Ortí Committee member
  5. Dolores Rosa Santos Peñate Committee member
Department:
  1. Ingeniería Informática y de Sistemas

Type: Thesis

Teseo: 196144 DIALNET

Abstract

Los problemas tipo tipo p-hub mediano son una clase de problemas de optimización combinatoria que plantean la búsqueda de la mejor selección de puntos para establecer centros de distribución (localización) y la mejor estrategia para servir a los usuarios, En la mayoría de los casos se trata de problemas NP duros, que modelizan a un conjunto importante de situaciones prácticas: movimientos de datos en redes de comunicación, movimientos de pasajeros en redes de transporte, movimientos de mercancías, et. Existen contextos en los que, para determinadas instancias, su resolución no sería posible sin el concurso de técnicas y métodos como los que se presentan. El objetivo de esta tesis es aportar técnicas y metodologías, en el marco de las metaheurísticas, con las que resolver de forma eficiente problemas del tipo p-hub mediano. Por eficiencia entendemos que los métodos sean capaces de aportar soluciones de alta calidad en tiempos de ejecución que puedan ser aceptables para el usuario que los utiliza. Nuestra hipótesis de partida es que las metaheurísticas evolutivas pueden ser buenas candidatas como técnicas de resolución genéricas en el contexto de los problemas del tipo p-hub. Como consecuencia, derivamos un conjunto de métodos heurísticos con los que abordar esta clase de problemas. Realizamos una aproximación progresiva e incremental para abordar las clases más generales de los problemas. Comenzando con estrategias voraces simples, en cada paso, proporcionamos un nuevo nivel de abstracción heurístico que, aprovechando las características de los niveles previos, se enriquece con diferentes criterios para recorrer el espacio de soluciones de manera más inteligente. La estrategia reutiliza las mejores propiedades que proporcionan los métodos más simples en la elaboración de métodos más sofisticados. El recorrido finaliza con la construcción de métodos híbridos que son capaces de enfrentarse a situaciones complejas y a problemas de tamaño considerable.