New models and solution algorithms for Hub Location and related problems

Esta tesis se enmarca en el área de optimización de redes. Específicamente, desarrolla nuevos modelos y algoritmos de resolución exacta para Problemas de Localización de Concentradores y problemas relacionados con el diseño de redes. La tesis está estructurada en seis capítulos, donde las principales contribuciones científicas se desarrollan en los Capítulos 3-5. El Capítulo 1 ofrece una visión general del área, establece los objetivos principales de la tesis y resume sus resultados principales. El Capítulo 2 introduce el tema principal de esta tesis. Revisa la literatura relevante, destacando tanto los avances teóricos como las aplicaciones prácticas de los Problemas de Localización de Concentradores, junto con extensiones de los modelos fundamentales y trabajos recientes. El Capítulo 3 introduce una novedosa formulación basada en flujo de 2 índices para los Problemas de Localización de Concentradores, que puede adaptarse a una gran clase de modelos de Localización de Concentradores. Debido a su pequeño número de variables, puede ser manejada directamente sin recurrir a reformulaciones donde algunas de las variables son proyectadas. La formulación propuesta es tanto computacionalmente eficiente como versátil para manejar extensiones. El capítulo también desarrolla un nuevo algoritmo de solución que hemos llamado Branch-and-Solve. Las dos principales contribuciones del capítulo son: (i) una formulación fuerte de 2 índices que produce cotas del LP ajustadas, y (ii) el algoritmo Branch-and-Solve, que es novedoso en la literatura de Localización de Concentradores y muestra tanto versatilidad como eficiencia. El Capítulo 4 se centra en el Problema de Localización de Concentradores con Asignación Múltiple. El punto de partida de este capítulo son las adaptaciones al Problema de Localización de Concentradores con Asignación Múltiple de la formulación basada en caminos de 4 índices y la formulación supermodular de 2 índices de Contreras y Fernández (2014). Ambas formulaciones son reforzadas y se demuestra que ambos refuerzos producen la misma cota del LP. Además, demostramos que la cota del LP reforzada coincide con la mejor cota conocida de las formulaciones existentes para el Problema de Localización de Concentradores con Asignación Múltiple. El Capítulo 5 introduce un nuevo Problema de Flujo Multicommodity en el que partes de las rutas de transporte son subcontratadas a proveedores externos. Esto puede modelarse como un problema binivel, el cual se muestra que es NP-duro incluso sin restricciones explícitas de capacidad. Desarrollamos varias formulaciones no lineales y sus linealizaciones, junto con un estudio detallado de las propiedades, características y complejidad del problema. Experimentos computacionales proporcionan información práctica, ilustrando la relevancia y aplicabilidad de las decisiones de subcontratación en el diseño de redes. El Capítulo 6 presenta un resumen de la tesis, junto con algunas conclusiones y direcciones para investigaciones futuras.

Author dc:creator

• Zerega Oyarzún, Nicolás Alberto

Advisor dc:contributor.advisor

• Fernández Areizaga, Elena

Statement dc:rights

• Attribution-NonCommercial-NoDerivatives 4.0 Internacional

Licence dc:rights.uri

• http://creativecommons.org/licenses/by-nc-nd/4.0/

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/10498/39651

OAI identifier oai:identifier

oai:rodin.uca.es:10498/39651