Modelo e método de resolução para rede de alta velocidade, uma abordagem do problema do caixeiro viajante com coleta de prêmios

Abstract

The Community Education and Research Networks (REDECOMEP) is based on scientific development through the connection of higher education institutions, an example of which is the GigaMossoró network. This paper discusses aspects and challenges of how to find the best route, proposing a method of resolution that defines the perimeter of the GigaMossoró network, in order to obtain a path that contemplates all the priority points and is able to reach the maximum of possible clients within it. As a parameter will be used the Traveling Collector's Problem with Collecting Prizes (PCVCP), PCVCP was initially developed by Balas in 1989 for the programming of factories that produced steel blades. Given that the proposed problem is admittedly a problem of high computational complexity, ie, con-proved NP-difficult, to solve the problem was proposed a mathematical model command. Defined the model was necessary to validate the mode, for this he used the proposed instances in the work of Chaves (2003) and the instances elaborated in the research for the studied problem. Given the validation through an exact model, it was realized the need to use a Metaheuristic approach based on a genetic algorithm, these have the characteristics of using random keys and genetic mutation as parameters to select the best solution, to this was developed a genetic algorithm to solve the problem and obtained satisfactory results for the same. Given this approach, the research presented contributions regarding the definition of concepts of the GigaMossoró network in order to know its future clients, and to define its structure and restrictions, in addition, it was possible to understand a solution approach of the problem through proposed Metaheuristics