{"id":{"repo_id":"cadiz","oai_identifier":"oai:rodin.uca.es:10498/39651"},"canonical_url":"https://search.dev.ndltd.org/etd/cadiz/oai:rodin.uca.es:10498/39651","repository":{"repo_id":"cadiz","name":"Universidad de Cadiz","base_url":"https://rodin.uca.es/oai/request"},"display":{"title":"New models and solution algorithms for Hub Location and related problems","abstract":"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.","abstract_html":"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.","abstract_has_math":false,"creators":["Zerega Oyarzún, Nicolás Alberto"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":["Fernández Areizaga, Elena"],"committee_chairs":[],"committee_members":[],"year":2026,"date_issued":"2026","date_published":"2026","updated_at":"2026-07-24T01:29:44Z","subjects":[],"languages":["eng"],"rights":["Attribution-NonCommercial-NoDerivatives 4.0 Internacional"],"rights_urls":["http://creativecommons.org/licenses/by-nc-nd/4.0/"],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/10498/39651","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Fernández Areizaga, Elena"]},{"key":"dc:contributor.other","label":"Dc Contributor Other","values":["Estadística e Investigación Operativa"]},{"key":"dc:creator","label":"Author","values":["Zerega Oyarzún, Nicolás Alberto"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2026-05-22T12:14:36Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2026-05-22T12:14:36Z"]},{"key":"dc:date.issued","label":"Date","values":["2026"]},{"key":"dc:type","label":"Dc Type","values":["doctoral thesis"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Attribution-NonCommercial-NoDerivatives 4.0 Internacional"]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://creativecommons.org/licenses/by-nc-nd/4.0/"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/10498/39651"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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.","This thesis is framed within the field of network optimization. Specifically, it develops new models and exact resolution algorithms for Hub Location and related network design problems. The thesis is structured in six chapters, where the main scientific contributions are developed in Chapters 3-5. Chapter 1 gives an overview of the area, states the primary objectives of the thesis, and summarizes its main results. Chapter 2 introduces the main topic of this thesis. It reviews relevant literature, highlighting both theoretical advances and practical applications of Hub Location Problems, along with extensions of the fundamental models and recent work. Chapter 3 introduces a novel 2-index flow based formulation for Hub Location Problems which can be adapted to a large class of Hub Location models. Due to its small number of variables, it can be handled directly without resorting to reformulations where some of the variables are projected out. The proposed formulation is both computationally efficient and versatile in handling extensions. The chapter also develops a new solution algorithm that we have called Branch-and-Solve. The two main contributions of the chapter are: (i) a strong 2-index formulation that produces tight LP bounds, and (ii) the Branch-and-Solve algorithm, which is novel in the Hub Location literature and shows both versatility and efficiency. Chapter 4 focuses on the Multiple Allocation Hub Location Problem. The starting point of this chapter are the adaptations to the Multiple Allocation Hub Location Problem of the path-based 4-index formulation and the supermodular 2-index formulation of Contreras and Fern´andez (2014). Both formulations are reinforced and it is shown that both reinforcements produce the same LP bound. Moreover, we prove that the reinforced LP bound coincides with the best-known LP bound of existing formulations for the Multiple Allocation Hub Location Problem (Hamacher et al., 2004; Mar´ın et al., 2006). Chapter 5 introduces a novel Multicommodity Flow Problem in which parts of transportation paths are outsourced to third-party providers. This can be modeled as a bilevel problem, which is shown to be NP-hard even without explicit capacity constraints. We develop several non-linear formulations and linearizations, along with a detailed study of the problem’s properties, characteristics and complexity. Computational experiments provide practical insights, illustrating the relevance and applicability of outsourcing decisions in network design. Chapter 6 presents a summary of the thesis, along with some conclusions, and future research directions."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["New models and solution algorithms for Hub Location and related problems"]}]}],"canonical_facts":{"dc:contributor.advisor":["Fernández Areizaga, Elena"],"dc:contributor.other":["Estadística e Investigación Operativa"],"dc:creator":["Zerega Oyarzún, Nicolás Alberto"],"dc:date.accessioned":["2026-05-22T12:14:36Z"],"dc:date.available":["2026-05-22T12:14:36Z"],"dc:date.issued":["2026"],"dc:description.abstract":["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.","This thesis is framed within the field of network optimization. Specifically, it develops new models and exact resolution algorithms for Hub Location and related network design problems. The thesis is structured in six chapters, where the main scientific contributions are developed in Chapters 3-5. Chapter 1 gives an overview of the area, states the primary objectives of the thesis, and summarizes its main results. Chapter 2 introduces the main topic of this thesis. It reviews relevant literature, highlighting both theoretical advances and practical applications of Hub Location Problems, along with extensions of the fundamental models and recent work. Chapter 3 introduces a novel 2-index flow based formulation for Hub Location Problems which can be adapted to a large class of Hub Location models. Due to its small number of variables, it can be handled directly without resorting to reformulations where some of the variables are projected out. The proposed formulation is both computationally efficient and versatile in handling extensions. The chapter also develops a new solution algorithm that we have called Branch-and-Solve. The two main contributions of the chapter are: (i) a strong 2-index formulation that produces tight LP bounds, and (ii) the Branch-and-Solve algorithm, which is novel in the Hub Location literature and shows both versatility and efficiency. Chapter 4 focuses on the Multiple Allocation Hub Location Problem. The starting point of this chapter are the adaptations to the Multiple Allocation Hub Location Problem of the path-based 4-index formulation and the supermodular 2-index formulation of Contreras and Fern´andez (2014). Both formulations are reinforced and it is shown that both reinforcements produce the same LP bound. Moreover, we prove that the reinforced LP bound coincides with the best-known LP bound of existing formulations for the Multiple Allocation Hub Location Problem (Hamacher et al., 2004; Mar´ın et al., 2006). Chapter 5 introduces a novel Multicommodity Flow Problem in which parts of transportation paths are outsourced to third-party providers. This can be modeled as a bilevel problem, which is shown to be NP-hard even without explicit capacity constraints. We develop several non-linear formulations and linearizations, along with a detailed study of the problem’s properties, characteristics and complexity. Computational experiments provide practical insights, illustrating the relevance and applicability of outsourcing decisions in network design. Chapter 6 presents a summary of the thesis, along with some conclusions, and future research directions."],"dc:format":["application/pdf"],"dc:identifier.uri":["http://hdl.handle.net/10498/39651"],"dc:language.iso":["eng"],"dc:rights":["Attribution-NonCommercial-NoDerivatives 4.0 Internacional"],"dc:rights.uri":["http://creativecommons.org/licenses/by-nc-nd/4.0/"],"dc:title":["New models and solution algorithms for Hub Location and related problems"],"dc:type":["doctoral thesis"]},"updated_at":"2026-07-24T01:29:44Z"}