Estudios computacionales para problemas tipo p-hub

Résumé

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.