Heurísticas paralelas aplicadas a problemas de alocação de concentradores

Projeto de redes do tipo Eixo-Raio (E-R), também conhecido como problemas de localização de concentradores, tem sua importância reconhecida em função da sua aplicação nas mais diversas áreas, tais como sistemas de transporte, telecomunicações e redes de serviço.Geralmente, estes problemas consistem em selecionar, entre um conjunto de possibilidades, nós concentradores que atuam como centros de comutação ou concentração de fluxo, permitindo assim a distribuição de mercadorias, informação e serviços entre pontos deuma rede. Este tipo de abordagem tem suas vantagens, pois dependendo do contexto da aplicação pode reduzir custos de infraestrutura, racionalizar o manuseio e triagem de fluxo, além de possibilitar a economia de escala por meio da consolidação de fluxos com o uso de tecnologias para o transporte ou transmissão de grandes volumes. Este trabalho apresenta contribuições para alguns dos problemas de localização de concentradores ao propor e avaliar o desempenho de dois algoritmos heurísticos paralelos, utilizando apenas a CPU, para tratar diferentes variantes e cenários do problema de planejamento de redes do tipo E-R: problema de localização de concentradores não capacitados com alocação simples (USAHLP, do inglês Uncapacitated single allocation hub location problem);problema de localização de concentradores não capacitados com alocação múltipla (UMAHLP, do inglês Uncapacitated multiple allocation hub location problem); problema de localização de concentradores em anel não capacitados como alocação simples (CHLP, do inglês Cycle Hub Location Problem). Embora algoritmos heurísticos paralelos tenham sido aplicados a outros problemas de localização de concentradores, não foi encontrada nenhuma abordagem para os problemas tratados nesta tese. Os algoritmos propostos neste trabalho foram comparados com os melhores algoritmos da literatura aplicados aos problemas estudados. Para isso, um conjunto de experimentosfoi feito utilizando instâncias teste, com tamanho variando de 10 a 200 nós, e instâncias criadas para este trabalho, que chegam a ter 3000 nós. O estudo destes problemas com instâncias deste tamanho é importante devido a diversas aplicações: planejamento de redes de transporte aéreo, se considerado todos os agentes envolvidos, tais como cidades, aeroportos regionais, estaduais e nacionais; problemas de logística, considerando pontos de distribuição com diferentes propósitos em escala nacional. Como esperado, os resultados obtidos mostram que as versões paralelas das heurísticas propostas superam, em tempo e qualidade, as versões sequenciais das mesmas. Além disso, foram obtidos resultados melhores que aqueles alcançados pelos algoritmos da literatura, mostrando a eficiência da proposta.The design of hub-and-spoke networks represented by hub location problems is of great importance due to the presence of such topology in a myriad of applications such as logistics, telecommunication systems and service networks. Generally speaking, hub location problems consist of locating hubs nodes, allocating non-hub nodes to the installed hubs, and inter-connecting the hub network. The bundle of flows at the hubs allows the use of more efficient, high volume carriers between hubs achieving thus scale economies. Furthermore, depending on the application, these networks can reduce infrastructure costs. The main contribution of this thesis is the proposal and evaluation of two parallel heuristics devised to solve three hub location problems: the uncapacitated single allocation hub location problem (USAHLP); the uncapacitated multiple allocation hub location problem (UMAHLP); and the cycle hub location problem. Although parallel heuristic algorithmshave been applied to other hub location problems and as further as the author knows it is the first time such approach is sought for the present problems. The proposed heuristics performance is compared with well-known heuristics from the literature on solving the AP benchmark test instances, and a larger scale set specially crafted to resemble a Brazilian logistic context. The AP test instance sizes range from 10to 200 nodes, whereas the proposed ones reach up to 3000 nodes.As expected, the attained results show that the parallel heuristics outperform the sequential ones, both in time and solution quality for all tested problem. Finally, practical problems usually have a large amount of data which results in a high-dimensional search space. Thusthe study of methods capable of dealing with such large scale problems are critical and a matter of importance to decision makers