Problema de roteamento em anéis de dois níveis

Abstract

In this dissertation, we study the ring/ring problem, which consists in, given a graph and costs associated to its edges, designing a hierarchical network in two levels, with both levels being rings. We present an integer linear programming model for the problem and propose an exact branch-and-price algorithm to solve it. Since the proposed model uses an exponential number of variables, we use the column generation method to solve the linear relaxation. We also propose a relaxation for the column generation and heuristics to improve the performance of the proposed algorithm.