Uma abordagem híbrida exata-heurística aplicada ao problema do ciclo mediano sem restrições de capacidade

Abstract

The telecommunication area plays an important role in everyday life for most people, its importance and complexity produce outlays that providers for this kind of service always try to avoid. One way to reduce these costs is to better set the arrangements of the links that integrate the installed network whose service data will flow through. The Ring Star Problem (RSP) converts in a computational problem the need for optimizing the installation of a ring-star topology into a network, and make it by minimizing the costs of building its central structure (ring) and assigning the remaining elements to this structure. Therefore, this paper brings three hybrid approaches to RSP, quasi-exact algorithms constituted by Branch-and-Bound (B&B), Greedy Randomized Adaptative Search Procedure (GRASP), Iterated Local Search (ILS) and Generic Variable Neighborhood Search (GVNS) procedures. The aim is to find a region with good initial solutions, using B&B partially, so the heuristics, two compositions called GRASPILS and GGVNS, can accomplish a smoother search. Computational experiments, performed on 360 test cases for each hybrid approach, revealed expressive results, especially when compared to the exact results produced by the B&B.