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

Abstract

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.