A metaheuristic and simheuristic approach for the p-HUB median problem from a telecommunication perspective

Abstract

Els últims avenços en la indústria de les telecomunicacions ofereixen grans oportunitats per a ciutadans i organitzacions en un món globalment connectat, però alhora presenten reptes als quals s'enfronten tècnics i enginyers que prenen decisions. Alguns d'aquests reptes es poden modelitzar com a problemes d'optimització. El primer objectiu d'aquest treball és proporcionar un revisió de la literatura sobre com s'han utilitzat aquestes tècniques tradicionalment per a tractar els problemes d'optimització associats a sistemes de telecomunicació, detectant les principals tendències i desafiaments. Particularment, l'estudi es centra en els problemes de disseny de xarxes, encaminament i problemes d'assignació de recursos. A causa de la naturalesa d’aquests problemes, aquest treball també analitza com es poden combinar les tècniques metaheurístiques amb metodologies de simulació per a ampliar les capacitats de resoldre problemes d'optimització estocàstics. A més, es tracta un popular problema d'optimització amb aplicacions pràctiques per a xarxes de telecomunicació, el problema de la p mediana no capacitat, analitzant-lo des d'escenaris deterministes i estocàstics.

Los recientes avances en la industria de las telecomunicaciones ofrecen grandes oportunidades para ciudadanos y organizaciones en un mundo globalmente conectado, pero también presentan una gran cantidad de desafíos complejos a los que se enfrentan diariamente técnicos e ingenieros. Algunos de estos desafíos se pueden modelar como problemas de optimización. El primer objetivo de esta tesis es proporcionar una revisión de la literatura de cómo se han utilizado estas técnicas tradicionalmente para tratar los problemas de optimización asociados a sistemas de telecomunicaciones, detectando las principales tendencias y desafíos. En particular, el estudio se centra en los problemas de diseño de red, direccionamiento y problemas de asignación de recursos. Debido a la naturaleza de estos problemas, este trabajo también analiza cómo se pueden combinar las técnicas metaheurísticas con metodologías de simulación para ampliar las capacidades de resolver problemas de optimización estocásticos. Después se trata un popular problema de optimización con aplicaciones prácticas para redes de telecomunicaciones, el problema de la p mediana no capacitado, analizándolo desde escenarios deterministas y estocásticos.

Recent advances in the telecommunications industry offer great opportunities to citizens and organizations in a globally-connected world, but they also create a vast number of complex challenges that decision-makers must face. Some of these challenges can be modelled as optimization problems. First, this thesis reviews how metaheuristics have been used to date to deal with optimization problems associated with telecommunication systems, detecting the main trends and challenges. In particular, the analysis focuses on problems in network design, routing, and allocation. Given the nature of these challenges, this work also discusses how the hybridization of metaheuristics with methodologies such as simulation can be employed to increase metaheuristics' capabilities when solving stochastic optimization problems. In addition, a popular optimization problem with practical applications in the design of telecommunications networks, the Uncapacitated Single Allocation p-Hub Median Problem (USApHMP) – where a fixed number of hubs have unlimited capacity, each non-hub node is allocated to a single hub and the number of hubs is known in advance –, is analysed in deterministic and stochastic scenarios.